Dynamic Programming for the Time-Dependent Traveling Salesman Problem with Time Windows

Gonzalo Lera-Romero (), Juan José Miranda Bront () and Francisco J. Soulignac ()
Additional contact information
Gonzalo Lera-Romero: Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, C1428EGA Buenos Aires, Argentina; Instituto de Investigación en Ciencias de la Computación (ICC), Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET)/Universidad de Buenos Aires, C1428EGA Buenos Aires, Argentina
Juan José Miranda Bront: Escuela de Negocios, Universidad Torcuato Di Tella, C1428BCW Buenos Aires, Argentina; CONICET, C1425FQB Buenos Aires, Argentina
Francisco J. Soulignac: Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, C1428EGA Buenos Aires, Argentina; Instituto de Investigación en Ciencias de la Computación (ICC), Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET)/Universidad de Buenos Aires, C1428EGA Buenos Aires, Argentina

INFORMS Journal on Computing, 2022, vol. 34, issue 6, 3292-3308

Abstract: The time-dependent traveling salesman problem with time windows (TDTSPTW) is a variant of the well-known traveling salesman problem with time windows, in which travel times are not assumed to be constant. The TDTSPTW accounts for the effects of congestion at the planning level, being particularly suited for distribution problems in large cities. In this paper we develop a labeling-based algorithm for the TDTSPTW that incorporates partial dominance and generalizes several state-of-the-art components from the time-independent related literature. We propose a framework general enough to be applied to the TDTSPTW and its variant without time windows, with the objective of minimizing the duration or the makespan. As part of the framework, we introduce a new state-space relaxation specifically designed for the time-dependent context. Extensive computational experiments show the effectiveness of the overall approach and the impact of the new relaxation, outperforming several recent algorithms proposed for these variants on more than 9,000 benchmark instances. In addition, we frame the minimum tour duration problem within the time-dependent literature and include it as a benchmark for our algorithm, obtaining improved computation times and 31 new optimal solutions. Summary of Contribution: In this paper, we study the time-dependent traveling salesman problem with time windows (TDTSPTW), a difficult single-vehicle routing problem that incorporates more realistic travel time functions than its classic time-independent counterpart. As a result, the TDTSPTW is harder to solve, as it requires more complex models and algorithms. Using state-of-the-art optimization techniques, we propose an efficient solution approach for the TDTSPTW and some related variants that outperforms the previous approaches in the literature. Our paper emphasizes the importance of algorithmic design and efficient implementations to tackle relevant practical combinatorial optimization problems—in particular, for time-dependent problems. Moreover, the resulting algorithm fosters a new research direction regarding exact algorithms for time-dependent problems using dynamic programming and relaxation techniques.

Keywords: traveling salesman problem; time-dependent travel times; time windows; dynamic programming; state-space relaxation; completion bounds (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1236 (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:orijoc:v:34:y:2022:i:6:p:3292-3308

Access Statistics for this article

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