The Electric Vehicle Routing Problem with Time Windows, Partial Recharges, and Parcel Lockers
Source abstract
Abstract
This paper presents an extension of the Electric Vehicle Routing Problem with Time Windows and Partial Recharges (EVRPTW-PR), which incorporates the use of parcel lockers as a delivery method (i.e., self-pickup method). This variant, named the electric vehicle routing problem with time windows, partial recharges, and parcel lockers (EVRPTW-PR-PL), focuses on minimizing delivery costs by employing a homogeneous fleet of electric vehicles (EVs) and providing two delivery methods for serving customers: home delivery and self-pickup methods. We derive a mathematical formulation and propose an adaptive large neighborhood search (ALNS) algorithm to address EVRPTW-PR-PL. Moreover, in ALNS, the solution representation is constructed to handle the assignment of delivery methods. The performance of our proposed ALNS algorithm is evaluated by solving EVRPTW-PR benchmark instances. Finally, the results of EVRPTW-PR-PL obtained by using the GUROBI solver and our ALNS algorithm are provided, accompanied by managerial insights on the implementation of parcel lockers.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Vehicle Routing Optimization Methods · Transportation and Mobility Innovations · Smart Parking Systems Research
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Industrial Management, National Taiwan University of Science and Technology, Taipei 106, Taiwan
Center for Cyber-Physical System Innovation, National Taiwan University of Science and Technology, Taipei 106, Taiwan
Funding
National Science and Technology Council of the Republic of China (Taiwan) · Center for Cyber-Physical System Innovation
References (56)
Show source-provided references
1. Statista (2022). Retail e-Commerce Sales Worldwide from 2014 to 2026, Statista. Technical Report.
2. Electric vehicle routing problem with flexible deliveries10.1080/00207543.2022.2032451 ↗
3. Characteristics of innovations in last-mile logistics-using best practices, case studies and making the link with green and sustainable logistics
4. World Economic Forum (2020). The Future of the Last-Mile Ecosystem, World Economic Forum. Technical Report.
5. Silva, V., Amaral, A., and Fontes, T. (2023). Sustainable urban last-mile logistics: A systematic literature review. Sustainability, 15.10.3390/su15032285 ↗
6. Conrad, R.G., and Figliozzi, M.A. (2011, January 6–9). The recharging vehicle routing problem. Proceedings of the 2011 Industrial Engineering Research Conference, IISE Norcross, Singapore.
7. Partial recharge strategies for the electric vehicle routing problem with time windows10.1016/j.trc.2016.01.013 ↗
8. A parcel locker network as a solution to the logistics last mile problem10.1080/00207543.2017.1395490 ↗
9. Last-mile delivery concepts: A survey from an operational research perspective10.1007/s00291-020-00607-8 ↗
10. Covering delivery problem with electric vehicle and parcel lockers: Variable neighborhood search approach10.1016/j.cor.2023.106263 ↗
11. The electric vehicle-routing problem with time windows and recharging stations10.1287/trsc.2013.0490 ↗
12. Exact algorithms for electric vehicle-routing problems with time windows10.1287/opre.2016.1535 ↗
13. Routing a mix of conventional, plug-in hybrid, and electric vehicles10.1016/j.ejor.2018.06.025 ↗
14. The electric vehicle routing problem with time windows, partial recharges and satellite customers10.1016/j.tre.2019.08.015 ↗
15. A matheuristic method for the electric vehicle routing problem with time windows and fast chargers10.1016/j.cor.2018.06.019 ↗
16. A large neighborhood search-based matheuristic for the load-dependent electric vehicle routing problem with time windows10.1007/s10479-021-04320-9 ↗
17. The electric vehicle routing problem with nonlinear charging function10.1016/j.trb.2017.02.004 ↗
18. Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions10.1016/j.cor.2018.12.013 ↗
19. Electric vehicle scheduling and optimal charging problem: Complexity, exact and heuristic approaches10.1080/00207543.2016.1192695 ↗
20. An energy-efficient green-vehicle routing problem with mixed vehicle fleet, partial battery recharging and time windows10.1016/j.ejor.2019.01.067 ↗
21. The hybrid vehicle routing problem10.1016/j.trc.2017.02.004 ↗
22. Electric vehicle routing problem with time-dependent waiting times at recharging stations10.1016/j.cor.2019.02.014 ↗
23. The electric vehicle routing problem with capacitated charging stations10.1287/trsc.2021.1111 ↗
24. Adaptive routing and recharging policies for electric vehicles10.1287/trsc.2016.0724 ↗
25. A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations10.1016/j.cor.2020.105060 ↗
26. The dial-a-ride problem with electric vehicles and battery swapping stations10.1016/j.tre.2018.08.005 ↗
27. The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology10.1016/j.ejor.2018.07.002 ↗
28. An improved matheuristic for solving the electric vehicle routing problem with time windows and synchronized mobile charging/battery swapping10.1016/j.cor.2023.106310 ↗
29. The time-dependent electric vehicle routing problem: Model and solution10.1016/j.eswa.2020.113593 ↗
30. A survey on the electric vehicle routing problem: Variants and solution approaches
31. Behnke, M. (2019, January 18–20). Recent Trends in Last Mile Delivery: Impacts of Fast Fulfillment, Parcel Lockers, Electric or Autonomous Vehicles, and More. Proceedings of the Logistics Management: Strategies and Instruments for Digitalizing and Decarbonizing Supply Chains-Proceedings of the German Academic Association for Business Research, Halle, Germany.10.1007/978-3-030-29821-0_10 ↗
32. De Jong, C., Kant, G., and Van Vlient, A. (1996). On Finding Minimal Route Duration in the Vehicle Routing Problem with Multiple Time Window, Department of Computer Science, Utrecht University.
33. Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows10.1016/j.cor.2007.02.012 ↗
34. The vehicle routing problem with multiple prioritized time windows: A case study10.1016/j.cie.2015.10.005 ↗
35. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows10.1016/j.cor.2013.08.010 ↗
36. Vehicle routing with roaming delivery locations10.1016/j.trc.2017.04.003 ↗
37. A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations10.1016/j.trb.2017.02.003 ↗
38. An iterative re-optimization framework for the dynamic vehicle routing problem with roaming delivery locations10.1016/j.trb.2019.08.004 ↗
39. The last-mile vehicle routing problem with delivery options10.1007/s00291-021-00633-0 ↗
40. A large neighborhood search approach to the vehicle routing problem with delivery options10.1016/j.trb.2020.11.012 ↗
41. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution10.1016/j.ejor.2017.08.011 ↗
42. Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): Model and implementation using hybrid approach10.1007/s10479-017-2722-x ↗
43. The two-echelon vehicle routing problem with covering options: City logistics with cargo bikes and parcel lockers10.1016/j.cor.2020.104919 ↗
44. Comparing home and parcel lockers’ delivery systems: A math-heuristic approach10.1016/j.trpro.2022.02.012 ↗
45. A Simulated Annealing Algorithm for the Vehicle Routing Problem with Parcel Lockers10.1109/ACCESS.2022.3152062 ↗
46. Flexible parcel delivery to automated parcel lockers: Models, solution methods and analysis10.1007/s13676-019-00144-7 ↗
47. The vehicle routing problem with heterogeneous locker boxes10.1007/s10100-020-00725-2 ↗
48. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows10.1287/trsc.1050.0135 ↗
49. An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics10.1016/j.cor.2012.04.007 ↗
50. A robust optimization approach for the vehicle routing problem with cross-docking under demand uncertainty10.1016/j.tre.2023.103106 ↗
51. The electric fleet size and mix vehicle routing problem with time windows and recharging stations10.1016/j.ejor.2016.01.038 ↗
52. An adaptive large neighborhood search for the location-routing problem with intra-route facilities10.1287/trsc.2017.0746 ↗
53. Routing a mixed fleet of electric and conventional vehicles10.1016/j.ejor.2015.01.049 ↗
54. An Adaptive Large Neighborhood Search for the green mixed fleet vehicle routing problem with realistic energy consumption and partial recharges10.1016/j.asoc.2021.107251 ↗
55. Kindervater, G.A., and Savelsbergh, M.W. (2018). Local Search in Combinatorial Optimization, Princeton University Press.
56. Shaw, P. (1997). A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems, University of Strathclyde.