Using simulated annealing to solve routing and location problems

Wiley - Tập 33 Số 2 - Trang 261-279 - 1986
Bruce Golden1, Christopher C. Skiścim2
1College of Business and Management, University of Maryland, College Park, Maryland 20742
2The MITRE Corporation, McLean, Virginia 22102

Tóm tắt

AbstractIn 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 p‐median location problem, and test the approach extensively.

Từ khóa


Tài liệu tham khảo

10.1287/mnsc.23.8.789

10.1287/mnsc.26.5.495

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).

10.1126/science.220.4598.671

10.1145/362588.362593

10.1002/j.1538-7305.1965.tb04146.x

10.1287/opre.21.2.498

10.1063/1.1699114

10.1287/mnsc.23.11.1208

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.

10.1068/a110373

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.

10.1287/opre.16.5.955

Thizy J.‐M. Princeton University private communication 1983.

Thông tin
Thông tin xuất bản

Wiley

Tập 33 Số 2

261-279

Thông tin tác giả