Intelligent Optimization Approaches For Solving Crew Scheduling And Rostering Problems

With the rapid urbanization and motorization, the problems like road congestion have become more and more serious in China, which makes urban transportation face severe challenges, prioritising the development of public transit is imperative. How to construct and manage modern public transit system has become a significant theoretical and practical problem in China’s economic and social development, which needs urgent research works. In the public transit planning and operation, crew scheduling and rostering problems are key problems, which determine the crews’working schedules, efficient schedules can enhance the efficiency of public transit operation, decrease the operation cost and ensure that the crews can enjoy the rights given by national labor laws. The crew scheduling and rostering problems include two subporblems, which are performed in sequence:crew scheduling problem and crew rostering problem, where the former is the basis of the latter. They are NP-hard, their complexity mainly consists in the large scale, mutiple objectives and a series of complex labour agreement rules. Therefore, it is of great theoretic and realistic significance to devise effective and robust crew scheduling approaches and crew rostering approaches. Intelligent optimization approach is one class of the most widely adopted approaches at present, however, due to the high complexity of the problems, there is still much scope for improvements, where deeply understanding their domain knowledge and then incorporating them into the design of the approaches appropriately is the key and difficulty, which needs further research. Moreover, shift evaluation in the crew scheduling problem is a complex multiple attribute decision making problem, which is the foundation of many crew scheduling approaches, however, little research has been done into multiple attribute decision making shift evaluation methods.To deal with the above problems, in this paper, four crew scheduling approaches are first devised from different perspectives, where two multiple attribute decision making shift evaluation methods are proposed, Then two multi-objective approaches are developed for the crew rostering problem. Specifically, they are listed as follows.A Adaptive Evolutionary Crew Scheduling approach (AECS) is proposed, in the AECS, a new chromosome representation is defined, it is straightforward and short, and allows infeasible schedules to be expressed. The initial chromosome length is specially designed as the lower bound of shift number in the optimal schedule. The chromosome length varys adaptively during the iterative process, which is achieved by devising genetic operations of crossover and mutation with removal and replenishment strategies. Experiments have shown that the AECS is fast and can obtain high-quality schedules.A Grey Relational Analysis (GRA) shift evaluation method is designed. To determine the optimal parameters of the method, an Evolutionary crew scheduling algorithm based on GRA (EGRA) is further developed, when the resulting set of parameters is generated, the best schedule is obtained correspondingly. The EGRA is a specially-designed hybrid Genetic Algorithm embedded a quick local search, where the local search is elaborately designed for intensification purposes. Experiments have shown the superiority of the EGRA.A Variable Iterated Greedy crew scheduling approach based on GRA (GRAVIG) is designed. GRAVIG tailors the Variable Iterated Greedy (VIG) algorithm to sovle the crew scheduling problem, where the GRA shift evaluation method is integrated into the VIG to serve as a solver for the shift evaluation during the scheduling process, which enhances greatly the VIG. Moreover, in the GRAVIG, a biased probability destruction phase is elaborately devised to keep the’good’ shifts remained in the schedule without compromising the randomness. Experimental results have demonstrated the GRAVIG is effective.A TOPSIS (Technique for Order Preference by Similarity to Ideal Solution) shift evaluation method is developed. Moreover, a Variable Neighbourhood Search crew scheduling approach (VNS) is proposed, which tailors the variable neighbourhood search algorithm to sovle the crew scheduling problem. In the VNS, two compound neighbourhood structures with probability are designed, which enhances considerably the diversification of the search space. In addition, the TOPSIS shift evaluation method is is embedded in the VNS to serve as a solver for the shift evaluation during the scheduling process. In addition, SA is integrated into the VNS to serve as a solver for effective local search. The effectiveness of the VNS has been verified by the experiments.Two multi-objective crew rostering approaches are developed, i.e. Multi-Objective Simulated Annealing crew rostering approach (MOSA) and multi-Objective Variable Neighbourhood Search crew rostering approach (VNS), both of them can deal with users’ preferences better by employing two evaluation functions. In the MOSA, a heuristic is first devised to construct an initial solution. Next, a SA-based feasibility repairing algorithm is designed to make the solution feasible. Finally, a SA-based non-dominated solution generating algorithm is developed to find the non-dominated solutions. In the MOSA, incremental evaluation, neighborhood pruning and biased elite solution restart strategy are respectively devised to make the search more quickly and effective. In the VNS, two compound neighbourhood structures are devised, each corresponds to an objective and the two neighbourhood structures are employed in turn, In each neighbourhood, SA is integrated into the VNS to serve as a solver for the local search. Moreover, an improved acceptance criterion is designed to enhance the search power of the VNS. Experiments have shown the two approaches are effective.