Public transportation fleet electrification and charger schedule optimization using a decomposition heuristic

Electric bus (E-bus) charging can occur overnight or en route during layovers, with the latter introducing challenges of limited competition for limited-capacity chargers. This paper presents an en route E-bus charging schedule optimization model, incorporating fleet characteristics, bus itinerary time windows, charging capacity and rate limitations, time-varying electricity prices, and partial charging capabilities. The objective function balances maximizing the number of electrified bus blocks with minimizing total charging costs. We develop a decomposition-based heuristic algorithm for large-scale networks with many bus blocks competing for chargers of limited outlet capacity. The decomposition algorithm solves the charging schedule problem for each bus individually and penalizes charger over-utilization, achieving near-optimal solutions more efficiently than exact methods. The model is evaluated using data from the General Transit Feed Specification of bus networks in Toronto, Vancouver, Washington, Manhattan, and the Bay Area. The results demonstrate the ability of the model to shift charging to lower-cost, off-peak hours and optimize charger utilization. Sensitivity analysis identifies battery size and minimum charge levels as critical factors influencing fleet electrification.