Article
ADAPTING JSPRIT FOR THE ELECTRIC VEHICLE ROUTING PROBLEM WITH RECHARGING: IMPLEMENTATION AND BENCHMARK
DOI: 10.7708/ijtte2022.12(3).04
12 / 3 / 340-351 Pages
Author(s)
Ayman Mahmoud - Université Paris-Saclay, CentraleSupélec, Laboratoire Génie Industriel, 91190, Gif-sur-Yvette, France -
Abstract
This article presents our adaptation of the Ruin-and-Recreate (R&R) algorithm to solve the electric vehicle routing problem with time windows and multiple trips. We implement this adaptation in JSprit, an open-source vehicle routing problem solver. We showcase the framework for a case study in Lyon, France. In the case study, we assess the efficiency impact of adding charging constraints to a simulation of a fleet of autonomous delivery robots. The framework is tested on benchmark instances and compared with results from literature.
Number of downloads: 260
Keywords:
electric;
vehicle;
routing;
JSprit;
optimization;
Acknowledgements:
The code related to the experiments presented in this paper can be obtained from the authors, and the detailed results with the sensitivity analysis can be shared upon request.
This paper presents work developed at IRT SystemX in the scope of the project LEAD, which has received funding from the European Union's Horizon 2020 research and innovation program under grant agreement no. 861598. This work has also received funding from the Région Île-de-France within the frame of the Future Cities Lab. The content of this paper does not reflect the official opinion of the European Union. Responsibility for the information and views expressed in this paper lies entirely with the authors.
References:
Bakach, I.; Campbell, A.M.; Ehmke, J.F. 2021. A two‐tier urban delivery network with robot‐based deliveries, Networks 78(4): 461-483.
Bean, W.L.; Joubert, J.W. 2019. Modelling receiver logistics behaviour. In Procedia Computer Science, The 10th International Conference on Ambient Systems, Networks and Technologies (ANT 2019) / The 2nd International Conference on Emerging Data and Industry 4.0 (EDI40 2019) / Affiliated Workshops 151: 763–768.
Christiaens, J.; Berghe, G.V. 2020. Slack Induction by String Removals for Vehicle Routing Problems, Transportation Science 54(2): 417–433.
Erdoğan, S.; Miller-Hooks, E. 2012. A Green Vehicle Routing Problem, Transportation Research Part E: Logistics and Transportation Review, Select Papers from the 19th International Symposium on Transportation and Traffic Theory 48(1): 100–114.
Ewert, R.; Martins-Turner, K.; Thaller, C.; Nagel, K. 2021. Using a route-based and vehicle type specific range constraint for improving vehicle routing problems with electric vehicles, Transportation Research Procedia 52: 517-524.
Gardrat, M. 2019. Survey methodology: the decoupling of household purchases and recovery of goods [In French: Méthodologie d’enquête: le découplage de l’achat et de la récupération des marchandises par les ménages] [Rapport de recherche] LAET (Lyon, France); Métropole de Lyon. 114p.
Goeke, D. 2019. Granular tabu search for the pickup and delivery problem with time windows and electric vehicles, European Journal of Operational Research 278(3): 821–836.
Hörl, S.; Balac, M. 2021. Synthetic population and travel demand for Paris and Île-de-France based on open and publicly available data, Transportation Research Part C: Emerging Technologies 130: 103291.
Horl, S.; Puchinger, J. 2022. From synthetic population to parcel demand: A modeling pipeline and case study for last-mile deliveries in Lyon. Transportation Reaseach Arena (TRA), Lisbon, Portugal.
JSprit. 2022. A Java based, open-source toolkit for solving rich traveling salesman (TSP) and vehicle routing problems (VRP). Available from Internet: https://jsprit.github.io/.
Karkula, M.; et al. 2019. Comparison of capabilities of recent open-source tools for solving capacitated vehicle routing problems with time windows, Carpathian Logistics Conference, Zakopane, Poland, 72-77.
Kullman, N.D.; Froger, A.; Mendoza, J.E.; Goodson, J.C. 2021. frvcpy: An open-source solver for the fixed route vehicle charging problem, INFORMS Journal on Computing 33(4): 1277-1283.
Martins-Turner, K., et al. 2019. Agent-based Modelling and Simulation of Tour Planning in Urban Freight Traffic. Transportation Research Procedia, Urban Mobility – Shaping the Future Together mobil.TUM 2018 – International Scientific Conference on Mobility and Transport Conference Proceedings 41: 328–332.
Martins-Turner, K., et al. 2020. Electrification of Urban Freight Transport - a Case Study of the Food Retailing Industry. Procedia Computer Science, The 11th International Conference on Ambient Systems, Networks and Technologies (ANT) / The 3rd International Conference on Emerging Data and Industry 4.0 (EDI40) / Affiliated Workshops 170: 757–763.
Montoya, A. et al. 2015. The electric vehicle routing problem with partial charging and nonlinear charging function (Research Report). LARIS. 11p.
Mucowska, M. 2021. Trends of Environmentally Sustainable Solutions of Urban Last-Mile Deliveries on the E-Commerce Market—A Literature Review, Sustainability 13(11): 5894.
Patella, S.M.; Grazieschi, G.; Gatta, V.; Marcucci, E.; Carrese, S. 2020. The adoption of green vehicles in last mile logistics: A systematic review, Sustainability 13(1): 6.
Schlenther, T.; Martins-Turner, K.; Bischoff, J.F.; Nagel, K. 2020. Potential of private autonomous vehicles for parcel delivery, Transportation Research Record 2674(11): 520-531.
Schneider, M.; Stenger, A.; Goeke, D. 2014. The electric vehicle-routing problem with time windows and recharging stations, Transportation Science 48(4): 500-520.
Schrimpf, G.; Schneider, J.; Stamm-Wilbrandt, H.; Dueck, G. 2000. Record breaking optimization results using the ruin and recreate principle, Journal of Computational Physics 159(2): 139-171.
Starship. 2022. Available from Internet: https://www.starship.xyz/. Vigo D.; Toth, P. 2014. Vehicle Routing: Problems, Methods, and Application, Second Edition. Volume 18 of MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics. 481p.
Villanueva, R.S. 2020. A pragmatic approach to improve the efficiency of the waste management system in Stockholm through the use of Big Data, Heuristics and open source VRP solvers: A real life waste collection problem; Stockholm’s waste collection system and inherent vehicle routing problem, VRP. Degree project in electrical engineering, second cycle, KTH.
Vosooghi, R.; Puchinger, J.; Bischoff, J.; Jankovic, M.; Vouillon, A. 2020. Shared autonomous electric vehicle service performance: Assessing the impact of charging infrastructure, Transportation Research Part D: Transport and Environment 81: 102283.
Yu, S.; Puchinger, J.; Sun, S. 2020. Two-echelon urban deliveries using autonomous vehicles, Transportation Research Part E: Logistics and Transportation Review 141: 102018.
Quoted IJTTE Works
There is no quoted studies.
Related Keywords