SEQUENTIAL AND PARALLEL LOCAL SEARCH FOR THE TIME-CONSTRAINED TRAVELING SALESMAN PROBLEM

Local search has proven to be an effective solution approach for the t raveling salesman problem. We consider variants of the TSP in which ea ch city is to be visited within one or more given time windows. The tr avel times are symmetric and satisfy the triangle inequality; the obje ctive is to minimize the tour duration. We develop efficient sequentia l and parallel algorithms for the verification of local optimality of a tour with respect to k-exchanges.