×

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

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

Citations:

Zbl 1225.90162
PDF BibTeX XML Cite
Full Text: DOI

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
[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.