Next Article in Journal
Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
Next Article in Special Issue
An FPTAS for Dynamic Multiobjective Shortest Path Problems
Previous Article in Journal
Urban e-Grocery Distribution Design in Pamplona (Spain) Applying an Agent-Based Simulation Model with Horizontal Cooperation Scenarios
Previous Article in Special Issue
A Discrete-Continuous Algorithm for Free Flight Planning
Open AccessArticle

Dynamic Shortest Paths Methods for the Time-Dependent TSP

1
Institute for Mathematical Optimization, Technische Universität Braunschweig, Universitätsplatz 2, 38106 Braunschweig, Germany
2
Cluster of Excellence SE2A—Sustainable and Energy-Efficient Aviation, Technische Universität Braunschweig, 38106 Braunschweig, Germany
3
Institute of Automotive Management and Industrial Production, Technische Universität Braunschweig, Mühlenpfordtstr. 23, 38106 Braunschweig, Germany
*
Author to whom correspondence should be addressed.
Received: 30 November 2020 / Revised: 4 January 2021 / Accepted: 8 January 2021 / Published: 12 January 2021
(This article belongs to the Special Issue Algorithms for Shortest Paths in Dynamic and Evolving Networks)
The time-dependent traveling salesman problem (TDTSP) asks for a shortest Hamiltonian tour in a directed graph where (asymmetric) arc-costs depend on the time the arc is entered. With traffic data abundantly available, methods to optimize routes with respect to time-dependent travel times are widely desired. This holds in particular for the traveling salesman problem, which is a corner stone of logistic planning. In this paper, we devise column-generation-based IP methods to solve the TDTSP in full generality, both for arc- and path-based formulations. The algorithmic key is a time-dependent shortest path problem, which arises from the pricing problem of the column generation and is of independent interest—namely, to find paths in a time-expanded graph that are acyclic in the underlying (non-expanded) graph. As this problem is computationally too costly, we price over the set of paths that contain no cycles of length k. In addition, we devise—tailored for the TDTSP—several families of valid inequalities, primal heuristics, a propagation method, and a branching rule. Combining these with the time-dependent shortest path pricing we provide—to our knowledge—the first elaborate method to solve the TDTSP in general and with fully general time-dependence. We also provide for results on complexity and approximability of the TDTSP. In computational experiments on randomly generated instances, we are able to solve the large majority of small instances (20 nodes) to optimality, while closing about two thirds of the remaining gap of the large instances (40 nodes) after one hour of computation. View Full-Text
Keywords: integer programming; traveling salesman problem; shortest path problem integer programming; traveling salesman problem; shortest path problem
Show Figures

Figure 1

MDPI and ACS Style

Hansknecht, C.; Joormann, I.; Stiller, S. Dynamic Shortest Paths Methods for the Time-Dependent TSP. Algorithms 2021, 14, 21. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010021

AMA Style

Hansknecht C, Joormann I, Stiller S. Dynamic Shortest Paths Methods for the Time-Dependent TSP. Algorithms. 2021; 14(1):21. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010021

Chicago/Turabian Style

Hansknecht, Christoph; Joormann, Imke; Stiller, Sebastian. 2021. "Dynamic Shortest Paths Methods for the Time-Dependent TSP" Algorithms 14, no. 1: 21. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010021

Find Other Styles
Note that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.

Article Access Map by Country/Region

1
Search more from Scilit
 
Search
Back to TopTop