Parallel local search for the time-constrained travelling 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 timeconstrained TSP that combine a tow running lime with a high solullon 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