An efficient implementation of local search algorithms for constrained routing problems

The paper investigates the implementation of local search algorithms for routing problems with various side constraints such as time windows on vertices and precedence relations between vertices. The algorithms are based on the k-exchange concept. In the case of unconstrained routing problems, a single k-exchange can obviously be processed on constant time. In the presence of side constraints feasibility problems arise. Testing the feasibility of a single solution requires an amount of time that is linear in the number of vertices. It is shown how this effort can, on the average, still be reduced to a constant.