Column Generation and Lagrangian Relaxation: Solving Real-World Crew (Re)Scheduling Problems

In this chapter, we describe the combination of column generation and Lagrangian relaxation to solve a large-scale optimization problem. In the setting of a minimization problem, Lagrangian relaxation is used to compute lower bounds. Column generation is applied to deal with the huge number of columns. We apply these techniques to the crew scheduling and the crew rescheduling problem. Crew scheduling is an important planning problem for public transport companies and airlines. It has been studied by many Operations Researchers over the last few decades. The most complex problems arise at large public transport companies where 10000s of tasks have to be assigned to 1000s of crew members. Usually, the crew scheduling problem is solved once a year. During the year and in particular on the day of operations when disruptions occur, duties are rescheduled. We look at both the tactical planning phase as well as real-time crew rescheduling on the day of operations. In the tactical planning phase, a computation time of several hours is acceptable and it is important to find near-optimal solutions. We discuss the combination of Lagrangian relaxation and column generation to find a lower bound on the optimal objective value, and a Lagrangian heuristic to find good feasible solutions. When a disruption occurs, it is important to react quickly. Therefore, computation times should be in the order of a few minutes. Thus, heuristic approaches are often used for the real-time crew rescheduling problem. We discuss the combination of large neighborhood search with column generation and Lagrangian relaxation to solve a real-world crew rescheduling problem.