Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks

被引:0
|
作者
Blauth, Jannis [1 ,2 ]
Held, Stephan [1 ,2 ]
Mueller, Dirk [1 ,2 ]
Schlomberg, Niklas [1 ,2 ]
Traub, Vera [1 ,2 ]
Trobst, Thorben [3 ]
Vygen, Jens [1 ,2 ]
机构
[1] Univ Bonn, Res Inst Discrete Math, Bonn, Germany
[2] Univ Bonn, Hausdorff Ctr Math, Bonn, Germany
[3] Univ Calif Irvine, Irvine, CA USA
关键词
Vehicle routing; Time-dependent travel times; Piecewise linear functions; Data structures; EJECTION CHAINS; NEIGHBORHOOD SEARCH; HEURISTIC ALGORITHM; SALESMAN PROBLEM; DELIVERY PROBLEM; LOCAL SEARCH; TABU SEARCH; WINDOWS; PICKUP;
D O I
10.1016/j.disopt.2024.100848
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We develop theoretical foundations and practical algorithms for vehicle routing with time- dependent travel times. We also provide new benchmark instances and experimental results. First, we study basic operations on piecewise linear arrival time functions. In particular, we devise a faster algorithm to compute the pointwise minimum of a set of piecewise linear functions and a monotonicity-preserving variant of the Imai-Iri algorithm to approximate an arrival time function with fewer breakpoints. Next, we show how to evaluate insertion and deletion operations in tours efficiently and update the underlying data structure faster than previously known when a tour changes. Evaluating a tour also requires a scheduling step which is non-trivial in the presence of time windows and time-dependent travel times. We show how to perform this in linear time. Based on these results, we develop a local search heuristic to solve real-world vehicle routing problems with various constraints efficiently and report experimental results on classical benchmarks. Since most of these do not have time-dependent travel times, we generate and publish new benchmark instances that are based on real-world data. This data also demonstrates the importance of considering time-dependent travel times in instances with tight time windows.
引用
收藏
页数:21
相关论文
共 50 条
  • [41] Time-Dependent Travel-Time Constrained Inventory Routing Problem
    Touzout, Faycal A.
    Ladier, Anne-Laure
    Hadj-Hamou, Khaled
    COMPUTATIONAL LOGISTICS, ICCL 2020, 2020, 12433 : 151 - 166
  • [42] The time-dependent shortest path and vehicle routing problem
    Jaballah, Rabie
    Veenstra, Marjolein
    Coelho, Leandro C.
    Renaud, Jacques
    INFOR, 2021, 59 (04) : 592 - 622
  • [43] Using traffic information for time-dependent vehicle routing
    Kritzinger, Stefanie
    Doerner, Karl F.
    Hartl, Richard F.
    Kiechle, Guenter
    Stadler, Horst
    Manohar, Senthanal Sirpi
    SEVENTH INTERNATIONAL CONFERENCE ON CITY LOGISTICS, 2012, 39 : 217 - 229
  • [44] Genetic algorithm for the time-dependent vehicle routing problem
    Jung, S
    Haghani, A
    TRANSPORTATION NETWORK MODELING 2001: PLANNING AND ADMINISTRATION, 2001, (1771): : 164 - 171
  • [45] A mathematical model for the time-dependent vehicle routing problem
    Zaman baʇimli araçrotalama problemi için bir matematiksel model
    Koç, Çaʇri, 1600, Gazi Universitesi (29):
  • [46] MATHEMATICAL MODEL FOR THE TIME-DEPENDENT VEHICLE ROUTING PROBLEM
    Koc, Cagri
    Karaoglan, Ismail
    JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY, 2014, 29 (03): : 549 - 558
  • [47] Time-dependent vehicle routing problem with path flexibility
    Huang, Yixiao
    Zhao, Lei
    Van Woensel, Tom
    Gross, Jean-Philippe
    TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2017, 95 : 169 - 195
  • [48] Research of the Time-dependent Electric Vehicle Routing Problem
    Liu, Kaiji
    Ye, Peng
    Hong, Tao
    Li, Bo
    ICCCV 2019: PROCEEDINGS OF THE 2ND INTERNATIONAL CONFERENCE ON CONTROL AND COMPUTER VISION, 2019, : 97 - 101
  • [49] A review of recent advances in time-dependent vehicle routing
    Adamo, Tommaso
    Gendreau, Michel
    Ghiani, Gianpaolo
    Guerriero, Emanuela
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2024, 319 (01) : 1 - 15
  • [50] Solving Capacitated Time-Dependent Vehicle Routing Problem
    Ribic, Filip
    Erdelic, Tomislav
    Caric, Tonci
    Erdelic, Martina
    CENTRAL EUROPEAN CONFERENCE ON INFORMATION AND INTELLIGENT SYSTEMS, CECIIS 2022, 2022, : 449 - 456