以基因演算求解航段指派為基之前艙機員與後艙組員排班問題

Genetic Algorithm for Solved Sector Based Cockpit Pilot and Cabin Crew Rostering Problems

藍柏鼎(Po-Ting Lan)

指導教授 ： 宮大川

中原大學/工學院/工業工程研究所/碩士(2005年)

https://doi.org/10.6840/cycu200500322

摘要

隨著我國加入世界貿易組織，國內航空市場的開放壓力接踵而來，民航業者在面臨新市場競爭者，必須提供最佳的服務才能在同業中脫穎而出。因此面對大環境不佳以及同業間的競爭，如何控制成本已為航空公司所面臨的重要課題之一。
由於國內線屬於短程航線，具航班密集、起降間隔小以及飛航時間短之特性，因此，在航班規劃上必須比中長程航空規劃更精準，以避免空載(Deadhead) 以及人員的閒置。此外，航空業之人員成本(Crew Cost)約佔總成本的10%~15%，是所有成本第二高者，也因如此優良的人員排班機制將可顯著提昇公司之競爭力。再者航空人員排班問題也受相關法規的限制，在求解期望成本最小化屬多重限制考量下NP hard問題。在過去多數研究為降低此問題之複雜性將問題切割成「勤務組成產生」問題(Crew Pairing Problem; CPP)以及「勤務指派」問題(Crew Rostering Problem; CSP)。是將各航段(Sector)組成群組亦即勤務組合(Pairing)，再將勤務指派到每組的空服員。惟國內航線因航班密集以及飛航時間較短，因此，傳統上係以勤務組合為單位做排班基礎，致使因排班的單位過大而造成排班的準確性降低以及在突發狀況發生時應變不易。因此本研究亦提出以「航段」為排班基礎，透過較小的排班單位之設計提升排班的準確性以及人員的利用率。
本研究以Java程式語言為基礎，發展基因演算法進行排班問題求解，並透過基因演算法多點搜尋的特色，求得近似最佳的排班組合與最適排班人數。

關鍵字

空勤組員排班問題 ； 基因演算法 ； 前/後艙航段指派問題 ； 航段為基之排班

並列摘要

After acceded to the World Trade Organization (WTO), domestic flight industry faced the competition from foreign competitor drastically. Companies in such industry must improve their performance, such as saving cost or improved profitability, to outperform their opponents. In such industries, the crew cost is about 10%~15% of total cost. Therefore, how to save the crew cost is one of the most important issues.
Due to characteristics of high density takeoff and short fly time, one of domestic airline must develop a more sophisticated flight plan than international airlines. In the thesis, a crew scheduling system is proposed to improve the competitive predominance. The Crew Sched-uling Problem had been simplified conventionally by decomposing it into two sub problems—namely the Crew Pairing Problem and the Crew Roistering problem due to high complexity of calculation. In the Crew Pairing Problem, sectors first grouped for pairings and after that the pairings are assigned to the crew.
Domestic airline with high density takeoff and short fly time characteristic the traditional model decreases the schedule accuracy and manpower utility. Therefore, in this thesis, the Crew Scheduling Problem thus focused on the “sector” for improves the performance.
In this thesis, a Crew Scheduling Problem is addressed. Then a Genetic Algorithm implemented by JAVA is proposed to solve the problem. Experiment results shows that the proposed algorithm find an approximate optimal solution rapidly.

並列關鍵字

crew scheduling ； sector based reostering ； genetic algorithm ； cockpit/ cabin rostering problem

參考文獻

[6]張育彰，「應用基因演算法於台鐵列車駕駛員排班與輪班整合問題之研究」，國立成功大學交通管理研究所碩士論文，民國九十二年六月。

[9]謝欣宏，「台鐵司機員排班與輪班問題之研究─以基因演算法求解」，國立成功大學交通管理研究所碩士論文，民國九十一年六月。

[13]Anbil, R., E. Gelman , B. Patty , and R. Tanga , “Recent Advances in Crew-Pairing Optimization at American Airlines,” Interfaces, Vol.21, 62–74, 1991.

[16]Beasely, J.E., and P.C. Chu , “A Genetic Algorithm for the Set Covering Problem,” European Journal of Operational Research, Vol. 94, 392-404, 1996.

[18]Byrne, J., “A Preferential Bidding System for Technical Aircrew,” AGI-FORS ,Proc.28., 87-99, 1988.