劉銀輝 袁 琪 姜 雨

(南京航空航天大學(xué)民航學(xué)院 南京 211106)

0 引 言

停機(jī)位指派是指在在停機(jī)位服務(wù)時(shí)間內(nèi)，由運(yùn)控中心將n個(gè)航班合理的指派至m個(gè)停機(jī)位，保證航班運(yùn)行正常一個(gè)過(guò)程，由于大型機(jī)場(chǎng)航班數(shù)量大，停機(jī)位數(shù)量多，屬于NP-hard問(wèn)題.近年來(lái)，停機(jī)位指派優(yōu)化問(wèn)題成為行業(yè)研究熱點(diǎn).Nikulin等[1]以航空器的被牽引數(shù)量最小，停機(jī)位指派與計(jì)劃偏差最小為目標(biāo)構(gòu)建停機(jī)位指派模型.馮程等[2]以旅客出入飛行區(qū)的時(shí)間最少為目標(biāo)建立停機(jī)位指派模型，并選擇滑行路徑優(yōu)化作為提高停機(jī)位指派效率的關(guān)鍵因素.Prem等[3]從成本、運(yùn)營(yíng)收入、機(jī)場(chǎng)魯棒性等方面建立多目標(biāo)指派模型.Deng等[4]以最短化旅客的步行距離、最小化停機(jī)位空閑時(shí)間和合理利用大型停機(jī)位作為優(yōu)化目標(biāo)構(gòu)建模型，并設(shè)計(jì)改進(jìn)了自適應(yīng)粒子群算法進(jìn)行求解.Sena[5]以最短化旅客步行距離為目標(biāo)，并考慮指派到離機(jī)場(chǎng)購(gòu)物區(qū)最近的旅客數(shù)量，以促進(jìn)機(jī)場(chǎng)銷售運(yùn)營(yíng).姜雨等[6]設(shè)計(jì)了以滑行道路徑規(guī)劃在上、以停機(jī)位再分配在下的雙層規(guī)劃模型，為場(chǎng)面運(yùn)行中停機(jī)位再指派多目標(biāo)模型的建立提供了新思路.對(duì)于由多個(gè)相互制約影響的單目標(biāo)組成的多目標(biāo)模型，現(xiàn)有求解方法包括優(yōu)先級(jí)法[7]、線性加權(quán)法[8]等.也有研究采用約束法將其轉(zhuǎn)化為單目標(biāo)模型并用啟發(fā)式算法[9-10]求解.

目前對(duì)停機(jī)位指派的研究大多集中于對(duì)停機(jī)位運(yùn)行效率、航空公司運(yùn)行成本或是旅客滿意度等單個(gè)或兩個(gè)主體進(jìn)行，其優(yōu)化結(jié)果難以滿足多方利益.由此可見(jiàn)，綜合考慮機(jī)場(chǎng)、航空公司和顧客三個(gè)利益主體進(jìn)行的停機(jī)位指派優(yōu)化研究有其必要性和先進(jìn)性.因此本文兼顧多方利益，同時(shí)融入航空公司間公平性原則，構(gòu)建停機(jī)位指派多目標(biāo)優(yōu)化模型，并尋找有效求解方法，為大型機(jī)場(chǎng)停機(jī)位調(diào)度提供決策依據(jù).

1 模型建立

1.1 模型假設(shè)

1) 在停機(jī)位指派之前，航班的基本信息和停機(jī)位狀態(tài)均齊備已知.

2) 停機(jī)位指派在實(shí)際運(yùn)行時(shí)是連續(xù)的、動(dòng)態(tài)的，假設(shè)只指派一個(gè)時(shí)間段內(nèi)的航班.

3) 機(jī)場(chǎng)的所有停機(jī)位足夠?yàn)闀r(shí)間段內(nèi)每個(gè)航班提供?？糠?wù).

4) 航班從指定的停機(jī)位到跑道端、從安檢點(diǎn)到登機(jī)口、從停機(jī)位至行李提取點(diǎn)的距離均為固定且已知的數(shù).

