The COVID-19 pandemic accelerated the adoption of e-commerce as consumers turned to online shopping to reduce infection risk. This surge has intensified last-mile delivery challenges, which is the most expensive and time-sensitive stage of logistics. Parcel lockers have emerged as a promising solution by providing contactless 24-hour pickup, reducing failed deliveries, and enhancing flexibility. At the same time, electric vehicles (EVs) are being deployed to support sustainable logistics, though their efficiency remains constrained by limited battery capacity, charging requirements, and fluctuating traffic conditions.

To overcome these real-world complexities, this study investigates the Time-Dependent Electric Vehicle Routing Problem with Time Windows and Parcel Lockers (TD-EVRPTWPL). The problem addresses package deliveries carried out by EVs, either directly to customers’ homes or via parcel lockers, while considering time windows, partial recharge, and energy consumption affected by time-dependent speeds. A mathematical programming model is formulated and a dataset is generated for this problem. The model is solved using CPLEX and a Simulated Annealing (SA) algorithm. Computational experiments show that SA consistently yields high-quality and robust solutions, demontrating its effectiveness in solving this challenging routing problem.