The Research On Bus Driver Scheduling Problem Based On The Pattern Of Generation And Selection

In this paper, the focus of my study is to solve the bus driver scheduling problem. This problem is referred to construct of a set of legal duties to cover all the blocks. Meanwhile, the objectives are to minimize the number of duties and find the minimum cost for operators. The process of driver scheduling can be divided into two stages.Stage one:the construction of a set of pre-generated legal potential shiftsFirst, the bus driver problem can be formulated as the covering problem. According to the characteristic of the set covering model, the constraints correspond to the pieces of work in the bus schedule, and the variables to the duties of the generated set. On average, the number of Piece of Work is enormous. On one hand, this will lead to generate a large of possible duties due to the combinations of pieces of work. However, it is impossible to generate all legal duties in practical schedules; on the other hand, since the number of the pieces of work corresponds to the number of constraints, the set of the constraints is large. So, a heuristic procedure is developed to form some time-bands in order to limit the number of relief times, which means rejecting some relief time outside the bands. Second, based on the analysis of the potential duties, the tree enumeration algorithm is employed to generate the potential legal duties.Stage two:searching for the set of feasible dutiesThis paper presents three genetic algorithms (GA) for bus driver scheduling problem to search for the optimal or near-optimal solution. Adopting unique strategies of initialization, the crossover and the mutation, these genetic algorithms are used to search for a set of feasible duties respectively.Under the pattern of generation and selection, Computational experiment based on the real-world bus operational data can has been conducted, and according to the three different strategies, the analysis and comparison has been undertaken. The results indicate that the improved operation of crossover in algorithm 2 can assist the genetic algorithm to search for the feasible set of duties quickly, and algorithm 3 incorporating the evaluation approach in the phase of initialization can find a better solution effectively and efficiently.