Combining heuristics for optimizing a neural net solution to the traveling salesman problem

A practical solution to the traveling salesman problem which utilizes three heuristics for guiding the search has been discovered. The problem is first represented by a fully connected net in which each node represents a city which is connected to every other city and the weights associated with each connection represent the distances between respective cities. Three heuristics are then iteratively applied to this network to solve the problem. The first heuristic is the use of a path-generation technique which connects the closest cities first. The second heuristic utilizes an annealing model which varies the weights slightly. The third heuristic detects segments of the tour which cross other segments and then uncrosses them. These techniques yield good tours whose computing time grows at a rate somewhat less than the cube of the number of cities