Challenges in designing a sustainable last-mile delivery network encompass the aims of minimizing total logistics costs and satisfying customer satisfaction as well as mitigating negative environmental impacts. These challenges are tackled by implementing electric vehicles (EVs) and integrating covering locations in the last-mile delivery networks. These locations are equipped with parcel lockers to serve customers and charging stations for recharging EV's batteries within their trips. With the availability of parcel lockers, customers have the option to pick up their parcels independently, called self-pickup service. As a result, we investigate two delivery options (i.e., attended home delivery and self-pickup service) in the electric vehicle routing problem with time windows and partial recharges (EVRPTW-PR) - namely, the electric vehicle routing problem with time windows, partial recharges, and covering locations (EVRPTW-PR-CL). This research aims to optimize routing plans for EVRPTW-PR-CL using a homogeneous fleet of EVs and leveraging covering locations (CLs). We also derive a comprehensive objective function that seeks to minimize overall costs consisting of travel costs, fixed costs for used EVs, fixed costs for used CLs, and compensation costs associated with the self-up service. EVRPTW-PR-CL is formally modeled as a mixed-integer programming formulation and we assess its feasibility through a commercial solver (i.e., GUROBI). Moreover, an effective variable neighborhood search (VNS) algorithm is developed to solve both EVRPTW-PR and EVRPTW-PR-CL. This algorithm combines the framework of VNS with a set partitioning (SP) formulation and a dynamic programming procedure to optimally insert charging stations. Finally, managerial insights are provided related to the investigation of delivery options and the effects of compensation cost, which can support decision-makers in devising sustainable and cost-effective last-mile delivery networks.

