Dynamic Programming for the Minimum Tour Duration Problem

Christian Tilk () and Stefan Irnich ()
Additional contact information
Christian Tilk: Johannes Gutenberg-Universitaet Mainz, Germany
Stefan Irnich: Johannes Gutenberg-Universitaet Mainz, Germany

No 1408, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: The minimum tour duration problem (MTDP) is the variant of the traveling salesman problem with time windows, which consists of finding a time window-feasible Hamiltonian path minimizing the tour duration. We present a new effective dynamic programming (DP)-based approach for the MTDP. When solving the traveling salesman problem with time windows with DP, two independent resources are propagated along partial paths, one for costs and one for earliest arrival times. For dealing with tour duration minimization, we provide a new DP formulation with three resources for which effective dominance and bounding procedures are applicable. This is a non-trivial task because in the MTDP at least two resources depend on each other in a non-additive and non-linear way. In particular, we define consistent resource extension functions (REF) so that dominance is straightforward using componentwise comparison for the respective resource vectors. Moreover, one of the main advantages of the new REF definition is that the DP can be reversed consistently such that the forward DP or any of its relaxations provides bounds for the backward DP, and vice versa. Computational test confirm the effectiveness of the proposed approach.

Keywords: traveling salesman problem; time windows; tour duration; dynamic programming; state-space relaxation (search for similar items in EconPapers)
Pages: 26 pages
Date: 2014-08-04, Revised 2014-08-04
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1408.pdf First version, 2014 (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:jgu:wpaper:1408

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().