Clustering heuristics for Stochastic Energy Capacitated Vehicle Routing Problem (ECVRP)

This paper presents an approach to solving the Stochastic Energy Capacitated Vehicle Routing Problem (SECVRP), focusing on electric vehicles and their limited battery capacity. A finite number of customers, each with their demand, must be serviced by an electric vehicle fleet while ensuring that none of the vehicles run out of energy. The time and energy required to travel between two points are modelled as a random variable with a known distribution. We present a Mixed Integer Program (MIP) for computing an exact solution and introduce clustering heuristics to improve the computation times. This enables efficient route re-planning in dynamic scenarios. The methodology transforms the SECVRP into smaller problems, yielding high-quality solutions quickly compared to existing methods. We demonstrate the effectiveness of this approach using a well-known benchmark problem sets as well as a set of randomly generated problems.