A Hybrid Metaheuristic For The Transit Bus And Driver Scheduling

Smart bus system is essential for urban public transit companies to improve their operation efficiency and service level.There are a number of problems in bus operations,such as the optimization of bus line network,the timetabling of bus lines,the vehicle scheduling,and driver scheduling and rostering.Among them,the scheduling of buses and the drivers is the basis of daily operations of public transit.A good operational plan can reduce the number of buses needed for bus lines and reasonably arrange drivers’ work and break/meal times,thus providing security for safe and efficient bus operations.This paper proposes a meta-heuristic algorithm for the problem of transit bus and driver scheduling.The major research topics are as follows:(1)the solution strategy for the bus vehicle and driver scheduling problem.Based on the analysis of the basic requirements of bus scheduling and driver scheduling,the problem is defined.The concept of shift chain is used to express the task arrangement of the bus and the task of the driver,and the neighborhood search meta-heuristic algorithm is used to improve the shift chains.(2)The implementation of meta-heuristic algorithm for the bus and driver scheduling.Based on the basic principles of the neighborhood search methods,a meta-heuristic framework is designed.It includes various modules such as the problem definition,chain evaluation,mathematical model,initial solution construction,chain adjustment operators,ruin and repair methods,and search strategy.Using the basic modules of the algorithm,a multi-start iterative local search algorithm is implemented.(3)The algorithm is tested using a set of problem instances.A total of 44 bus lines are prepared to carry out vehicle scheduling and driver scheduling.Three scheduling modes,the person-vehicle coupling for single bus line,the person-vehicle separation for single bus line and the person-vehicle separation for multiple single bus lines,are considered.The main conclusions and innovations in this paper are as follows:(1)An efficient and flexible meta-heuristic algorithm for bus vehicle scheduling and driver scheduling was implemented.The algorithm belongs to a multi-start iterative local search algorithm.First,an initial solution is obtained through a model of vehicle scheduling,and then the shift chains are iteratively improved through five chain adjustment operators.In order to avoid the algorithm falling into a local optimum,the algorithm introduces two ruin-and-repair methods.In order to overcome the short-sighted limitations of local search,a model of set-covering problem(SCP)is used to select better chain combinations from a global perspective.The test finds that this algorithm is suitable for bus vehicle and driver scheduling on the three scheduling modes.(2)The algorithm was tested on 13 single-line instances with person-vehicle coupling scheme.Experimentation shows that the SCP model can further improve the quality of scheduling scheme.Compared with the manual scheduling plans,the algorithm has high execution efficiency and is better than the current schedules.In particular,the algorithm can benefit the drivers by reducing their work times and providing reasonable break and meal times.(3)The algorithm was tested on 21 single-line instances with person-vehicle separation scheme.Compared with the person-vehicle coupling scheme,the person-vehicle separation scheme can reduce the number of required vehicles evidently.The number of required drivers can also be reduced for some bus lines.(4)The algorithm was tested on eight multi-line instances with person-vehicle separation scheme.It is found that the model of vehicle scheduling can be solved efficiently,and the bus fleet with the least number of vehicles is obtained.Since the algorithm allows the driver to drive multiple vehicles during a day’s work,the driver’s break and meal times are guaranteed.Compared with single-line operations,the total operational cost can be reduced notably.(5)Compared with the existing algorithms,this algorithm proposed in this paper has several advantages.First,the fixed and variable costs of buses and drivers are considered in the algorithm.Second,the algorithm is tested on a set of real cases with three scheduling modes.Third,setting suitable scheduling parameters,the algorithm can meet the flexible and diverse management requirements in the bus companies.The algorithm proposed in this paper is successfully test on various problem instances.However,there are still some limitations in the algorithm design.Further research work includes: different vehicle types and costs should be included in the algorithm;more flexible driver work shifts and compensation rules should be introduced;and electric and hybrid bus fleets are also essential for bus and driver scheduling.