基于網(wǎng)絡(luò)流理論的停機(jī)位實(shí)時再分配模型*

劉 芳，宮 華，孫文娟，趙偉麗

(沈陽理工大學(xué) 理學(xué)院，沈陽 110159)

機(jī)場的停機(jī)位是飛機(jī)在地面上的停放位置.機(jī)場停機(jī)位的分配需要考慮班機(jī)機(jī)型大小、起降時刻和停機(jī)位容量等多種因素，需要在一定時限內(nèi)，由機(jī)場調(diào)度指揮中心為進(jìn)港和出港班機(jī)指定合適的停機(jī)位，以保證班機(jī)的正常起降而不發(fā)生延誤.然而，班機(jī)會因?yàn)閻毫拥奶鞖狻C(jī)身機(jī)械問題、機(jī)場安全問題、機(jī)場擁擠、機(jī)場之間的延遲傳播等多種因素導(dǎo)致延誤，使班機(jī)離到港時刻表發(fā)生較大變化.同一停機(jī)位如果某個班機(jī)的離港時刻晚于其他班機(jī)的到港時刻，班機(jī)的調(diào)度就會出現(xiàn)沖突.機(jī)場停機(jī)位管理人員的日常任務(wù)之一就是如何合理地再分配有沖突的班機(jī).如果這種再分配沒有適當(dāng)?shù)臎Q策支持工具，會給停機(jī)位管理人員帶來巨大的困難.科學(xué)、高效的停機(jī)位再分配是機(jī)場各項(xiàng)工作順利進(jìn)行的有效保障，是提升民航產(chǎn)業(yè)服務(wù)能力和競爭力的重要環(huán)節(jié).

對于停機(jī)位再分配算法，國內(nèi)外很多研究人員從不同角度進(jìn)行了廣泛而深入的實(shí)驗(yàn)研究.Dorndorf等使用圖論中的團(tuán)劃分模型解決了確定性和隨機(jī)性的停機(jī)位再分配問題[1]；涂浩以延誤的過站航班為研究對象，提出了一種對延誤的過站航班預(yù)分配停機(jī)位的再分配方案[2]；陳前等基于遺傳算法，建立了以避免沖突為約束的安全停機(jī)位再分配模型[3]；劉長有等人采用粒子群遺傳算法，考慮避免潛在的航班雙推沖突問題，提出了基于運(yùn)行安全的停機(jī)位再分配優(yōu)化模型[4]；Yu等考慮了滑行道調(diào)度問題，提出一種新的啟發(fā)式算法，對每種調(diào)度進(jìn)行成本評估和沖突檢測，求解停機(jī)位再分配問題[5]；Wang等建立了基于停車位重新分配導(dǎo)致的干擾與懲罰最小的目標(biāo)函數(shù)，采用蟻群算法驗(yàn)證了模型的有效性[6]；李亞玲等針對機(jī)場最大化停機(jī)位利用率以及最小化旅客行走路程問題，提出了一種動態(tài)、靈活分配停機(jī)位的禁忌搜索算法[7]；Deng等將遺傳算法和蟻群優(yōu)化算法相結(jié)合，提出了一種兩階段混合算法(GAOTWSH)，用于求解延遲停機(jī)位重新分配問題[8].

從目前對停機(jī)位再分配的研究中可以看出，大多只單方面考慮機(jī)場的利益，兼顧乘客滿意度的模型較少.即便選用多目標(biāo)優(yōu)化模型，綜合考慮了機(jī)場和乘客雙方利益，但模型計(jì)算時間較長.本文是在多商品網(wǎng)絡(luò)流停機(jī)位分配模型[9]的基礎(chǔ)上，對停機(jī)位再分配模型作進(jìn)一步研究，建立了以飛機(jī)燃油消耗成本和對乘客舒適度影響最小為目標(biāo)的實(shí)時再分配模型.該模型兼顧了機(jī)場和乘客的利益，有效減少了對既存的航班分配方案影響程度，降低了傳統(tǒng)機(jī)場再分配模型的時間消耗，具有較好的實(shí)時性.

1 機(jī)場停機(jī)位實(shí)時再分配模型

1.1 問題描述

停機(jī)位再分配問題是指在已分配好初始停機(jī)位的基礎(chǔ)上，根據(jù)航班時刻的實(shí)時變化，對停機(jī)位初始分配方案進(jìn)行實(shí)時調(diào)整，使得航班的停機(jī)位分配更加合理.一般是在確定了延誤航班的到/離港信息的情況下，對延誤航班和相關(guān)航班的停機(jī)位分配做出調(diào)整，以滿足旅客和機(jī)場各部門的要求.研究對象是一個時間段內(nèi)一組航班和一組停機(jī)位之間的調(diào)整.研究目的是在原分配方案的基礎(chǔ)上得到一個新的分配方案，提高機(jī)場的運(yùn)營效率，降低運(yùn)營費(fèi)用，提升旅客的滿意度.

