A Threshold Recourse Policy for the Electric Vehicle Routing Problem with Stochastic Energy Consumption

The Electric Vehicle Routing Problem (EVRP) aims at routing Electric Vehicles (EVs) while planning their stops at Charging Stations (CSs), due to the limited autonomy of their batteries. The majority of studies on the EVRP and its variants have considered deterministic energy consumption. However, energy consumption is subject to a great deal of uncertainty, which if ignored can lead the EV to run out of battery mid-route. In this paper, we develop a two-stage stochastic programming formulation for the electric vehicle routing problem with stochastic energy consumption. In particular, we propose a threshold recourse policy which entails that the EV will head to a charging station after a certain energy level is reached. We show the added value of the extensive formulation of our model on a set of small instances derived from the deterministic literature.