On the joint optimization of charging stations location, electric bus routing and charging scheduling

Objectives. When replacing a fleet of diesel buses with a fleet of electric buses, the problem of planning the fleet composition, charging infrastructure oriented towards fast recharging at route terminals, and electric bus charging schedules is relevant. The purpose of the study is to develop models and methods for elaboration of cost-effective solutions for selecting a fleet of electric buses, charging infrastructure of this type, taking into  account a number of specific conditions. The functioning of the fleet and charging infrastructure is modeled for route terminals during the most representative period of the day, characterized by the highest passenger flow intensity and maximum energy consumption.

Methods. Methods of set theory, graph theory and mathematical programing are used. 

Results. A mathematical model has been developed for the optimization problem of a homogeneous electric bus fleet, assignment of service trips to electric buses, location and quantity of fast charging stations at route terminals, and a schedule for charging electric buses on them. The total daily cost of electric buses, charging stations, and consumed electricity has been selected as the objective function. A two-level decomposition scheme for solving the problem has been proposed, at the upper level of which the assignment of electric buses to service trips from a given set is selected, and at the lower level, the infrastructure of homogeneous charging stations of terminals and the charging schedules of electric buses on them are determined with a fixed  assignment of service trips to electric buses. A heuristic randomized algorithm has been proposed to solve the upper-level subproblem, and a mixed integer linear programming model has been developed for the lower-level subproblem.

Conclusion. The solution to the upper-level subproblem consists of selecting the assignment of electric buses to service trips from a given set. Standard solvers such as IBM ILOG CPLEX, Gurobi Optimizer can be used to solve the formulated lower-level subproblem. 

1. Dirks N., Schiffer M., Walther G. On the integration of battery electric buses into urban bus networks. Transportation Research Part C: Emerging Technologies, 2022, vol. 139, р. 103628. DOI: 10.1016/j.trc.2022.103628.

2. Gao Z., Lin Z., LaClair T. J., Liu C., Li J.-M., …, Ward J. Battery capacity and recharging needs for electric buses in city transit service. Energy, 2017, vol. 122, pp. 588-600.

3. Olsson O., Grauers A., Pettersson S. Method to analyze cost effectiveness of different electric bus systems. EVS29 International Battery, Hybrid and Fuel Cell Electric Vehicle Symposium, Montreal, Quebec, Canada, June 2016, pp. 1-12.

4. Guschinsky N., Kovalyov M. Y., Rozin B., Brauner N. Fleet and charging infrastructure decisions for fastcharging city electric bus service. Computers and Operations Research, 2021, vol. 135, р. 105449. DOI: 10.1016/j.cor.2021.105449.

5. Battaïa O., Dolgui A., Guschinsky N., Kovalev M. Y. Designing fast-charge urban electric bus services: An Integer Linear Programming model. Transportation Research Part E: Logistics and Transportation Review, 2023, vol. 171, р. 103065. DOI: 10.1016/j.tre.2023.103065.

6. Nath R. B., Rambha T., Schiffer M. On the impact of co-optimizing station locations, trip assignment, and charging schedules for electric buses. Transportation Research Part C: Emerging Technologies, 2024, vol. 167, р. 104839.

7. Quttineh N.-H., Häll C. H., Ekström E. J., Ceder A. Integrated solution for electric bus timetabling and vehicle scheduling combined with choices of charging locations. Journal of Public Transportation, 2023, vol. 25, р. 100055.

8. Alvo M., Angulo G., Klapp M. A. An exact solution approach for an electric bus dispatch problem. Transportation Research Part E: Logistics and Transportation Review, 2021, vol. 156, р. 102528.