Research On Electric Bus And Driver Scheduling Problem Based On Column Generation Heuristic

We study electric bus scheduling problem and driver scheduling problem under the background of the rapid development of electric bus,considering the mileage constraints of electric bus and the constraints of drivers’ continuous working time and total working time.Firstly,we build set covering models for the electric bus scheduling problem and the driver scheduling problem in the sequential scheduling mode.The sequential scheduling mode first generates the vehicle utilization plan to ensure that all the trips are covered by the vehicle driving path.And we generate the driver scheduling plan according to the vehicle utilization plan,ensuring that all the empty driving generated by the vehicle utilization plan are covered by the driver scheduling plan.Integrated scheduling mode generates electric bus utilization plan and driver scheduling plan at the same time.In this paper,the set covering model of electric bus and the set covering model of driver scheduling are combined to build the set coverage model for the integrated scheduling mode.And we use dynamic programming algorithm combined with time-space network to generate feasible vehicle driving paths and driver schedules.We design a column-generation-based heuristic algorithm,combining the column generation algorithm with the pure diving heuristic strategy.And we solve the bus scheduling problem and driver scheduling peoblem with the column generation based heuristic algorithm from two perspectives of sequential scheduling and integrated scheduling respectively.The column generation algorithm is used to get the linear optimal solution,and pure diving heuristic strategy is used to get the integer solution.We generate trip information to test the effectiveness of the proposed algorithm randomly according to the information of three bus lines in Hefei City.and we compare the results of sequential scheduling and integrated scheduling.Finally,the sensitivity analysis of electric bus mileage,charging time,fixed cost of electric bus and fixed cost of driver is carried out to analyze the influence of the different parameters on the bus operation system.