The Preferential Bidding System at Air Canada

Michel Gamache, François Soumis, Daniel Villeneuve, Jacques Desrosiers and Éric Gélinas
Additional contact information
Michel Gamache: Groupe d'études et de recherche en analyse des décisions, and École Polytechnique de Montréal, Montréal H3C 3A7, Canada
François Soumis: Groupe d'études et de recherche en analyse des décisions, and École Polytechnique de Montréal, Montréal H3C 3A7, Canada
Daniel Villeneuve: Groupe d'études et de recherche en analyse des décisions, and École Polytechnique de Montréal, Montréal H3C 3A7, Canada
Jacques Desrosiers: Groupe d'études et de recherche en analyse des décisions, and École des Hautes Études Commerciales de Montréal, Montréal H3T 2A7, Canada
Éric Gélinas: Ad Opt Technologies Inc., Montréal H3V 1G4, Canada

Transportation Science, 1998, vol. 32, issue 3, 246-255

Abstract: This paper describes the Preferential Bidding Problem solved in the airline industry to construct personalized monthly schedules for pilots and officers. This problem consists in assigning to crew members pairings, days off, annual leaves, training periods, etc., while considering a set of weighted bids that reflect individual preferences. This assignment must be done under strict seniority restrictions: the construction of a maximum-score schedule for a particular crew member must never be done at the expense of a more senior employee. This research and development project has resulted in the Preferential Bidding System that has been used at Air Canada since May 1995. The solution process is summarized as follows. For each employee, from the most senior to the most junior, a so-called residual problem is solved: given an employee and a set of unassigned pairings, the solution to an integer linear program determines the employee's maximum-score schedule while taking into account all the remaining employees. The residual problem is solved by column generation embedded in a branch-and-bound tree. Integer solutions are obtained by using very efficient cutting planes, without which it would have been impossible to solve some of these residual problems.

Date: 1998
References: View complete reference list from CitEc
Citations: View citations in EconPapers (29)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.32.3.246 (application/pdf)

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:inm:ortrsc:v:32:y:1998:i:3:p:246-255

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().