Multi-Day Scheduling for Electric Vehicle Routing: A Novel Model and Comparison Of Metaheuristics

Abstract

The increasing use of electric vehicles (EVs) requires efficient route planning solutions that take into account the limited range of EVs and the associated charging times, as well as the different types of charging stations. In this work, we model and solve an electric vehicle routing problem (EVRP) designed for a cross-platform navigation system for individual transport. The aim is to provide users with an efficient route for their daily appointments and to reduce possible inconveniences caused by charging their EV. Based on these assumptions, we propose a multi-day model in the form of a mixed integer programming (MIP) problem that takes into account the vehicle's battery capacity and the time windows of user's appointments. The model is solved using various established metaheuristics, including tabu search (TS), adaptive large neighborhood search (ALNS), and ant colony optimization (ACO). Furthermore, the performance of the individual approaches is analyzed using generated ensembles to estimate their behavior in reality and is compared with the exact results of the Google OR-Tools solver.