Metaheuristics for Logistics

5The Traveling Salesman Problem

The traveling salesman problem (TSP) is to combinatorial optimization problems what Formula One is to the motor industry: a formidable laboratory that pours its stream of ideas into the whole of the field. On one hand, this problem constitutes a showcase. By virtue of its simplicity, it is regularly employed to illustrate the mechanisms of an emerging metaheuristic or as a tutorial (particle swarm, ant colonies, etc.). On the other hand, the intensive studies dedicated to it have enabled us to devise techniques, simultaneously innovative and highly efficient. Certain mathematical properties of the TSP have been used to conceive metaheuristic components that become more and more effective. Several ideas, originally drawn from the TSP, have afterwards been applied to other problems. It is some of these ideas that we will focus on in this chapter.

5.1. Representing a solution: the two-level tree structure

It is handy to represent the solution of a TSP, which we will call a “tour”, as a permutation of its set of n cities (for the sake of simplification, we will continue to use this representation for the rest of the chapter). However, many others have been used in the literature on the TSP. Out of these, we will introduce the two-level tree structure, which has turned out to be as useful for the implementation of the Lin & Kernighan moves [FRE 95] as for the application of ejection chains [GAM 05]. These two techniques will be described in detail ...