An Exact Constraint Logic Programming Algorithm for the Traveling Salesman Problem with Time Windows

TLDR

The study introduces a constraint logic programming model for the traveling salesman problem with time windows that produces an exact branch‑and‑bound algorithm without restrictive time‑window assumptions. The algorithm uses a data‑driven approach that applies operations‑research pruning rules both a priori and dynamically, and its performance is evaluated against exact and heuristic methods. The algorithm avoids the space‑complexity limitations of dynamic programming and, on Solomon’s benchmark, sets new best solutions for several RC2 instances while confirming optimality for the best known C2 solutions.

Abstract

This paper presents a constraint logic programming model for the traveling salesman problem with time windows which yields an exact branch-and-bound optimization algorithm without any restrictive assumption on the time windows. Unlike dynamic programming approaches whose performance relies heavily on the degree of discretization applied to the data, our algorithm does not suffer from such space-complexity issues. The data-driven mechanism at its core more fully exploits pruning rules developed in operations research by using them not only a priori but also dynamically during the search. Computational results are reported and comparisons are made with both exact and heuristic algorithms. On Solomon's well-known test bed, our algorithm is instrumental in achieving new best solutions for some of the problems in set RC2 and strengthens the presumption of optimality for the best known solutions to the problems in set C2.