{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T00:22:38Z","timestamp":1723162958375},"reference-count":64,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T00:00:00Z","timestamp":1720569600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Optimization"],"published-print":{"date-parts":[[2024,8]]},"DOI":"10.1016\/j.disopt.2024.100848","type":"journal-article","created":{"date-parts":[[2024,7,27]],"date-time":"2024-07-27T01:28:33Z","timestamp":1722043713000},"page":"100848","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks"],"prefix":"10.1016","volume":"53","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-5181-802X","authenticated-orcid":false,"given":"Jannis","family":"Blauth","sequence":"first","affiliation":[]},{"given":"Stephan","family":"Held","sequence":"additional","affiliation":[]},{"given":"Dirk","family":"M\u00fcller","sequence":"additional","affiliation":[]},{"given":"Niklas","family":"Schlomberg","sequence":"additional","affiliation":[]},{"given":"Vera","family":"Traub","sequence":"additional","affiliation":[]},{"given":"Thorben","family":"Tr\u00f6bst","sequence":"additional","affiliation":[]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"2","key":"10.1016\/j.disopt.2024.100848_b1","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":"European J. Oper. Res."},{"issue":"3","key":"10.1016\/j.disopt.2024.100848_b2","first-page":"159","article-title":"An optimal algorithm for approximating a piecewise linear function","volume":"9","author":"Imai","year":"1986","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.disopt.2024.100848_b3","doi-asserted-by":"crossref","DOI":"10.1145\/2444016.2444020","article-title":"Minimum time-dependent travel times with contraction hierarchies","volume":"18","author":"Batz","year":"2013","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"4","key":"10.1016\/j.disopt.2024.100848_b4","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.1287\/trsc.2019.0938","article-title":"Efficient move evaluations for time-dependent vehicle routing problems","volume":"54","author":"Visser","year":"2020","journal-title":"Transp. Sci."},{"issue":"2","key":"10.1016\/j.disopt.2024.100848_b5","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/j.disopt.2007.05.004","article-title":"An iterated local search algorithm for the time-dependent vehicle routing problem with time windows","volume":"5","author":"Hashimoto","year":"2008","journal-title":"Discrete Optim."},{"key":"10.1016\/j.disopt.2024.100848_b6","series-title":"10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems","first-page":"74","article-title":"Engineering time-dependent many-to-many shortest paths computation","author":"Geisberger","year":"2010"},{"issue":"7","key":"10.1016\/j.disopt.2024.100848_b7","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1016\/0305-0548(93)90060-V","article-title":"Implementing an insertion heuristic for vehicle routing on parallel hardware","volume":"20","author":"Foisy","year":"1993","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.disopt.2024.100848_b8","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s10107-022-01841-4","article-title":"Improving the approximation ratio for capacitated vehicle routing","volume":"197","author":"Blauth","year":"2023","journal-title":"Math. Program."},{"key":"10.1016\/j.disopt.2024.100848_b9","series-title":"International Conference on Integer Programming and Combinatorial Optimization","article-title":"Improved approximations for CVRP with unsplittable demands","author":"Friggstad","year":"2022"},{"key":"10.1016\/j.disopt.2024.100848_b10","doi-asserted-by":"crossref","unstructured":"N. Bansal, A. Blum, S. Chawla, A. Meyerson, Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows, in: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, ISBN: 1581138520, 2004, pp. 166\u2013174.","DOI":"10.1145\/1007352.1007385"},{"issue":"3","key":"10.1016\/j.disopt.2024.100848_b11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2229163.2229167","article-title":"Improved algorithms for orienteering and related problems","volume":"8","author":"Chekuri","year":"2012","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"10.1016\/j.disopt.2024.100848_b12","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1007\/s00453-011-9509-2","article-title":"The directed orienteering problem","volume":"60","author":"Nagarajan","year":"2011","journal-title":"Algorithmica"},{"key":"10.1016\/j.disopt.2024.100848_b13","doi-asserted-by":"crossref","unstructured":"A.A. Pessoa, R. Sadykov, E. Uchoa, F. Vanderbeck, A Generic Exact Solver for Vehicle Routing and Related Problems, in: International Conference on Integer Programming and Combinatorial Optimization, IPCO, 2019, pp. 354\u2013369.","DOI":"10.1007\/978-3-030-17953-3_27"},{"key":"10.1016\/j.disopt.2024.100848_b14","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/j.cor.2012.07.018","article-title":"A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows","volume":"40","author":"Vidal","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.disopt.2024.100848_b15","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.cor.2019.01.002","article-title":"Knowledge-guided local search for the vehicle routing problem","volume":"105","author":"Arnold","year":"2019","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"10.1016\/j.disopt.2024.100848_b16","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1287\/trsc.2021.1059","article-title":"A fast and scalable heuristic for the solution of large-scale capacitated vehicle routing problems","volume":"55","author":"Accorsi","year":"2021","journal-title":"Transp. Sci."},{"key":"10.1016\/j.disopt.2024.100848_b17","doi-asserted-by":"crossref","DOI":"10.1016\/j.cor.2021.105475","article-title":"A POPMUSIC matheuristic for the capacitated vehicle routing problem","volume":"136","author":"Queiroga","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.disopt.2024.100848_b18","doi-asserted-by":"crossref","DOI":"10.1016\/j.cor.2021.105643","article-title":"Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood","volume":"140","author":"Vidal","year":"2022","journal-title":"Comput. Oper. Res."},{"year":"2014","series-title":"Vehicle Routing: Problems, Methods, Applications","key":"10.1016\/j.disopt.2024.100848_b19"},{"key":"10.1016\/j.disopt.2024.100848_b20","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1287\/trsc.26.3.185","article-title":"Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms","volume":"26","author":"Malandraki","year":"1992","journal-title":"Transp. Sci."},{"issue":"3","key":"10.1016\/j.disopt.2024.100848_b21","doi-asserted-by":"crossref","first-page":"1174","DOI":"10.1016\/j.ejor.2006.06.047","article-title":"Time dependent vehicle routing problem with a multi ant colony system","volume":"185","author":"Donati","year":"2008","journal-title":"European J. Oper. Res."},{"issue":"3","key":"10.1016\/j.disopt.2024.100848_b22","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1016\/j.tre.2011.11.006","article-title":"The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics","volume":"48","author":"Figliozzi","year":"2012","journal-title":"Transp. Res. E Logist. Transp. Rev."},{"issue":"3","key":"10.1016\/j.disopt.2024.100848_b23","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1287\/trsc.1120.0445","article-title":"Branch and price for the time-dependent vehicle routing problem with time windows","volume":"47","author":"Dabia","year":"2013","journal-title":"Transp. Sci."},{"key":"10.1016\/j.disopt.2024.100848_b24","doi-asserted-by":"crossref","DOI":"10.1016\/j.cor.2020.105193","article-title":"A hybrid algorithm for time-dependent vehicle routing problem with time windows","volume":"128","author":"Pan","year":"2021","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"10.1016\/j.disopt.2024.100848_b25","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.ejor.2020.09.022","article-title":"Multi-trip time-dependent vehicle routing problem with time windows","volume":"291","author":"Pan","year":"2021","journal-title":"European J. Oper. Res."},{"key":"10.1016\/j.disopt.2024.100848_b26","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/j.trpro.2014.10.024","article-title":"Time dependent travel speed vehicle routing and scheduling on a real road network: the case of Torino","volume":"3","author":"Mancini","year":"2014","journal-title":"Transp. Res. Procedia"},{"key":"10.1016\/j.disopt.2024.100848_b27","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.trb.2016.10.013","article-title":"Time-dependent vehicle routing problem with path flexibility","volume":"95","author":"Huang","year":"2017","journal-title":"Transp. Res. B"},{"year":"2017","series-title":"Vehicle Routing Problems with Road-Network information","author":"Ticha","key":"10.1016\/j.disopt.2024.100848_b28"},{"issue":"4","key":"10.1016\/j.disopt.2024.100848_b29","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1002\/net.21852","article-title":"A branch-and-price algorithm for the vehicle routing problem with time windows on a road network","volume":"73","author":"Ticha","year":"2019","journal-title":"Networks"},{"issue":"1","key":"10.1016\/j.disopt.2024.100848_b30","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/j.ejor.2020.05.041","article-title":"Tabu search for the time-dependent vehicle routing problem with time windows on a road network","volume":"288","author":"Gmira","year":"2021","journal-title":"European J. Oper. Res."},{"key":"10.1016\/j.disopt.2024.100848_b31","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.cor.2015.06.001","article-title":"Time-dependent routing problems: A review","volume":"64","author":"Gendreau","year":"2015","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"10.1016\/j.disopt.2024.100848_b32","doi-asserted-by":"crossref","first-page":"90","DOI":"10.3390\/a14030090","article-title":"Space-efficient, fast and exact routing in time-dependent road networks","volume":"14","author":"Strasser","year":"2021","journal-title":"Algorithms"},{"key":"10.1016\/j.disopt.2024.100848_b33","doi-asserted-by":"crossref","unstructured":"A. Wiernik, Planar realizations of nonlinear Davenport\u2013Schinzel sequences by segments, in: 27th Annual Symposium on Foundations of Computer Science, FOCS, 1986, pp. 97\u2013106.","DOI":"10.1109\/SFCS.1986.43"},{"issue":"2","key":"10.1016\/j.disopt.2024.100848_b34","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","article-title":"Nonlinearity of Davenport\u2013Schinzel sequences and of generalized path compression schemes","volume":"6","author":"Hart","year":"1986","journal-title":"Combinatorica"},{"issue":"2","key":"10.1016\/j.disopt.2024.100848_b35","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1287\/trsc.1030.0062","article-title":"Time-varying travel times in vehicle routing","volume":"38","author":"Fleischmann","year":"2004","journal-title":"Transp. Sci."},{"key":"10.1016\/j.disopt.2024.100848_b36","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.dam.2018.09.017","article-title":"Time-dependent asymmetric traveling salesman problem with time windows: Properties and an exact algorithm","volume":"261","author":"Arigliano","year":"2019","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.disopt.2024.100848_b37","doi-asserted-by":"crossref","DOI":"10.1016\/j.cor.2019.104795","article-title":"An enhanced lower bound for the time-dependent travelling salesman problem","volume":"113","author":"Adamo","year":"2020","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.disopt.2024.100848_b38","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/j.cor.2017.06.026","article-title":"An integer programming approach for the time-dependent traveling salesman problem with time windows","volume":"88","author":"Montero","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.disopt.2024.100848_b39","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.endm.2018.07.008","article-title":"Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints","volume":"69","author":"Lera-Romero","year":"2018","journal-title":"Electron. Notes Discrete Math."},{"issue":"1","key":"10.1016\/j.disopt.2024.100848_b40","doi-asserted-by":"crossref","DOI":"10.3390\/a14010021","article-title":"Dynamic shortest paths methods for the time-dependent TSP","volume":"14","author":"Hansknecht","year":"2021","journal-title":"Algorithms"},{"key":"10.1016\/j.disopt.2024.100848_b41","article-title":"Solving time dependent traveling salesman problems with time windows","volume":"6640","author":"Vu","year":"2018","journal-title":"Optimization Online"},{"issue":"1","key":"10.1016\/j.disopt.2024.100848_b42","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0377-2217(94)00299-1","article-title":"A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem","volume":"90","author":"Malandraki","year":"1996","journal-title":"European J. Oper. Res."},{"year":"2020","series-title":"Dynamic Programming for the Time-Dependent Traveling Salesman Problem with Time Windows","author":"Lera-Romero","key":"10.1016\/j.disopt.2024.100848_b43"},{"issue":"2","key":"10.1016\/j.disopt.2024.100848_b44","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1287\/trsc.2015.0626","article-title":"Dynamic programming for the minimum tour duration problem","volume":"51","author":"Tilk","year":"2017","journal-title":"Transp. Sci."},{"issue":"3","key":"10.1016\/j.disopt.2024.100848_b45","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1016\/j.ejor.2016.08.012","article-title":"New benchmark instances for the capacitated vehicle routing problem","volume":"257","author":"Uchoa","year":"2017","journal-title":"European J. Oper. Res."},{"key":"10.1016\/j.disopt.2024.100848_b46","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.cor.2019.03.006","article-title":"Efficiently solving very large-scale routing problems","volume":"107","author":"Arnold","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.disopt.2024.100848_b47","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1287\/opre.35.2.254","article-title":"Algorithms for the vehicle routing and scheduling problems with time window constraints","volume":"35","author":"Solomon","year":"1987","journal-title":"Oper. Res."},{"key":"10.1016\/j.disopt.2024.100848_b48","series-title":"Proceedings of EUROGEN 99","first-page":"57","article-title":"A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows","author":"Gehring","year":"1999"},{"key":"10.1016\/j.disopt.2024.100848_b49","article-title":"The time-dependent vehicle routing problem with time windows and road-network information","volume":"2","author":"Ticha","year":"2021","journal-title":"Oper. Res. Forum"},{"key":"10.1016\/j.disopt.2024.100848_b50","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.cor.2017.06.024","article-title":"Empirical analysis for the VRPTW with a multigraph representation for the road network","volume":"88","author":"Ticha","year":"2017","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"10.1016\/j.disopt.2024.100848_b51","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1007\/s00453-012-9714-7","article-title":"On the complexity of time-dependent shortest paths","volume":"68","author":"Foschini","year":"2014","journal-title":"Algorithmica"},{"key":"10.1016\/j.disopt.2024.100848_b52","series-title":"Handbook of Computational Geometry","first-page":"1","article-title":"Davenport\u2013Schinzel sequences and their geometric applications","author":"Agarwal","year":"2000"},{"issue":"2","key":"10.1016\/j.disopt.2024.100848_b53","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","article-title":"An effective heuristic algorithm for the traveling-salesman problem","volume":"21","author":"Lin","year":"1973","journal-title":"Oper. Res."},{"year":"2017","series-title":"An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems","author":"Helsgaun","key":"10.1016\/j.disopt.2024.100848_b54"},{"issue":"1","key":"10.1016\/j.disopt.2024.100848_b55","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-218X(94)00037-E","article-title":"Ejection chains, reference structures and alternating path methods for traveling salesman problems","volume":"65","author":"Glover","year":"1996","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"10.1016\/j.disopt.2024.100848_b56","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/S0167-8191(00)00102-2","article-title":"Node-ejection chains for the vehicle routing problem: Sequential and parallel algorithms","volume":"27","author":"Rego","year":"2001","journal-title":"Parallel Comput."},{"key":"10.1016\/j.disopt.2024.100848_b57","series-title":"Hybrid Metaheuristics","first-page":"78","article-title":"Fast ejection chain algorithms for vehicle routing with time windows","author":"Sontrop","year":"2005"},{"key":"10.1016\/j.disopt.2024.100848_b58","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.cie.2017.03.022","article-title":"Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem","volume":"107","author":"Soto","year":"2017","journal-title":"Comput. Ind. Eng."},{"issue":"1","key":"10.1016\/j.disopt.2024.100848_b59","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1287\/ijoc.15.1.82.15157","article-title":"Chained Lin-Kernighan for large traveling salesman problems","volume":"15","author":"Applegate","year":"2003","journal-title":"INFORMS J. Comput."},{"key":"10.1016\/j.disopt.2024.100848_b60","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/s13676-017-0115-6","article-title":"Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows","volume":"7","author":"Curtois","year":"2018","journal-title":"EURO J. Transp. Logist."},{"key":"10.1016\/j.disopt.2024.100848_b61","series-title":"Computational Logistics","first-page":"253","article-title":"A matheuristic approach to the pickup and delivery problem with time windows","author":"Sartori","year":"2018"},{"issue":"02","key":"10.1016\/j.disopt.2024.100848_b62","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1142\/S0218213003001186","article-title":"A metaheuristic for the pickup and delivery problem with time windows","volume":"12","author":"Li","year":"2003","journal-title":"Int. J. Artif. Intell. Tools"},{"year":"2018","series-title":"An Enhanced Branch and Price Algorithm for the Time-Dependent Vehicle Routing Problem with Time Window","author":"Lera-Romero","key":"10.1016\/j.disopt.2024.100848_b63"},{"issue":"1","key":"10.1016\/j.disopt.2024.100848_b64","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1002\/net.21937","article-title":"Linear edge costs and labeling algorithms: The case of the time-dependent vehicle routing problem with time windows","volume":"76","author":"Lera-Romero","year":"2020","journal-title":"Networks"}],"container-title":["Discrete Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1572528624000276?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1572528624000276?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T19:50:11Z","timestamp":1723146611000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1572528624000276"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8]]},"references-count":64,"alternative-id":["S1572528624000276"],"URL":"https:\/\/doi.org\/10.1016\/j.disopt.2024.100848","relation":{},"ISSN":["1572-5286"],"issn-type":[{"type":"print","value":"1572-5286"}],"subject":[],"published":{"date-parts":[[2024,8]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks","name":"articletitle","label":"Article Title"},{"value":"Discrete Optimization","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.disopt.2024.100848","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2024 The Author(s). Published by Elsevier B.V.","name":"copyright","label":"Copyright"}],"article-number":"100848"}}