機(jī)場登機(jī)口分配問題的頂點(diǎn)著色模型與算法

梁超超,陳培軍

(太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院，太原 030024)

隨著旅行業(yè)快速發(fā)展,機(jī)場航班日起降架次的增多和乘飛機(jī)出行人數(shù)的迅速增長,現(xiàn)有的登機(jī)口資源正面臨著越來越嚴(yán)峻的考驗(yàn)。在航空運(yùn)輸管理中,機(jī)場管理處于重要地位。在機(jī)場管理中,航班機(jī)位(即登機(jī)口)分配處于重要地位。針對航班-登機(jī)口分配問題,文軍和孫宏[1]等提出了一種登機(jī)口分配問題的排序模型,并采用登機(jī)口標(biāo)號函數(shù)建立標(biāo)號算法對其進(jìn)行求解。田晨和熊桂喜[2]通過運(yùn)用遺傳算法來求解航班-登機(jī)口分配問題。文軍、李冰[3]等人提出了一種登機(jī)口分配問題的圖著色模型,并通過時(shí)間片算法確定航班使用登機(jī)口的時(shí)間沖突集合,根據(jù)“先到先服務(wù)”的原則建立登機(jī)口分配的頂點(diǎn)序列著色算法。

但很多現(xiàn)有航站樓的旅客流量已達(dá)飽和狀態(tài),為了應(yīng)對與日俱增的運(yùn)營壓力,正增設(shè)衛(wèi)星廳。2018年“華為杯”第十五屆研究生數(shù)學(xué)競賽F題對這類問題的登機(jī)口分配提出了研究要求。航站樓T和衛(wèi)星廳S的布局設(shè)計(jì)如圖1所示。航站樓T有28個(gè)登機(jī)口,衛(wèi)星廳S有41個(gè)登機(jī)口,具體數(shù)據(jù)見賽題。航班分配問題的任務(wù)可理解為在盡可能節(jié)約資源的情況下,給出能夠有效分配最多的航班到適合的登機(jī)口的問題。由于登機(jī)口與機(jī)型的約束,以及航班與航班之間存在時(shí)間沖突,可將問題轉(zhuǎn)化為帶約束的頂點(diǎn)著色問題。本文的主要工作是設(shè)計(jì)了簡單有效的可以應(yīng)用于具有衛(wèi)星廳的登機(jī)口分配的貪婪算法策略。

圖1 衛(wèi)星廳S相對于航站樓T示意圖Fig.1 A sketch of satellite hall S relative to terminal building T

1 航班分配問題數(shù)學(xué)模型的建立

1.1 登機(jī)口分配的分析

根據(jù)登機(jī)口的規(guī)格,可將登機(jī)口分為國內(nèi)-國內(nèi)寬體機(jī)、國內(nèi)-國際寬體機(jī)、國際-國內(nèi)寬體機(jī)、國際-國際寬體機(jī)、國內(nèi)-國內(nèi)窄體機(jī)、國內(nèi)-國際窄體機(jī)、國際-國內(nèi)窄體機(jī)、國際-國際窄體機(jī)共8種類型。登機(jī)口分配是指根據(jù)航班的機(jī)型規(guī)格以及達(dá)到時(shí)刻、離開時(shí)刻,為每一個(gè)航班分配一個(gè)具體的登機(jī)口。在一天的不同時(shí)刻,由于到達(dá)的航班機(jī)型規(guī)格、航班數(shù)目、飛行類型(國際或者國內(nèi))不同,確定使用登機(jī)口的類型和時(shí)間也不同,具體分配登機(jī)口使用時(shí),必須滿足以下約束條件:

(1)對于每一個(gè)登機(jī)口而言,同一時(shí)間同一登機(jī)口只能分配給一個(gè)航班,或處于空閑狀態(tài)。

(2)對于每一個(gè)航班而言,登機(jī)口是唯一的,即必須給每個(gè)航班分配一個(gè)且僅分配一個(gè)登機(jī)口。

(3)航班一旦開始使用某登機(jī)口,則該使用過程不能中斷,直到使用完畢。

(4)登機(jī)口應(yīng)與航班相匹配,即寬型航班只能使用寬型登機(jī)口,窄型航班只能使用窄型登機(jī)口。