本文提出的停機(jī)位實(shí)時再分配模型解決了以下幾個問題：

1) 使機(jī)場的運(yùn)營成本最低，降低了飛機(jī)的燃油消耗；

2) 盡最大可能提高旅客的舒適度，減少由于再分配導(dǎo)致的麻煩；

3) 短時間內(nèi)完成停機(jī)位的再分配，一般在1 min內(nèi)完成；

4) 再分配后的結(jié)果對其他班機(jī)的影響較小.

為了解決上述問題，本文提出了多商品網(wǎng)絡(luò)流停機(jī)位實(shí)時再分配模型.將停機(jī)位映射為商品，這些商品在源節(jié)點(diǎn)和終節(jié)點(diǎn)之間通過到達(dá)節(jié)點(diǎn)和離開節(jié)點(diǎn)連接.當(dāng)連接節(jié)點(diǎn)之間的弧可用時商品會流經(jīng)弧，即停機(jī)位可分配給該航班，否則不可分配給該航班.

1.2 問題假設(shè)

基于多商品網(wǎng)絡(luò)流模型，本文對停機(jī)位實(shí)時再分配模型做出如下假設(shè)：

1) 所有的停機(jī)位可提供再分配，能夠容納任何尺寸的飛機(jī)；

2) 僅有一條跑道提供起飛和降落；

3) 假設(shè)所有尺寸飛機(jī)飛行時燃料費(fèi)相同；

4) 假設(shè)所有尺寸飛機(jī)怠速時燃料費(fèi)相同.

1.3 數(shù)學(xué)符號

本文使用的數(shù)學(xué)符號定義如下：

1) 集合符號.F為所有未降落班機(jī)集合；N為停機(jī)位有沖突班機(jī)集合；K為全部停機(jī)位集合.

3) 決策變量符號.Xik為二值變量，當(dāng)且僅當(dāng)班機(jī)i被分到停機(jī)位k時為1；Zijk為二值變量，當(dāng)且僅當(dāng)班機(jī)i和j依次都被分配到停機(jī)位k時為1.

4) 輔助變量符號.Yik為二值變量，當(dāng)且僅當(dāng)班機(jī)i在前次更新被分配給停機(jī)位k時為1，即等于時間t-Δt時的Xik；Ai為隨機(jī)變量，班機(jī)i到達(dá)時刻.

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

為了使停機(jī)位再分配既能同時兼顧機(jī)場和乘客的利益，又能提供短時間突發(fā)事件的處理能力，根據(jù)多商品網(wǎng)絡(luò)流模型提出了如下目標(biāo)函數(shù)，即

(1)

I(-∞，vp](E(Ai)-fi-t)=

(2)

(3)

式(2)表示班機(jī)i離港后剩余時間間隔，當(dāng)且僅當(dāng)剩余時間間隔小于等于給定的閾值vp時為1，否則為0，即i不需要重新分配停機(jī)位.式(3)表示當(dāng)班機(jī)i被再分配到另一個停機(jī)位k時求和結(jié)果為1.

1.5 約束條件

模型需要滿足以下約束條件：

(4)

(5)

(6)

E(Aj)+(1-Zijk)M≥E(Ai)+ai+bk(i，j∈F，k∈K)

(7)

Xik+Xjk=1 (i，j∈N，k∈K)

(8)

(9)

Xik，Zijk∈{0，1}

(10)

約束(4)表示一個班機(jī)只能分配到一個停機(jī)位；約束(5)、(6)表示引進(jìn)中間決策變量；約束(7)表示班機(jī)i、j之間的先后順序；約束(8)表示強(qiáng)制重分配集合N中的班機(jī)；約束(9)表示再分配級別的限制；約束(10)表示二值決策變量.

1.6 到港時刻

符號Ai是一個隨機(jī)變量，對于每天給定的航線，其分布隨時間發(fā)生變化.對于某個特定的班機(jī)，它的預(yù)期到港時刻E(Ai)可以通過預(yù)測天氣狀況來進(jìn)行合理預(yù)測.一些與天氣相關(guān)的預(yù)測包括如下變量：風(fēng)速、風(fēng)向、能見度、溫度、云層和大氣壓等.多元回歸模型可以擬合歷史數(shù)據(jù)來為特定航線預(yù)測班機(jī)的延誤，一旦得到了回歸模型，就可以通過使用由機(jī)場提供的天氣預(yù)報(bào)來估計(jì)班機(jī)的延遲，擬合的質(zhì)量可以由R平方統(tǒng)計(jì)量進(jìn)行測量.

