基于延誤油耗優化原則的停機位實時分配算法＊

（南京航空航天大學民航學院 南京 210016）

0 引 言

停機位是機場的重要資源，高效、合理的分配停機位是提高機場運行效率的重要途徑之一．關于停機位分配問題，國內外很多學者已經做了很多研究．主要有兩方面內容：（1）停機位預分配問題；（2）停機位實時分配問題．

Babic等［1］建立了以離港旅客和進港旅客的總步行距離最短為優化目標的停機位分配模型，對模型的求解采用了分枝定界法．文軍等［2］將停機位分配抽象成為排序問題，采用“先到先服務”規則通過標號算法進行求解，通過模型優化提高了停機位使用效率．王力等［3］提出了以旅客登轉機時間、機型與停機位類型匹配為優化目標，同時考慮航班性質、航班數量與密度、停機時間的多目標停機位分配的數學模型，并設計求解模型的禁忌搜索算法．熊杰等［4］在考慮跑道和滑行道的基礎上，建立了飛機油耗總和最小的分配目標．

Yu等［5］針對航班大面積延誤時進行實時調整，并采用了遺傳算法進行求解．朱世群［6］設計了以旅客和機場地面服務人員的移動總距離最短為目標，并采用遺傳算法進行求解的停機位實時調整策略．Tang［7］研究了停機位短缺和航班隨機延誤下的停機位實時調整．

停機位實時分配的研究還比較少，大部分研究都是通過模型和算法達到高效合理利用資源的目的［8－12］．然而，從延誤油耗和從航空公司相同機型所承擔延誤油耗均衡的角度來考慮停機位實時分配問題的文章還未曾發現．航空運輸業是一個高風險、高投入的資金密集型行業，平均利潤只有3%～6%，降低成本對于每個航空公司都具有非常重要的意義，而飛機的油耗成本占到總成本的1／3左右．由于航空公司規模各不相同，并且各航空公司在某一段時間內涉及的航班架次和機型大小也各不相同，不能籠統的要求各航空公司的耗油均衡，因此本文建立了以延誤油耗最低和各航空公司相同機型所承擔延誤耗油均衡為目標的停機位適時調整模型，采用遺傳算法進行求解，所得結果表明此模型和算法在停機位實時分配中是合理而可行的．

1 模型描述

延誤油耗優化原則：降低由于航班延誤所產生的延誤油耗，并使各航空公司相同機型所承擔的延誤油耗基本均衡．由于調整之后個別航班延誤油耗可能有增有減，因此，在降低油耗的同時使各航空公司的油耗變化基本均衡．

1.1 模型的數據定義

Pmn為n公司m型飛機油耗變化占所有公司m型飛機油耗變化的百分比；COi為航班i每分鐘的耗油量；CTi為飛機滑行到停機位i所消耗的時間；COmn為n公司m型飛機的耗油量；Bmn為n公司m型飛機分配到的停機位集合；Xij的意義為，若航班i分配到停機位j則Xij為1，否則Xij為0；Rij為航班到達停機位時間；Lij航班離開停機位時間；K1i為停機位i空閑的開始時間；K2i為停機位i空閑的結束時間；Gj為停機位；Qi為航班機型；Di為航班i初始分配到的停機位；D′i為航班調整后的停機位；ΔT為同一停機位2架航班的最小間隔．

1.2 模型的目標分析

1）延誤產生的總油耗最低 要求停機位的實時調整使航班由于延誤增加的油耗降到最低，通過最小化航班調整前后增加的滑行時間來實現．

式中：（CTD′i－CTDi）為航班i增加的滑行時間．三項相乘的結果為延誤增加的油耗，求其最小值即可滿足延誤增加的總油耗最低的目標．

2）延誤油耗均衡 要求各航空公司相同機型油耗的均衡．通過最小化各公司相同機型油耗變化的百分比與平均值之間的差距來實現延誤油耗的均衡．

3）多目標優化模型

約束條件：式（1）是每個航班都只分配一個停機位；式（2）滿足停機位與機型相匹配；式（3）表示停機位的空閑時間大于最低安全時間；式（4）表示停機位空閑的開始時間要早于航班的到港時間并且空閑的結束時間要晚于航班離港時間．

2 模型求解

根據停機位分配的特點，采用遺傳算法對多目標優化模型進行求解．

2.1 初始解的產生

采用如下方法產生初始可行解：

1）讀取航班信息，停機位信息，讀取初始航班可?？康耐C位集合．

2）對于第一個航班，隨機選取集合中的一個停機位，作為該航班的停機位，然后更新該停機位的空閑開始時間，使該停機位的空閑開始時間等于該航班的離港時間．

3）對于第二個航班，重新調整其可?？康耐C位集合，然后從中選取某一停機位，更新停機位空閑開始時間，若無進停機位可分，跳轉到2）．

