AN EXACT CONSTRAINT LOGIC PROGRAMMING ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM WITH TIME WINDOWS

Citation
G. Pesant et al., AN EXACT CONSTRAINT LOGIC PROGRAMMING ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM WITH TIME WINDOWS, Transportation science, 32(1), 1998, pp. 12-29
Citations number
36
Categorie Soggetti
Transportation,Transportation
Journal title
ISSN journal
00411655
Volume
32
Issue
1
Year of publication
1998
Pages
12 - 29
Database
ISI
SICI code
0041-1655(1998)32:1<12:AECLPA>2.0.ZU;2-O
Abstract
This paper presents a: constraint logic programming model for the trav eling 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 perfor mance relies heavily on the degree of discretization applied to the da ta, our algorithm does not suffer from such space-complexity issues. T he 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 achie ving new best solutions for some of the problems in set RC2 and streng thens the presumption of optimality for the best known solutions to th e problems in set C2.