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

無效

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

1、一種基于遺傳算法的飛機航班規劃方法，其特征在于，該方法包括以下步驟：

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

(2)計算種群中每個個體的適應值。

(3)根據一定的約束條件對種群內的非法解進行修補。考慮的約束條件包括：飛機數量和日利用率約束，機型可用性約束，需求實現約束和降落條件限制。修補的方法為，對不滿足約束條件的個體，將其適應度函數值置為0。

(4)對種群執行輪盤賭選擇算子，選擇出下一代的種群。

(5)對下一代的種群執行交叉和變異算子，其中交叉算子采用單點交叉而變異算子則采用均勻變異。

(6)如果達到結束條件，則輸出飛機航班調度的結果，否則回到步驟(2)。

2、基于權利要求1所述的一種基于遺傳算法的飛機航班規劃方法，其特征在于染色體的編碼為：

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

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

3、基于權利要求1所述的一種基于遺傳算法的飛機航班規劃方法，其特征在于適應值函數的定義為：

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

其中R_ij表示客座率，V_ij表示座位容量，S_i表示票價，C_i表示小時飛行成本，T_ij表示飛行時間。

4、基于權利要求1所述的一種基于遺傳算法的飛機航班規劃方法，其特征在于約束條件的設定為：

飛機數量和日利用率約束：2Σj=1NTijxij≤UiAi,∀i,1≤i≤M,]]>其中T_ij表示飛行時間，A_i表示飛機數量，U_i表示日利用率。對于每一種機型，將其在所有航線上的飛行總時間加起來，必須不能超過總的日利用率。

機型可用性約束：當某機型s對于某航線A→t不可用時，即為該機型在該航線上的航次x_st＝0。

需求實現約束：Lj≤Σi=1Mxij,∀j,1≤j≤N,]]>其中L_j為航線上的各機型飛機總數的下限。

降落條件限制：U′j≥Σi=1Mxij,∀j,1≤j≤N,]]>其中U′_j為從城市A到城市j的航班總數的上限。