Dynamic programming for the minimum tour duration Problem
- Publikationstyp:
- Zeitschriftenaufsatz
- Metadaten:
-
- Autoren
- Christian Tilk
- Stefan Irnich
- Sammlungen
- metadata
- ISSN
- 1526-5447
- Ausgabe der Veröffentlichung
- 2
- Zeitschrift
- Transportation science
- Schlüsselwörter
- 330 Wirtschaft
- 330 Economics
- Sprache
- eng
- Paginierung
- Seiten: 549 - 565
- Datum der Veröffentlichung
- 2016
- Herausgeber
- INFORMS
- Herausgeber URL
- http://dx.doi.org/10.1287/trsc.2015.0626
- Datum der Datenerfassung
- 2020
- Datum, an dem der Datensatz öffentlich gemacht wurde
- 2020
- Zugang
- Public
- Titel
- Dynamic programming for the minimum tour duration Problem
- Ausgabe der Zeitschrift
- 51
Datenquelle: METADATA.UB
- Andere Metadatenquellen:
-
- Autoren
- Christian Tilk
- Stefan Irnich
- Autoren-URL
- https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:000401146800010&DestLinkType=FullRecord&DestApp=WOS_CPL
- DOI
- 10.1287/trsc.2015.0626
- Externe Identifier
- Clarivate Analytics Document Solution ID: EU6LZ
- ISSN
- 0041-1655
- Ausgabe der Veröffentlichung
- 2
- Zeitschrift
- TRANSPORTATION SCIENCE
- Schlüsselwörter
- traveling salesman problem
- time windows
- tour duration
- dynamic programming
- state-space relaxation
- Paginierung
- 549 - 565
- Datum der Veröffentlichung
- 2017
- Status
- Published
- Titel
- Dynamic Programming for the Minimum Tour Duration Problem
- Sub types
- Article
- Ausgabe der Zeitschrift
- 51
Datenquelle: Web of Science (Lite)
- Abstract
- <jats:p> The minimum tour duration problem (MTDP) is a 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 nontrivial task because in the MTDP at least two resources depend on each other in a nonadditive and nonlinear way. In particular, we define consistent resource extension functions (REFs) 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 provide bounds for the backward DP, and vice versa. Computational tests confirm the effectiveness of the proposed approach. </jats:p>
- Autoren
- Christian Tilk
- Stefan Irnich
- DOI
- 10.1287/trsc.2015.0626
- eISSN
- 1526-5447
- ISSN
- 0041-1655
- Ausgabe der Veröffentlichung
- 2
- Zeitschrift
- Transportation Science
- Sprache
- en
- Paginierung
- 549 - 565
- Datum der Veröffentlichung
- 2017
- Status
- Published
- Herausgeber
- Institute for Operations Research and the Management Sciences (INFORMS)
- Herausgeber URL
- http://dx.doi.org/10.1287/trsc.2015.0626
- Datum der Datenerfassung
- 2023
- Titel
- Dynamic Programming for the Minimum Tour Duration Problem
- Ausgabe der Zeitschrift
- 51
Datenquelle: Crossref
- Autoren
- Christian Tilk
- Stefan Irnich
- DOI
- 10.1287/trsc.2015.0626
- Zeitschrift
- Transp. Sci.
- Artikelnummer
- 2
- Paginierung
- 549 - 565
- Datum der Veröffentlichung
- 2017
- Titel
- Dynamic Programming for the Minimum Tour Duration Problem.
- Ausgabe der Zeitschrift
- 51
Datenquelle: DBLP
- Beziehungen:
- Eigentum von