Bidline scheduling with equity by heuristic dynamic constraint aggregation

Khaled Boubaker, Guy Desaulniers and Issmail Elhallaoui

Transportation Research Part B: Methodological, 2010, vol. 44, issue 1, 50-61

Abstract: The bidline scheduling problem with equity arises in several North American airlines. It consists of determining anonymous monthly schedules, called bidlines, that will be subsequently assigned to the crew members according to their bids and seniority. These bidlines must satisfy safety and collective agreement rules. Furthermore, to ensure an equity between the employees, each bidline should have as much as possible the same number of days off and the same number of credited (paid) hours. In this paper, we propose an approximate set partitioning type formulation for this problem and two heuristics for solving it. The first one is a standard branch-and-price heuristic that relies on a rounding procedure to derive integer solutions. The second one is obtained by combining this first heuristic with a dynamic constraint aggregation method that was recently proposed in the literature. Computational results show that, for the largest tested instances, the dynamic constraint aggregation heuristic can produce better quality solutions in a fraction of the computational time required by the standard branch-and-price heuristic.

Keywords: Bidline; scheduling; Air; transportation; Dynamic; constraint; aggregation; Column; generation (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191-2615(09)00074-5
Full text for ScienceDirect subscribers only

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:eee:transb:v:44:y:2010:i:1:p:50-61

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().