對飛機(jī)進(jìn)行登機(jī)口分配時(shí),根據(jù)已知的航班時(shí)刻表,并且按照“先到先服務(wù)”的原則對航班進(jìn)行登機(jī)口分配,這樣就可以應(yīng)用有序的頂點(diǎn)著色理論建立有關(guān)登機(jī)口分配的數(shù)學(xué)模型。

1.2 數(shù)據(jù)處理

以下為數(shù)據(jù)處理的具體步驟：

(1)根據(jù)飛機(jī)型號判斷并保存所有航班的寬、窄類型。

(2)對所有航班根據(jù)到達(dá)類型和出發(fā)類型合在一起保存,并結(jié)合(1)中的寬窄將航班分為國內(nèi)-國內(nèi)寬體機(jī)、國內(nèi)-國際寬體機(jī)、國際-國內(nèi)寬體機(jī)、國際-國際寬體機(jī)、國內(nèi)-國內(nèi)窄體機(jī)、國內(nèi)-國際窄體機(jī)、國際-國內(nèi)窄體機(jī)、國際-國際窄體機(jī)共8種類型。

(3)將2018年1月19日0點(diǎn)作為起點(diǎn),計(jì)算并繪制19日-22日不同時(shí)刻(單位：min )航班的數(shù)量,見圖2;同時(shí)考慮間隔45 min后,計(jì)算并繪制19日-22日不同時(shí)刻航班的數(shù)量,見圖3.

圖2 19-22日不同時(shí)刻航班的數(shù)量 Fig.2 Number of flights at different time from 19 to 22

圖3 考慮空檔間隔后,19-22日不同時(shí)刻航班的數(shù)量Fig.3 Number of flights at different time from 19 to 22 after considering gap intervals

由圖3可得：航班數(shù)最多為80個(gè),而該機(jī)場可供使用的登機(jī)口共有69個(gè),因此現(xiàn)有登機(jī)口無法安排下所有的航班,這就需要盡可能多的安排航班到合適的登機(jī)口,使登機(jī)口最大化被利用。

(4)將20日作為起點(diǎn),由于航班到達(dá)時(shí)間和出發(fā)時(shí)間之差的最小值為50 min ,為處理簡單,我們統(tǒng)一對19日到達(dá)20日出發(fā)的航班采用虛擬的到達(dá)時(shí)刻,即比出發(fā)時(shí)刻提前50 min，另外該到達(dá)時(shí)間不能超過起始時(shí)0點(diǎn),如果位于0點(diǎn)之前,統(tǒng)一將0點(diǎn)作為虛擬的到達(dá)時(shí)間。

(5)同樣,對于20日到達(dá),而較長時(shí)間才離開的航班,將其到達(dá)時(shí)間延后50 min時(shí)間視為其虛擬的出發(fā)時(shí)間,若超過了24點(diǎn),即已超過20日考慮范圍,則可視為24點(diǎn)。

通過步驟(4)、(5)對24點(diǎn)和0點(diǎn)的特殊處理,可篩選并保存滿足20日到達(dá)和20日出發(fā)的航班以及對應(yīng)原順序的下標(biāo)。

(6)計(jì)算并繪制20日不同時(shí)刻的航班數(shù)以及考慮空檔間隔45 min的不同時(shí)刻的航班數(shù),見圖4、圖5.

圖4 20日不同時(shí)刻航班的數(shù)量Fig.4 Number of flights at different time on the 20th day

圖5 考慮空檔間隔后,20日不同時(shí)刻航班的數(shù)量Fig.5 Number of flights at different time on the 20th day after considering the gap intervals

(7)按照步驟(2)中的8種航班類型統(tǒng)計(jì)并繪制出20日不同時(shí)刻不同類型的航班數(shù),以及考慮空檔間隔45 min后20日不同時(shí)刻不同類型的航班數(shù)。圖6、圖7展示了國內(nèi)-國內(nèi)窄體機(jī)的結(jié)果,其他類型的航班數(shù)不在此一一展示。

圖6 20日窄體機(jī)國內(nèi)-國內(nèi)航班分布Fig.6 Domestic-domestic flight distribution of narrow body aircraft on the 20th day

