Dynamic adjustment strategy of electric bus operations: A spatial branch-and-bound method with acceleration techniques

Electric bus systems frequently encounter operational instability, resulting in delays, bunching and disturbed charging schemes. Advanced technologies like sensoring and wireless connectivity strongly support dynamic adjustments to improve the stability of electric bus systems, fostering flexibility responsiveness to changing operating conditions. This article explores the dynamic adjustment problem of electric bus operations to jointly generate bus charging schemes and timetable adjustments in a real-time decision-making process. We propose a mixed-integer nonlinear programming model for each decision stage, explicitly considering factors such as vehicle overtaking, passenger load, capacity limitations, and charging behaviors. To efficiently solve this problem, we design a spatial branch-and-bound method with multiple acceleration techniques of logical inference for bound contraction, bilinear-specific branching, and parallel computation. Indeed, the original mixed-integer nonlinear programming problem can be split into a series of mixed-integer quadratic programming problems with reduced domains. The acceleration techniques proposed could be easily customized to address other mixed-integer nonlinear programs in such branch-and-bound-based schemes. Computational experiments validate the effectiveness of the proposed adjustment strategy yielding feasible solutions that enhance headway regularity, energy savings and service quality. Additionally, our solution method efficiently tackles real-world scenarios of significant complexity, with up to 12 vehicles running 8 loops on a route comprising 54 stops, with an average of 5.11-seconds computational time, outperforming both the common commercial solver and standard spatial branch-and-bound approaches in computational speed.