Article ID: | iaor20033007 |
Country: | United States |
Volume: | 14 |
Issue: | 4 |
Start Page Number: | 403 |
End Page Number: | 417 |
Publication Date: | Oct 2002 |
Journal: | INFORMS Journal On Computing |
Authors: | Lodi Andrea, Focacci Filippo, Milano Michela |
Keywords: | constraint programming |
The Traveling Salesman Problem with Time Windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a specific time window. We propose a hybrid approach for solving the TSPTW that merges Constraint Programming propagation algorithms for the feasibility viewpoint (find a path), and Operations Research techniques for coping with the optimization perspective (find the best path). We show with extensive computational results that the synergy between Operations Research optimization techniques embedded in global constraints, and Constraint Programming constraint solving techniques, makes the resulting framework effective in the TSPTW context also if these results are compared with state-of-the-art algorithms from the literature.