圖7 考慮空檔間隔45 min，20日窄體機(jī)國內(nèi)-國內(nèi)航班分布Fig.7 Considering the distribution of domestic-domestic flights on narrow-body aircraft with 45-minute gap on the 20th day

1.3 航班登機(jī)口分配的頂點(diǎn)著色模型

頂點(diǎn)著色問題在生產(chǎn)調(diào)度領(lǐng)域有著廣泛的應(yīng)用背景,已被應(yīng)用于資源分配、貨物存儲和課表編排、頻率分配[4-7]等問題當(dāng)中。本文將航班-登機(jī)口分配問題看成頂點(diǎn)著色問題。首先引入航班登機(jī)口分配二元圖G(V,R),對各航班按照到達(dá)時(shí)間的先后順序依次編號,記為1,2,…,n,記V(G)={1,2,…,n},R為引入的鄰接矩陣,用來表示各航班之間的關(guān)聯(lián)情況,即R=(rij)n×n,其中:

rij=

當(dāng)rij=0時(shí)表示航班i和航班j的時(shí)間不沖突,即可分配到同一登機(jī)口;當(dāng)rij=1時(shí)表示航班i和航班j的時(shí)間相沖突,即不能分配到同一登機(jī)口。n表示航班數(shù),題目中n=303.

接下來利用鄰接矩陣,我們可構(gòu)建航班-登機(jī)口分配優(yōu)化模型為:

滿足:

(1)[V1,V2,…,Vm+1]是頂點(diǎn)V的一個(gè)劃分。

(2)航班的類型應(yīng)與登機(jī)口的類型相匹配,并且登機(jī)口的數(shù)量滿足一定的限制。

2 頂點(diǎn)著色模型的貪婪算法設(shè)計(jì)

2.1 與一般的頂點(diǎn)著色的不同

(1)按照“先到先服務(wù)”的原則,不同的航班根據(jù)到達(dá)時(shí)間構(gòu)成一個(gè)自然的序關(guān)系。

(2)經(jīng)典的貪婪算法中對于任意給定的所有頂點(diǎn)的一個(gè)全排列,一般用當(dāng)前可用的最小色對當(dāng)前的頂點(diǎn)著色。在該問題中,選擇啟發(fā)式規(guī)則是根據(jù)之前航班的起飛時(shí)間的先后順序來選擇登機(jī)口,選擇已空閑時(shí)間最長的登機(jī)口,這樣大大地增加了分配的魯棒性,并且也有益于處理飛機(jī)不可避免的短時(shí)間的延誤。

(3)經(jīng)典的頂點(diǎn)著色問題,顏色的數(shù)目是沒有限制的,而現(xiàn)在由于機(jī)場的條件,不同的顏色的數(shù)量有一定的限制。

(4)根據(jù)登機(jī)口的國內(nèi)/國際、到達(dá)/出發(fā)、寬體機(jī)/窄體機(jī)等功能屬性將其分為8類。

2.2 貪婪算法的設(shè)計(jì)

根據(jù)上述獨(dú)有的特點(diǎn)設(shè)計(jì)貪婪算法求解,具體步驟為:

(1)尋找不同類型的登機(jī)口編號及個(gè)數(shù),且根據(jù)其功能屬性將其分成8種類型,即將顏色分為8類,根據(jù)航站樓的特點(diǎn),每種類型的登機(jī)口由其數(shù)量限制,這樣便獲得顏色集和所允許的個(gè)數(shù)。

(2)計(jì)算鄰接矩陣。

(3)利用貪婪算法求解。按落地時(shí)間“先到先服務(wù)”原則,依次為每個(gè)航班根據(jù)鄰接矩陣找到能使用的登機(jī)口,并選擇已空閑時(shí)間最長的登機(jī)口。若可供使用的登機(jī)口已經(jīng)用完,則安排臨時(shí)停靠方式。

2.3 實(shí)驗(yàn)結(jié)果與分析

