Sequential and parallel local search for the time-constrained travelling salesman problem

Local search has proven to be an effective solution approach for the traveling salesman problem. We consider variants of the TSP in which each city is to be visited within one or more given time windows. The travel times are symmetric and satisfy the triangle inequality; therobjective is to minimize the tour duration. We develop efficient sequential and parallel algorithms for the verification of local optimality of a tour with respect to <em>k</em>-exchanges.