碩士 / 國立交通大學 / 運輸科技與管理學系 / 91 / The airline crew rostering problem considers the assignment of the crew staff to a set of pairings covering all the scheduled flights so that the line of work for each crew’s monthly schedule could be obtained. Traditional methods to solve airline crew rostering problem are usually based on mathematical programming (MP) to get a minimized operation cost. However, the optimization-oriented MP models can hardly deal with an equitable rostering problem which has both hard and soft constraints. In this research, we formulate the equitable airline rostering problem as a constraint satisfaction problem (CSP) and have developed a constraint programming (CP) model for solving the problem.
In order to develop efficient solution tools for real world large-scale problems, we decompose the problem the problem into sub-problems according to the length of pairings, and then solve the problem sequentially in four phases. In each phase, there is a CP model which serves as the core of the heuristic solution respectively. The results generated in each phase would be taken as the known input in the next phase until all the pairings were assigned.
We have applied our models to a case study with a month of rostering data provided by an international airline in Taiwan. There are 1274 pairings to be assigned to 169 pursers in the case problem. The CP models were implemented on an AMD personal computer (1.6G Hz). The OPL Studio 3.0 was used as the solver of our CP. Four attributes were used to measure the equitability of the roster assignment: Time Away Form Base (TAFB), Block Hours (BH), Flight Legs (FL), and Working Days (WD). The results showed that four normalized average deviation rates are all smaller than the source data and the total equitable cost decreased by 36.7%. The total cpu time of four solution phases is approximately 20 minutes. It proved that our CP-based model could generate feasible and equitable lines of work very efficiently.
| Identifer | oai:union.ndltd.org:TW/091NCTU0423016 |
| Date | January 2003 |
| Creators | Yi-Ling Tang, 唐依伶 |
| Contributors | Anthony Fu-Wha Han, 韓復華 |
| Source Sets | National Digital Library of Theses and Dissertations in Taiwan |
| Language | zh-TW |
| Detected Language | English |
| Type | 學位論文 ; thesis |
| Format | 79 |
Page generated in 0.0108 seconds