Robust planning for bus fleet electrification and charging facility deployment

Electric buses are being increasingly adopted, given their significant environmental advantages. This paper examines the multi-period planning problem for bus fleet electrification and charging facility deployment within an urban bus service network. We first develop a deterministic model aimed at minimizing the sum of investment-related cost and emission-related cost. Subsequently, we depart from the assumption of deterministic bus service frequency and charging demand and account for their uncertainties, and adopt budget uncertainty sets that allow the flexibility to adjust the conservatism level of robust solutions. We then reformulate the robust optimization problem into a tractable mixed-integer linear programming model, which can be solved using existing solvers for smaller-scale problems. For large-scale instances, we design an exact solution approach that integrates Integer Benders decomposition and Lagrangian relaxation methods within a branch-and-cut framework. Compared to existing Integer Benders decomposition methods, our approach yields a tighter subproblem bound. Numerical results reveal an average bound improvement of 10.9%, which effectively reduces the frequency of exact subproblem evaluations by 77.0% on average across various planning horizons. Numerical studies on two Hong Kong bus systems indicate that our method outperforms both the Gurobi solver and heuristic algorithms. For large-scale instances where neither Gurobi nor heuristics can find an optimal solution, our approach consistently reaches optimality in at most 11.04 hours, demonstrating its computational efficiency and scalability for large-scale planning problems.