2022/07/27 by Marelot de Vos, de Vos, Marelot, Rolf Nelson van Lieshout +2 · 1 citation
Engineering · #Electric Vehicles and Infrastructure #FOS: Mathematics #Optimization and Control (math.OC) #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2207.13734
openalex publication_date 2022/07/27 · openalex created_date 2022/07/30 · openalex updated_date 2026/08/01
This paper considers the scheduling of electric vehicles in a public transit system. Our main innovation is that we take into account that charging stations have limited capacity, while also considering partial charging. To solve the problem, we expand a connection-based network in order to track the state of charge of vehicles and model recharging actions. We then formulate the electric vehicle scheduling problem as a path-based binary program, whose linear relaxation we solve using column generation. We find integer feasible solutions using two heuristics: price-and-branch and truncated column generation, including acceleration strategies. We test the approach using data of the concession Gooi en Vechtstreek in the Netherlands, containing up to 816 trips. The truncated column generation outperforms the other heuristic, and solves the entire concession within 28 hours of computation time with an optimality gap less than 3.5 percent.