Mixing decomposition techniques and approximate dynamic programming for the Stochastic Electric Vehicle Routing Problem

This work addresses the Electric Vehicle Routing Problem with Time Windows (E-VRPTW), incorporating stochastic consumption and travel times due to possible uncertainties in road conditions and unforeseen events. Unlike traditional approaches that assume deterministic variables, this study formulates a more realistic version of the E-VRPTW, where both energy consumption and travel times are subject to fluctuations. Furthermore, the problem is complicated by the need for electric vehicles (EVs) to recharge at stations en-route, given their limited driving range. In order to address this complexity, a solution methodology combining Approximate Dynamic Programming (ADP) and Column Generation (CG) is proposed. The ADP agents are created to optimize energy consumption and time management while accounting for factors such as partial recharging and the dynamic state of charge (SOC) of the vehicles. Different approaches for representing the value function, including full discretization and approximation via interpolators, are compared in terms of solution accuracy and computational efficiency. Many tests are then conducted on instances of increasing size and complexity, in order to evaluate the overall performance of this approach. The results are able to demonstrate that the proposed solution can effectively handle uncertainty, reducing total costs while maintaining adherence to the various constraints.