5) 本文的航班指一個(gè)航班對(duì).

1.2 模型建立

1.2.1目標(biāo)函數(shù)

文中以停機(jī)位的占用時(shí)間均衡為基本目標(biāo)，旨在提高機(jī)場(chǎng)停機(jī)位的利用效率，使停機(jī)位的保障人員有一個(gè)合適的平均勞動(dòng)強(qiáng)度。此外，旅客步行時(shí)間是影響機(jī)場(chǎng)服務(wù)水平評(píng)價(jià)和航空公司印象的重要標(biāo)準(zhǔn)之一，飛機(jī)的滑行油耗成本是航空公司總運(yùn)行成本的重要部分.但為使旅客步行距離最小，擁有旅客數(shù)量少的航空公司的航班往往被指派到遠(yuǎn)機(jī)位，同理為降低總油耗將會(huì)使擁有航空器機(jī)型小的航空公司的航班被指派到里跑道端較遠(yuǎn)的停機(jī)位.綜上，本文考慮機(jī)場(chǎng)、旅客與航空公司利益設(shè)置下列目標(biāo)函數(shù).

(1)

(2)

(3)

(4)

(5)

式(1)為最小化各停機(jī)位占用時(shí)間平方和，Z1值越小，代表機(jī)場(chǎng)停機(jī)位利用率越高；式(2)為最小化平均每旅客步行時(shí)間，一般來(lái)說(shuō)，Z2值越小，旅客滿意度越高；式(3)為最小化總滑行油耗成本，Z3值越小，航空公司的利潤(rùn)更能得到保障；式(4)為各航空公司之間在每旅客平均步行時(shí)間上的均衡，式(5) 為各航空公司之間在滑行的成本上的均衡程度。Z1、Z2、Z3值若均在較小的合理范圍內(nèi)，這說(shuō)明機(jī)場(chǎng)、航空公司和旅客三方的利益得到了均衡與保障，Z4、Z5值越小，則代表航空公司之間的指派越公平.

1.2.2約束條件

(6)

(7)

(8)

(9)

(10)

(11)

式中：T為同一停機(jī)位上連續(xù)兩航班之間最短間隔時(shí)間；δ為被指派到相鄰兩停機(jī)位的兩航班的最小間隔；σ為被指派到遠(yuǎn)機(jī)位的航班停機(jī)時(shí)間限制；U為足夠大的一個(gè)值；Pfi為航班fi使用的航空器型號(hào)；Pgk為停機(jī)位gk的類型；Zfi,fj為輔助變量，航班fi為航班fj的前序航班，當(dāng)航班fi和航班fj指派到同一個(gè)停機(jī)位，Zfi,fj的值等于1，反之為0；K為遠(yuǎn)機(jī)位編號(hào).

式(6)為每個(gè)航班都需要被指派一個(gè)停機(jī)位，且只能被指派到一個(gè)停機(jī)位；式(7)為每個(gè)停機(jī)位在同一個(gè)時(shí)段里面只能供一個(gè)航空器?？?；式(8)為派到相同停機(jī)位的連續(xù)兩個(gè)航班之間必須有相應(yīng)的間隔時(shí)間；式(9)為停機(jī)位之間最小安全鄰近間隔約束，即指派到相鄰?fù)C(jī)位的兩個(gè)航班，要注意推入與推出的最小時(shí)間間隔，以避免相鄰航空器發(fā)生碰撞；式(10)為停機(jī)位與機(jī)型大小約束；式(11)為盡量使停機(jī)時(shí)間小于σ的航班不指派到遠(yuǎn)機(jī)位所做的約束條件，以免為了實(shí)現(xiàn)第一個(gè)目標(biāo)函數(shù)而將一定數(shù)量航班分配到遠(yuǎn)機(jī)位.

2 算法設(shè)計(jì)

