  Transit agencies that operate battery-electric buses must carefully manage
fast-charging infrastructure to extend daily bus range without degrading
on-time performance. To support this need, we propose a mixed-integer linear
programming model to schedule opportunity charging that minimizes the amount of
departure delay in all trips served by electric buses. Our novel approach
directly tracks queuing at chargers in order to set and propagate departure
delays. Allowing but minimizing delays makes it possible to optimize
performance when delays due to traffic conditions and charging needs are
inevitable, in contrast with existing methods that require charging to occur
during scheduled layover time. To solve the model, we develop two algorithms
based on decomposition. The first is an exact solution method based on
Combinatorial Benders (CB) decomposition, which avoids directly enumerating the
model's logic-based "big M" constraints and their inevitable computational
challenges. The second, inspired by the CB approach but more efficient, is a
polynomial-time heuristic based on linear programming that we call 3S.
Computational experiments on both a simple notional transit network and the
real bus system of King County, Washington, USA demonstrate the performance of
both methods. The 3S method appears particularly promising for creating good
charging schedules quickly at real-world scale.