2 模型求解

由目標(biāo)函數(shù)的特點(diǎn)可知，本文模型屬于二值混合整數(shù)規(guī)劃模型，求解步驟如下：

1) 按E(Conflictijk)>vg構(gòu)造班機(jī)沖突集合N，如果N不為空轉(zhuǎn)到步驟2)；

2) 運(yùn)行一個優(yōu)化程序來分配相關(guān)班機(jī)；

3) 反復(fù)重新分配不同級別直至達(dá)到滿意的最小值，此算法在一個固定的時間間隔t為15 min重復(fù)執(zhí)行一次或者根據(jù)實(shí)際情況調(diào)整.

班機(jī)i被再分配到停機(jī)位k后可能會導(dǎo)致許多班機(jī)和停機(jī)位重新分配，因此發(fā)生再分配的班機(jī)需要控制分配次數(shù).當(dāng)用戶指定參數(shù)l后，算法中再分配班機(jī)最大數(shù)量為N·l.在實(shí)踐中，可選取l的幾個不同值代入目標(biāo)函數(shù)中計(jì)算求解，在得到的幾個新分配方案中選擇一個最佳方案.

3 實(shí)例分析

3.1 10個停機(jī)位20個航班

采用國內(nèi)某大型機(jī)場的某一天具體班機(jī)時刻表為例，選定一個時間段內(nèi)空閑的10個停機(jī)位(G1，G2，…，G10)，對20個即將到達(dá)的班機(jī)按照上述模型算法進(jìn)行分配，使用由IBM公司開發(fā)的ILOG優(yōu)化軟件進(jìn)行求解.班機(jī)i到港時刻E(Ai)和從另一個機(jī)場離港時刻E(Di)如表1所示.

表1 班機(jī)時刻表(實(shí)例1)Tab.1 Flight schedule (example 1)

表1(續(xù))Tab.1(Cont)

表2中初始停機(jī)位的分配方案采用參考文獻(xiàn)[9-10]算法計(jì)算得到.

表2 初始停機(jī)位分配方案Tab.2 Initial gate reassignment scheme

表2中，方框中數(shù)字1標(biāo)注的班機(jī)表示有沖突.使用ILOG軟件編寫程序得到停機(jī)位再分配結(jié)果如表3所示，計(jì)算時間為0.093 75 s.

表3 停機(jī)位再分配方案(實(shí)例1)Tab.3 Gate reassignment scheme (example 1)

由表3可知，每個停機(jī)位調(diào)整的班機(jī)最多是2個，保證了對班機(jī)的調(diào)整盡可能少，降低了班機(jī)調(diào)整給乘客帶來的不必要麻煩，提高了乘客的滿意度.

3.2 10個停機(jī)位40個航班

在實(shí)驗(yàn)一的基礎(chǔ)上，加大航班規(guī)模，選取某航空公司40個航班的到港和離港時刻作為基礎(chǔ)數(shù)據(jù)，如表4所示.

表4 班機(jī)時刻表(實(shí)例2)Tab.4 Flight schedule (example 2)

表4(續(xù))Tab.4(Cont)

模型參數(shù)取值與實(shí)例一相同，從而得到初始停機(jī)位分配方案.使用ILOG軟件編寫程序得到停機(jī)位再分配結(jié)果，如表5所示，計(jì)算時間為4.187 5 s.由表5可知，在航班規(guī)模擴(kuò)大1倍后，每個停機(jī)位調(diào)整的班機(jī)仍舊最多2個，算法運(yùn)行時間遠(yuǎn)遠(yuǎn)小于1 min，算法在保障盡可能減少調(diào)整班機(jī)個數(shù)的同時又顯示了較好的時效性.

4 結(jié) 論

本文通過使用多商品網(wǎng)絡(luò)流模型解決了機(jī)場停機(jī)位再分配的問題，建立的模型既考慮了機(jī)場又兼顧了旅客，實(shí)現(xiàn)了機(jī)場和旅客雙贏的目標(biāo).這樣既能提高旅客對機(jī)場服務(wù)的滿意度，又能減少機(jī)場的運(yùn)營成本.模型以國內(nèi)某大型機(jī)場停機(jī)位的分配方案為基礎(chǔ)，利用ILOG優(yōu)化求解軟件得出班機(jī)停機(jī)位的再分配方案.在不同航班規(guī)模的仿真實(shí)驗(yàn)中，調(diào)整的班機(jī)最多為2個，模型求解時間均小于5 s，分配模型顯示了較好的實(shí)時性和有效性.

表5 停機(jī)位再分配方案(實(shí)例2)Tab.5 Gate reassignment scheme (example 2)