使用遺傳算法求解時(shí)將對(duì)各個(gè)目標(biāo)設(shè)置優(yōu)先級(jí)，五個(gè)目標(biāo)將分別被設(shè)置為第一優(yōu)先級(jí)進(jìn)行五次試驗(yàn).采用十進(jìn)制整數(shù)編碼的方式，染色體上的基因代表停機(jī)位編號(hào)，染色體長(zhǎng)度為航班總數(shù)，根據(jù)停機(jī)位編號(hào)隨機(jī)生成初始種群，并根據(jù)目標(biāo)函數(shù)與優(yōu)先級(jí)計(jì)算個(gè)體適應(yīng)度。經(jīng)過(guò)交叉、變異操作后，選擇目標(biāo)函數(shù)值最小的N個(gè)個(gè)體進(jìn)入新種群，其中交叉過(guò)程為奇數(shù)染色體與偶數(shù)染色體進(jìn)行多點(diǎn)交叉，變異操作選擇隨機(jī)變異法[11].

NSGA-II算法不設(shè)置目標(biāo)優(yōu)先級(jí)，而是同時(shí)對(duì)5個(gè)目標(biāo)進(jìn)行求解.NSGA-II算法在遺傳算法的基礎(chǔ)上，增加非支配排序和聚集距離排序的過(guò)程[12].步驟為

步驟1將父代與經(jīng)過(guò)交叉、變異后的子代合并，得到2N個(gè)個(gè)體.

步驟2對(duì)2N個(gè)個(gè)體計(jì)算多個(gè)目標(biāo)函數(shù)值，采用規(guī)模為2的錦標(biāo)賽方式，即兩兩個(gè)體進(jìn)行比較，判斷每個(gè)個(gè)體之間是否存在支配關(guān)系，支配關(guān)系指的是一個(gè)個(gè)體A的各個(gè)目標(biāo)函數(shù)指標(biāo)均比另一個(gè)個(gè)體B優(yōu)越，則稱A支配B，否則為非支配關(guān)系.

步驟3根據(jù)個(gè)體之間的關(guān)系分為若干層，每層里面的個(gè)體為非支配關(guān)系，上層對(duì)下層的個(gè)體為支配關(guān)系.

步驟4對(duì)每層的非支配的個(gè)體計(jì)算它們的聚集距離，個(gè)體的聚集距離等于與其最鄰近的兩個(gè)個(gè)體在每個(gè)單目標(biāo)上的目標(biāo)函數(shù)值上的差距相加，聚集距離大的個(gè)體適應(yīng)度越高.

步驟5由上層開(kāi)始選取N個(gè)個(gè)體組成新的子代種群.

圖1為NSGA-II的新種群構(gòu)成示例。

圖1 NSGA-II的新種群構(gòu)成示例

3 仿真驗(yàn)證

數(shù)據(jù)來(lái)源于長(zhǎng)沙黃花國(guó)際機(jī)場(chǎng)2020年4月8日的航班運(yùn)行數(shù)據(jù)，選取當(dāng)天08:30—18:00時(shí)間段內(nèi)由五個(gè)規(guī)模不等的航空公司服務(wù)的76個(gè)國(guó)內(nèi)進(jìn)離港航班進(jìn)行仿真驗(yàn)證，航班數(shù)據(jù)示例見(jiàn)表1，其中一條航班數(shù)據(jù)為兩個(gè)航班組成的一個(gè)航班對(duì).選擇機(jī)場(chǎng)T2航站樓停機(jī)位號(hào)為211-216、221-228的14個(gè)近機(jī)位及241、242的2個(gè)遠(yuǎn)機(jī)位共16個(gè)機(jī)位為研究對(duì)象，編號(hào)為1-16，所在位置見(jiàn)圖2，停機(jī)位的基本狀態(tài)信息見(jiàn)表2，其中遠(yuǎn)機(jī)位的旅客步行距離在實(shí)際步行距離上加上了一段“懲罰距離”，以更符合實(shí)際運(yùn)行過(guò)程中的旅客心理.另外在模型中涉及到的其他參數(shù)設(shè)置見(jiàn)表3.

表1 研究時(shí)段內(nèi)進(jìn)離港航班數(shù)據(jù)示例

圖2 長(zhǎng)沙黃花國(guó)際機(jī)場(chǎng)T2航站樓停機(jī)位編號(hào)示意圖

