Metaheuristic optimization for scheduling mixed-fleet electric buses in a practical urban network

Abstract

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.