A Heuristic for the Electric Vehicle Routing Problem with Time Windows and Stochastic Waiting Times

Logistics is one of the greatest sources of pollution. For this reason, electric vehicles for pick up and deliveries are starting to be common. In the last mile setting, the management of these vehicles is not a big challenge since batteries have enough charge to cover the entire day of usage. Nevertheless, in the mid-haul setting, the distances to be covered in a single working day are usually more than the vehicle's capability over a single charge, therefore a recharging stop is required. This paves the way for the application of optimization methods. In this context, we consider the Electric Vehicle Routing Problem for defining the planning of a series of pick-ups spatially distributed so that the vehicles may need a recharge at a station. The proposed solution methodology uses an Adaptive Large Neighborhood Search in which the first stage aims at destroying and repairing the solution using the expected waiting time at the stations. The second stage uses the realized waiting time which could lead to customers' demand being violated, whereby a recourse operation rectifies the broken solution by sending a new vehicle to the interested node. This is where the proposed heuristic comes in, which aims at improving horizontally on the consolidated methodologies of the literature. More specifically it strives to give alternative operators to the recourse step, considering other realistic situations that the operations would find themselves in. The alternative recourse strategies provide an exchange of the customer needs between vehicles and the possibility of trying to recharge less at a station to still be able to serve without violating the customer's demand.