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

（南京航空航天大學(xué)民航學(xué)院 南京 210016）

0 引 言

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

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

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

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

1 模型描述

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

1.1 模型的數(shù)據(jù)定義

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空閑的結(jié)束時間；Gj為停機位；Qi為航班機型；Di為航班i初始分配到的停機位；D′i為航班調(diào)整后的停機位；ΔT為同一停機位2架航班的最小間隔．

1.2 模型的目標分析

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

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

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

3）多目標優(yōu)化模型

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

2 模型求解

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

2.1 初始解的產(chǎn)生

采用如下方法產(chǎn)生初始可行解：

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

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

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

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

2.2 適應(yīng)度函數(shù)的設(shè)計

采用基于目標優(yōu)劣表現(xiàn)的排序法［12］確定個體適應(yīng)度．適應(yīng)度計算如式（5）所示．

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

2.3 遺傳操作

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

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

3 實驗分析

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

表1 航班信息表

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

表2 停機位預(yù)分配結(jié)果

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

表3 停機位預(yù)分配結(jié)果

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

表4 實時分配結(jié)果

結(jié)果分析：

圖1 航空公司油耗變化圖

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

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

4 結(jié) 論

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

［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］．系統(tǒng)工程，2004，22（7）：103－105．

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

［4］熊 杰，張 晨．基于飛機滑行油耗的樞紐機場停機位分配研究［J］．交通運輸系統(tǒng)工程與信息，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］朱世群．大型機場停機位實時調(diào)配問題的研究［D］．南京：南京航空航天大學(xué)，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］．南京：南京理工大學(xué)，2008．

［9］戴順南．機場停機位分配模型構(gòu)建及算法實現(xiàn)［D］．北京：北京交通大學(xué)，2008．

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

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

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