Electric bus; Fleet management; Genetic algorithm; Mixed-Fleet; Simulated annealing; Urban mobility; Vehicle Scheduling; Integer Linear Programming; Meta-heuristic approach; Mixed integer linear; Mixed-fleet; Small scale; Urban networks; Vehicle scheduling; Computer Science (all); Engineering (all); Management Science and Operations Research
Abstract :
[en] This study addresses the scalability challenges of the Mixed-Fleet Multi-Terminal Electric Bus Scheduling Problem by exploring various heuristic and metaheuristic approaches applied to large urban networks. A novel Repeated Local Search (RLS) algorithm is developed to optimize full-day scheduling, incorporating key factors such as fleet assignment, charging constraints, and deadheading costs, while accounting for limited charging infrastructure. The RLS method generates initial greedy yet feasible schedules for a mixed fleet of electric and hybrid buses, serving as the foundation for two metaheuristic strategies: Simulated Annealing and a Genetic Algorithm. The Simulated Annealing approach is implemented in two variants: one integrating a Mixed-Integer Linear Programming (MILP)-based move, and the other using an RLS-based move to reschedule trip chains while maintaining feasibility. Meanwhile, the Genetic Algorithm employs repair mechanisms to correct infeasible solutions arising during the crossover process. To evaluate these methodologies, a three-phase experimental framework is employed: (1) stress-testing a MILP model under various fleet and infrastructure conditions, (2) benchmarking MILP performance against metaheuristic methods on small-scale instances, and (3) conducting a comparative analysis of metaheuristics across small, medium, and real-size urban scenarios. The urban-scale instances are derived from real-world public transit timetables in Luxembourg City, encompassing 1,084 trips, 12 terminals, 10 bus lines, and full-day operations. Results indicate that the proposed metaheuristic approaches achieve solutions comparable to exact MILP formulations in small-scale cases while offering substantial scalability improvements for larger networks. Each algorithm exhibits distinct advantages and trade-offs, highlighting the importance of selecting an appropriate method based on the specific scenario and computational constraints. These findings extend prior research on smaller instances and suggest that as urban transit systems transition to electric fleets, the marginal operational benefits for transit agencies may diminish with increasing network size.
Disciplines :
Engineering, computing & technology: Multidisciplinary, general & others
Author, co-author :
BOSI, Tommaso ; University of Luxembourg ; Department of Civil, Computer Science and Aeronautical Technologies Engineering, Roma Tre University, Rome, Italy ; Department of Transport & Planning, Delft University of Technology, Delft, Netherlands
RINALDI, Marco ; University of Luxembourg > Faculty of Science, Technology and Medicine > Department of Engineering > Team Francesco VITI ; Department of Civil, Computer Science and Aeronautical Technologies Engineering, Roma Tre University, Rome, Italy ; Department of Transport & Planning, Delft University of Technology, Delft, Netherlands
D'Ariano, Andrea; Department of Civil, Computer Science and Aeronautical Technologies Engineering, Roma Tre University, Rome, Italy ; Department of Transport & Planning, Delft University of Technology, Delft, Netherlands ; Faculty of Science, Technology and Medicine (FSTM), University of Luxembourg, Esch-Sur-Alzette, Luxembourg
VITI, Francesco ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Engineering (DoE) ; Department of Civil, Computer Science and Aeronautical Technologies Engineering, Roma Tre University, Rome, Italy ; Department of Transport & Planning, Delft University of Technology, Delft, Netherlands
External co-authors :
yes
Language :
English
Title :
Metaheuristic optimization for scheduling mixed-fleet electric buses in a practical urban network
European Environment Agency, “Greenhouse gas emissions from transport in Europe,” 2022.
Pelletier, S., Jabali, O., Mendoza, J.E., Laporte, G., The electric bus fleet transition problem. Transportation Research Part C: Emerging Technologies 109 (Dec. 2019), 174–193.
International Energy Agency, “Global EV Outlook 2023 - Catching up with climate ambitions,” 2023.
D. Jefferies and D. Göhlich, “A Comprehensive TCO Evaluation Method for Electric Bus Systems Based on Discrete-Event Simulation Including Bus Scheduling and Charging Infrastructure Optimisation,” World Electric Vehicle Journal, vol. 11, no. 3, 2020.
Hall, D., Lutsey, N., Electric Vehicle Charging Guide for Cities. International Council on Clean Transportation, 2020.
Amiri, A., Amin, S.H., Zolfagharinia, H., A bi-objective green vehicle routing problem with a mixed fleet of conventional and electric trucks: Considering charging power and density of stations. Expert Systems with Applications, 213, 2023, 119228.
Y. Feng, A. (Avi) Ceder, S. Zhang, and Z. Cao, “Bus routing fine-tuning for integrated network-based demand and bus bridging for a disrupted railway system,” Expert Systems With Applications vol. 242, p. 122825, May 2024.
Fei, F., Sun, W., Iacobucci, R., Schmöcker, J.-D., Exploring the profitability of using electric bus fleets for transport and power grid services. Transportation Research Part C: Emerging Technologies, 149, 2023, 104060.
Noel, L., Mccormack, R., A cost benefit analysis of a V2G-capable electric school bus compared to a traditional diesel school bus. Applied Energy 126 (2014), 246–255.
Ceder, A., Public Transit Planning and operation. 2016, CRC Press.
A. Costa, I. Branco, and J. M. Pinto Paixão, “Vehicle Scheduling Problem with Multiple Type of Vehicles and a Single Depot,” in Computer-Aided Transit Scheduling, J. R. Daduna, I. Branco, and J. M. P. Paixão, Eds., Berlin, Heidelberg: Springer Berlin Heidelberg, 1995, pp. 115–129.
Picarelli, E., Rinaldi, M., D'Ariano, A., Viti, F., Model and solution methods for the mixed-fleet multi-terminal bus scheduling problem. Transportation Research Procedia 47 (2020), 275–282.
Rinaldi, M., Picarelli, E., D'Ariano, A., Viti, F., Mixed-fleet single-terminal bus scheduling problem: Modelling, solution scheme and potential applications. Omega (Westport), 96, 2020, 102070.
Perumal, S.S.G., Lusby, R.M., Larsen, J., Electric bus planning & scheduling: A review of related problems and methodologies. European Journal of Operational Research 301:2 (2022), 395–413.
Ibarra-Rojas, O.J., Delgado, F., Giesen, R., Muñoz, J.C., Planning, operation, and control of bus transport systems: A literature review. Transportation Research Part B: Methodological 77 (Jul. 2015), 38–75.
Shang, H., Liu, Y., Wu, W., Zhao, F., Multi-depot vehicle scheduling with multiple vehicle types on overlapped bus routes. Expert Systems with Applications, 228, Oct. 2023, 120352.
Gintner, V., Kliewer, N., Suhl, L., Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice. OR Spectrum 27:4 (Aug. 2005), 507–523.
Kliewer, N., Mellouli, T., Suhl, L., A time–space network based exact optimization model for multi-depot bus scheduling. European Journal of Operational Research 175:3 (Dec. 2006), 1616–1627.
Pepin, A.-S., Desaulniers, G., Hertz, A., Huisman, D., A comparison of five heuristics for the multiple depot vehicle scheduling problem. Journal of Scheduling 12:1 (Feb. 2009), 17–30.
Marín Moreno, C.A., Escobar Falcón, L.M., Bolaños, R.I., Subramanian, A., Escobar Zuluaga, A.H., Granada Echeverri, M., A hybrid algorithm for the multi-depot vehicle scheduling problem arising in public transportation. International Journal of Industrial Engineering Computations, 2019, 361–374.
Chao, Z., Xiaohong, C., Optimizing Battery Electric Bus Transit Vehicle Scheduling with Battery Exchanging: Model and Case Study. Procedia-Social and Behavioral Sciences 96 (2013), 2725–2736.
J. Reuer, N. Kliewer, and L. Wolbeck, “The Electric Vehicle Scheduling Problem - A study on time-space network based and heuristic solution approaches,” Conference on Advanced Systems in Public Transport 2015 - CASPT, 2015.
Van Kooten Niekerk, M.E., van den Akker, J.M., Hoogeveen, J.A., Scheduling electric vehicles. Public Transport 9:1–2 (2017), 155–176.
Rogge, M., van der Hurk, E., Larsen, A., Sauer, D.U., Electric bus fleet size and mix problem with optimization of charging infrastructure. Applied Energy 211 (Feb. 2018), 282–295.
Liu, T., Ceder, A., Battery-electric transit vehicle scheduling with optimal number of stationary chargers. Transportation Research Part C: Emerging Technologies 114 (May 2020), 118–139.
Olsen, N., Kliewer, N., Wolbeck, L., A study on flow decomposition methods for scheduling of electric buses in public transport based on aggregated time–space network models. Cent Eur J Oper Res 30:3 (Sep. 2022), 883–919.
Zhou, G.-J., Xie, D.-F., Zhao, X.-M., Lu, C., Collaborative Optimization of Vehicle and Charging Scheduling for a Bus Fleet mixed with Electric and Traditional Buses. IEEE Access 8 (2020), 8056–8072.
Wang, C., Guo, C., Zuo, X., Solving multi-depot electric vehicle scheduling problem by column generation and genetic algorithm. Applied Soft Computing, 112, 2021, 107774.
Perumal, S.S.G., Dollevoet, T., Huisman, D., Lusby, R.M., Larsen, J., Riis, M., Solution approaches for integrated vehicle and crew scheduling with electric buses. Computers and Operations Research, 132, Aug. 2021, 105268.
Sistig, H.M., Sauer, D.U., Metaheuristic for the integrated electric vehicle and crew scheduling problem. Applied Energy, 339, Jun. 2023, 120915.
Parmentier, A., Martinelli, R., Vidal, T., Electric vehicle fleets: scalable route and recharge scheduling through column generation. Transportation Science 57:3 (May 2023), 631–646.
Zhou, Y., Meng, Q., Ong, G.P., Wang, H., Electric bus charging scheduling on a bus network. Transportation Research Part C: Emerging Technologies, 161, Apr. 2024, 104553.
Fusco, G., Alessandrini, A., Colombaroni, C., Valentini, M.P., A Model for Transit Design with Choice of Electric Charging System. Procedia-Social and Behavioral Sciences 87 (Oct. 2013), 234–249.
Xylia, M., et al. Impact of bus electrification on carbon emissions: The case of Stockholm. Journal of Cleaner Production 209 (Feb. 2019), 74–87.
Lajunen, A., Energy consumption and cost-benefit analysis of hybrid and electric city buses. Transportation Research Part C: Emerging Technologies 38 (Jan. 2014), 1–15.
Goeke, D., Schneider, M., Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research 245:1 (Aug. 2015), 81–99.
Feng, W., Figliozzi, M., An economic and technological analysis of the key factors affecting the competitiveness of electric commercial vehicles: A case study from the USA market. Transportation Research Part C: Emerging Technologies 26 (Jan. 2013), 135–145.
Bektaş, T., Ehmke, J.F., Psaraftis, H.N., Puchinger, J., The role of operational research in green freight transportation. European Journal of Operational Research 274:3 (May 2019), 807–823.
Steward, D., “Critical elements of vehicle-toGrid (V2G) Economics,” Report National Renewable Energy. The Laboratory, 2017.
J. A. Manzolli, J. P. F. Trovão, and C. Henggeler Antunes, “Electric bus coordinated charging strategy considering V2G and battery degradation,” Energy, vol. 254, p. 124252, Sep. 2022.
Thingvad, A., Calearo, L., Andersen, P.B., Marinelli, M., Empirical capacity measurements of electric vehicles subject to battery degradation from V2G services. IEEE Transactions on Vehicular Technology 70:8 (2021), 7547–7557.
Li, J.Q., Transit bus scheduling with limited energy. Transportation Science 48:4 (2014), 521–539.
Zhang, M., Yang, M., Li, Y., Huang, S., Optimization of electric bus scheduling considering charging station resource constraints. Transportation Research Record: Journal of the Transportation Research Board 2678:3 (2024), 13–23.
Jovanovic, R., Bayhan, S., Voß, S., “Matheuristic Fixed Set Search Applied to Electric Bus Fleet Scheduling,” in Learning and Intelligent. Optimization, 2023, 393–407.
Vendé, P., Desaulniers, G., Kergosien, Y., Mendoza, J.E., Matheuristics for a multi-day electric bus assignment and overnight recharge scheduling problem. Transportation Research Part C: Emerging Technologies, 156, 2023, 104360.
Yao, E., Liu, T., Lu, T., Yang, Y., Optimization of electric vehicle scheduling with multiple vehicle types in public transport. Sustainable Cities and Society, 52, Jan. 2020, 101862.
Kost, V., Merakou, M., Gkiotsalitis, K., Electric Bus Scheduling Problem with Time Windows and Stochastic Travel Times. Information, 16(5), Apr. 2025, 376.
Eglese, R.W., Simulated annealing: A tool for operational research. European Journal of Operational Research 46:3 (1990), 271–281.
Ciancio, C., Laganà, D., Musmanno, R., Santoro, F., An integrated algorithm for shift scheduling problems for local public transport companies. Omega (Westport) 75 (2018), 139–153.
Nourani, Y., Andresen, B., A comparison of simulated annealing cooling strategies. Journal of Physics A: Mathematical and General 31:41 (Oct. 1998), 8373–8385.
