基于改進(jìn)模擬退火算法的登機(jī)口分配問(wèn)題①

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

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

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

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

1 問(wèn)題描述

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

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

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

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

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

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

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

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

2.1 基本假設(shè)

假設(shè)臨時(shí)機(jī)位的數(shù)量無(wú)限多,停留在臨時(shí)登機(jī)口飛機(jī)的乘客不計(jì)算其換乘緊張度.因?yàn)樵谀Ｐ椭幸炎钚∈褂门R時(shí)登機(jī)口的數(shù)目,假設(shè)臨時(shí)機(jī)位數(shù)量無(wú)限多,為了防止飛機(jī)無(wú)法安排在合適的登機(jī)口,得不到可行解.

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

(1)參數(shù)

K:固定登機(jī)口的集合;

I:所有飛機(jī)的集合;

C:旅客的集合;

si:飛機(jī)i的到達(dá)時(shí)刻;

ei:飛機(jī)i的出發(fā)時(shí)刻;

sc:旅客c的到達(dá)時(shí)刻;

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

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

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

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

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

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

L:表示p和q的集合;

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

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

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

(2)決策變量

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

zi:飛機(jī)i是否停在臨時(shí)停機(jī)位.如果是,則為1,否則為0;

xik:飛機(jī)i是否可以?？吭诘菣C(jī)口k.如果是,則為1,否則為0;

lij:在同一登機(jī)口的飛機(jī)i是否比飛機(jī)j停靠時(shí)間早.如果是,則為1,否則為0;

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

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

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

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

:在登機(jī)口k到達(dá)在登機(jī)口m出 發(fā)的旅客c的捷運(yùn)時(shí)間;

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

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

2.3 模型建立

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

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

3 基于集束搜索的改進(jìn)模擬退火算法

3.1 模擬退火算法介紹

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

3.2 集束搜索改進(jìn)模擬退火算法

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

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

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

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

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

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

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

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

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

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

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

其中,Δ=objnew-ob jold

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

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

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

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

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

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

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

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

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

第5 步:終止條件

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

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

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

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

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

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

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

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

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

圖2 改進(jìn)模擬退火算法流程圖

4 算例分析

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

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

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

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

5 結(jié)論

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