3.1 基于遺傳算法的停機(jī)位指派結(jié)果分析

使用Matlab R2018a版本，按照遺傳算法的思想，采用優(yōu)先級(jí)的方法為多目標(biāo)模型進(jìn)行編程和運(yùn)算.根據(jù)多次實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，當(dāng)種群為100，最大進(jìn)化次數(shù)為500次是速度最快、效果最好，因而將種群大小設(shè)置100，最大進(jìn)化次數(shù)為500，交叉概率設(shè)置為0.8，變異概率為0.08，產(chǎn)生的不同目標(biāo)優(yōu)先級(jí)最高條件下的優(yōu)化結(jié)果見(jiàn)表4.

表3 實(shí)例參數(shù)設(shè)置

表4 基于遺傳算法求解的五種條件下的結(jié)果比較

由表4可知：當(dāng)以停機(jī)位占用時(shí)間均衡為優(yōu)先級(jí)最高的目標(biāo)條件下，此時(shí)停機(jī)位的利用率較高，但Z4和Z5的目標(biāo)函數(shù)值均偏大，說(shuō)明此時(shí)以機(jī)場(chǎng)效率作為單個(gè)目標(biāo)考慮會(huì)削弱公平性.

將旅客步行時(shí)間最少設(shè)置為目標(biāo)優(yōu)先級(jí)最高的條件下，也出現(xiàn)Z4和Z5的函數(shù)值普遍偏大的情況，并且當(dāng)設(shè)置滑行油耗最少為優(yōu)先級(jí)最高的目標(biāo)時(shí)，停機(jī)位的占用時(shí)間指標(biāo)非常大，比最低Z1值高出了25%，說(shuō)明算法為了降低油耗將航空器分配到了離跑道端較近的停機(jī)位上，導(dǎo)致了離跑道端較遠(yuǎn)的停機(jī)位得不到有效利用.

當(dāng)目標(biāo)為航空公司的旅客步行時(shí)間最均衡和航空公司的航班滑行時(shí)間最均衡時(shí)，代表停機(jī)位占用時(shí)間的目標(biāo)值過(guò)大，說(shuō)明只考慮絕對(duì)公平也會(huì)導(dǎo)致機(jī)位資源上的浪費(fèi).

3.2 基于NSGA-II算法的停機(jī)位指派結(jié)果分析

使用Matlab編寫NSGA-II算法程序，對(duì)五個(gè)目標(biāo)同時(shí)進(jìn)行求解仿真.經(jīng)過(guò)多次試驗(yàn)，將種群大小設(shè)置為100，進(jìn)化次數(shù)為800，同樣以0.8的概率進(jìn)行交叉，以0.08的概率變異. 使用NSGA-II算法對(duì)模型的五個(gè)目標(biāo)同時(shí)進(jìn)行求解后得到的多個(gè)pareto解中，人工分別側(cè)重Z1，Z2，Z3，Z4，Z5值最優(yōu)條件選出5個(gè)解，見(jiàn)表5.

表5 基于NSGA-II算法求解的pareto前沿解

由表5可知：各個(gè)指派方案互不支配.相比隨機(jī)指派方案，使用NSGA-II算法求解得到的不同條件下的方案，其各個(gè)目標(biāo)值均在一個(gè)合適的范圍內(nèi)，其中Z1各值均在150以下，Z4值均保持在0.35以下，Z5值均保持在0.20以內(nèi)，其中有4組方案的Z5值在0.15以下，Z2，Z3在個(gè)別條件下比隨機(jī)指派方案的目標(biāo)函數(shù)值高，但增加幅度不到6%.

在產(chǎn)生的pareto解中選擇一種方案與隨機(jī)指派方案進(jìn)行對(duì)比，見(jiàn)圖3，任務(wù)框中的數(shù)字代表航班所屬航空公司.

