Advanced Column Generation Techniques for Crew Pairing Problems

Tran Van Hoai (), Gerhard Reinelt () and Hans Georg Bock ()
Additional contact information
Tran Van Hoai: University of Heidelberg, Interdisciplinary Center for Scientific Computing
Gerhard Reinelt: University of Heidelberg, Institute for Computer Science
Hans Georg Bock: University of Heidelberg, Interdisciplinary Center for Scientific Computing

A chapter in Modeling, Simulation and Optimization of Complex Processes, 2005, pp 203-214 from Springer

Abstract: Summary Crew pairing problems are often solved using column generation in a branch-and-price framework. The main idea of this approach consists of solving linear programming relaxations for a subset of variables and employing pricing for introducing additional variables with negative reduced costs. Since the dual variables are not bounded, this leads to instability in the standard implementation of this method. Therefore, a so-called stabilized column generation with respective control parameters is suggested to overcome this problem by reducing the number of redundant variables. In this paper we report about possible realizations of this principle and show that the performance of algorithms can be improved significantly.

Date: 2005
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:sprchp:978-3-540-27170-3_16

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

DOI: 10.1007/3-540-27170-8_16

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().