Optimising EV Fleet Charging Coordination by Column Generation

Sammanfattning

The number of electric vehicles (EVs) operating in the European transport sector is expected to increase in the coming years. While transport electrification offers both economic and environmental benefits, a growing number of EVs also comes with new challenges. One such example is charging demand that exceeds the capacity of available infrastructure, leading to congestions at charging points. The aim of this thesis is to formulate and evaluate a column generation (CG) approach as a solution method for minimizing congestion at chargers, while meeting the energy needs of each EV. The method iteratively solves a restricted version of the problem and dynamically generates new columns, corresponding to EV charging decisions, that have the potential to improve the overall solution. The proposed solution method successfully solves most of the tested instances to either optimality or near-optimality, with small optimality gaps. All obtained solutions are feasible and satisfy the integrality requirements of the original problem, eliminating the need for additional algorithmic components, such as branch-and-price. For larger instances, the imposed time limit (50 minutes) may terminate the solution process before a feasible solution is found. Furthermore, the results indicate that more granularity in time and charging level discretization leads to improved route durations, albeit at the cost of increased computation times. Charger coordination resulting from the presented CG solver effectively reduces congestions at charging points.