Comparison of Optimisation Techniques for the Electric Vehicle Scheduling Problem - Jacques Wüst; Marthinus Johannes Booysen; James Bekker (Smart Cities)
The Electric Vehicle Scheduling Problem (E-VSP) addresses the challenge of efficiently assigning predetermined trips to an electric vehicle fleet while accounting for charging infrastructure and battery range constraints. Despite numerous optimisation approaches proposed in the literature, comparative analyses of these methods remain scarce, with researchers typically focusing on developing novel algorithms rather than evaluating existing algorithms. Moreover, studies often employ convenient assumptions tailored to improve the performance of their optimisation technique. This study presents a comprehensive comparison of several optimisation techniques (mixed integer linear programming (MILP) using the branch-and-cut algorithm, metaheuristics, and heuristics) applied to the E-VSP under identical assumptions and constraints. The techniques are evaluated across multiple metrics, including solution quality, computational efficiency, and implementation complexity. Findings reveal that the branch-and-cut algorithm cannot solve instances with more than 10 trips in a reasonable time. Among metaheuristics, only genetic algorithms and simulated annealing demonstrate competitive performance, but both struggle with instances exceeding 100 trips. Our recently developed heuristic algorithm consistently found better solutions in significantly shorter computation times than the metaheuristics due to its ability to efficiently navigate the solution space while respecting the unique constraints of the E-VSP.