Article ID: | iaor1995348 |
Country: | Netherlands |
Volume: | 42 |
Issue: | 2/3 |
Start Page Number: | 212 |
End Page Number: | 225 |
Publication Date: | Apr 1993 |
Journal: | Discrete Applied Mathematics |
Authors: | Lenstra Jan Karel, Kindervater Gerard, Savelsbergh Martin |
Local search has proven to be an effective solution approach for the traveling salesman problem. The authors 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; the objective is to minimize the tour duration. The authors develop efficient sequential and parallel algorithms for the verification of local optimality of a tour with respect to