A Branch-and-Price Algorithm for Large-Scale Multidepot Electric Bus Scheduling

Electric buses (e-buses) are increasingly adopted in the transit systems for their benefits of reduced roadside pollution and better onboard experience. E-bus scheduling is a critical problem in the operation planning stage of transit management to ensure efficient and reliable transit service. In Chinese mega cities, the e-bus networks are operated with many bus routes characterized by high service frequency and long operation time, making the e-bus scheduling a large-scale problem. Besides, the transit agency requires the vehicle-depot constraint to limit the e-bus reposition since it is not cost-efficient. An efficient method to generate optimized schedules that meet the above requirements is desired by the transit agencies. In this paper, we address a large-scale multi-depot electric bus scheduling problem considering the vehicle-depot constraint and partial recharging policy. A mixed integer programming model and an efficient branch-and-price (BP) algorithm are developed to solve the problem. In the BP algorithm, we devise a heuristic method to generate good initial solutions and adopted heuristic decisions in the label setting algorithm to solve the pricing problem. In this way, the efficiency of the BP algorithm is achieved and the large-sized problem instances can be solved. We conduct extensive numerical experiments based on the fixed-route and multi-route operation cases in Shenzhen. The results show that the BP algorithm can generate provable high-quality solutions. Sensitivity analysis indicates that increasing battery capacity and charging rate can reduce the operational cost. The optimal charging schedules can also provide guide in determining the capacity of the charging facilities.