Article ID: | iaor20062196 |
Country: | Netherlands |
Volume: | 7 |
Issue: | 1 |
Start Page Number: | 33 |
End Page Number: | 46 |
Publication Date: | Mar 2006 |
Journal: | Optimization and Engineering |
Authors: | Reinelt Gerhard, Tran Van Hoai, Bock Hans Georg |
Keywords: | timetabling |
Crew pairing problems are often solved using column generation in a branch-and-price framework. The oscillation of dual points is the main reason which leads to instability in the standard implementation of this method. One device to deal with the problem is to use the trust-region idea to stabilize the path of dual points. Therefore, a so-called stabilized column generation with respect to control parameters is suggested to overcome this problem. In this paper we report about possible realizations of this principle and show that the performance of algorithms can be improved significantly. Three stabilizing methods are used to investigate good control parameters which contribute to the improved computation time in solving a set of crew pairing problems involving about 400 flights per week.