李明捷，石 榮，蔣鳳偉

（1.中國(guó)民航飛行學(xué)院 a.空中交通管理學(xué)院；b.飛行技術(shù)學(xué)院，四川 廣漢 618307；2.四川省機(jī)場(chǎng)集團(tuán)有限公司，成都 610200）

隨著機(jī)場(chǎng)航班日起降架次的增多和乘飛機(jī)出行旅客數(shù)量的迅速增長(zhǎng)，現(xiàn)有的登機(jī)口資源正面臨著日益嚴(yán)峻的考驗(yàn)。目前，大多數(shù)機(jī)場(chǎng)通過(guò)借鑒其他機(jī)場(chǎng)的做法，或根據(jù)以往的經(jīng)驗(yàn)來(lái)進(jìn)行登機(jī)口分配和調(diào)度，往往導(dǎo)致很多載客數(shù)量較多的大中型飛機(jī)?？吭诰喟矙z或者行李提取大廳較遠(yuǎn)的登機(jī)口；或由于遠(yuǎn)、近機(jī)位登機(jī)口航班密度安排不合理，使得每個(gè)登機(jī)口的航班組合沒(méi)有達(dá)到最優(yōu)，從而降低了登機(jī)口的利用效率。

對(duì)于中國(guó)大多數(shù)中小型機(jī)場(chǎng)來(lái)說(shuō)，由于航班日起降架次相對(duì)較少、到離港時(shí)間相對(duì)分散，故在機(jī)場(chǎng)運(yùn)行資源分配和優(yōu)化問(wèn)題研究時(shí)，學(xué)者們多將目光集中在停機(jī)位資源優(yōu)化與分配問(wèn)題上，而較少考慮登機(jī)口的分配和調(diào)度優(yōu)化方法。南京航空航天大學(xué)的王志清等人將圖論應(yīng)用到登機(jī)口分配問(wèn)題中，提出旅客登機(jī)口調(diào)度優(yōu)化網(wǎng)絡(luò)模型，具有一定的創(chuàng)新性，模型假設(shè)進(jìn)、出港旅客步行距離基本相等，沒(méi)有考慮中轉(zhuǎn)旅客對(duì)登機(jī)口分配的影響[1]。南京航空航天大學(xué)的曹燕在其碩士學(xué)位論文中利用表上作業(yè)法對(duì)登機(jī)口分配模型進(jìn)行了考慮，但直觀性不強(qiáng)[2]。中國(guó)民航飛行學(xué)院文軍等人將圖著色模型應(yīng)用到機(jī)位分配中，使圖論的思想在資源分配中得到應(yīng)用[3]。但在考慮登機(jī)口分配問(wèn)題時(shí)，由于近機(jī)位登機(jī)口與近機(jī)位一一對(duì)應(yīng)，因而可以用機(jī)位分配與優(yōu)化模型來(lái)模擬登機(jī)口的分配；而遠(yuǎn)機(jī)位登機(jī)口具有一定的特殊性，對(duì)于旅客而言，登機(jī)口與機(jī)位是一一對(duì)應(yīng)的關(guān)系，但從空間分布上來(lái)看，其可以是一個(gè)或幾個(gè)登機(jī)口對(duì)應(yīng)一個(gè)或多個(gè)機(jī)位的設(shè)置形式，也就是“一對(duì)多”或“多對(duì)多”問(wèn)題，此時(shí)若再使用停機(jī)位的分配與優(yōu)化方法來(lái)解決登機(jī)口的分配就不合理了。

本文以進(jìn)、出港旅客總的步行距離最短為主要優(yōu)化目標(biāo)，運(yùn)用圖論中的網(wǎng)絡(luò)最大流理論來(lái)解決登機(jī)口的分配與優(yōu)化問(wèn)題，在保證機(jī)場(chǎng)安全、高效運(yùn)行的前提下，盡可能提高登機(jī)口利用效率，體現(xiàn)民航旅客運(yùn)輸?shù)谋憬菪耘c舒適性。

1 研究與方法

1.1 旅客步行距離最短模型的優(yōu)化目標(biāo)與約束條件

1.1.1 優(yōu)化目標(biāo)

1）使進(jìn)、出港旅客的總步行距離最短，滿足旅客對(duì)航空運(yùn)輸“便捷性”的需求；

2）使現(xiàn)有設(shè)施使用效率達(dá)到最高，優(yōu)化資源配置。

1.1.2 約束條件

1）機(jī)型與機(jī)位類(lèi)型相匹配；

