Theory And Method For Crew Scheduling Problem Of Urban Public Transport

With the development of economy and acceleration of urbanization, the problems of urban traffic congestion are getting more and more serious, which have made a negative effect on the urban continual development. Giving priority development of public transport is an important means to solve these problems. Bus crew scheduling is a key step for the process of transit planning. A scientific, reasonable and practical of bus crew scheduling plan, can be a rational allocation of resources, meet the diversified demand of passengers with minimum operating cost of public transport, improve the utilization rate of crew resources, and effectively alleviate the problem of traffic congestion.At present, most bus companies mainly rely on managers with manual experience and take a long time. In the case of a large number of bus trips, it is difficult to make a quick and accurate arrangement and adjustment of the scheduling scheme. It is more difficult to ensure the economic, correctness and rationality of the scheduling results.Due to the limitation and lagging of existing methods of crew scheduling and lag, the optimization theory of urban bus crew scheduling with two patterns, namely vehicle-crew fixed pattern and vehicle-crew unfixed pattern, is discussed in this paper. The paper includes the following sections:(1) The paper makes a review on the generation, development and last achievements of the problem of crew scheduling in China and abroad in detail, and gives a literature review with two areas: mathematical modeling and solving algorithms. Finally, the innovative points and framework context of this thesis are described.(2) In view of the single-depot crew scheduling problem with vehicle-crew fixed pattern, the two crew scheduling models considering single duty and multiple duties are established respectively. The former model is formulated as a 0-1 integer programming problem with the minimum cost of pull-in/pull-out time and waiting time as the objective function and the work intensity and impartiality as the main constraints. The tabu search algorithm is used to solve the proposed model. Based on the single duty model, the early, day, and late duty modes are considered in the latter model. The duty type compatibility constraint should be taken into account in constructing the corresponding model and algorithm.(3) In view of the multiple-depots crew scheduling problem with vehicle-crew fixed pattern, the two crew scheduling models considering single duty and multiple duties are established respectively. The former model is constructed as a 0-1 integer programming problem with the minimum total time cost as the objective function. The tabu search algorithm is also used to solve the model. All trips from several lines in one day are used for test instances illustrate the proposed model. Based on the single duty model, the time window of duty type constraint is also considered in the latter model. The data analysis of numerical example is carried out for the corresponding model and algorithm.(4) The arrival time of each trip is often delayed and the plan of crew scheduling may be easily affected by delayed trips. The concept of delayed trips is proposed and three strategies including maintaining the original plan, increasing number of crew and rearranging schedules of crew, can be applied to optimize the crew scheduling scheme in cases of delayed trips. Finally, the corresponding algorithm design and example analysis are presented in this section.(5) In view of the crew scheduling problem with vehicle-crew unfixed pattern, a set covering model is proposed to select a crew set with minimum cost. Each task of crew should be strictly included in the set of consecutive trip section. A column generation algorithm is designed to solve the problem. At last, an example illustrates the correctness and effectiveness of the proppsed model and algorithm.