A literature overview on scheduling electric vehicles in public transport and location planning of the charging infrastructure

Abstract

The Vehicle Scheduling Problem (VSP) is a well-studied combinatorial optimization problem arising for bus companies in public transport. The objective is to cover a given set of timetabled trips by a set of buses at minimum costs. The Electric Vehicle Scheduling Problem (E-VSP) complicates traditional bus scheduling by considering electric buses with limited driving ranges. To compensate these limitations, detours to charging stations become necessary for charging the vehicle batteries during operations. To save costs, the charging stations must be located within the road network in such a way that required deadhead trips are as short as possible or even redundant. For solving the traditional VSP, a variety of solution approaches exist capable of solving even real-world instances with large networks and timetables to optimality. In contrast, the problem complexity increases significantly when considering limited ranges and chargings of the batteries. For this reason, there mainly exist solution approaches for the E-VSP which are based von heuristic procedures as exact methods do not provide solutions within a reasonable time. In this paper, we present a literature review of solution approaches for scheduling electric vehicles in public transport and location planning of charging stations. Since existing work differ in addition to the solution methodology also in the mapping of electric vehicles' technical aspects, we pay particular attention to these characteristics. To conclude, we provide a perspective for potential further research.