A branch-and-price algorithm for integrated optimization on vehicle and crew scheduling of electric bus system

Electric buses (EBs) play a vital role in environment protection and sustainable development. Because EBs have a limited driving range and relatively long daytime charging times, it is reasonable to redeploy drivers during charging to reduce idle time in crew schedules. Network-level vehicle and crew scheduling problems should consider labor regulations, deadheading insertions, and available time slots of vehicle usage. This paper develops a mixed integer nonlinear programming (MINLP) model to formulate this integrated optimization problem under an EB’s fast charging mode. In particular, two models are built involving two dispatching modes: a driver & EB binding mode and a freely-combined mode. A customized branch-and-price (B&P) algorithm is designed to cope with both MINLP models. Numerical tests and a real-world case study verify that the freely-combined mode reduces charging events and achieves 4.42% cost savings relative to the binding mode. In large-scale scenarios, the B&P algorithm exhibits superior computational efficiency and solution quality compared to Gurobi and a grouping genetic algorithm (as another benchmark). Finally, sensitivity analysis shows that the network integration optimization scheme can reduce the operation cost by 2.83%-11.94%. EB acquisition cost (54.44%-71.40%) and charging cost (6.81%-18.85%) are the key factors affecting the total cost, and their fluctuations will significantly affect the optimal scheduling scheme.