利用不等式方法為基礎的多目標遺傳演算法解決航空排程問題

【类型】学位论文

【作者】周大源 

【关键词】 基因演算法,不等式方法,排程,多目標,最佳化

【摘要】在航空業的排程問題中，班機排程與人員任務航段組合問題分別與燃油成本及人事成本高度相關。在進行班機排程與人員任務航段組合時，有幾項目標，例如地停時間、流量平衡、轉移時間、人員轉機成本、過夜成本、飛行時數、飛航任務期間等等目標都必須考慮。要針對這些目標同時進行最佳化，是相當困難的。許多問題尚待解決，如下所示。1. 大多數與班機排程與人員任務航段組合相關的研究都使用集合分割或集合覆蓋的模型。排班人員必須 (1) 列舉所有班次的子集合 (2) 給定成本值，還要 (3) 同時檢查可行性。這樣的工作相當耗時，因為實際的班次子集合數與班次數量成指數次方相關。2. 經由列舉而得之班次子集合的數量通常太小，以致於無法覆蓋全體解空間。 所以，就算能夠找到最佳解，也僅是被侷限在列舉而得的集合中。3. 當使用傳統最佳化演算法求取子集合的組合並使成本最小時，必須確保每一個班次恰巧被覆蓋一次。這會造成檢測班次出現次數的額外成本。4. 在傳統的解決方案中，班機數量與人員組數無法預先指定，因為這些數值只能在最佳化演算法完成後獲得。5. 所有列舉出的子集合都必須依據各項目標來評定，諸如地停時間、流量平衡、轉移時間、人員轉機成本、過夜成本、飛行時數、飛航任務期間，而給定一個成本值。此成本值之指定是相當困難的，因為這與該領域之知識高度相關，而且通常是非線性的。若給定不適用的成本值，會有單目標最佳化問題的特性，如最佳化時的偏差，而且會在多個目標的影響下產生混淆。因此，在數學定式的階段，我們提出新的排列為基礎的模型，具有以下特色：1. 本論文提出的排列為基礎的模型可以節省事先列舉所有可能解片段的時間消耗。2. 排列為基礎的模型可以覆蓋整個搜尋空間。因此，這種方法會有更多的機會可以找到全域最佳解。3. 本論文提出的排列為基礎的模型可以確保每一個班次都只被覆蓋一次，藉以節省檢測覆蓋次數的時間消耗。4. 本論文提出的排列為基礎的模型提供一個新的方法，讓排班人員可以預先指定班機數量或是人員組數。5. 應用多項目標的方式來定義問題，各種目標可以分開來考慮，不需要以指定成本值的方式來進行。就算在所有目標的最佳化定義與單位不同時，所有目標都能夠個別地考慮。在解決方案階段，我們應用不等式方法為基礎的多目標遺傳演算法來解決班機排程問題人員任務航段組合問題。不等式方法為基礎的多目標遺傳演算法原本用於數值最佳化的控制器設計問題。利用不等式方法為基礎的多目標遺傳演算法，設計者可以藉由輔助向量指標調整解答的範圍。為了讓不等式方法為基礎的多目標遺傳演算法更加適合解決班機排程與人員任務航段組合問題，我們加入某些改變，例如染色體編碼、修復策略、交叉方式，以及突變方式。這項作法有以下特性：1. 在班機排程與人員任務航段組合問題中，與定式階段相同的排列為基礎之編碼方式，可以確保每一個班次恰巧被覆蓋一次。2. 另外，在人員任務航段問題中所採用的區段式排列為基礎的編碼方式，會將所有班次分成三個區段，如較早班次、較晚班次，以及浮動班次。以此方式可以增強不等式為基礎的多目標遺傳演算法找到符合飛行任務期間的最佳解。3. 為了要克服隨機產生候選解時會造成大量違反值的問題，我們使用修復策略，亦即針對每一組候選解以起飛時間排序來進行修復。4. 區段式順序為基礎的交叉方式可以進行一個比一般常用的部分對應交叉法更為穩定的演化。另外，它也可以讓每一個新生的子代保有在編碼方式中所定義的三區段特徵。5. 另外，區段式的突變方式可以繼承一般常用的交互式突變的優點，也可以保有編碼階段中定義的三階段特徵。在班機排程問題中，實驗結果顯示本論文提出的方法可以在班機數量足夠的情況下找到最佳解。另一方面，當班機數量不足且違反值較小時，排班人員可以針對演算法獲得的解答進行時間的微調。在人員任務航段組合問題中，實驗顯示本論文提出的以不等式方法為基礎的多目標遺傳演算法可以解決人員任務航段組合問題，並獲得以分支-界定法驗證過的最少組數。以不等式方法為基礎的遺傳演算法，可以有效地解決班機排程與人員任務航段組合問題。換句話說，排程人員可以在短時間內解決這些問題，而不需要像傳統方法一樣需要耗時間列舉並驗證可行性。因此，排班人員可以更進一步地考量重要的議題，例如提出更好、成本更低、利潤更高的飛航班表。

【学位授予单位】国立中山大学

【学位授予年度】2016

【读秀链接】读秀链接