×

zbMATH — the first resource for mathematics

A hybrid exact algorithm for the TSPTW. (English) Zbl 1238.90054
Summary: 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.

MSC:
90B30 Production models
90C35 Programming involving graphs or networks
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
Software:
TSPTW
PDF BibTeX Cite
Full Text: DOI