Column Generation Based Approaches For Solving Crew Scheduling Problems

The aim of crew scheduling is to transform the predetermined vehicle blocks into a set of shifts, and each shift must comply with various labor rules and operational constraints (i.e. each shift can be implemented by a crew), such that the overall operational cost (the number or the payable cost of shifts) is to be minimized. Crew scheduling is one of the main problems arising in public transit planning and operation, and an efficient crew schedule can enhance the efficiency of public transit operation and save an enormous amount of money for the enterprises. However, the following two difficulties are encountered in solving crew scheduling problems. On one hand, the crew scheduling problem is NP-hard, which is one of the most well-known difficult problems in the area of public transportation and combinatorial optimization. Up to date, the solution approaches can be classified into the following three groups:traditional integer linear programming (ILP) approaches, heuristics or meta-heuristics (e.g. Genetic Algorithm, Tabu Search) approaches and Column Generation approaches. Traditional ILP approaches have limited solving abilities, which often encounter big difficulties in solving large scale problems; meta-heuristic approaches have an advantage of high-speed computational abilities, but they cannot guarantee the solution quality; column generation approaches can solve large scale problems and obtain optimal (or near-optimal) solutions, but they have a disadvantage of slow convergence. On the other hand, the frequently-used formulations (i.e. set covering or partitioning formulation) for crew scheduling are too idealistic, and their solutions usually can’t meet the practical requirements or expectations of operational enterprises.To deal with the difficulties described above, this dissertation mainly studied fast solving approaches for large scale crew scheduling problems and more generalized formulations. Firstly, based on problem-specific knowledge, an approach to decrease the problem scale was presented to solve the crew scheduling with Chinese meal-break rules. Secondly, some fast column generation approaches were studied to deal with large scale problems. Finally, a more generalized crew scheduling formulation and its corresponding solving approach were studied. Specifically, the main work and results are as follows: (1) To deal with the crew scheduling problems with Chinese meal break rules, a heuristic approach to select "good" ROs (a RO, i.e. relief opportunity, consists of a time and location pair for crew’s relieving) was firstly proposed and then an ILP approach based on "generate and select" was used to solve the problems. The main idea is that Chinese meal break rules and some problem-specific characteristics were considered when heuristically selecting ROs and Chinese meal break rules were handled in the "generate" phase. Finally, a group of practical problems in Chinese public transport were tested to show the efficiency of the proposed approach.(2) According to the problem-specific characteristics, a network flow formulation that considers whether or not use a RO was proposed and was transformed to a set covering formulation by using the Dantzig-Wolfe decomposition method. Then, a column generation approach was designed to solve the transformed formulation to get a lower bound. Finally, an integer solution approach was proposed, i.e. using LP relaxation solution to fix some ROs not be used step by step, and using the column generation approach to solve a small crew scheduling problem that only considering partial ROs not be fixed. By testing some real crew scheduling problems, optimal or near-optimal integer solutions can be obtained quickly for most instances.(3) To overcome the drawback of spending too much time to solve the column generation subproblem by using the traditional method (i.e. exact dynamic programming method), a two-phase approach that combines selecting shifts from a predefined shift set with constructing shifts by a directed graph was proposed. Specifically, by analyzing the characteristics of crew scheduling, a heuristic approach that constructs high efficient shifts (which form a shift pool) was firstly proposed. When solving the subproblems, shifts that can improve the current objective value is firstly selected from the shift pool; new shifts will be constructed by exact dynamic programming method to improve the current objective value only if there no exists shift in the shift poll. By testing real instances and comparing with traditional approach, the proposed approach can decrease the overall solution time by20%.(4) According to the characteristics of crew scheduling problems, a new accelerating strategy for column generation was proposed. The new accelerating strategy mainly considers three aspects as follows:when implementing the column generation algorithm, some "bad" columns are periodically (after a given number of iterations) removed from the current restricted master problem to reduce its scale; a strong label-eliminating rule was proposed and a two-phase method based on the rule was presented to accelerate the solving process of subproblems; a shift pool strategy was proposed to exploit the current solution information was proposed to accelerate the speed of searching for integer solutions. Some real instances were tested to show the efficiency of the proposed approach.(5) To overcome the drawback of traditional set covering or partitioning formulations which do not meet some specific requirements that may be imposed by public transit operators, an extended set covering formulation with multiple additional constraints was proposed. To solve the extended set covering formulation, a column generation algorithm was designed. Since additional constraints will bring difficult when solving the column generation subproblem, traditional solving method of the subproblem cannot be directly used. According to the shift sets restricted by the additional constraints, all feasible shifts were reclassified into new disjoint shift sets and a decomposition solution approach for the subproblem was presented. Finally, the proposed formulation and the corresponding solving approach were tested by the real instances from Chinese public transit, and the computational results show that optimal or near-optimal integer solutions can be obtained in a reasonable amount of time for most instances.