Using simulated annealing to solve routing and location problems
Tóm tắt
In recent papers by Kirkpatrick et al., 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
Từ khóa
Tài liệu tham khảo
Golden B. L., 1985, The Traveling Salesman Problem, 207
Kirkpatrick S. Gelatt Jr. C. D. andVecchi M. P. “Optimization by Simulated Annealing ” IBM Computer Science/Engineering Technology Report IBM Thomas J. Watson Research Center Yorktown Heights NY (1982).
Or I. “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.
Stewart W. R. “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.
Thizy J.‐M. Princeton University private communication 1983.