Beheshti, A. K., Hejazi, S. R., and Alinaghian, M. (2015). The vehicle routing problem with multiple prioritized time windows: A case study. Computers & Industrial Engineering, 90:402–413.
Bezerra, S. N., de Souza, S. R., and Souza, M. J. F. (2023). A general vns for the multidepot open vehicle routing problem with time windows. Optimization Letters, pages 1–31.
Boysen, N., Fedtke, S., and Schwerdfeger, S. (2021). Last-mile delivery concepts: a survey from an operational research perspective. OR Spectrum, 43:1–58.
Brimberg, J., Salhi, S., Todosijević, R., and Urošević, D. (2023). Variable neighborhood search: The power of change and simplicity. Computers & Operations Research, 155:106221.
Cantillo, V., Amaya, J., Serrano, I., Cantillo-García, V., and Galván, J. (2022). Influencing factors of trucking companies willingness to shift to alternative fuel vehicles. Transportation Research Part E: Logistics and Transportation Review, 163:102753.
Çatay, B. and Sadati, İ. (2023). An improved matheuristic for solving the electric vehicle routing problem with time windows and synchronized mobile charging/battery swapping. Computers & Operations Research, page 106310.
Conrad, R. G. and Figliozzi, M. A. (2011). The recharging vehicle routing problem. In Proceedings of the 2011 industrial engineering research conference, volume 8. IISE Norcross, GA.
Cortés-Murcia, D. L., Prodhon, C., and Afsar, H. M. (2019). The electric vehicle routing problem with time windows, partial recharges and satellite customers. Transportation Research Part E: Logistics and Transportation Review, 130:184–206.
de Jong, C., Kant, G., and Van Vlient, A. (1996). On finding minimal route duration in the vehicle routing problem with multiple time windows. Manuscript, Department of Computer Science, Utrecht University, Holland.
de Mello Bandeira, R. A., Goes, G. V., Gonçalves, D. N. S., Márcio de Almeida, D., and de Oliveira, C. M. (2019). Electric vehicles in the last mile of urban freight transportation: A sustainability assessment of postal deliveries in rio de janeiro-brazil. Transportation Research Part D: Transport and Environment, 67:491–502.
Desaulniers, G., Errico, F., Irnich, S., and Schneider, M. (2016). Exact algorithms for electric
vehicle-routing problems with time windows. Operations Research, 64(6):1388–1405.
Deutsch, Y. and Golany, B. (2018). A parcel locker network as a solution to the logistics last mile problem. International Journal of Production Research, 56(1-2):251–261.
Doerner, K. F., Gronalt, M., Hartl, R. F., Kiechle, G., and Reimann, M. (2008). Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows. Computers & Operations Research, 35(9):3034–3048.
Drexl, M. and Schneider, M. (2015). A survey of variants and extensions of the location routing problem. European journal of operational research, 241(2):283–308.
Dumez, D., Lehuédé, F., and Péton, O. (2021). A large neighborhood search approach to the vehicle routing problem with delivery options. Transportation Research Part B: Methodological, 144:103–132.
Enthoven, D. L., Jargalsaikhan, B., Roodbergen, K. J., Uit het Broek, M. A., and Schrotenboer, A. H. (2020). The two-echelon vehicle routing problem with covering options: City logistics with cargo bikes and parcel lockers. Computers & Operations Research, 118:104919.
Erdelić, T. and Carić, T. (2019). A survey on the electric vehicle routing problem: variants and solution approaches. Journal of Advanced Transportation, 2019.
Erdelić, T. and Carić, T. (2022). Goods delivery with electric vehicles: Electric vehicle routing optimization with time windows and partial or full recharge. Energies, 15(1):285.
Forum, W. E. (2020). The future of the last-mile ecosystem. Technical report.
Foster, B. A. and Ryan, D. M. (1976). An integer programming approach to the vehicle scheduling problem. Journal of the Operational Research Society, 27:367–384.
Froger, A., Jabali, O., Mendoza, J. E., and Laporte, G. (2022). The electric vehicle routing problem with capacitated charging stations. Transportation Science, 56(2):460–482.
Gevaers, R., Van de Voorde, E., Vanelslander, T., et al. (2009). Characteristics of innovations in last-mile logistics-using best practices, case studies and making the link with green and sustainable logistics. Association for European Transport and contributors, 1:21.
Goeke, D. and Schneider, M. (2015). Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research, 245(1):81–99.
Grabenschweiger, J., Doerner, K. F., Hartl, R. F., and Savelsbergh, M. W. (2021). The vehicle routing problem with heterogeneous locker boxes. Central European Journal of Operations Research, 29:113–142.
Hiermann, G., Hartl, R. F., Puchinger, J., and Vidal, T. (2019). Routing a mix of conventional, plug-in hybrid, and electric vehicles. European Journal of Operational Research, 272(1):235–248.
Keskin, M. and Çatay, B. (2016). Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies, 65:111–127.
Keskin, M. and Çatay, B. (2018). A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. Computers & Operations research, 100:172–188.
Keskin, M., Laporte, G., and Çatay, B. (2019). Electric vehicle routing problem with time-dependent waiting times at recharging stations. Computers & Operations Research, 107:77–94.
Kiniulis, M. (2022). 9 mind-blowing worldwide ecommerce statistics. Technical report.
Liu, Z., Zuo, X., Zhou, M., Guan, W., and Al-Turki, Y. (2023). Electric vehicle routing problem with variable vehicle speed and soft time windows for perishable product delivery. IEEE Transactions on Intelligent Transportation Systems.
Lu, J., Chen, Y., Hao, J.-K., and He, R. (2020). The time-dependent electric vehicle routing problem: Model and solution. Expert Systems with Applications, 161:113593.
Mladenović, N. and Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11):1097–1100.
Montoya, A., Guéret, C., Mendoza, J. E., and Villegas, J. G. (2017). The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B: Methodological, 103:87–110.
Orenstein, I., Raviv, T., and Sadan, E. (2019). Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis. EURO Journal on Transportation and Logistics, 8(5):683–711.
Ozbaygin, G., Karasan, O. E., Savelsbergh, M., and Yaman, H. (2017). A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations. Transportation Research Part B: Methodological, 100:115–137.
Ozbaygin, G. and Savelsbergh, M. (2019). An iterative re-optimization framework for the dynamic vehicle routing problem with roaming delivery locations. Transportation Research Part B: Methodological, 128:207–235.
Rastani, S. and Çatay, B. (2021). A large neighborhood search-based matheuristic for the load-dependent electric vehicle routing problem with time windows. Annals of Operations Research, pages 1–33.
Reyes, D., Savelsbergh, M., and Toriello, A. (2017). Vehicle routing with roaming delivery locations. Transportation Research Part C: Emerging Technologies, 80:71–91.
Sadati, M. E. H., Akbari, V., and Çatay, B. (2022). Electric vehicle routing problem with flexible deliveries. International Journal of Production Research, 60(13):4268–4294.
Schiffer, M. and Walther, G. (2018). An adaptive large neighborhood search for the location-routing problem with intra-route facilities. Transportation Science, 52(2):331–352.
Schneider, M., Stenger, A., and Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation science, 48(4):500–520.
Statista (2022). Retail e-commerce sales worldwide from 2014 to 2026. Technical report.
Subramanian, A., Drummond, L. M., Bentes, C., Ochi, L. S., and Farias, R. (2010). A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 37(11):1899–1911.
Tilk, C., Olkis, K., and Irnich, S. (2021). The last-mile vehicle routing problem with delivery options. OR spectrum, 43(4):877–904.
UNCTAD (2017). Unctad framework for sustainable freight transport. Technical report.
Vukićević, M., Ratli, M., Rivenq, A., and Zrikem, M. (2023). Covering delivery problem with electric vehicle and parcel lockers: Variable neighborhood search approach. Computers & Operations Research, 157:106263.
Yu, V. F., Anh, P. T., and Baldacci, R. (2023a). A robust optimization approach for the vehicle routing problem with cross-docking under demand uncertainty. Transportation Research Part E: Logistics and Transportation Review, 173:103106.
Yu, V. F., Anh, P. T., and Chen, Y.-W. (2023b). The electric vehicle routing problem with time windows, partial recharges, and parcel lockers. Applied Sciences, 13(16):9190.
Yu, V. F., Anh, P. T., Gunawan, A., and Han, H. (2023c). A simulated annealing with variable neighborhood descent approach for the heterogeneous fleet vehicle routing problem with multiple forward/reverse cross-docks. Expert Systems with Applications, page 121631.
Zhou, L., Baldacci, R., Vigo, D., and Wang, X. (2018). A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution. European Journal of Operational Research, 265(2):765–778.