謝 維,關(guān)嘉欣,周 游,朱文斌

(華南理工大學(xué) 工商管理學(xué)院,廣州 510641)

登機口分配問題求解的目標(biāo)函數(shù)通常考慮兩個主要目標(biāo):最小化登機口的使用數(shù)量和最小化所有航班的延誤時間[1,2].在與登機口相關(guān)的約束條件當(dāng)中,例如登機口只能容納特定類型的飛機、兩個大型飛機不能同時被分配到兩個登機口等,這些條件必須進行考慮[3,4].當(dāng)飛機的數(shù)量比較少時,可以通過變換不同的目標(biāo)條件來生成有效的分配計劃.但是當(dāng)飛機數(shù)量的顯著增加時,我們就很難生成有效的分配方案[5].在目前國內(nèi)外的研究中,有關(guān)登機口分配問題的求解方法可以分為兩類:(1)精確算法,其能夠產(chǎn)生最優(yōu)的解決方案.比較典型的有:Mangoubi 等[6]提出了整數(shù)線性規(guī)劃模型,并以最小化旅客的行走距離為目標(biāo).Bihr[7]提出了一種原始對偶單純形算法,并找到了最優(yōu)解.Yan等[8]建立了多目標(biāo)0-1 整數(shù)規(guī)劃模型,并使用加權(quán)方法、列生成方法、單純形法和分支定界法來求解該模型.李云鵬等[9]使用CPLEX 求解混合整數(shù)規(guī)劃模型.Bolat[10],Xu 等[11]和Li[12]使用分支定界法來求解他們建立的模型.但是由于登機口分配問題是一個NP-hard的組合優(yōu)化問題,當(dāng)擴大求解規(guī)模后,可行解的數(shù)量將呈指數(shù)增加,如果仍然采用精確算法來求解的話,會導(dǎo)致維數(shù)災(zāi)難,因此研究學(xué)者們提出了啟發(fā)式算法和元啟發(fā)式算法來對該問題進行求解.(2)啟發(fā)式算法和元啟發(fā)式算法.Xu 等[11]采用禁忌搜索算法對登機口分配的0-1 混合整數(shù)二次規(guī)劃模型進行求解,該模型以旅客步行總時間為目標(biāo)函數(shù),并沒有考慮捷運時間和流程時間,而且禁忌搜索算法對初始解的依賴性較強.Ding 等[13]對過量限制條件下的登機口分配問題進行了研究,并對文獻[11]中提出的禁忌搜索方法進行了改進,同時提出了禁忌搜索混合模擬退火和模擬退火算法,但是他們只考慮了最小化航班數(shù)和旅客的行走總距離,并未考慮時間因素.Lim 等[14]考慮了航班到達和離開時間可能發(fā)生變化的更現(xiàn)實的情況,并使用“插入移動算法”,“間隔交換移動算法”和“貪婪算法”,以解決建立的登機口分配模型,和本文相比,沒有考慮最小化登機口的數(shù)量.陳欣等[15]設(shè)計了一種排序模擬退火算法以求解樞紐機場的停機位指派問題,同樣沒有考慮最小化登機口的數(shù)量.鞠姝妹等[16]以旅客滿意度為優(yōu)化目標(biāo)建立數(shù)學(xué)模型,并設(shè)計了貪婪模擬退火算法來求解樞紐機場的停機位分配問題,該學(xué)者只是從顧客的角度來建立模型,并沒有考慮機場的登機口使用情況.Zhao 等[17]建立了一種混合整數(shù)模型,并設(shè)計了蟻群算法對該模型進行求解,與本文不同的是,該文并未考慮登機口情況,而且蟻群算法一般需要較長的搜索時間.Dell’Orco 等[18]基于模糊蜂群優(yōu)化(FBCO)開發(fā)了一種新的元啟發(fā)式算法,該算法將BCO的概念與模糊推理系統(tǒng)相結(jié)合,該文在建模方面和本文比較相似,都考慮了旅客和機場登機口兩個方面,但是本文的考慮更加全面.Yu 等[19]擴展了傳統(tǒng)的登機口分配問題,同時考慮了傳統(tǒng)成本和魯棒性,并建立了數(shù)學(xué)模型,然后設(shè)計了自適應(yīng)大鄰域搜索(ALNS)算法來求解該模型,與其不同的是,本文重點考慮的是時間和登機口兩個因素.Wu 等[20]設(shè)計了基于蟻群協(xié)同策略和信息素更新策略的改進蟻群優(yōu)化算法(ICQACO)來解決他們提出的多目標(biāo)優(yōu)化模型,與該文不同的是,本文考慮了最小化登機口數(shù)量.

