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

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

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

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

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

1 機場停機位實時再分配模型

1.1 問題描述

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

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

1) 使機場的運營成本最低，降低了飛機的燃油消耗；

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

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

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

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

1.2 問題假設(shè)

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

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

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

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

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

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

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

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

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

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

1.4 目標函數(shù)

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

(1)

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

(2)

(3)

式(2)表示班機i離港后剩余時間間隔，當(dāng)且僅當(dāng)剩余時間間隔小于等于給定的閾值vp時為1，否則為0，即i不需要重新分配停機位.式(3)表示當(dāng)班機i被再分配到另一個停機位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)表示一個班機只能分配到一個停機位；約束(5)、(6)表示引進中間決策變量；約束(7)表示班機i、j之間的先后順序；約束(8)表示強制重分配集合N中的班機；約束(9)表示再分配級別的限制；約束(10)表示二值決策變量.

1.6 到港時刻

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

2 模型求解

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

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

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

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

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

3 實例分析

3.1 10個停機位20個航班

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

表1 班機時刻表(實例1)Tab.1 Flight schedule (example 1)

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

表2中初始停機位的分配方案采用參考文獻[9-10]算法計算得到.

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

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

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

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

3.2 10個停機位40個航班

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

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

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

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

4 結(jié) 論

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

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