On the Significance of the Initial Solution in Travelling Salesman Heuristics

The quality requirements set by edge exchange heuristics on their initial solutions are evaluated in connection with the travelling salesman problem. The performance of the heuristics is measured using the expected value of the best solution achievable in a certain computing time. The computational results show that the use of initial solutions generated by applying a construction heuristic, instead of random initial solutions, typically improves the performance of edge exchange heuristics. The improvement, however, is dependent on the edge exchange heuristic to be used, the properties of the problem, and the computing time available.