Parallel local search for the time-constrained traveling salesman problem

In the time-constrained TSP, each city has to be visited within a given time interval. Such `time windows' often occur in practice. When practical vehicle routing problems are solved in an interactive setting, one needs algorithms for the time-constrained TSP that combine a low running time with a high solution quality. Local search seems a natural approach. It is not obvious, however, how local search for the TSP has to be implemented so as to handle time windows efficiently. This is particularly true when parallel computer architectures are available. We consider these questions.