2）分配登機(jī)口時(shí)，一個(gè)航班必須被分配且僅能被分配至一個(gè)登機(jī)口；

3）應(yīng)滿足最短過(guò)站時(shí)間和同機(jī)位安全間隔時(shí)間的要求；

4）“航班對(duì)”的限制：由于在機(jī)場(chǎng)?？康慕^大部分航班既擔(dān)負(fù)著進(jìn)港航班任務(wù)，又擔(dān)負(fù)著出港航班任務(wù)，因此，盡量將此類(lèi)飛機(jī)盡可能安排在同一個(gè)登機(jī)口，降低航空公司運(yùn)營(yíng)成本。

除此之外，根據(jù)各機(jī)場(chǎng)的性質(zhì)和特點(diǎn)不同，還需考慮登機(jī)口分配的優(yōu)先原則、航班過(guò)夜、飛機(jī)維修等約束條件[1-4]。

1.2 旅客步行距離最短模型的設(shè)置條件

1.2.1 假設(shè)條件

假設(shè)某機(jī)場(chǎng)有m個(gè)可用登機(jī)口，當(dāng)日有n個(gè)航班，每個(gè)登機(jī)口的啟用和停用時(shí)間、每個(gè)航班的載客人數(shù)均已知。根據(jù)某機(jī)場(chǎng)一天中部分時(shí)段的航班計(jì)劃，將各航班信息匯總?cè)绫?所示。

1.2.2 航站樓布局對(duì)登機(jī)口分配的影響

當(dāng)?shù)菣C(jī)口位置布局已知，則安檢區(qū)和行李提取大廳的位置將會(huì)直接影響到進(jìn)、出港旅客步行距離的長(zhǎng)短。這里所講的航站樓布局，主要分為兩種：一是安檢區(qū)與行李提取大廳位于航站樓上、下兩層中基本相同的位置；二是安檢區(qū)與行李提取大廳位于航站樓上、下兩層或同層中不同位置。

表1 某機(jī)場(chǎng)一天中部分時(shí)段航班信息匯總表Tab.1 Flight information table of an airport in the part time during a day

1）安檢區(qū)與行李提取大廳不同層但位置相近

對(duì)于大部分機(jī)場(chǎng)而言，進(jìn)、出港旅客總?cè)藬?shù)總體來(lái)講近似相等，對(duì)于圖1[4]這種設(shè)置方式，雖然進(jìn)、離港旅客的行走路徑不同，但一般情況下，在進(jìn)行登機(jī)口優(yōu)化分配過(guò)程中可將進(jìn)、出港旅客步行距離視為相等，在進(jìn)行登機(jī)口分配時(shí)，需按照航班實(shí)際載客人數(shù)，盡量將人數(shù)較多的航班安排在靠近安檢區(qū)的登機(jī)口。

2）安檢區(qū)與行李提取大廳（不）同層且位置不同

對(duì)于某些中、小機(jī)場(chǎng)，其安檢區(qū)與行李提取大廳采用同層或分層且相隔較遠(yuǎn)的方式設(shè)置，如圖2[4]所示，在這種情況下，應(yīng)根據(jù)航班人數(shù)，結(jié)合其他限制條件進(jìn)行登機(jī)口分配。

2 結(jié)果與分析

2.1 數(shù)據(jù)收集與整理

本文利用表1中已知航班信息作為實(shí)例分析的數(shù)據(jù)來(lái)源，采用最廣泛的航站樓布局形式，即假定安檢區(qū)和行李提取大廳分別位于航站樓的上、下兩層，位置近似相同，以此來(lái)說(shuō)明該模型的構(gòu)建方法和應(yīng)用過(guò)程。

2.2 優(yōu)化分配網(wǎng)絡(luò)模型的構(gòu)建

2.2.1 進(jìn)、出港旅客步行距離最短模型建立與實(shí)證分析

對(duì)于國(guó)內(nèi)大部分干線和支線機(jī)場(chǎng)而言，始發(fā)或終到旅客所占比例甚多，從長(zhǎng)時(shí)間的數(shù)據(jù)統(tǒng)計(jì)來(lái)看，這兩部分旅客所占比例相當(dāng)，因此，可將其步行距離視為近似相等。以下就是進(jìn)、出港旅客步行距離最短模型的實(shí)施步驟：

