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

0 引 言

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

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

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

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

1 模型描述

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

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

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

1.2 模型的目標(biāo)分析

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

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

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

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

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

2 模型求解

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

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

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

1）讀取航班信息，停機(jī)位信息，讀取初始航班可停靠的停機(jī)位集合．

2）對(duì)于第一個(gè)航班，隨機(jī)選取集合中的一個(gè)停機(jī)位，作為該航班的停機(jī)位，然后更新該停機(jī)位的空閑開(kāi)始時(shí)間，使該停機(jī)位的空閑開(kāi)始時(shí)間等于該航班的離港時(shí)間．

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

4）以此類(lèi)推，輸出可行解．

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

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

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

2.3 遺傳操作

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

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

3 實(shí)驗(yàn)分析

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

表1 航班信息表

采用首都機(jī)場(chǎng)11個(gè)典型的近停機(jī)位進(jìn)行實(shí)驗(yàn)，其中1，2，3，5，6，11號(hào)停機(jī)位為大型停機(jī)位；8，9，10號(hào)停機(jī)位為中型停機(jī)位；4，7號(hào)停機(jī)位為小型停機(jī)位．預(yù)先分配的停機(jī)位見(jiàn)表2．

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

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

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

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

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

結(jié)果分析：

圖1 航空公司油耗變化圖

因?yàn)樾⌒惋w機(jī)只有1架，可將其調(diào)整到4號(hào)停機(jī)位，也可調(diào)整到7號(hào)停機(jī)位，由于7號(hào)停機(jī)位的滑行時(shí)間比4號(hào)停機(jī)位少4min，因此搜索出7號(hào)停機(jī)位作為最優(yōu)解，使總油耗降低．

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

4 結(jié) 論

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

［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ī)場(chǎng)停機(jī)位分配問(wèn)題研究［J］．系統(tǒng)工程，2004，22（7）：103－105．

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

［4］熊 杰，張 晨．基于飛機(jī)滑行油耗的樞紐機(jī)場(chǎng)停機(jī)位分配研究［J］．交通運(yùn)輸系統(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］朱世群．大型機(jī)場(chǎng)停機(jī)位實(shí)時(shí)調(diào)配問(wèn)題的研究［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］孔佳玉．機(jī)場(chǎng)停機(jī)位分配建模及其遺傳算法研究［D］．南京：南京理工大學(xué)，2008．

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

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

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

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