{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T06:40:59Z","timestamp":1763620859920,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,1,12]],"date-time":"2021-01-12T00:00:00Z","timestamp":1610409600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Project-ID 390881007"],"award-info":[{"award-number":["Project-ID 390881007"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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\u2014namely, 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\u2014tailored for the TDTSP\u2014several families of valid inequalities, primal heuristics, a propagation method, and a branching rule. Combining these with the time-dependent shortest path pricing we provide\u2014to our knowledge\u2014the 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.<\/jats:p>","DOI":"10.3390\/a14010021","type":"journal-article","created":{"date-parts":[[2021,1,12]],"date-time":"2021-01-12T14:28:53Z","timestamp":1610461733000},"page":"21","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Dynamic Shortest Paths Methods for the Time-Dependent TSP"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3948-9344","authenticated-orcid":false,"given":"Christoph","family":"Hansknecht","sequence":"first","affiliation":[{"name":"Institute for Mathematical Optimization, Technische Universit\u00e4t Braunschweig, Universit\u00e4tsplatz 2, 38106 Braunschweig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0189-0557","authenticated-orcid":false,"given":"Imke","family":"Joormann","sequence":"additional","affiliation":[{"name":"Cluster of Excellence SE<sup>2<\/sup>A\u2014Sustainable and Energy-Efficient Aviation, Technische Universit\u00e4t Braunschweig, 38106 Braunschweig, Germany"},{"name":"Institute of Automotive Management and Industrial Production, Technische Universit\u00e4t Braunschweig, M\u00fchlenpfordtstr. 23, 38106 Braunschweig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8792-4390","authenticated-orcid":false,"given":"Sebastian","family":"Stiller","sequence":"additional","affiliation":[{"name":"Institute for Mathematical Optimization, Technische Universit\u00e4t Braunschweig, Universit\u00e4tsplatz 2, 38106 Braunschweig, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2021,1,12]]},"reference":[{"key":"ref_1","unstructured":"Applegate, D.L., Bixby, R.E., Chvatal, V., and Cook, W.J. (2011). The Traveling Salesman Problem: A Computational Study, Princeton University Press."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Gutin, G., and Punnen, A.P. (2006). The Traveling Salesman Problem and Its Variations, Springer.","DOI":"10.1007\/b101971"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","article-title":"An effective implementation of the Lin\u2013Kernighan traveling salesman heuristic","volume":"126","author":"Helsgaun","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"McMenemy, P., Veerapen, N., Adair, J., and Ochoa, G. (2019). Rigorous Performance Analysis of State-of-the-Art TSP Heuristic Solvers. European Conference on Evolutionary Computation in Combinatorial Optimization (Part of EvoStar), Springer.","DOI":"10.1007\/978-3-030-16711-0_7"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Batz, G.V., Delling, D., Sanders, P., and Vetter, C. (2009, January 3). Time-Dependent Contraction Hierarchies. Proceedings of the 2009 Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX), New York, NY, USA.","DOI":"10.1137\/1.9781611972894.10"},{"key":"ref_6","first-page":"1","article-title":"Fastest paths in time-dependent networks for intelligent vehicle-highway systems applications","volume":"1","author":"Kaufman","year":"1993","journal-title":"J. Intell. Transp. Syst."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-642-05465-5_8","article-title":"Time-Dependent Route Planning","volume":"5868","author":"Delling","year":"2009","journal-title":"Robust Online Large-Scale Optim."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","article-title":"An Analysis of Several Heuristics for the Traveling Salesman Problem","volume":"6","author":"Rosenkrantz","year":"1977","journal-title":"SIAM J. Comput."},{"key":"ref_9","unstructured":"Christofides, N. (1976). Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem, Carnegie-Mellon Univ. Pittsburgh Pa Management Sciences Research Group. Technical Report."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/1097-0037(200009)36:2<69::AID-NET1>3.0.CO;2-Q","article-title":"A Polyhedral Study of the Asymmetric Traveling Salesman Problem with Time Windows","volume":"36","author":"Ascheuer","year":"2000","journal-title":"Networks"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/PL00011432","article-title":"Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut","volume":"90","author":"Ascheuer","year":"2001","journal-title":"Math. Program."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Toth, P., and Vigo, D. (2002). The Vehicle Routing Problem, SIAM.","DOI":"10.1137\/1.9780898718515"},{"key":"ref_13","unstructured":"Fukasawa, R., Barboza, A.S., and Toriello, A. (2020, October 02). On the Strength of Approximate Linear Programming Relaxations for the Traveling Salesman Problem. Available online: www2.isye.gatech.edu\/~atoriello3\/bcpalp.pdf."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/s10107-005-0644-x","article-title":"Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem","volume":"106","author":"Fukasawa","year":"2006","journal-title":"Math. Program."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/s12532-012-0047-y","article-title":"The time dependent traveling salesman problem: Polyhedra and algorithm","volume":"5","author":"Abeledo","year":"2013","journal-title":"Math. Program. Comput."},{"key":"ref_16","first-page":"393","article-title":"Solution of a large-scale traveling-salesman problem","volume":"2","author":"Dantzig","year":"1954","journal-title":"J. Oper. Res. Soc. Am."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1287\/ijoc.1040.0117","article-title":"The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k \u2265 3","volume":"18","author":"Irnich","year":"2006","journal-title":"INFORMS J. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1287\/trsc.2013.0474","article-title":"Dynamic ng-Path Relaxation for the Delivery Man Problem","volume":"48","author":"Roberti","year":"2014","journal-title":"Transp. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1287\/opre.26.1.86","article-title":"The Time-Dependent Traveling Salesman Problem and its Application to the Tardiness Problem in One-Machine Scheduling","volume":"26","author":"Picard","year":"1978","journal-title":"Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/j.disopt.2008.04.001","article-title":"The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times","volume":"5","author":"Bigras","year":"2008","journal-title":"Discret. Optim."},{"key":"ref_21","first-page":"369","article-title":"Mixed integer formulations for the multiple minimum latency problem","volume":"19","year":"2019","journal-title":"Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/s12532-010-0019-z","article-title":"Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems","volume":"2","author":"Pessoa","year":"2010","journal-title":"Math. Program. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1287\/trsc.1120.0449","article-title":"Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem","volume":"48","author":"Cordeau","year":"2014","journal-title":"Transp. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1002\/net.21830","article-title":"A branch-and-bound algorithm for the time-dependent travelling salesman problem","volume":"72","author":"Arigliano","year":"2018","journal-title":"Networks"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/S0377-2217(02)00147-9","article-title":"Vehicle dispatching with time-dependent travel times","volume":"144","author":"Ichoua","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1287\/trsc.2019.0911","article-title":"Dynamic Discretization Discovery for Solving the Time-Dependent Traveling Salesman Problem with Time Windows","volume":"54","author":"Vu","year":"2020","journal-title":"Transp. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s11750-019-00514-4","article-title":"Perspectives on integer programming for time-dependent models","volume":"27","author":"Boland","year":"2019","journal-title":"TOP"},{"key":"ref_28","unstructured":"Hansknecht, C., Joormann, I., and Stiller, S. (2018). Cuts, Primal Heuristics, and Learning to Branch for the Time-Dependent Traveling Salesman Problem. arXiv."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Korte, B., and Vygen, J. (2012). Combinatorial Optimization: Theory and Algorithms, Springer.","DOI":"10.1007\/978-3-642-24488-9"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","article-title":"A Dynamic Programming Approach to Sequencing Problems","volume":"10","author":"Held","year":"1962","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","article-title":"The traveling-salesman problem and minimum spanning trees","volume":"18","author":"Held","year":"1970","journal-title":"Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0377-2217(93)E0238-S","article-title":"A classification of formulations for the (time-dependent) traveling salesman problem","volume":"83","author":"Gouveia","year":"1995","journal-title":"Eur. J. Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1287\/opre.1050.0234","article-title":"Selected Topics in Column Generation","volume":"53","author":"Desrosiers","year":"2005","journal-title":"Oper. Res."},{"key":"ref_34","first-page":"33","article-title":"Lineare Charakterisierungen von Travelling Salesman Problemen","volume":"21","author":"Padberg","year":"1977","journal-title":"Z. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0377-2217(99)00015-6","article-title":"Conflict graphs in solving integer programming problems","volume":"121","author":"Nemhauser","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1137\/0402038","article-title":"The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope on a Directed Graph","volume":"2","author":"Balas","year":"1989","journal-title":"SIAM J. Discret. Math."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1016\/j.ejor.2013.05.022","article-title":"Facets and valid inequalities for the time-dependent travelling salesman problem","volume":"236","author":"Zabala","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s12532-008-0001-1","article-title":"SCIP: Solving constraint integer programs","volume":"1","author":"Achterberg","year":"2009","journal-title":"Math. Program. Comput."},{"key":"ref_39","unstructured":"Gurobi Optimization, LLC (2020). Gurobi Optimizer Reference Manual, Gurobi Optimization, LLC."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/21\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:10:08Z","timestamp":1760159408000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,12]]},"references-count":39,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["a14010021"],"URL":"https:\/\/doi.org\/10.3390\/a14010021","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,1,12]]}}}