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

Twan Dollevoet () and Dennis Huisman ()
Additional contact information
Twan Dollevoet: Erasmus University Rotterdam
Dennis Huisman: Erasmus University Rotterdam

Chapter 10 in Optimization Essentials, 2024, pp 297-323 from Springer

Abstract: Abstract 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.

Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-981-99-5491-9_10

Ordering information: This item can be ordered from
http://www.springer.com/9789819954919

DOI: 10.1007/978-981-99-5491-9_10

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().