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

Gilles Pesant, Michel Gendreau, Jean-Yves Potvin and Jean-Marc Rousseau
Additional contact information
Gilles Pesant: Centre de recherche sur les transports, Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal H3C 3J7, Canada
Michel Gendreau: Centre de recherche sur les transports and Département d'informatique et de recherche opérationnelle, Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal H3C 3J7, Canada
Jean-Yves Potvin: Centre de recherche sur les transports and Département d'informatique et de recherche opérationnelle, Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal H3C 3J7, Canada
Jean-Marc Rousseau: Centre de recherche sur les transports and Département d'informatique et de recherche opérationnelle, Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal H3C 3J7, and GIRO, Inc., 75 rue de Port-Royal est, bureau #500, Montréal H3L 3T1, Canada

Transportation Science, 1998, vol. 32, issue 1, 12-29

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.

Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.32.1.12 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:32:y:1998:i:1:p:12-29

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().