Research And Implementation Of Multi-depot Bus Vehicle Scheduling

With the development of social economy,big cities are facing traffic congestion.Developing public transportation is an effective way to alleviate urban traffic congestion.The problem of bus vehicle scheduling is an important issue for bus operations.Pure electric vehicles have attracted the attention of government because of their low transportation costs,low noise,and zero emissions.However,due to their short driving range and long charging time,electric vehicle scheduling problems are more complicated.Multi-depot bus scheduling can dynamically allocate buses on various lines,saving bus operating costs,and is therefore a current research hotspot for bus scheduling.However,the current research on multi-depot electric bus scheduling is rarely.This paper studies the Multi-depot electric vehicle scheduling problem(MD-EVSP).As we all know,Branch and Price(BP)is an effective method to solve vehicle scheduling,but it cannot solve large-scale problems in an acceptable time.Therefore,this paper improves BP to solve MD-EVSP.First,a heuristic method is proposed,which is used to generate the initial solution,and improving the initialization method of each node in the branch and bound tree to accelerate the convergence of the BP algorithm.In order to balance the computational efficiency of the algorithm and the quality of the solution obtained,a two-stage method(Column generation and Genetic algorithm(CG-GA))was introduced to solve MD-EVSP.it uses column generation to generate a set of candidate column sets for MD-EVSP in one stage.The second stage uses a genetic algorithm with a diversity retention mechanism and an elite retention strategy to select partial columns from the candidate column set to build the final solution.The BP introduced in this paper and mainstream truncated column generation algorithm(TCG)are tested on public data sets to prove the effectiveness of the BP.The CG-GA and BP and TCG algorithms was experimented on Beijing and Qingdao transit dataset,compared to BP and TCG,CG-GA can find an approximate solution of the optimal solution faster.Compare CG-GA's scheduling results on actual route data in Qingdao with manual scheduling results,for large-scale problem examples,the CG-GA's scheduling results have higher vehicle utilization and trip coverage.The results could provide decision support for the practical application of multi-depot electric bus vehicle scheduling.