步驟1 按照登機(jī)口啟用時(shí)間的先后順序，由左至右把每個(gè)航班作為網(wǎng)絡(luò)圖上的一個(gè)節(jié)點(diǎn)，在考慮各種約束條件的基礎(chǔ)上，將節(jié)點(diǎn)之間進(jìn)行有向連線，方向?yàn)橛呻x港時(shí)間早的航班指向晚的，由此形成一個(gè)由節(jié)點(diǎn)和箭頭構(gòu)成的網(wǎng)絡(luò)圖。不難理解，網(wǎng)絡(luò)圖中從起點(diǎn)到終點(diǎn)的每一條有向路徑上的節(jié)點(diǎn)都是可以安排在一個(gè)登機(jī)口上的航班組合，如圖3所示。

步驟2 在圖3上，按照各節(jié)點(diǎn)的時(shí)間順序?qū)ζ溥M(jìn)行二次編號(hào)G（A，B），G表示航班編號(hào)；A表示航班G的前一個(gè)航班的編號(hào)（若為起始航班，則其編號(hào)為本次航班的號(hào)碼）；B表示航班載客人數(shù)的累計(jì)，即前一個(gè)航班A的實(shí)際載客人數(shù)與本次航班G的實(shí)際載客人數(shù)之和。需要注意的是，若A前有兩個(gè)或多個(gè)已編號(hào)航班，則擇選B最大的那個(gè)航班作為G的前一個(gè)航班，如圖4所示。

步驟3 將每架航班的人數(shù)看成是網(wǎng)絡(luò)圖中的流量，從登機(jī)口結(jié)束使用的這個(gè)網(wǎng)絡(luò)圖的最大流量就表示可以使用同一個(gè)登機(jī)口的人數(shù)最多的航班組合。從終點(diǎn)開(kāi)始逆向?qū)ふ乙粭l至起點(diǎn)航班人數(shù)最多的路徑，并把這條路徑上的航班安排在距安檢出口最近的登機(jī)口。在圖4中，01→04→07即為該網(wǎng)絡(luò)圖中旅客流量最大的航班組合，可將這3個(gè)航班按照登機(jī)口啟用先后順序安排至離安檢區(qū)最近的登機(jī)口。

步驟4 在調(diào)度網(wǎng)絡(luò)圖上去掉已安排過(guò)的航班節(jié)點(diǎn)及與其相關(guān)聯(lián)的箭線，再?gòu)男碌钠瘘c(diǎn)開(kāi)始尋找一條至終點(diǎn)航班人數(shù)最多的路徑，并把這條路徑上的航班安排在距安檢出口次近的登機(jī)口，如圖5所示。在圖5中，02→03→05→08為網(wǎng)絡(luò)圖中旅客流量最大的航班組合，可將這4個(gè)航班按照登機(jī)口啟用先后順序安排至離安檢區(qū)次近的登機(jī)口。

步驟5 重復(fù)步驟4，按照上述方法直到所有的航班安排完為止。本例中剩下06號(hào)航班，可將其安排至3號(hào)登機(jī)口。

2.2.2 中轉(zhuǎn)旅客步行距離最短模型

對(duì)于大型樞紐機(jī)場(chǎng)以及部分干線機(jī)場(chǎng)而言，國(guó)際轉(zhuǎn)國(guó)際、國(guó)際轉(zhuǎn)國(guó)內(nèi)、國(guó)內(nèi)轉(zhuǎn)國(guó)內(nèi)的中轉(zhuǎn)旅客數(shù)量較其他中小機(jī)場(chǎng)多。中轉(zhuǎn)旅客的流程大致可以概括為：旅客下機(jī)→中轉(zhuǎn)柜臺(tái)→中轉(zhuǎn)休息廳→安全檢查→登機(jī)，中轉(zhuǎn)旅客的所有中轉(zhuǎn)過(guò)程都在隔離區(qū)內(nèi)完成，旅客不用出去重新辦理登機(jī)手續(xù)。則中轉(zhuǎn)休息廳相對(duì)于安檢區(qū)的位置將直接決定中轉(zhuǎn)旅客在航站樓內(nèi)步行距離的長(zhǎng)短。假設(shè)該段距離長(zhǎng)短已定，則需考慮登機(jī)口與安檢區(qū)的相對(duì)位置，以便盡量減少該部分旅客的步行距離。

具體分配的思路是：根據(jù)進(jìn)、出港旅客步行距離最短模型的分配結(jié)果，利用網(wǎng)絡(luò)最大流理論，考慮在航班間隙將中轉(zhuǎn)旅客流量最大的航班安排在距離安檢區(qū)最近的登機(jī)口，以此類(lèi)推，具體過(guò)程參見(jiàn)本文的2.2.1節(jié)。

