[發明專利]基于遺傳算法的飛機航班規劃方法

無效

• 申請號: 200810220652.0
• 申請日: 2008-12-31
• 公開（公告）號: CN101464966A
• 公開（公告）日: 2009-06-24
• 發明（設計）人: 張軍;詹志輝;黃韜
• 申請（專利權）人: 中山大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06Q10/00;G06Q50/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域：

本發明涉及市場規劃和智能計算兩大領域，主要涉及一種運用遺傳算法優化飛機航班規劃的方法。

技術背景：

航班規劃是指對航空公司的有限資源(如飛機、航線、資金、人員等)進行配置，規定正班飛行的航線、機型、飛行頻率及班期時刻。一般來說，廣義的航班規劃包括了五個方面的內容，按規劃進行的先后順序分別是市場分析和預測、航班頻率和時刻的確定、機型的指派、飛機的排班和機組的排班，狹義的航班規劃則只包含了前三個方面的內容。本發明只在狹義航班規劃的范疇中進行討論，根據市場分析和預測結果對航班的頻率進行確定和機型進行指派。相應的優化問題就是研究如何對有限的資源進行合理的配置，即確定每條航線應該投入什么機型或者是機型的組合以及其飛行頻率為多少才能提高工作效率和經濟效益。

在飛機調度問題的流程中，航班規劃屬于市場規劃的范疇。通常由市場部根據機務部調度員提供的次日可用每種機型和飛機架數以及其它的具體的實際情況制定次日的航班計劃。航班計劃的制定在很多情況下依賴于工作人員的經驗，而隨著航空公司飛機數的增加以及航線的復雜化，人工排班已經滿足不了要求。因此，研究一種算法，使得可以利用計算機科學、高效、合理地制定航班計劃具有重大的意義。

解決航班規劃問題，傳統的方法是整數規劃及線性規劃等數學規劃方法。由于航班規劃是一個動態多變的過程，隨著問題規模的增大及目標函數的復雜化，傳統的數學方法就出現了求解復雜度大、運算時間長等缺陷，難以適應實際的應用需求。近年來，智能計算方法逐漸開始在飛機調度問題上得到了應用。本發明針對飛機調度問題中的航班規劃環節論述了如何用遺傳算法解決航班規劃的問題，實現在航班正常運行情況下，航空公司能實現最大的利益。利益最大化問題是一個最優化問題，因此遺傳算法在其上可以得到很好的應用。

發明內容：

本發明將遺傳算法運用到飛機航班規劃問題的解決中。遺傳算法求解飛機航班規劃問題的步驟為：

(1)初始化算法的各個參數，建立遺傳算法的第一代種群，其中每個個體為一種航班安排的方案。染色體的編碼為：

CH＝[x₁₁，x₁₂，…，x_1N，x₂₁，…x_2N，…x_MN]＝[x₁，x₂，…，x_M*N]

其中，x_ij的具體含義為機型i在從城市A到城市j的航線上有x_ij次往返。

(2)計算種群中每個個體的適應值。適應值函數的定義為：

f=2Σi=1MΣj=1N(RijVijSixij-CiTijxij)]]>

其中R_ijV_ijS_ix_ij是客座率乘以座位容量乘以票價再乘以班次，得到總收入。C_iT_ijx_ij是小時飛行成本乘以飛行時間再乘以班次，得到總成本。公式前面帶有系數2，這是由于x_ij表示的是往返次數，而不是單程次數。

(3)根據一定的約束條件對種群內的非法解進行修補，考慮的約束條件如下。