An efficient implementation of local search algorithms for constrained routing problems (Q918421)

Two exchange algorithms for local improvement in the traveling salesman problem with side constraints are discussed. The first is the well known 2-exchange algorithm. The second is an exchange algorithm proposed by Or in which a subsequence of the tour is shifted to some other place in the tour. The constraints considered are precedence constraints, time windows, and constraints which arise if a truck with limited capacity has to collect and to deliver the same type of goods at each vertex of the tour. It is shown that in all these cases feasibility of an exchange step can be checked in constant time. Thus the side constraints can be handled without increasing the time complexity.