An Adapted Iterated Greedy Algorithm for The Electric Vehicle Routing Problem with Time Windows, Partial Recharges, and Parcel Lockers

The rapid growth of e-commerce has challenged urban logistics and sustainability due to the surge in delivery services. The Electric Vehicle Routing Problem with Time Windows, Partial Recharges, and Parcel Lockers integrates important characteristics of sustainable last-mile delivery operations, such as electric vehicles and alternative delivery locations through parcel lockers. The objective is to minimize the total distance traveled by a fleet of homogeneous EVs serving a set of customers while starting and ending the route at a depot. To this end, we developed an Iterated Greedy algorithm with Random Variable Neighborhood Descent (IG-RVND). We conducted computational experiments on 92 benchmark instances and compared the results with those from the literature. IG-RVND achieved the best solution in 80 instances, with an average gap of -1.85\%. The algorithm proved highly efficient with runtimes four times faster than those reported in the literature while reducing the required fleet size for large instances.