IE-OPIM Joint Seminar
Ş. İlker Birbil – Sabancı University
October 3, 2012, Wednesday @ 13:40pm @ FENS G029
A Robust Crew Pairing Model for Managing Extra Flights
(or how a simple application led to fruitful research)
In this study, we solve a robust version of the airline crew pairing problem. Our concept of robustness was partially shaped during our discussions with small local airlines in Turkey which may have to add a set of extra flights into their schedule at short notice during operation. Thus, robustness in this case is related to the ability of accommodating these extra flights at the time of operation by disrupting the original plans as minimally as possible. We focus on the crew pairing aspect of robustness and prescribe that the planned crew pairings incorporate a number of predefined recovery solutions for each potential extra flight. These solutions are implemented only if necessary for recovery purposes and involve either inserting an extra flight into an existing pairing or partially swapping the flights in two existing pairings in order to cover an extra flight. The resulting mathematical programming model follows the conventional set covering formulation of the airline crew pairing problem typically solved by column generation with an additional complication. The model includes constraints that depend on the columns due to the robustness consideration and grows not only column-wise but also row-wise as new columns are generated. To solve this difficult model, we propose a row and column generation approach. This approach requires a set of modifications to the multi-label shortest path problem for pricing out new columns (pairings) and various mechanisms to handle the simultaneous increase in the number of rows and columns in the restricted master problem during column generation. We conduct computational experiments on a set of real instances compiled from local airlines in Turkey.
This seemingly straightforward application led to an interesting research in our group at Sabancı University. The story behind it will also be presented in this talk.
Ş. İlker Birbil
Ş. İlker Birbil received his PhD degree from North Carolina State University, Raleigh, USA. He then worked for two years as a postdoctoral research fellow in Erasmus Research Institute of Management, Rotterdam, The Netherlands. His research interests include local and global nonlinear optimization with particular emphasis on algorithm development. He is also an associate editor of Journal of Industrial and Management Optimization (JIMO). Currently, he is working as a faculty member in Sabanci University, Istanbul, Turkey, where he teaches various courses on operations research.