由圖3可知：隨機(jī)指派條件下的停機(jī)位指派將4個(gè)航班分配到了遠(yuǎn)機(jī)位，G10沒(méi)有得到利用，G7、G3等停機(jī)位則十分繁忙，需要服務(wù)4～5個(gè)航班，而NSGA-II求解模型得到的停機(jī)位指派方案各個(gè)近機(jī)位得到了均衡利用，均有2～4個(gè)航班，且只有1個(gè)航班被分配到遠(yuǎn)機(jī)位.停機(jī)位號(hào)為211-216即編號(hào)為1-6的近機(jī)位步行時(shí)間較遠(yuǎn)，而基于NSGA-II算法得出的方案中，對(duì)于標(biāo)號(hào)為5的航空公司的小型航班在使得旅客步行時(shí)間盡可能小的情況下，沒(méi)有被分配到遠(yuǎn)機(jī)位，而是大部分被分配到了步行距離稍遠(yuǎn)的近機(jī)位，說(shuō)明算法保障了第二個(gè)目標(biāo)與第四個(gè)目標(biāo)的同時(shí)實(shí)現(xiàn).

圖3 停機(jī)位指派甘特圖

將NSGA-II算法在各個(gè)條件下的目標(biāo)函數(shù)值與遺傳算法相比，發(fā)現(xiàn)基于NSGA-II算法求的Z1值均優(yōu)于遺傳算法，其值相比遺傳算法平均降低17%；Z4值在大多數(shù)條件下優(yōu)于遺傳算法，且變化幅度穩(wěn)定；Z5值雖在大部分情況下高于遺傳算法所得到的目標(biāo)值，但其變化幅度仍比遺傳算法要穩(wěn)定，見(jiàn)圖4.由圖4可知：相比遺傳算法，基于NSGA-II算法求解的Z2值在大部分條件下有所升高，但其最大變化幅度在30%以內(nèi)，平均每旅客步行時(shí)間仍控制在4 min以下.基于NSGA-II算法求解的Z3值與其變化幅度相比遺傳算法均有增加，但其變化幅度的增加仍控制在10%以內(nèi)，表明算法在用場(chǎng)面滑行總油耗的合理增加換取停機(jī)位占用時(shí)間均衡，以保障停機(jī)位資源利用效率.

圖4 不同條件下遺傳算法與NSGA-II算法

綜上所述，在選取合適的算法運(yùn)用于該模型時(shí)，不僅可以兼顧機(jī)場(chǎng)停機(jī)位利用率、旅客步行距離和航空器滑行油耗等因素，還能使得航空公司之間在滑行距離與旅客滿意度上也保持相對(duì)的公平，滿足了旅客和航空公司的服務(wù)要求，促進(jìn)了停機(jī)位的有效利用.

4 結(jié) 論

1) 從大型機(jī)場(chǎng)停機(jī)位指派過(guò)程中涉及的機(jī)場(chǎng)、航空公司與旅客的利益出發(fā)，構(gòu)建了基于公平性的停機(jī)位指派多目標(biāo)優(yōu)化模型.

2) 使用NSGA-II算法對(duì)模型進(jìn)行求解，結(jié)果發(fā)現(xiàn)各個(gè)條件下的解的目標(biāo)函數(shù)值均在合理的范圍之內(nèi)，其中Z1各值均在150以下，Z4值均保持在0.35以下，Z5值均保持在0.20以內(nèi)，緩解了機(jī)位指派過(guò)程中提高了效率卻要犧牲公平性的問(wèn)題，為停機(jī)位指派中協(xié)調(diào)各方利益提供了一種可行思路.

3) NSGA-II算法求解得到的方案比隨機(jī)指派方案求解得出的Z1目標(biāo)函數(shù)值均優(yōu)，使停機(jī)位利用效率提高8%.相比遺傳算法，NSGA-II算法求解得到的Z1各值平均降低17%，其他各值的變化幅度均在合理范圍內(nèi)，驗(yàn)證了模型與求解的有效性.

4) 使用航班數(shù)據(jù)均為固定已知，下一步研究可考慮如何在大面積延誤、航班取消等應(yīng)急情況下兼顧公平性進(jìn)行停機(jī)位指派，使研究更符合實(shí)際運(yùn)行情況.