結合限制規劃與數學規劃求解大型後艙空勤組員排班問題

Abstract

空勤組員排班屬於NP-Hard之大型組合最佳化問題，也是航空公司營運規劃的重要課題，由於其實務問題之規模龐大計算複雜度高，故在作業研究領域中有諸多文獻探討。本研究將應用新近發展之限制規劃方法與傳統的數學規劃方法，求解大型後艙空勤組員排班問題。 CP源自於人工智慧領域，主要是用來求解限制滿足問題(CSP)，此方法論之最大優點在於高度的模式彈性與快速的求解績效。一般而言，組員排班可分為「勤務組合產生」與「排班成本最小化」兩個部分。本研究將勤務組合產生問題視為一個CSP問題，並應用CP建立一個有效率的勤務組合產生模式(簡稱CSP模式)，該模式能同時考慮各種排班法規(飛時、工時、休時)與營運因素(基地、機型接續、艙等、空載)，故較傳統之勤務組合產生方法更具彈性。以CSP模式為基礎，將航段依班次頻率分類，再加上專家知識之限制式，構建一個CSP-CP模式來產生具有實用價值之受限性勤務組合集合(簡稱CP集合)，期能有效地縮小最小成本問題之求解規模。 考慮實務問題規模通常屬於大型問題，本研究結合CSP-CP模式與MP模式建立一套以限制規劃為基礎之變數產生法。在績效比較方面，本研究採用兩篇文獻所使用之測試問題作為比較基準，其問題之實際規模分別為1.7*106與6*107。測試結果發現，此求解方法在兩個大型測試例題上所求得之最小成本皆優於文獻結果，其改善幅度分別為3%與2.7%，運算時間分別為23.9秒與203.2秒。此結果顯示，CSP-CP模式確實能有效地結合MP來求解大型後艙組員排班問題。 基於CSP-CP模式能有效地產生具實用性之受限性勤務組合，本研究亦根據CSP-CP模式列舉所有不含空載之基本勤務組合(Basic Pairing, BP)集合與恰含1個空載之延伸性勤務組合(Extended Pairing, EP)集合，直接作最小成本之優化。結果發現，此種限制列舉式之產生-優化法(Generate-and-Optimize)，對兩個大型測試例題亦可不經由變數產生法的分解機制，直接求得相同最小成本的結果，由此可知，CSP-CP模式確實能有效地縮減問題規模並保持解之品質。

Because crew cost is only second to fuel in airline operations, the crew scheduling problem has been widely studied in the literature. Most existing literature on this problem is based on mathematical programming (MP) models. This research takes a new approach using constraint programming (CP) to complement MP in solving large-scale crew scheduling problems. Essentially, a crew scheduling problem can be decomposed into a pairing generation problem, and a minimum-cost set partitioning problem (SPP). In this research, we took the pairing generation problem as a constraint satisfaction problem (CSP) and developed a CSP model to generate feasible pairings. Since the number of feasible pairings tends to be enormous, we developed a CSP-CP model to generate feasible constrained pairings (CP) by adding some expert-knowledge rules to CSP model. Considering most crew scheduling problems in practice are large-scale, we combine the CSP-CP model and SPP model to develop a CP-based column generation method. To evaluate the performance of this method, we adopted two large-scale problems in literature as our test problems, each has a problem size of 1.7*106 and 6*107 respectively. Computational results showed that CP-based column generation yields an improvement of 3% and 2.7% over the published best-known solutions of the two test problems respectively. Such results imply that the CSP-CP model can be used to complement the MP in column generation effectively. Because the CSP-CP model can effectively generate feasible pairings, we also applied the CSP-CP model to solve the crew scheduling problem in the “generate-and-optimize” framework. The generated CP includes a set of basic pairings (BP), each of which contains no deadheads, and a set of extended pairings, each of which contains exactly one deadhead. We found that the CP-based generate-and-optimize method yielded the same optimal costs as we obtained in the CP-based column generation method. Such results imply that the CSP-CP model may effectively reduce the problem size without losing solution quality in solving large-scale cabin crew scheduling problems.