綜上所述,針對登機口分配問題,本文綜合考慮時間和登機口使用數(shù)量兩個方面來建立數(shù)學(xué)模型,并結(jié)合變鄰域搜索的鄰域構(gòu)造思想,綜合利用集束搜索和模擬退火算法的優(yōu)勢,提出了一種優(yōu)化效果和魯棒性均較好的求解算法——基于集束搜索的改進型模擬退火算法,通過算例驗證了該算法的優(yōu)化效果和魯棒性.

1 問題描述

本文以某機場固定登機口分配為研究對象,并假定該機場現(xiàn)有航站樓T的旅客流量已達飽和狀態(tài),為了應(yīng)對未來的發(fā)展,現(xiàn)正增設(shè)衛(wèi)星廳S.其中航站樓T的所有登機口集合為K,衛(wèi)星廳S 中的臨時登機口數(shù)量假設(shè)為無限,示意圖如圖1所示.

圖1 衛(wèi)星廳S 相對于航站樓T示意圖

(1)機場布局:該機場包含了航站樓T和衛(wèi)星廳S;航站樓T 具有完備的國際機場航站樓所擁有的功能,其中包含出發(fā)、到達、出入境及候機功能.而衛(wèi)星廳S為航站樓T 延伸,但其功能只有候機,沒有設(shè)置出入境的功能.同時航站樓T 與衛(wèi)星樓S 之間具有相通的快速運輸通道,稱為捷運通道,能夠快速的運送國內(nèi)及國際的出入境旅客.現(xiàn)假設(shè)旅客無需等待,隨時可以離開,并且單程運送旅客所需的時間為8 分鐘.

(2)登機口的分配:登機口是用來在飛機?？繒r,對飛機進行相關(guān)技術(shù)操作的固定位置,一般每個登機口統(tǒng)一配備專業(yè)的設(shè)備.分配航班的登機口需要考慮以下幾個規(guī)則:其一,航站樓T和衛(wèi)星樓S的所有登機口規(guī)劃統(tǒng)籌和分配;其二,考慮到每個登機口的國內(nèi)/國際,到達/離開,寬體機型/窄體機型等的功能.飛機轉(zhuǎn)場計劃中的航班需分配給與其屬性匹配的登機口;其三,每次飛機轉(zhuǎn)機的出發(fā)和到達航班必須分配在同一登機口,不能轉(zhuǎn)移到其他登機口;其四,分配于同一登機口的兩架飛機之間的空檔時間間隔必須大于或等于45 分鐘;最后,機場存在臨時停機位,當(dāng)出現(xiàn)無法分配固定登機口時飛機可以停靠,國內(nèi)和國際飛機均可以?？吭谂R時停機位.

(3)旅客流程:旅客可以分為以3 類,包括始發(fā)旅客、終點到達旅客、過境中轉(zhuǎn)旅客.由于新建立的衛(wèi)星大廳對始發(fā)旅客和終點到達旅客的影響較小,所以這兩類旅客不屬于本文所研究的對象.而過境中轉(zhuǎn)旅客則可以根據(jù)前一航班到達至后一航班出發(fā)之間的流程,按國內(nèi)航班(D)和國際航班(I),航站樓(T)和衛(wèi)星大廳(S)組成16 種不同的場景.同時最短流程時間不包括捷運通行時間和旅客步行時間.

(4)旅客換乘緊張度:表示旅客航班換乘時間除以航班的連續(xù)時間,而航班的換乘時間則等于最短旅客流程時間加上捷運通行時間以及步行時間.航班的連續(xù)時間等于前一航班的達到時間減去下一航班的出發(fā)時間.

本文在航班合理分配登機口的基礎(chǔ)上,盡可能的減少登機口數(shù)量和臨時登機口的使用數(shù)量,同時還需考慮旅客換乘影響因素,例如旅客的捷運時間、行走時間及航班連接時間,這3 個外生變量.而新建的衛(wèi)星廳則延長了中轉(zhuǎn)旅客的換乘時間,本文綜合考慮了所有旅客的換乘緊張度、使用登機口的數(shù)量、使用臨時登機口的數(shù)量,使其加權(quán)和最小.

