Research On Bus Scheduling And Timetabling Based On Intelligent Optimization Algorithms

With the development of social economy,people’s travel needs and individual household motor vehicle holdings are increasing.Most cities in our country face severe traffic congestion problems.Giving priority to public transport has become an effective way to alleviate traffic congestion in many regions of China.As an important part of public transport,buses are necessary to meet the travel demand of residents.Due to buses having the characteristics of large passenger capacity,flexibility,and low energy consumption,taking buses is one of the travel mode choices that meet the situation in China.Timetabling and bus scheduling are key components of public transport operation planning.Vehicle scheduling is based on generated timetables,and the quality of timetables would directly affects the quality of a vehicle scheduling solution.According to factors such as passenger flow demand et al.,timetabling determines the departure time interval(departure time frequency)of buses at control points(original and terminal stations)to generate timetables.Based on given timetables,bus scheduling arranges buses to execute the trips in timetables so that each timetabled trip is executed by exactly one bus.The objective is to generate a bus scheduling scheme with the minimum number of buses while satisfying the relevant constraints.Reasonable departure time interval(departure time frequency)can not only improve passengers’ satisfaction,but also reduce the operational cost.A good bus scheduling scheme can improve buses’utilization rate and reduce the number of buses.High-quality timetables and bus scheduling schemes would improve the service quality of bus companies,increase the attractiveness of public transport,and alleviate traffic congestion,which would promote the development of cities.Based on extensive literature review,it is found that the following studies on bus scheduling and timetabling have practical significance.Firstly,although there exist studies on bus scheduling,those studies mainly focus on bi-directional bus lines.Bus scheduling of a bus line with branch lines is also common in practice,but there is no study on this problem.Furthermore,existing bus scheduling approaches seldom consider driver scheduling and rostering factors,and generated bus scheduling schemes are not convenient for driver scheduling and rostering,which makes those methods cannot be used effectively in practice.Therefore,the study of bus scheduling methods for a bus line with branch lines has practical value.Secondly,due to the zero-emission and low-noise characteristics,electric buses have been widely used in public transport recently.However,because of the limitation of battery capacity,electric buses need to be recharged during the whole day driving task.However,the charging time is longer than the refueling time for fuel buses,which makes the traditional bus scheduling methods cannot be applied directly to solve electric bus scheduling problem.In addition,there exist several bus lines and timetables in multi-depot electric bus scheduling,and the coordination between different buses as well as the buses and bus lines brings challenges to multi-depot bus scheduling.Studies on multi-depot electric bus scheduling contribute to effectively arranging buses of different bus lines,which is conducive to improve buses’ utilization rate.Finally,as a bus scheduling scheme is generated based on given timetables,the quality of timetables would affect that of a bus scheduling scheme.Solving timetabling and bus scheduling independently can obtain a satisfactory solution for each problem,but it may be a suboptimal solution for the two problems as a whole.Integrated timetabling and bus scheduling considers the interests of both passengers and bus companies,and can reduce operational cost while ensuring the service quality of bus companies.Based on the above analysis,this dissertation summarizes the studies on timetabling and bus scheduling,and conducts the following three researches:(1)Research on the bus scheduling method for a Bus Line with Branch Lines(BBL).In view of the fact that there is no study on bus scheduling for BBL,this dissertation proposes a Construction-and-Repair based Method(C&RM)to solve this problem.Furthermore,to make the generated bus scheduling scheme facilitate driver scheduling and rostering,this dissertation takes into account the driver scheduling and rostering factors,The method consists of two phases.In the first phase,a trip assignment strategy based on two types of heuristic information is devised to assign timetabled trips to buses to construct a solution.If the constructive solution does not satisfy all the driver scheduling constraints,the solution is improved by the second phase.In the second phase,an iterative repair method is devised to improve the constructive solution to make it satisfy the constraints of driver scheduling.The repair method removes the vehicle blocks that do not satisfy driver scheduling constraints,and then TAS is used again to reassign all trips of those deleted vehicle blocks to buses.Finally,the proposed method is applied to real-world problem as well as 50 medium-and large-scale random problem instances.Experimental results show that C&RM outperforms comparative methods on the number of buses and in balancing buses’ driving tasks.Furthermore,the solution found by C&RM is suitable for generating driver scheduling and rostering schemes with balanced working time and driving mileage.(2)Research on the multi-depot electric bus scheduling method.Due to the limitation of battery capacity,electric buses need to be recharged to complete the driving task throughout the day.However,the charging time for electric buses is typically longer than the refueling time of fuel buses,the traditional bus scheduling methods cannot be used to solve electric bus scheduling problem.To solve multi-depot electric bus scheduling problem(MD-EBSP),a genetic algorithm with trip-adjustment strategy(GA-TAS)is proposed.A coding scheme based on initial time points is specifically devised for MD-EBSP.Then,a decoding procedure is devised to decode a solution coding into a bus scheduling solution,which considers the limited driving range,as well as the decision on when a bus is recharged and the recharging time.To diversify the individuals and improve the global search capability of GA-TAS,three crossover operators and seven mutation operators based on the characteristics of the coding scheme are designed.In addition,there may exist a timetabled trip that is repeatedly executed by different buses or trips that are not executed by any bus in the solution found by genetic algorithm(GA).To make each trip executed by exactly one bus,a trip adjustment strategy(TAS)is designed to improve the quality of the solutions found by GA.To test the performance of GA-TAS,it is applied to two real-world problem and five large-scale random problem instances.Experimental results show that GA-TAS is superior to the comparative methods in reducing the number of buses and balancing the buses’ driving tasks.(3)Research on the approach of integrated timetabling and bus scheduling.A bus scheduling scheme is generated based on given timetables.Compared with solving the two problems independently in sequence,integrated Timetabling and Bus Scheduling(TT-BS)can obtain satisfactory solutions for both two problems as a whole.To solve TT-BS,this dissertation proposes a Multiobjective Evolutionary Algorithm based on Decomposition with Auction Algorithm(MOEAlD-AA).Three objective functions are designed to take into account the interests of both passengers and bus companies.Wherein,two objective functions are constructed to evaluate the quality of timetables.To simultaneously consider passenger satisfaction and operational cost,the first objective is to minimize the difference between provided vehicle and passenger flow demand capacities.The second objective aims at reducing the weighted sum of passengers’ waiting time and the squared difference of the departure time intervals in peak and off-peak periods.The third objective is to reduce the number of buses used for bus scheduling.Under the framework of MOEA/D,a twopoint crossover operator and a uniform mutation operator are used to change the departure time interval of two adjacent time points in a timetable,and timetables are generated by decoding.Based on the generated timetables,an auction algorithm(AA)is used to generate a bus scheduling scheme.In addition,this dissertation constructs a timetable adjustment strategy.If the numbers of trips in the timetable of two control points(original and terminal stations)are not equal after decoding,the departure time intervals in different periods of the two timetables would be re-adjusted to make the number of trips in two timetables being equal.To obtain a bus scheduling scheme with fewer buses,the timetable adjustment strategy prioritizes reducing the difference of departure time intervals between peak and off-peak periods.To test the performance of MOEA/D-AA,it is applied to two real-word problem instances.Experimental results show that compared to the comparative methods,the timetables and bus scheduling schemes generated by MOEA/D-AA can reduce the number of buses while meeting the needs of passenger flow.