2.3 算法復(fù)雜度分析和最優(yōu)性證明

2.3.1 算法的復(fù)雜度分析

如前所述，該模型總運(yùn)算次數(shù)不會(huì)超過(guò)n，而網(wǎng)絡(luò)圖中航班節(jié)點(diǎn)的總數(shù)也不會(huì)超過(guò)n，故總運(yùn)算次數(shù)不會(huì)大于 n2，即其計(jì)算復(fù)雜度為 o（n2）。

2.3.2 算法的最優(yōu)性證明

為了說(shuō)明算法是最優(yōu)算法，現(xiàn)在登機(jī)口調(diào)度網(wǎng)絡(luò)圖上增加一個(gè)虛擬起始節(jié)點(diǎn)s和一個(gè)虛擬終結(jié)節(jié)點(diǎn)t，并將虛擬起始節(jié)點(diǎn)s與所有起始航班節(jié)點(diǎn)用箭頭相連，同樣，將所有終結(jié)節(jié)點(diǎn)與虛終結(jié)節(jié)點(diǎn)t也用箭頭相連，如圖6所示。

由于各航班節(jié)點(diǎn)是按時(shí)間順序由左至右排列的，因此，圖6所示的網(wǎng)絡(luò)圖是一個(gè)具有兩端點(diǎn)s和t的無(wú)環(huán)路網(wǎng)絡(luò)圖。其中每一條從s到t的有向路徑，都是可在同一個(gè)登機(jī)口安排航班組合的可行方案。如果把各節(jié)點(diǎn)的航班人數(shù)作為以該節(jié)點(diǎn)為終點(diǎn)的各箭線的權(quán)值，則該網(wǎng)絡(luò)圖就相當(dāng)于一個(gè)雙代號(hào)計(jì)劃網(wǎng)絡(luò)圖，而上面的算法等同于在此雙代號(hào)網(wǎng)絡(luò)圖中尋找從s到t的最大權(quán)值路線的算法[5]。因此，當(dāng)各箭線的邊權(quán)值為該箭線指向節(jié)點(diǎn)的航班乘客人數(shù)時(shí)，所形成的最長(zhǎng)路線就是可以安排在同一個(gè)登機(jī)口的乘客人數(shù)最多的航班安排組合，由此印證了該算法的最優(yōu)性。

3 結(jié)語(yǔ)

1）本文采用圖論中的最大流理論構(gòu)造了登機(jī)口分配的網(wǎng)絡(luò)模型，以旅客步行距離最短為主要優(yōu)化目標(biāo)，方法簡(jiǎn)單，實(shí)際操作性較強(qiáng)。

2）較傳統(tǒng)的登機(jī)口分配方法，該模型能夠有效應(yīng)對(duì)航班延誤、返場(chǎng)備降等突發(fā)情況，對(duì)機(jī)場(chǎng)運(yùn)行管理中的登機(jī)口分配工作具有一定的指導(dǎo)意義。

3）該模型有利于機(jī)場(chǎng)運(yùn)行資源的均衡使用，對(duì)提高現(xiàn)有資源利用率、緩解機(jī)場(chǎng)運(yùn)行設(shè)施設(shè)備供需矛盾、節(jié)約機(jī)場(chǎng)的運(yùn)營(yíng)和建設(shè)成本、降低航空公司的運(yùn)行成本等方面具有一定的理論研究?jī)r(jià)值。

[1]王志清，商紅巖，寧宣熙.機(jī)場(chǎng)登機(jī)口優(yōu)化調(diào)度算法及實(shí)證[J].南京航空航天大學(xué)學(xué)報(bào)，2007，39（6）：819-823.

[2]曹 燕.民航運(yùn)輸旅客流程的優(yōu)化研究[D].南京：南京航空航天大學(xué)，2005.

[3]文 軍，李 冰，王清蓉，等.機(jī)場(chǎng)停機(jī)位分配問(wèn)題的圖著色模型及其算法[J].系統(tǒng)工程理論方法應(yīng)用，2005，14（2）：136-140.

[4]常 鋼，魏生民，張建龍.基于多目標(biāo)規(guī)劃的停機(jī)位分配建模技術(shù)研究[J].西北大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，36（5）：725-728.

[5]寧宣熙.運(yùn)籌學(xué)實(shí)用教程[M].北京：科學(xué)出版社，2002：231-239.