2 數(shù)學(xué)模型建立

2.1 基本假設(shè)

假設(shè)臨時機位的數(shù)量無限多,停留在臨時登機口飛機的乘客不計算其換乘緊張度.因為在模型中已最小使用臨時登機口的數(shù)目,假設(shè)臨時機位數(shù)量無限多,為了防止飛機無法安排在合適的登機口,得不到可行解.

2.2 參數(shù)及決策變量的定義

(1)參數(shù)

K:固定登機口的集合;

I:所有飛機的集合;

C:旅客的集合;

si:飛機i的到達時刻;

ei:飛機i的出發(fā)時刻;

sc:旅客c的到達時刻;

ec:旅客c的出發(fā)時刻;

dik:飛機i是否允許使用登機口k.如果是,則為1,否則為0;

ni:飛機i的乘客數(shù)量;

hci:旅客c是否乘坐飛機i.如果是,則為1,否則為0;

p:DT、DS、IT和IS 中的一種,其中D 表示國內(nèi),I 表示國際,T 表示航空樓,S 表示衛(wèi)星廳;

q:DT、DS、IT和IS 中的一種,其中D 表示國內(nèi),I 表示國際,T 表示航空樓,S 表示衛(wèi)星廳;

L:表示p和q的集合;

w1:使用臨時機位個數(shù)權(quán)重;

w2:換乘緊張度權(quán)重;

w3:使用登機口數(shù)量權(quán)重.

(2)決策變量

uk:登機口k是否被使用.如果是,則為1,否則為0;

zi:飛機i是否停在臨時停機位.如果是,則為1,否則為0;

xik:飛機i是否可以停靠在登機口k.如果是,則為1,否則為0;

lij:在同一登機口的飛機i是否比飛機j?？繒r間早.如果是,則為1,否則為0;

fc:旅客c是否換乘成功.如果是,則為0,否則為1;

:到達類型出發(fā)類型q的旅客c是否在登機口k到達在登機口m起飛.如果是,則為1,否則為0;

:到達類型為p且 在登機口k到達,出發(fā)類型為q且在登機口m出發(fā)的旅客c的流程時間;

:到達類型為p且在登機口k到達出發(fā)類型為q且在登機口m出發(fā)的旅客c的行走時間;

:在登機口k到達在登機口m出 發(fā)的旅客c的捷運時間;

M(c):換乘成功旅客c的換乘緊張度,計算公式為:

N(c):換乘失敗旅客c的換乘緊張度,計算公式為:

2.3 模型建立

建立的0-1 整數(shù)線性規(guī)劃模型為:

其中,在目標(biāo)函數(shù)式(1)中,第一項為臨時機位的數(shù)量,第二項為中轉(zhuǎn)旅客的換乘緊張度,第三項為被使用登機口的數(shù)量;約束條件式(2)表示?？匡w機的類型必須和登機口允許的類型一致;約束條件式(3)表示如果有飛機停在某登機口,則表明該登機口被使用;約束條件式(4)表示每架飛機都至少要停在固定登機口或者臨時機位;約束條件式(5)表示?？吭谕粋€登機口的兩架飛機,后一飛機必須在前一飛機起飛后 τ分鐘后才能到達該登機口,本文中取 τ=45;約束條件式(6)表示在式(5)的前提下,這兩架飛機都?？吭谠摰菣C口;約束條件式(7)表示某旅客的到達時間、中轉(zhuǎn)流程時間和起飛時間之間的數(shù)量關(guān)系;約束條件式(8)和式(9)表示某旅客使用的登機口和該旅客乘坐的飛機使用的登機口應(yīng)該相同;約束條件式(10)表示這些變量都是0-1 變量.

3 基于集束搜索的改進模擬退火算法

3.1 模擬退火算法介紹

模擬退火算法(simulated annealing algorithm)是一種根據(jù)給定的函數(shù),通過概率選擇構(gòu)造解獲得全局近似最優(yōu)解的啟發(fā)式算法.該算法的優(yōu)點是在初期就能夠搜索廣泛的解空間,并能通過擴大搜索范圍以及接受較差解來避免算法陷入局部最優(yōu),最早由Kirkpatrick用以解決組合優(yōu)化問題,但在后來的大量研究發(fā)現(xiàn),傳統(tǒng)的模擬退火算法在面臨大規(guī)模的優(yōu)化問題時,普遍存在算法參數(shù)敏感、易早熟陷入局部最優(yōu)等問題.

