以限制規劃求解公平性空服組員派遣問題-以座艙長為例

Abstract

公平性空服組員派遣係指將一個月的勤務組合行程指派給空服組員，而形成組員之月行程班表，除了符合各項派遣規定限制，也要盡量顧及組員之偏好與滿意。組員派遣直接影響空服人員的工作士氣，間接影響對顧客第一線的服務品質，「公平」派班的重要性不可言喻。過去相關研究多著墨於派遣成本最小化，較少考慮組員對於勤務公平之需求，本研究除了飛安管制要求之派遣限制以外，更納入許多公平性考量因素（如：休假日安排、待命任務公平…），符合現代重視人性化之趨勢潮流。 從方法論來看，傳統求解航空組員派遣問題多架構於數學規劃基礎之上，較難完整描述複雜限制問題。本研究將公平性組員派遣列式為限制滿足問題求解（CSP），應用限制規劃（CP）方法，經由問題變數與限制函數之設計，將本研究中所考量各項限制模式化求解。同時為提升求解效率，本研究適當地加入「以最小累積飛行時數者優先指派」之搜尋策略，並以「分階段指派」啟發式方法，將勤務組合分成3日以上勤務組合、2日勤務組合、1日勤務組合以及待命勤務四個階段進行指派。 本研究以台灣一家國際航空公司（C航）2001年12月座艙長班表資料作為測試實例，包含169位座艙長及1274個待指派勤務組合。測試環境為Windows 2000作業系統、1.6G Hz處理器速度，以OPL Studio 3.0執行求解，四個階段總求解時間約為20分鐘，找到一組可行解之後，平均0.6秒便可產生下一組可行解。本研究所求解結果總公平性成本較原班表改善36.7%，差旅時間、飛行時間、航段數、工作天數四項屬性正規化平均偏差率均較小，由此證明本研究發展之公平性派遣限制規劃模式，確實能有效率地產生公平的組員月行程班表，並能提供排班人員彈性的決策支援使用。

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.