1965/12/01 by Shen Lin · 9 citations
Computer Science · Engineering · #Data Management and Algorithms #Optimization and Packing Problems #Vehicle Routing Optimization Methods
paper · doi:10.1002/j.1538-7305.1965.tb04146.x
crossref issued 1965/12/01 · crossref published 1965/12/01 · crossref published-print 1965/12/01 · openalex publication_date 1965/12/01 · crossref published-online 2013/07/29 · crossref created 2013/07/29 · crossref deposited 2020/10/14 · openalex created_date 2025/10/10 · crossref indexed 2026/07/28 · openalex updated_date 2026/07/29
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 30n3microseconds 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.