3.2 集束搜索改進模擬退火算法

集束搜索(beam search)是一種根據(jù)給定的規(guī)則,通過下界來指導(dǎo)搜索過程的經(jīng)典搜索樹算法,在不排除最優(yōu)解的期望下,減掉一些質(zhì)量較差的解,保留質(zhì)量較高的解,提高整體算法性能.改進后的算法的基本框架同模擬退火算法相同,但是在迭代規(guī)則構(gòu)造方法上采用集束搜索,同時利用了Two-exchange 算子及Relocate算子構(gòu)造領(lǐng)域,通過保留一定數(shù)量的不完全解及增加搜索空間,來避免算法陷入局部最優(yōu)解,彌補傳統(tǒng)模擬退火算法的不足.

基于此,本文結(jié)合變鄰域搜索的鄰域構(gòu)造思想,綜合利用集束搜索和模擬退火算法的優(yōu)點,提出了基于集束搜索的改進型模擬退火算法(simulated annealing algorithm based beam search),并使用該方法對本文模型進行求解.

第1 步:參數(shù)初始化

(1)給出初始解:加權(quán)的使用臨時登機口的數(shù)目,使用登機口的數(shù)目,和在固定登機口的旅客數(shù)目之和最小為目標(biāo)函數(shù),以式(2)～式(6)為約束,用CPLEX 求出該問題的最優(yōu)解作為初始解,這個初始解只考慮了飛機-登機口分配,分配好之后,乘客與飛機綁定在一起,這樣只是構(gòu)造一個初始解.

(2)設(shè)定初始溫度為Tstart,衰減率為d,終止溫度為Tend.

第2 步:基于Two-exchange 算子的鄰域構(gòu)造

Two-exchange 算子:交換兩個登機口所停靠的飛機,令在登機口k1?？康娘w機分別為a′1,a′2,a′3等,即Gatek1={a′1,a′2,a′3,···},令在登機口k2?？康娘w機分別為a′1′,a′2′,a′3′等,即Gatek2={a′′1,a′′2,a′′3,···},經(jīng)Two-exchange 算子處理后,?？吭诘菣C口k1和k2飛機的一種調(diào)整方式為Gatek1={a′1,a′′2,a′3,···}和Gatek2={a′′1,a′2,a′′3,···}.

利用Two-exchange 算子得到上述解的集合中每個解的領(lǐng)域,在其中按照如下模擬退火規(guī)則選取n個較優(yōu)的子代解:

(1)如果子代解的目標(biāo)值優(yōu)于父代解,則保留;

(2)如果子代解的目標(biāo)值與父代解相同,則以一定的小概率p保留;

(3)如果子代解的目標(biāo)值劣于父代解,則根據(jù):

其中,Δ=objnew-ob jold

決策保留的子代解,越差的解保留概率越大;

(4)如果保留的解集個數(shù)已經(jīng)達到了上限n,則遍歷已保留的解,替換第一個找到比當(dāng)前保留的解大的解;如果是未改進的解,則不保留.

第3 步:基于Relocate 算子的鄰域構(gòu)造

Relocate 算子:將停靠在某個登機口的飛機轉(zhuǎn)移到另一個登機口去?？?對停靠在登機口k1的飛機集合Gatek1={a′1,a′2,a′3,···}和?？吭诘菣C口k2的飛機集合Gatek2={a′′1,a′′2,a′′3,···},經(jīng)Relocate 算子處理后,停靠在登機口k1和k2飛 機的一種調(diào)整方式為Gatek1={a′1,a′3,···}和Gatek2={a′′1,a′′2,a′′3,a′2···}.利用Relocate 算子得到上述解的集合中每個解的領(lǐng)域,與上述模擬退火規(guī)則相同選取n個較優(yōu)的子代解.

第4 步:基于集束搜索的迭代規(guī)則構(gòu)造

將上述兩個集合合并,若其中有優(yōu)于全局最優(yōu)解的則進行更新,否則從合并后的集合中根據(jù)下列集束搜索規(guī)則選取m個較優(yōu)的解進入下一次迭代.