4）以此類推，輸出可行解．

2.2 適應度函數的設計

采用基于目標優劣表現的排序法［12］確定個體適應度．適應度計算如式（5）所示．

式中：n為目標函數個數；N為種群個體總數；Xj為種群的第j個個體；Ri（Xj）為種群所有個體對目標i優劣排序后個體j在序列中的序號；Fi（Xj）為Xj對目標i所得的適應度；k為（1，2）區間的常數，用于加大個體的函數值表現最優時的適應度．

2.3 遺傳操作

1）基于航班交換的變異：采用交換變異的方式，對航班基因串進行變異：即在航班基因串中隨機選擇兩位置，交換該位置處的兩航班基因．

2）Pareto最優解更新策略．算法執行過程中采用Pareto最優解作為選擇判斷條件，最終得到多目標優化問題的最優解集．

3 實驗分析

采用首都機場實際運行的22個航班數據（見表1）．涉及到國航、東航、南航和海航4個航空公司．根據實際操作，得到大型飛機耗油46kg／min，中型飛機耗油28kg／min，小型飛機耗油12kg／min．

表1 航班信息表

采用首都機場11個典型的近停機位進行實驗，其中1，2，3，5，6，11號停機位為大型停機位；8，9，10號停機位為中型停機位；4，7號停機位為小型停機位．預先分配的停機位見表2．

表2 停機位預分配結果

飛機從跑道滑行到停機位所消耗的時間見表3．現第7個航班延誤到10：15到港，根據文獻［6］選取10：00～11：00內航班作為實時調整的區間．停機位空閑時間如表3所列，對于此前沒有使用的停機位設置停機位開始時刻為08：00，對于此后沒有使用的停機位，設置停機位空閑結束時刻為14：00．

表3 停機位預分配結果

程序在Matlab7．8．0環境下進行實驗，參數設計如下：交叉概率Pc＝0．8；變異概率Pm＝0．08；初始種群數量N＝50；進化代數T＝300．結果見表4．

表4 實時分配結果

結果分析：

圖1 航空公司油耗變化圖

因為小型飛機只有1架，可將其調整到4號停機位，也可調整到7號停機位，由于7號停機位的滑行時間比4號停機位少4min，因此搜索出7號停機位作為最優解，使總油耗降低．

3）特殊航班保障 本例選擇4號和11號航班為特殊航班，調整后其分配到的停機位未發生變化，滿足此前設定的目標．因此本文的模型，在航班發生延誤時，能在滿足油耗優化原則的前提下，通過調整少量航班使機場運行恢復正常，滿足機場實際運行的要求．

4 結 論

在航班發生延誤時，為降低油耗成本，本文建立了以延誤油耗最小以及各航空公司所承擔延誤油耗成本均衡為目標的停機位實時調整策略，并通過遺傳算法進行求解．通過實驗證明，該停機位實時調整策略是一種合理可行的調整策略，其在兼顧特殊性質航班的同時，能很好降低延誤油耗，均衡各航空公司之間的成本．

［1］BABIC O，TEODOROVIC D，TOSIC V．Aircraft stand assignment to minimize walking［J］．Joumal of Trans－Portation Engineerin，1984，110（3）：55－66．

［2］文 軍，孫 宏，徐 杰，等．基于排序算法的機場停機位分配問題研究［J］．系統工程，2004，22（7）：103－105．

［3］王 力，劉長有，涂奉生．民用機場停機位優化配置［J］．南京航空航天大學學報，2006，38（4）：434－437．

［4］熊 杰，張 晨．基于飛機滑行油耗的樞紐機場停機位分配研究［J］．交通運輸系統工程與信息，2010，10（3）：166－170．

［5］YU Gu，CHRISTOPHER A．Genetic algorithm approch for airport gate assignments for stochastic flight delays［J］．Journal of Transportation Engineering，2000，125（5）：385－389．

［6］朱世群．大型機場停機位實時調配問題的研究［D］．南京：南京航空航天大學，2007．

［7］TANG Chinghui．Real－time gate assignments under temporary gate shortages ans stochastic flight delays［C］／／2009IEEE International Conference on Service Operation，Logistics and Informatics，2009：267－271．

［8］孔佳玉．機場停機位分配建模及其遺傳算法研究［D］．南京：南京理工大學，2008．

［9］戴順南．機場停機位分配模型構建及算法實現［D］．北京：北京交通大學，2008．

［10］鞠姝妹，許 俐．基于GSAA的停機位指派優化問題的研究［J］．交通運輸系統工程與信息，2008，8（1）：139－143．

［11］常 鋼，魏生民．停機位分配問題優化技術［J］．中國民航學院學報，2006，24（2）：25－29．

［12］游進軍，紀昌明，付 湘．基于遺傳算法的多目標問題求解方法［J］．水利學報，2003（7）：64－69．