所需安排航班總數(shù)為303個(gè),所能提供的登機(jī)口總數(shù)為69個(gè),通過上述算法可得到航班-登機(jī)口分配結(jié)果:寬體機(jī)安排比例為100%,窄體機(jī)安排比例為78.74%,共安排了249個(gè)班次的航班,航站樓T和衛(wèi)星廳S被使用登機(jī)口的平均使用率(登機(jī)口占用時(shí)間比率)分別見圖8和圖9.

圖8 航站樓T的每個(gè)登機(jī)口的平均使用率 Fig.8 Average utilization at each gate of terminal T

圖9 衛(wèi)星廳S的每個(gè)登機(jī)口平均使用率Fig.9 Average utilization at each boarding gate of satellite hall S

3 改進(jìn)的頂點(diǎn)著色模型的貪婪算法設(shè)計(jì)

3.1 基于頂點(diǎn)著色方法的改進(jìn)

根據(jù)有些登機(jī)口可以為多種類型(國際、國內(nèi))的航班服務(wù)的特點(diǎn),根據(jù)寬、窄機(jī),落地和起飛航班為國內(nèi)或國際,將登機(jī)口可供使用的類型數(shù)分成三類,即僅供一類使用的,僅供兩類使用的,供四類使用的。 從而將這些登機(jī)口(顏色)進(jìn)一步分成8×3=24類,先考慮僅供一種類型航班使用的登機(jī)口,然后考慮可供兩種類型航班使用的登機(jī)口,最后考慮可供四種類型使用的登機(jī)口。

3.2 改進(jìn)的貪婪算法的設(shè)計(jì)

根據(jù)上述改進(jìn)的頂點(diǎn)著色方法設(shè)計(jì)貪婪算法求解,具體步驟為:

(1)尋找不同類型的登機(jī)口編號及個(gè)數(shù),分成8種類型,每種類型又分為3類,即只供該類型使用,可供兩種類型使用,可供四種類型使用。

(2)計(jì)算鄰接矩陣。

(3)利用貪婪算法求解。按落地時(shí)間“先到先服務(wù)”原則,依次為每個(gè)航班根據(jù)鄰接矩陣找到能使用的登機(jī)口。在這些登機(jī)口中,優(yōu)先使用只供該類型使用的登機(jī)口(顏色),然后使用可供兩種類型使用的登機(jī)口,最后使用可供四種類型使用的登機(jī)口,并選擇已空閑時(shí)間最長的登機(jī)口。若可供使用的登機(jī)口已經(jīng)用完,則安排臨時(shí)?？糠绞?。

3.3 實(shí)驗(yàn)結(jié)果與分析

通過上述算法可得到航班-登機(jī)口分配結(jié)果:寬體機(jī)安排比例為100%,窄體機(jī)安排比例為80.71%,共安排了254個(gè)班次的航班,航站樓T和衛(wèi)星廳S被使用登機(jī)口的平均使用率(登機(jī)口占用時(shí)間比率)分別見圖10和圖11.改進(jìn)的算法安排的航班數(shù)比2.2的算法安排的航班數(shù)多5個(gè),說明改進(jìn)的頂點(diǎn)著色模型的貪婪算法大大地提高了登機(jī)口的使用效率。

圖10 航站樓T的每個(gè)登機(jī)口的平均使用率Fig.10 Average utilization at each gate of terminal T

圖11 衛(wèi)星廳S的每個(gè)登機(jī)口平均使用率Fig.11 Average utilization at each boarding gate of satellite hall S

4 總結(jié)

本文提出了可以應(yīng)用于具有衛(wèi)星廳的登機(jī)口分配的貪婪算法策略。首先按照“先到先服務(wù)”的原則，運(yùn)用簡單的(選擇已空閑時(shí)間最長的登機(jī)口)啟發(fā)式規(guī)則為當(dāng)前航班選擇登機(jī)口,結(jié)果共安排了249個(gè)航班。然后我們進(jìn)一步提出簡單有效的啟發(fā)式規(guī)則,即先使用僅供一種類型航班使用的登機(jī)口,然后考慮可供兩種類型航班使用的登機(jī)口,最后使用可供四種類型使用的登機(jī)口,結(jié)果共安排了254個(gè)航班,大大提高了登機(jī)口的使用效率。所提出的算法簡單有效，可操作性強(qiáng)。