(1)首先將該集合按照目標(biāo)值由小到大進行排序;

(2)選取m/2的最優(yōu)個解與m/2的最劣個解組成下一次迭代的解的集合;

(3)更新當(dāng)前溫度T=T×d;

第5 步:終止條件

判斷循環(huán)條件并執(zhí)行循環(huán),如果當(dāng)前溫度T＞Tend,則執(zhí)行步驟2～4,否則終止.改進后的算法流程圖如圖2所示.

3.3 基于集束搜索的改進模擬退火算法的創(chuàng)新點

(1)保留概率計算方式的改進.

原始模擬退火算法的保留概率計算方式為:

本文提出算法的保留概率計算方式正好與此相反,這樣做是為了增強解的跳躍能力,所以越差的解保留概率越大.

(2)利用變鄰域搜索算法的優(yōu)勢,同時使用算子.

同時使用兩種算子,擴大產(chǎn)生的鄰域范圍,同時如果保留的解集個數(shù)已經(jīng)達到了上限n,則遍歷已保留的解,替換第一個找到比當(dāng)前保留的解大的解;如果是未改進的解,則不保留.

(3)允許較優(yōu)解和較劣解同時進入下一次迭代.

集束搜索一般會選擇目標(biāo)值更優(yōu)的多個解進入下一次迭代的考慮,考慮選擇較優(yōu)解和較劣解進入下一次迭代的優(yōu)勢在于有助于避免陷入局部最優(yōu)解,從而有助于逼近最優(yōu)解.

圖2 改進模擬退火算法流程圖

4 算例分析

數(shù)據(jù)來源包含某月20 號的某機場的飛機轉(zhuǎn)場記錄和旅客中轉(zhuǎn)記錄數(shù)據(jù)以及通過計算機隨機生成的旅客數(shù)據(jù).其中航站樓T 有28 個登機口,航站樓S 有41 個登機口,飛機共計305 架.在建立數(shù)學(xué)模型時,包含臨時機位數(shù)目權(quán)重w1=10 000、旅客最短流程時間權(quán)重w2=100、登機口使用數(shù)目權(quán)重w3=1這3 個參數(shù),在建立基于集束搜索的改進模擬退火算法時,包含模擬退火算法較優(yōu)子代解數(shù)目n=10、初始溫度Tstart、衰減比例d、終止溫度Tend和集束搜索算法較優(yōu)解數(shù)目m這5 個參數(shù),因此共計有6 個可調(diào)整參數(shù).

本文所考慮的基準(zhǔn)算法是禁忌搜索(Tabu Search)、變鄰域搜索(Variable Neighborhood Search),并加入經(jīng)典蟻群算法(Ant Colony Algorithm)進行求解性能對比,通過對這些參數(shù)進行調(diào)整,得到各種乘客下的4 種算法的最優(yōu)求解結(jié)果,如表1所示.

表1 不同乘客數(shù)下3 個算法性能對比

從表1中可以看出,在不同的乘客數(shù)下,隨著乘客數(shù)的增加,本文所提出算法的優(yōu)化效果都是要優(yōu)于禁忌搜索算法、變鄰域搜索算法和經(jīng)典蟻群算法.而且從表中改進百分比數(shù)據(jù)可以看出,相較于3 個算法的最優(yōu)結(jié)果,本文所提出算法的優(yōu)化改進效果基本上都在5%以上,由此可見本文算法的優(yōu)化效果非常明顯.

5 結(jié)論

本文研究了新建衛(wèi)星廳S 對中轉(zhuǎn)旅客的航班銜接的影響,為了優(yōu)化登機口分配和降低中轉(zhuǎn)旅客的換乘緊張程度,建立了0-1 整數(shù)規(guī)劃模型,利用本文所提出的基于集束搜索的改進模擬退火算法對問題進行求解,解結(jié)果表明:與禁忌搜索算法、變鄰域搜索算法和經(jīng)典蟻群算法相比,本文所提出算法的優(yōu)化效果更好.從實際應(yīng)用的角度來說,本文所提出模型對航班-登機口的分配問題具有重要參考價值,對提高機場的運營能力和旅客的服務(wù)水平大有裨益,本文所提出算法對于未來登機口問題的求解具有重大的參考和應(yīng)用價值.