A Hybrid Exact Algorithm for the TSPTW

Filippo Focacci, Andrea Lodi, Michela Milano

INFORMS Journal on Computing · 2002 · Volume 14 · Issue 4

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.

Keywords

routing, scheduling, relaxations, cutting planes, constraint programming

Enable JavaScript for citation tools and additional paper interactions.