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.