Using Congestion Zones for Solving the Time Dependent Vehicle Routing Problem
Abstract
This paper provides a framework for solving the Time Dependent Vehicle Routing Problem (TDVRP) by using historical data. The data are used to predict travel times during certain times of the day and derive zones of congestion that can be used by optimization algorithms. A combination of well-known algorithms was adapted to the time dependent setting and used to solve the real-world problems. The adapted algorithm outperforms the best-known results for TDVRP benchmarks. The proposed framework was applied to a real-world problem and results show a reduction in time delays in serving customers compared to the time independent case.
References
Kok AL, Hans EW, Schutten JMJ. Vehicle routing under time-dependent travel times: The impact of congestion avoidance. Computers & Operations Research. 2012;39(5): 910-8.
Gendreau M, Ghiani G, Guerriero E. Time-dependent routing problems: A review. Computers & Operations Research. 2015;64: 189-97.
Dantzig GB, Ramser JH. The truck dispatching problem. Management Science. 1959;6(1): 80-91.
Eksioglu B, Vural AV, Reisman A. The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering. 2009;57(4): 1472-83.
Braekers K, Ramaekers K, van Nieuwenhuyse I. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering. 2016;99: 300-13.
Ichoua S, Gendreau M, Potvin J-Y. Vehicle dispatching with time-dependent travel times. European Journal of Operational Research. 2003;144: 379-96.
Fleischmann B, Gietz M, Gnutzmann S. Time-varying travel times in vehicle routing. Transportation Science. 2004;38(2): 160-73.
Hashimoto H, Yagiura M, Ibaraki T. An iterated local search algorithm for the time-dependent vehicle routing problem with time windows. Discrete Optimization. 2008;5: 434-56.
Donati AV, Montemanni R, Casagrande N, Rizzoli AE, Gambardella LM. Time dependent vehicle routing problem with a multi ant colony system. European Journal of Operational Research. 2008;185(3): 1174-91.
Ehmke JF, Steinert A, Mattfeld DC. Advanced routing for city logistics service providers based on time-dependent travel times. Journal of Computational Science. 2012;3(4): 193-205.
Lecluyse C, Sörensen K, Peremans H. A network-consistent time-dependent travel time layer for routing optimization problems. European Journal of Operational Research. 2013;226(3): 395-413.
Solomon M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research. 1987;35(2): 254-65.
Gehring H, Homberger J. A Parallel Hybrid Evolutionary Metaheuristic for the Vehicle Routing Problem with Time Windows. 1999. p. 57-64. Available from: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.617.1364&rep=rep1&type=pdf
Figliozzi MA. The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics. Transportation Research Part E: Logistics and Transportation Review. 2012;48(3): 616-36.
Dijkstra EW. A note on two problems in connexion with graphs. Numerische Mathematik. 1959;1(1): 269-71.
Cherkassky BV, Goldberg AV, Radzik T. Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming. 1993;73(2): 129-74.
Cooke KL, Halsey E. The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis and Applications. 1966;14(3): 493-8.
Braysy O, Gendreau M. Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation Science. 2005;39(1): 104-18.
Nagata Y, Braysy O. A powerful route minimization heuristic for the vehicle routing problem with time windows. Operations Research Letters. 2009(37): 333-8.
Schrimpf G, Schneider J, Stamm-Wilbrandt H, Dueck G. Record breaking optimization results using the ruin and recreate principle. Journal of Computational Physics. 2000;159(2): 139-71.
Pisinger D, Ropke S. A general heuristic for vehicle routing problem. Computers & Operations Research. 2007;34(8): 2403-35.
Ehmke J. Integration of information and optimization models for routing in city logistics. S.l: Springer; 2014.
Erdelić T, Ravlić M, Carić T. Travel time prediction using speed profiles for road network of Croatia. 2016 International Symposium ELMAR, 12-14 Sept. 2016, Zadar, Croatia. IEEE; 2016. p. 97-100.
Batz GV, Geisberger R, Neubauer S, Sanders P. Time-dependent contraction hierarchies and approximation. In: Experimental Algorithms, Proceedings of the 9th International Symposium, SEA 2010, 20-22 May 2010, Ischia Island, Naples, Italy; 2010. p.166-177.
Fosin J. Time dependent vehicle routing problem solving method based on speed profiles. PhD thesis. University of Zagreb, Faculty of Transport and Traffic Sciences; 2016.
Gonzalez R, Woods R. Digital Image Processing. 4th ed. Pearson; 2017.
Kumar SN, Panneerselvam R. A time-dependent vehicle routing problem with time windows for e-commerce supplier site pickups using genetic algorithm. Intelligent Information Management. 2015;7: 181-94.
Rincon-Garcia N, Waterson, B & Cherrett, T. A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows. International Journal of Industrial Engineering Computations. 2017;8(1): 141-60.
Desaulniers G, Madsen OBG, Ropke S. The vehicle routing problem with time windows. In: Toth P, Vigo D. (eds.) Vehicle routing: problems, methods and applications. 2nd ed. Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics; 2015. p. 119-159.
Copyright (c) 2020 Tonči Carić, Juraj Fosin
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
