Location Planning of Charging Stations for Electric Buses in Public Transport Considering Vehicle Scheduling: A Variable Neighborhood Search Based Approach

Many public transport companies have recently launched projects testing the operation of electric buses. Progressively, traditional combustion engine buses are being replaced by electric buses. In such cases, some stops on bus lines are equipped with charging technology. Combustion engine buses can operate for an entire day without having to refuel. By contrast, electric buses have considerably shorter ranges and need to recharge their batteries throughout a day. For cost-efficient use of electric buses, charging stations must be located within the road network so that required deadhead trips are as short as possible, but attention must also be paid to construction costs. In contrast to vehicle scheduling, which is a more short-term planning task of public transport companies, location planning of charging stations is a long-term planning problem and requires a simultaneous solving of both optimization problems. Specifically, location planning and vehicle scheduling have to be considered simultaneously in order to open up optimization potentials by comparison to sequential planning, since locations of charging stations directly influence the resulting vehicle rotations. To this purpose, we present a novel solution method for the simultaneous optimization of location planning of charging stations and vehicle scheduling for electric buses in public transport, using variable neighborhood search. By a computational study using real-world public transport data, we show that a simultaneous consideration of both problems is necessary because sequential planning generally leads to either infeasible vehicle rotations or to significant increases in costs. This is especially relevant for public transport companies that start operating electric bus fleets.