旅行商问题
启发式
数学优化
计算
还原(数学)
计算机科学
旅行购买者问题
国际商用机器公司
2-选项
数学
方案(数学)
订单(交换)
算法
数学分析
材料科学
几何学
财务
经济
纳米技术
标识
DOI:10.1002/j.1538-7305.1965.tb04146.x
摘要
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer. The first produces guaranteed optimal solution for problems involving no more than 13 cities; the time required (IBM 7094 II) varies from 60 milliseconds for a 9-city problem to 1.75 seconds for a 13-city problem. The second algorithm produces precisely characterized, locally optimal solutions for large problems (up to 145 cities) in an extremely short time and is based on a general heuristic approach believed to be of general applicability to various optimization problems. The average time required to obtain a locally optimal solution is under 30n 3 microseconds where n is the number of cities involved. Repeated runs on a problem from random initial tours result in a high probability of finding the optimal solution among the locally optimal solutions obtained. For large problems where many locally optimal solutions have to be obtained in order to be reasonably assured of having the optimal solution, an efficient reduction scheme is incorporated in the program to reduce the total computation time by a substantial amount.
科研通智能强力驱动
Strongly Powered by AbleSci AI