The value of collaborative logistics in the Electric Vehicle Routing Problem with Time Windows and Stochastic Waiting Times

In recent years, there has been a surge in interest in electric vehicles (EVs) driven by environmental concerns, with the aim of reducing greenhouse gas emissions and dependence on non-renewable energy sources. With an increased adoption of EVs, several challanges arise related to their limited driving range, battery capacity and availability of recharging stations. In this work, we face the Electric Vehicle Routing Problem with Time Windows and Stochastic Waiting Times at Recharging Stations, an extension of the well known Electric Vehicle Routing Problem (EVRP) where customers, depot and stations are associated with time windows, and vehicles must wait in queue upon arrival at the recharging stations. We address this problem using a two-stage solution strategy based on Adaptive Large Neighborhood Search, which employs several destroy and repair operators commonly used in the literature. In the first stage, the routes are constructed by considering the expected value of queuing times at recharging stations. In the second stage, the random variables representing queuing times are realized. If the realized waiting time exceeds the expected value, the solution may need to be corrected, potentially skipping some customers. To handle this, two recourse strategies are proposed: the first involves serving each skipped customer with a dedicated vehicle, while the second leverages collaborative logistics to attempt to insert skipped customers into other routes. We conduct experiments on large instances from the literature to compare these two approaches. Finally, we analyze the impact of uncertainty in the problem to determine the number of scenarios needed to accurately represent it.