Optimal electric bus fleet scheduling considering battery degradation and non-linear charging profile

This study aims to determine the battery electric bus service and charging strategy to minimize the total operational cost of transit system, where the cost incurred by battery degradation and non-linear charging profile is taken into account. We formulate a set partitioning model for this problem, subject to predefined trip schedule and limited charging facilities. A tailored branch-and-price approach is then proposed to find the global optimal solution. In particular, we develop an effective multi-label correcting method to deal with the pricing problem (i.e., generating columns) in column generation procedure within the branch-and-price framework, coupled with a dual stabilization technique with an aim to accelerate the convergence rate. Meanwhile, a branch-and-bound solution approach is adopted to guarantee optimal integer solutions. Numerical experiments and a case study arising from real transit network are conducted to further assess the efficiency and applicability of the proposed method. Our experiments confirm that, despite the complexity of the considered problem, optimal solution can still be generated within reasonable computational time using the proposed algorithm. The results also show considerable cost saving (about 10.1–27.3% less) if this optimization model is implemented, mainly contributed by the substantial extension of battery life. A number of managerial insights stemmed from the numerical case study are outlined, which can help transit operators formulate more cost-efficient electric bus fleet scheduling plans.