Using simulated annealing to solve routing and location problems. (English) Zbl 0593.90054

Golden, Bruce L.; Skiscim, Christopher C.

Nav. Res. Logist. Q. 33, 261-279 (1986).

Summary: In recent papers by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi [“Optimization by simulated annealing”, IBM T. J. Watson Research Centre, Yorktown Hights, NY (1982); Science 220, 671–680 (1983; Zbl 1225.90162)] an analogy between the statistical mechanics of large multivariate physical systems and combinatorial optimization has been presented and used to develop a general strategy for solving discrete optimization problems. The method relies on probabilistically accepting intermediate increases in the objective function through a set of user-controlled parameters. It is argued that by taking such controlled uphill steps, from time to time, a high quality solution can eventually be found in a moderate amount of computer time. In this paper, we implement this idea, apply it to the traveling salesman problem and the p-median location problem, and test the approach extensively.

MSC:

90C10	Integer programming
65K05	Numerical mathematical programming methods
68Q25	Analysis of algorithms and problem complexity
90B05	Inventory, storage, reservoirs

Keywords:

simulated annealing; statistical mechanics of large multivariate physical systems; combinatorial optimization; controlled uphill steps; traveling salesman; p-median location

Citations:

Zbl 1225.90162

References:

[1]	Cornuejols, Management Science 23 pp 789– (1977)
[2]	Crowder, Management Science 26 pp 495– (1980)
[3]	and , ”The Empirical Analysis of Heuristics,” in The Traveling Salesman Problem, edited by , , , and , Wiley, 1985, pp. 207–249.
[4]	, and , ”Optimization by Simulated Annealing,” IBM Computer Science/Engineering Technology Report, IBM Thomas J. Watson Research Center, Yorktown Heights, NY (1982).
[5]	Kirkpatrick, Science 220 pp 671– (1983)
[6]	Krolak, Communications of the ACM 14 pp 327– (1971)
[7]	Lin, Bell System Technical Journal 44 pp 2245– (1965) · Zbl 0136.14705 · doi:10.1002/j.1538-7305.1965.tb04146.x
[8]	Lin, Operations Research 21 pp 498– (1973)
[9]	Metropolis, Journal of Chemical Physics 21 pp 1087– (1953)
[10]	Norback, Management Science 23 pp 1208– (1977)
[11]	”Traveling Salesman-Type Combinatorial Problems and their Relation to the Logistics of Blood Banking,” Ph.D. Thesis, Dept. of Industrial Engineering and Management Sciences, Northwestern University, 1976.
[12]	Rosing, Environment and Planning 11A pp 373– (1979)
[13]	”A Computationally Efficient Heuristic for the Traveling Salesman Problem,” in Proceedings of the 13th Annual Meeting of Southeastern TIMS, Myrtle Beach, SC, 1977, pp. 75–83.
[14]	Teitz, Operations Research 16 pp 955– (1968)
[15]	Princeton University, private communication, 1983.