The Electric Vehicle Routing Problem with Time Windows, Partial Recharges, and Parcel Lockers

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.

Keywords

• electric vehicle
• routing problem
• partial recharging
• parcel locker
• adaptive large neighborhood search