A hybrid exact algorithm for the Travelling Salesman Problem with Time Windows

A hybrid exact algorithm for the Travelling Salesman Problem with Time Windows

0.00 Avg rating0 Votes
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: , ,
Keywords: constraint programming
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.