A Heuristic Approach to Solving Travelling Salesman Problems

A code for solving travelling salesman problem employing heuristic ideas is described. Acyclic permutations of the cities are constructed by first choosing two cities at random for a permutation of length two, putting the remaining cities in a random list and then inserting cities from the list in the partially constructed permutations so that they add least to the length of the partial tour. A second heuristic idea used in the code is that of breaking up the problem into convex, or almost convex sub-problems and employing the above-mentioned heuristic on these subproblems. Numerical experience with the code is described as well as weaknesses and strengths of the method.

• 저널Management Science · 10(2) · 225–248
• 토픽Data Management and Algorithms · Signal Processing
• DOI10.1287/mnsc.10.2.225
• 저자Robert L. Karg, Gerald L. Thompson