袁 媛，翟好鑫，吳宏元，閆 萍

(沈陽(yáng)航空航天大學(xué) 經(jīng)濟(jì)與管理學(xué)院，沈陽(yáng) 110136)

民用機(jī)場(chǎng)的停機(jī)位作為進(jìn)港飛機(jī)運(yùn)行的終點(diǎn)和離港飛機(jī)運(yùn)行的起點(diǎn)，為飛機(jī)停放、旅客上下飛機(jī)、行李貨物裝載提供了場(chǎng)所，也是航空與地面運(yùn)輸?shù)霓D(zhuǎn)接點(diǎn)。隨著航空運(yùn)輸業(yè)的快速發(fā)展，國(guó)內(nèi)各大機(jī)場(chǎng)的航班數(shù)量都有明顯增長(zhǎng)，有限的機(jī)場(chǎng)設(shè)施資源逐漸成為限制民航事業(yè)發(fā)展的重要因素，因此，合理地分配使用各項(xiàng)設(shè)施資源是機(jī)場(chǎng)需要解決的主要問(wèn)題。停機(jī)位作為機(jī)場(chǎng)運(yùn)輸資源的核心，其分配結(jié)果對(duì)大量物資、旅客以及相關(guān)工作人員都會(huì)產(chǎn)生影響，分配計(jì)劃對(duì)機(jī)場(chǎng)航班和航線也均有直接的經(jīng)濟(jì)影響。作為機(jī)場(chǎng)運(yùn)營(yíng)管理人員日常面臨的重要問(wèn)題之一，停機(jī)位分配的目的是把每個(gè)航班分配至可用的登機(jī)口，同時(shí)也最大限度地為乘客和機(jī)場(chǎng)的運(yùn)營(yíng)效率提供便利，這就需要一個(gè)方法來(lái)實(shí)時(shí)更改和更新停機(jī)位分配數(shù)據(jù)。

為解決這一問(wèn)題人們進(jìn)行了大量的研究，許多學(xué)者針對(duì)經(jīng)典停機(jī)位分配問(wèn)題 (Gate Assignment Problem,GAP)進(jìn)行研究和改進(jìn)，包括綜合考慮停機(jī)位分配各主體利益的多目標(biāo)優(yōu)化問(wèn)題[1]，最大化預(yù)分配方式魯棒性的優(yōu)化算法設(shè)計(jì)[2]，考慮機(jī)位類型時(shí)最大化航班靠橋率的優(yōu)化算法設(shè)計(jì)[3]，考慮航班時(shí)刻受到干擾時(shí)對(duì)停機(jī)位實(shí)時(shí)再分配問(wèn)題的優(yōu)化建模和算法進(jìn)行設(shè)計(jì)[4-5]等。

結(jié)合國(guó)內(nèi)外文獻(xiàn)對(duì)停機(jī)位分配問(wèn)題的分析，本文首先對(duì)停機(jī)位分配問(wèn)題的特征進(jìn)行描述，總結(jié)以往文獻(xiàn)中常見的約束條件和優(yōu)化目標(biāo)，并對(duì)解決停機(jī)位分配問(wèn)題的方法進(jìn)行分類總結(jié)，分析未來(lái)該領(lǐng)域發(fā)展可研究的方向。

1 問(wèn)題特征

1.1 約束條件

停機(jī)位分配涉及機(jī)場(chǎng)、旅客以及航空公司三方的切身利益，需要綜合考慮多方面的因素：機(jī)場(chǎng)的停機(jī)位數(shù)量、航班類型與停機(jī)位類型的匹配、飛機(jī)機(jī)型、停機(jī)位的分布構(gòu)造、停機(jī)位利用率、靠橋率、航班時(shí)刻、航班數(shù)量與密度、地面作業(yè)時(shí)間、旅客總?cè)藬?shù)、旅客行走距離、停機(jī)位間距離、行李托運(yùn)距離等。

在為航班分配停機(jī)位時(shí)，兩個(gè)基本約束應(yīng)該首先滿足：

(1)唯一性約束

每一個(gè)航班能且只能被分配到一個(gè)停機(jī)位。

(2)獨(dú)占性約束

飛機(jī)在時(shí)間上和空間上對(duì)停機(jī)位具有獨(dú)占性。

除了以上兩個(gè)基本約束之外，在實(shí)際機(jī)場(chǎng)運(yùn)行過(guò)程中和以往文獻(xiàn)研究中也經(jīng)?？紤]下列8個(gè)重要約束(見表1)。

(3)緩沖時(shí)間約束

對(duì)于連續(xù)分配到同一停機(jī)位的兩架飛機(jī)來(lái)說(shuō)，它們應(yīng)該有必要的安全時(shí)間間隔，被稱為停機(jī)位緩沖時(shí)間，用來(lái)保障前后航班的安全，還要給地面作業(yè)人員充足的準(zhǔn)備工作時(shí)間。同時(shí)緩沖時(shí)間還可以吸收實(shí)際運(yùn)行中存在的隨機(jī)延誤，大多數(shù)文獻(xiàn)都會(huì)考慮此約束，一般取值在10～50分鐘不等。

表1 約束條件文獻(xiàn)概況

(4)等待時(shí)間限制

航班到達(dá)機(jī)場(chǎng)上空時(shí)，可能會(huì)因?yàn)榉峙湟蟛辉试S立刻降落而執(zhí)行空中等待指令，但其有最大的空中等待時(shí)間限制。

(5)航班機(jī)型與停機(jī)位類型匹配性約束

機(jī)場(chǎng)停機(jī)位有大停機(jī)位和小停機(jī)位之分，一般情況下大型飛機(jī)不允許停放至小型機(jī)位，而大型機(jī)位由于可以滿足小型飛機(jī)的服務(wù)需求，也可以停放小型飛機(jī)，但會(huì)降低停機(jī)位的利用率，影響到后續(xù)大型飛機(jī)的停機(jī)位分配，因此機(jī)場(chǎng)一般會(huì)盡量減少小型航班停放到大型機(jī)位的情況。因此，關(guān)注機(jī)場(chǎng)停機(jī)位利用率的文獻(xiàn)大都會(huì)考慮此約束。

(6)停機(jī)位與航空公司的約束

即航空公司屬性約束。機(jī)場(chǎng)為了方便地勤服務(wù)的需求，會(huì)對(duì)不同航空公司分配其專屬的機(jī)位，應(yīng)盡量將該航空公司航班分配至專屬停機(jī)位，以提高停機(jī)位分配效率。由于不同航空公司之間的競(jìng)爭(zhēng)性，考慮航空公司公平性的文獻(xiàn)一般會(huì)采用此約束。

(7)航線屬性約束

即停機(jī)位與停放航班的航線屬性匹配。一般情況下，中小機(jī)場(chǎng)的大部分停機(jī)位只能停放飛往國(guó)內(nèi)航線的飛機(jī)，少量機(jī)位可以停放飛往國(guó)際航線的飛機(jī)。

(8)同一跑道飛機(jī)下降時(shí)間限制

在同一跑道上相繼降落的航班之間有最小降落時(shí)間間隔，用以保證安全，研究多跑道機(jī)場(chǎng)的停機(jī)位分配問(wèn)題一般會(huì)考慮此約束。

(9)宵禁限制

宵禁限制用來(lái)保證時(shí)間窗結(jié)束前安排好航班的停機(jī)位。

(10)使用登機(jī)橋登機(jī)的旅客占比約束

中國(guó)民用航空局發(fā)布的《民用機(jī)場(chǎng)服務(wù)質(zhì)量》中規(guī)定，旅客通過(guò)登機(jī)橋登機(jī)的數(shù)量不宜低于80%。

以上所列舉的約束是一些比較常見的約束，除了上述約束規(guī)則還有許多其它約束，機(jī)場(chǎng)的實(shí)際情況不同，其對(duì)應(yīng)的約束也會(huì)相應(yīng)發(fā)生變化。

1.2 主要優(yōu)化目標(biāo)

停機(jī)位分配問(wèn)題涉及到機(jī)場(chǎng)、旅客以及航空公司多方主體的利益，為多目標(biāo)組合優(yōu)化問(wèn)題。以往的停機(jī)位分配研究由于不同的機(jī)場(chǎng)側(cè)重點(diǎn)不同，主要注重提高旅客服務(wù)質(zhì)量、優(yōu)化機(jī)場(chǎng)和航空公司的運(yùn)行效益。本文從以下3個(gè)方面對(duì)主要優(yōu)化目標(biāo)進(jìn)行介紹(見表2)。

表2 優(yōu)化目標(biāo)文獻(xiàn)概況

(1)機(jī)場(chǎng)方面

①最大化停機(jī)位預(yù)分配方式的魯棒性

停機(jī)位分配的魯棒性是指停機(jī)位預(yù)分配方式自身具有一定的“抗干擾能力”。由于目前機(jī)場(chǎng)停機(jī)位資源非常緊缺，當(dāng)進(jìn)離港航班發(fā)生不確定性延誤時(shí)，就不可避免地影響到其他航班而導(dǎo)致重新分配。因此，為提高機(jī)場(chǎng)的服務(wù)質(zhì)量，降低機(jī)場(chǎng)的運(yùn)營(yíng)成本，在確保機(jī)場(chǎng)快速恢復(fù)的情況下，還應(yīng)該使航班的機(jī)位分配與原計(jì)劃?rùn)C(jī)位分配盡量保持一致[6]。

②停機(jī)位占用均衡

綜合考慮旅客候機(jī)便捷與舒適和行李提取、機(jī)場(chǎng)安檢等問(wèn)題，當(dāng)停機(jī)位空閑時(shí)應(yīng)盡量分散?？康暮桨啵C(jī)位空閑時(shí)間段的相對(duì)均衡可以明顯降低航班由于延誤起飛或到達(dá)而產(chǎn)生的影響，同時(shí)也能保證機(jī)場(chǎng)調(diào)度人員工作強(qiáng)度與時(shí)間的均衡。因此，該目標(biāo)函數(shù)在近幾年的文獻(xiàn)中使用較多。

③最少化占用停機(jī)位數(shù)目

在考慮旅客登轉(zhuǎn)機(jī)時(shí)間、停機(jī)時(shí)間、空中等待時(shí)間、航班機(jī)型與停機(jī)位匹配、航班類型、數(shù)量與密度等優(yōu)化目標(biāo)的條件下，將有限的停機(jī)位資源快速合理地分配給更多的航班。這需要更加經(jīng)濟(jì)合理地使用機(jī)場(chǎng)固定設(shè)施資源，從而使停機(jī)位盡可能多地安排航班的停機(jī)位進(jìn)行作業(yè)。

④最大化停機(jī)位效率

一方面，由于機(jī)場(chǎng)停機(jī)位是有限的，如果航班沒(méi)有合適的近機(jī)位可供起降，就只能使用遠(yuǎn)停機(jī)坪，采用擺渡車上下旅客，增加旅客在機(jī)場(chǎng)停留的時(shí)間，也會(huì)增加地面作業(yè)成本，因此應(yīng)尋求一種分配方案，使未分配至近機(jī)位的航班盡可能少。而最大化航班靠橋率是繁忙機(jī)場(chǎng)評(píng)價(jià)停機(jī)位分配方案的依據(jù)，航班靠橋率即?？拷鼨C(jī)位的航班數(shù)量占航班總數(shù)的比例[7]。另一方面，為了最大化機(jī)場(chǎng)停機(jī)位利用率，飛機(jī)機(jī)型要與所停放的停機(jī)位大小匹配。如果當(dāng)前暫時(shí)沒(méi)有空閑機(jī)位，應(yīng)該將到達(dá)的飛機(jī)先停放至遠(yuǎn)機(jī)位等待再次分配機(jī)位。由于機(jī)型與停機(jī)位不匹配將導(dǎo)致停機(jī)位資源的嚴(yán)重浪費(fèi)，最大化停機(jī)位利用率、最大化靠橋率也就是最小化停機(jī)位資源的浪費(fèi)[8]。因此，如何高效率地利用機(jī)場(chǎng)有限的資源也是國(guó)內(nèi)外文獻(xiàn)研究的熱點(diǎn)。

⑤最小化停機(jī)位計(jì)劃成本

機(jī)場(chǎng)進(jìn)行停機(jī)位分配時(shí)會(huì)消耗一定的成本，如機(jī)場(chǎng)資源的使用成本，相關(guān)工作人員的調(diào)度成本。如何經(jīng)濟(jì)有效地利用機(jī)場(chǎng)有限的資源進(jìn)行停機(jī)位分配是機(jī)場(chǎng)主體方常考慮的優(yōu)化目標(biāo)。

(2)旅客方面

①最小化旅客等待時(shí)間

在機(jī)場(chǎng)運(yùn)行管理中，同一個(gè)時(shí)段可能會(huì)有多個(gè)航班起降，航班降落后?？吭谙鄳?yīng)的停機(jī)位，并隨之進(jìn)行清潔、加油、食品供應(yīng)等一系列的地面作業(yè)，等到飛機(jī)準(zhǔn)備就緒后再起飛，因?yàn)楹桨鄶?shù)量眾多，機(jī)場(chǎng)的停機(jī)位可能不滿足一對(duì)一的?？俊．?dāng)前一航班降落并?？恐聊骋惶囟ㄍC(jī)位完成地面作業(yè)起飛之后，后續(xù)的航班才能停靠在同一機(jī)位，因此優(yōu)化目標(biāo)需要考慮最小化航班延誤時(shí)間，即一個(gè)時(shí)段降落的航班都安排在停機(jī)位?？坎⑶沂购桨嘌诱`時(shí)間最小，以此減少旅客候機(jī)時(shí)間，即提升旅客的滿意度。如何最小化航班延誤給旅客帶來(lái)的影響也是大多數(shù)文獻(xiàn)的研究熱點(diǎn)。

②最小化旅客中轉(zhuǎn)等待成本

該目標(biāo)充分考慮航空公司的時(shí)隙互換性以及多航站樓的資源共享性，以最小化多方延誤費(fèi)用，降低航班延誤引起的旅客中轉(zhuǎn)等待成本，在航班波的環(huán)境下可以實(shí)現(xiàn)航空公司與機(jī)場(chǎng)的協(xié)同決策[9]。

③最小化旅客進(jìn)離港行走距離

旅客到達(dá)或離開機(jī)場(chǎng)時(shí)，進(jìn)離港的距離較先決定了旅客的行程體驗(yàn)，為提高服務(wù)質(zhì)量，應(yīng)減少旅客行走距離，為旅客帶來(lái)便利。因此，關(guān)注旅客滿意度的文獻(xiàn)大都會(huì)使用該目標(biāo)函數(shù)。

④最小化旅客轉(zhuǎn)機(jī)行走距離

旅客由于不確定因素需要轉(zhuǎn)機(jī)，為了給旅客提供方便，提高旅客滿意度，最小化旅客轉(zhuǎn)機(jī)行走距離的優(yōu)化目標(biāo)常被提及。

(3)航空公司

①最少化耗油量

燃油成本是航空公司最直接的運(yùn)行成本，最少化航空公司的耗油量將降低飛機(jī)的燃油消耗，使機(jī)場(chǎng)的運(yùn)營(yíng)成本降低，其中減少航班在機(jī)場(chǎng)的滑行距離也會(huì)節(jié)省航空燃料。因此，國(guó)內(nèi)外很多文獻(xiàn)都從降低航空公司油耗成本角度考慮停機(jī)位分配問(wèn)題。

②最小化總延誤成本

在協(xié)同決策機(jī)制下綜合考慮多方主體利益，建立多目標(biāo)一體化停機(jī)位實(shí)時(shí)分配模型，考慮航班延誤、飛機(jī)交換、空中等待等多方面成本，有利于從根本上節(jié)約成本。

③最小化場(chǎng)面滑行時(shí)間

目前對(duì)于停機(jī)位分配的研究主要針對(duì)機(jī)場(chǎng)的陸側(cè)部分，但對(duì)于樞紐機(jī)場(chǎng)來(lái)說(shuō)，旅客在機(jī)場(chǎng)飛行區(qū)的停留時(shí)間大大超過(guò)了航站樓內(nèi)部行走所需的時(shí)間，這也是航班延誤的主要原因。因此優(yōu)化目標(biāo)應(yīng)考慮最小化場(chǎng)面滑行時(shí)間，以確保航班的正常運(yùn)行。

④最大化航空公司的公平性

航空運(yùn)輸業(yè)作為高風(fēng)險(xiǎn)、高投入的資金密集型行業(yè)，降低成本對(duì)于每一個(gè)航空公司都具有非常重要的意義。近幾年的文獻(xiàn)非常關(guān)注航空公司之間競(jìng)爭(zhēng)的公平性，且大部分從耗油成本和延誤損失等方面考慮均衡的機(jī)位分配策略。

2 研究方法

停機(jī)位分配問(wèn)題是近年來(lái)學(xué)術(shù)界研究的熱點(diǎn)。該問(wèn)題是一個(gè)NP-hard問(wèn)題，其計(jì)算的時(shí)間復(fù)雜度隨著機(jī)場(chǎng)和航班規(guī)模的增加呈指數(shù)增長(zhǎng)，對(duì)于大規(guī)模問(wèn)題在較短時(shí)間內(nèi)難以獲得最優(yōu)解。停機(jī)位分配有許多分類方法，文獻(xiàn)[10]研究了理論和實(shí)際的AGAP問(wèn)題后將研究方法分為精確算法、啟發(fā)式算法和元啟發(fā)式算法；文獻(xiàn)[11]把停機(jī)位研究方法按專家系統(tǒng)、數(shù)學(xué)規(guī)劃和人工智能進(jìn)行分類；文獻(xiàn)[12]把解決停機(jī)位分配問(wèn)題的文獻(xiàn)總結(jié)為集中在建模算法上和集中在模型仿真上兩種類型。本文從數(shù)學(xué)規(guī)劃、智能優(yōu)化和系統(tǒng)仿真三類方法來(lái)綜述停機(jī)位分配問(wèn)題的研究現(xiàn)狀。

2.1 數(shù)學(xué)規(guī)劃法

數(shù)學(xué)規(guī)劃法是指將機(jī)場(chǎng)的各種約束規(guī)則，如航班類型、位置、航班時(shí)刻、機(jī)位類型等用關(guān)系式或符號(hào)表示，再根據(jù)實(shí)際情況建立相應(yīng)的數(shù)學(xué)模型，最后從運(yùn)籌學(xué)角度對(duì)優(yōu)化模型進(jìn)行求解[13]。數(shù)學(xué)規(guī)劃方法的主要問(wèn)題在于目標(biāo)函數(shù)的選擇，由于影響停機(jī)位的因素非常多，怎樣綜合考慮多種影響因素并提出符合實(shí)際問(wèn)題的優(yōu)化目標(biāo)函數(shù)、快速地設(shè)計(jì)出有效的求解算法是當(dāng)前研究急需解決的問(wèn)題。早期的運(yùn)籌學(xué)中的傳統(tǒng)方法，如整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、線性規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、分支定界法等大都屬于此類?；趩渭冃畏ā⒎种Фń缂夹g(shù)和列生成法，一些學(xué)者提出了如圖著色模型及算法、頂點(diǎn)著色模型及算法、排序算法等。

(1)整數(shù)規(guī)劃

國(guó)外早期就對(duì)此方法進(jìn)行研究，主要運(yùn)用混合整數(shù)規(guī)劃、0-1整數(shù)規(guī)劃進(jìn)行建模：文獻(xiàn)[14]建立了基于混合整數(shù)規(guī)劃的數(shù)學(xué)模型來(lái)解決機(jī)型指派問(wèn)題；文獻(xiàn)[15]研究了基于專門分支和定界程序的求解技術(shù)，同時(shí)提出基于大鄰域搜索原理的改進(jìn)方法；文獻(xiàn)[16]在傳統(tǒng)的確定性模型基礎(chǔ)上，提出了0-1整數(shù)規(guī)劃，用于航班在延誤的情況下對(duì)停機(jī)位進(jìn)行最優(yōu)重分配，該計(jì)劃最大限度地減少了進(jìn)離港和中轉(zhuǎn)旅客的總步行距離，但并未提出求解該模型的算法。近些年停機(jī)位分配建模逐漸開始關(guān)注魯棒性問(wèn)題，文獻(xiàn)[17]就采用0-1整數(shù)規(guī)劃方法來(lái)提高停機(jī)位分配問(wèn)題的魯棒性。因?yàn)镹P-hard問(wèn)題，大規(guī)模整數(shù)規(guī)劃模型求解上一般需要借助其他智能算法。

國(guó)內(nèi)對(duì)于停機(jī)位分配熱點(diǎn)問(wèn)題的關(guān)注稍晚于國(guó)外，早期文獻(xiàn)[6]總結(jié)并分析了國(guó)內(nèi)繁忙機(jī)場(chǎng)停機(jī)位分配情況和機(jī)場(chǎng)運(yùn)行管理方式，并建立了以最小化更換停機(jī)位的航班數(shù)和機(jī)場(chǎng)恢復(fù)正常起降后分配到遠(yuǎn)機(jī)位的航班數(shù)之加權(quán)和為優(yōu)化目標(biāo)的整數(shù)規(guī)劃模型。近五年內(nèi)緊跟科研熱點(diǎn)利用整數(shù)規(guī)劃進(jìn)行建模，許多文獻(xiàn)開始關(guān)注旅客滿意度，文獻(xiàn)[18]建立了以停機(jī)位保障能力和客戶滿意度為目標(biāo)優(yōu)化模型，文獻(xiàn)[19]-[20]以最小化旅客行走距離為目標(biāo)建立了停機(jī)位分配優(yōu)化模型，對(duì)旅客滿意度的關(guān)注在一定程度上提升了機(jī)場(chǎng)的服務(wù)質(zhì)量。還有一些文獻(xiàn)則較為關(guān)注非正常運(yùn)行情況下的停機(jī)位調(diào)度問(wèn)題：文獻(xiàn)[21]建立了以最小化航班延誤時(shí)間為目標(biāo)的整數(shù)規(guī)劃模型對(duì)機(jī)場(chǎng)航班停機(jī)位調(diào)度進(jìn)行研究；文獻(xiàn)[22]從機(jī)場(chǎng)和航班非正常運(yùn)行的角度出發(fā)，建立了混合整數(shù)規(guī)劃模型并取得較好效果，解決了研究領(lǐng)域熱點(diǎn)停機(jī)位實(shí)時(shí)分配問(wèn)題；文獻(xiàn)[23]把國(guó)際和國(guó)內(nèi)航班的停機(jī)位作為研究對(duì)象，以最小化等待停機(jī)位的航班數(shù)量為目標(biāo)建立了整數(shù)規(guī)劃模型。對(duì)航班延誤等非正常運(yùn)行情況的研究大大提高了機(jī)場(chǎng)的運(yùn)行效率，同時(shí)也使旅客滿意度有所增加。另外，分支定界法作為一種較為常用的整數(shù)規(guī)劃方法，較適用于變量數(shù)量和約束條件都較少的問(wèn)題求解，但因?yàn)椴荒軡M足動(dòng)態(tài)實(shí)時(shí)性要求而不適用于解決停機(jī)位分配一類規(guī)模較大的問(wèn)題。

(2)圖論相關(guān)方法

圖論是用圖示的方法把任務(wù)成員特征和接受任務(wù)成員特征描述出來(lái)，用圖論的方法在任務(wù)和系統(tǒng)成員之間建立匹配，并據(jù)此設(shè)計(jì)出可行合理的任務(wù)分配方法。而圖著色法是針對(duì)沖突圖中的頂點(diǎn)來(lái)著色，在滿足一定條件的情況下讓任意2個(gè)相鄰頂點(diǎn)不具有同樣的顏色，且使所需要的顏色數(shù)最少，即停機(jī)位數(shù)量最少。

① 圖著色模型及算法

圖著色問(wèn)題在調(diào)度領(lǐng)域應(yīng)用非常廣泛，目前已被應(yīng)用于資源分配、貨物存儲(chǔ)、課表編排和頻率分配，國(guó)外文獻(xiàn)[24]-[25]提出了用圖論方法來(lái)解決具有確定性和隨機(jī)目標(biāo)的停機(jī)位分配問(wèn)題，并在后來(lái)的工作中針對(duì)同樣的問(wèn)題提出了可靠方法。國(guó)內(nèi)有部分學(xué)者早期對(duì)圖著色模型研究較多：文獻(xiàn)[26]根據(jù)停機(jī)位排序模型設(shè)計(jì)出一種標(biāo)號(hào)算法，并據(jù)此設(shè)計(jì)了頂點(diǎn)序列著色算法；文獻(xiàn)[27]利用劃片時(shí)間片算法將停機(jī)位分配問(wèn)題轉(zhuǎn)化為圖定點(diǎn)著色問(wèn)題；文獻(xiàn)[28]使用時(shí)間沖突算法建立了停機(jī)位分配計(jì)劃的頂點(diǎn)著色模型，結(jié)合圖著色問(wèn)題分解算法應(yīng)用到具體的機(jī)場(chǎng)管理中，這種方法使機(jī)場(chǎng)設(shè)施資源更高效地被利用。但該模型主要關(guān)注使用停機(jī)位數(shù)量最少的目標(biāo)函數(shù)，因此對(duì)所研究問(wèn)題的范圍有一定限制。最新的文獻(xiàn)一般基于圖論的思想來(lái)求解其他目標(biāo)函數(shù)，文獻(xiàn)[29]引入有向無(wú)環(huán)圖并基于網(wǎng)絡(luò)狀態(tài)圖建立了線性規(guī)劃模型，設(shè)計(jì)了一個(gè)成本最小化和飛機(jī)使用均衡的目標(biāo)函數(shù)。

② 多商品網(wǎng)絡(luò)流模型

多商品網(wǎng)絡(luò)流停機(jī)位實(shí)時(shí)分配模型把停機(jī)位映射為商品，這些商品在源節(jié)點(diǎn)和終節(jié)點(diǎn)之間通過(guò)眾多到達(dá)節(jié)點(diǎn)和離開節(jié)點(diǎn)連接，當(dāng)連接節(jié)點(diǎn)之間的弧可以利用時(shí)商品就會(huì)流經(jīng)此弧，即停機(jī)位可以分配給該航班，否則不能分配給該航班。

國(guó)外文獻(xiàn)較早將網(wǎng)絡(luò)流理論運(yùn)用到停機(jī)位分配中，針對(duì)暫缺飛機(jī)的實(shí)時(shí)擾動(dòng)問(wèn)題，文獻(xiàn)[30]采用調(diào)機(jī)策略，并且對(duì)延誤和取消策略分別建立了最小費(fèi)用網(wǎng)絡(luò)流模型，但是這兩個(gè)模型只能單獨(dú)使用。近年來(lái)大部分文獻(xiàn)用其解決多目標(biāo)優(yōu)化問(wèn)題：文獻(xiàn)[31]對(duì)多商品網(wǎng)絡(luò)流模型進(jìn)行了分析，建立一種多目標(biāo)魯棒優(yōu)化模型并將其轉(zhuǎn)化為單目標(biāo)優(yōu)化模型進(jìn)行求解；文獻(xiàn)[32]基于0-1整數(shù)多商品網(wǎng)絡(luò)流模型提出了最小化飛機(jī)滑行的燃油消耗成本和因再分配停機(jī)位而引起的乘客不適的優(yōu)化目標(biāo)，該方法在實(shí)際問(wèn)題的分解方法中被證明計(jì)算效率很高；文獻(xiàn)[33]創(chuàng)新性地建立了兩個(gè)多商品網(wǎng)絡(luò)流模型，該模型針對(duì)停機(jī)位再分配問(wèn)題提出了一種有效的方法，并以最小化航班總延誤的加權(quán)和、再分配的次數(shù)和延誤轉(zhuǎn)機(jī)乘客數(shù)量為優(yōu)化目標(biāo)，文獻(xiàn)[33]中的模型是文獻(xiàn)[34]的重大改進(jìn)，雖然文獻(xiàn)[34]提出了類似的網(wǎng)絡(luò)流模型，但因?yàn)橹贫髁科胶獾姆绞绞箾Q策變量的數(shù)量隨著模型大小的增長(zhǎng)而迅速增長(zhǎng)，而抵消了多商品網(wǎng)絡(luò)流模型所帶來(lái)的高效率優(yōu)勢(shì)。由此可見，多商品網(wǎng)絡(luò)流在大規(guī)模停機(jī)位分配應(yīng)用中具有高效性，同時(shí)還可以對(duì)多目標(biāo)優(yōu)化問(wèn)題有效求解。

國(guó)內(nèi)學(xué)者主要將網(wǎng)絡(luò)流模型與算法相結(jié)合來(lái)解決停機(jī)位分配問(wèn)題。文獻(xiàn)[35]研究了不正常航班的飛機(jī)調(diào)度和機(jī)組調(diào)度，建立多商品網(wǎng)絡(luò)流的數(shù)學(xué)模型并采用算法進(jìn)行求解，并最終得到了一種基于列生成法的合理的飛機(jī)調(diào)度法。文獻(xiàn)[36]對(duì)列生成算法進(jìn)行改進(jìn)，將由于飛機(jī)資源短缺造成的不正常航班停機(jī)位分配問(wèn)題視為帶容量約束的多商品最小費(fèi)用流問(wèn)題，并建立了網(wǎng)絡(luò)流模型。網(wǎng)絡(luò)流理論和算法的結(jié)合使得停機(jī)位分配問(wèn)題的求解速度有了進(jìn)一步的提升。此后，文獻(xiàn)[37]還將其應(yīng)用在航線、機(jī)型調(diào)度中，建立了多機(jī)型一體化飛機(jī)排班的多商品網(wǎng)絡(luò)流模型。最新的文獻(xiàn)[19]也采用0-1整數(shù)多商品網(wǎng)絡(luò)流模型，解決了乘客滿意度不高和停機(jī)位再分配的延遲問(wèn)題。

(3)混合集合規(guī)劃方法

混合集合規(guī)劃方法建模的一般步驟為：數(shù)據(jù)建模、邏輯建模和求解規(guī)則設(shè)計(jì)?；旌霞弦?guī)劃方法首先通過(guò)約束推理對(duì)解空間進(jìn)行切割，然后查詢關(guān)鍵變量對(duì)解空間進(jìn)行搜索，這使得關(guān)鍵變量從模糊變?yōu)榇_定[7]。

近幾年國(guó)內(nèi)個(gè)別學(xué)者開始關(guān)注此方法，并將其運(yùn)用在繁忙機(jī)場(chǎng)和協(xié)同決策機(jī)制中。針對(duì)繁忙機(jī)場(chǎng)的停機(jī)位分配問(wèn)題，文獻(xiàn)[7]采用混合集合規(guī)劃方法進(jìn)行了數(shù)據(jù)建模和邏輯建模，運(yùn)用自然約束語(yǔ)言編程設(shè)計(jì)出高效的求解策略，并以國(guó)內(nèi)某繁忙機(jī)場(chǎng)為例進(jìn)行求解，結(jié)果表明混合集合規(guī)劃方法得出的分配相對(duì)于人工分配靠橋率提升了20.7%。文獻(xiàn)[9]與[38]較為重視協(xié)同決策機(jī)制，從多區(qū)域多航站樓的角度出發(fā)，綜合考慮機(jī)場(chǎng)、旅客和航空公司多方主體利益，借助混合集合規(guī)劃方法建立了停機(jī)位實(shí)時(shí)分配模型以保障航班波有效銜接，并求解了該模型。停機(jī)位分配問(wèn)題本身涉及機(jī)場(chǎng)、旅客、航空公司、空管等多方主體利益，因此混合集合規(guī)劃法在機(jī)場(chǎng)協(xié)同決策中的應(yīng)用對(duì)機(jī)場(chǎng)整體的運(yùn)營(yíng)效益非常重要。

(4)列生成算法

列生成算法將原線性規(guī)劃問(wèn)題分為主問(wèn)題和子問(wèn)題兩部分。其中因?yàn)橹鲉?wèn)題包含的變量數(shù)目非常多，故需從中選擇部分變量來(lái)構(gòu)建一個(gè)限制主問(wèn)題，通過(guò)對(duì)限制主問(wèn)題求解得到對(duì)偶變量，并將對(duì)偶變量傳遞給子問(wèn)題。然后對(duì)子問(wèn)題進(jìn)行求解，得出主問(wèn)題非基變量的最小簡(jiǎn)約成本，如果最小簡(jiǎn)約成本為負(fù)，則把其對(duì)應(yīng)的列加入到限制主問(wèn)題中繼續(xù)求解，直到最小簡(jiǎn)約成本大于等于零為止，此時(shí)即使得原問(wèn)題最優(yōu)。當(dāng)限制主問(wèn)題的解不是整數(shù)解時(shí)，采用分支定界法求出整數(shù)解。

對(duì)于列生成算法，國(guó)外文獻(xiàn)主要在算法設(shè)計(jì)上進(jìn)行創(chuàng)新。文獻(xiàn)[39]通過(guò)對(duì)有限變量集的迭代線性規(guī)劃求解，得到一個(gè)近似最優(yōu)解，首先用列生成的方法求解整數(shù)規(guī)劃松弛問(wèn)題，發(fā)現(xiàn)一個(gè)限制集，在每一個(gè)列生成迭代中都會(huì)生成少量的附加列，并將其放入列集中，在線性規(guī)劃松弛問(wèn)題得到最優(yōu)解后，利用列集中生成的列和所有附加列來(lái)解決線性規(guī)劃問(wèn)題。文獻(xiàn)[40]還提出了使用列生成算法直接將航班分配給物理停機(jī)位的可能性。這些研究都為將來(lái)的應(yīng)用研究提供了重要參考，但列生成算法的實(shí)施比較復(fù)雜，也一定程度地限制了該算法的應(yīng)用。

國(guó)內(nèi)文獻(xiàn)較為關(guān)注求解速度，由于一般的列生成算法在每次迭代過(guò)程中只加入一個(gè)列，造成算法迭代次數(shù)過(guò)多降低了效率，因此文獻(xiàn)[41]把具有相同性質(zhì)的停機(jī)位劃分為同一停機(jī)位類型，從而將停機(jī)位分配問(wèn)題轉(zhuǎn)化為選擇適合航班對(duì)應(yīng)機(jī)位類型的最佳停機(jī)位計(jì)劃，并在此基礎(chǔ)上建立了最大化停機(jī)位分配魯棒性的數(shù)學(xué)模型，并采用列生成算法較快求得結(jié)果。近幾年很多文獻(xiàn)也在算法上進(jìn)行改進(jìn)，文獻(xiàn)[36]在每次迭代中加入多個(gè)列，并對(duì)加入的多個(gè)列應(yīng)該滿足的條件進(jìn)行分析，提高了該算法的效率，最后用實(shí)例驗(yàn)證了此方法的有效性和正確性。為了實(shí)現(xiàn)模型的有效求解，文獻(xiàn)[37]提出了一種基于約束規(guī)劃的動(dòng)態(tài)列生成算法，該算法可以利用約束規(guī)劃實(shí)現(xiàn)快速求解，計(jì)算各個(gè)航班串的簡(jiǎn)約成本，實(shí)現(xiàn)動(dòng)態(tài)選擇列集并與限制主問(wèn)題進(jìn)行迭代，該方法對(duì)提高航空公司盈利能力的現(xiàn)實(shí)意義非常重要。

2.2 智能優(yōu)化算法

(1)遺傳算法(Genetic Algorithm)

使用遺傳算法，由于其生成的初始種群已經(jīng)找到一定數(shù)量的可行解，即使問(wèn)題規(guī)模變大，在要求時(shí)間內(nèi)不能夠完成規(guī)定代數(shù)的運(yùn)算時(shí)，也可以中止運(yùn)算，并得到較為優(yōu)化的分配結(jié)果。另外，遺傳算法具有并行性，解決問(wèn)題時(shí)可以依賴這一特性增加物理投入來(lái)減少運(yùn)行優(yōu)化時(shí)間。

國(guó)外文獻(xiàn)早期主要直接在停機(jī)位分配領(lǐng)域應(yīng)用該算法，文獻(xiàn)[4]運(yùn)用遺傳算法最小化航班等待時(shí)間。隨著該算法的普及，部分學(xué)者將其與其他算法相結(jié)合應(yīng)用，文獻(xiàn)[42]結(jié)合遺傳算法和蟻群優(yōu)化(ACO)算法，以客運(yùn)量、航空公司和機(jī)場(chǎng)運(yùn)營(yíng)的損失為目標(biāo)，建立了停機(jī)位分配的數(shù)學(xué)模型，并提出了一種兩級(jí)混合算法(GAOTWSH)用來(lái)解決延誤航班停機(jī)位調(diào)度的數(shù)學(xué)模型，對(duì)非正常航班停機(jī)位再分配的數(shù)學(xué)模型進(jìn)行了仿真和論證，為非正常航班飛行提供了一種新的方法和思路。很多文獻(xiàn)將遺傳算法應(yīng)用到多目標(biāo)優(yōu)化模型中，文獻(xiàn)[43]采用遺傳算法針對(duì)停機(jī)位分配問(wèn)題建立了多目標(biāo)優(yōu)化模型。最新文獻(xiàn)[44]將第二代非支配排序遺傳算法(NSGA-II)作為并行進(jìn)化優(yōu)化算法進(jìn)行求解，與其他多目標(biāo)算法相比在尋找較優(yōu)解方面顯示了良好的前景。

利用Citespace對(duì)近20年停機(jī)位分配領(lǐng)域的國(guó)內(nèi)文獻(xiàn)分析可以發(fā)現(xiàn)，國(guó)內(nèi)學(xué)者最常用的算法就是遺傳算法，且主要考慮在一些約束條件下對(duì)遺傳算法的應(yīng)用：文獻(xiàn)[45]主要考慮航班銜接和過(guò)站時(shí)間要求，建立了航班串的數(shù)學(xué)優(yōu)化模型，并構(gòu)造了一種自適應(yīng)遺傳算法進(jìn)行求解；文獻(xiàn)[46]采用遺傳算法對(duì)考慮安全運(yùn)行約束的停機(jī)位分配模型進(jìn)行有效求解；文獻(xiàn)[47]以各航空公司飛機(jī)滑行耗油均衡為目標(biāo)建立了停機(jī)位分配策略，采用遺傳算法進(jìn)行求解，證明了模型和算法的有效性。近年來(lái)部分學(xué)者也開始在遺傳算法設(shè)計(jì)上進(jìn)行改進(jìn)，文獻(xiàn)[48]引入了合作型協(xié)同進(jìn)化遺傳算法有效地解決了傳統(tǒng)遺傳算法種群多樣性低、易早熟的問(wèn)題。文獻(xiàn)[49]設(shè)計(jì)了求解最小化航班延誤成本模型的初始、改進(jìn)遺傳算法，而改進(jìn)后的模型算法提供的停機(jī)位再分配方案更優(yōu)。因此，對(duì)遺傳算法進(jìn)行改進(jìn)或?qū)⑵渑c其他算法相結(jié)合是未來(lái)該領(lǐng)域可研究的方向之一。

(2)禁忌搜索算法(Tabu Search)

禁忌搜索算法主要通過(guò)引入一個(gè)靈活的儲(chǔ)存結(jié)構(gòu)及其禁忌準(zhǔn)則來(lái)避免反復(fù)搜索，用來(lái)避免此搜索陷入局部最優(yōu)狀態(tài)，該算法還通過(guò)藐視準(zhǔn)則使部分被禁忌的優(yōu)良狀態(tài)得到利用，保證了多樣化、有效地搜索來(lái)實(shí)現(xiàn)全局優(yōu)化。其最重要的思想是對(duì)應(yīng)已經(jīng)搜索到的局部最優(yōu)對(duì)象進(jìn)行標(biāo)記，并在下一步迭代搜索中盡可能避開這些對(duì)象。

1989年Glover教授提出了禁忌搜索算法，該算法是一種通過(guò)模擬人類智力的元啟發(fā)式搜索技術(shù)，也是對(duì)局部鄰域搜索算法的一種豐富。禁忌搜索算法對(duì)于大規(guī)模問(wèn)題的求解有明顯優(yōu)勢(shì)，文獻(xiàn)[50]利用禁忌搜索算法來(lái)解決航班數(shù)量遠(yuǎn)大于可利用停機(jī)位數(shù)量時(shí)的停機(jī)位分配問(wèn)題。文獻(xiàn)[51]建立的隨機(jī)規(guī)劃模型是一個(gè)規(guī)模很大的混合整數(shù)規(guī)劃，該模型采用禁忌搜索算法求解并取得了較好效果。隨著禁忌搜索算法在該領(lǐng)域的逐漸應(yīng)用，很多學(xué)者開始對(duì)其進(jìn)行改進(jìn)，文獻(xiàn)[52]提出了一種新的禁忌搜索算法并與模擬退火方法作比較，證明了新提出的元啟發(fā)式算法較優(yōu)，并把開發(fā)出一種超啟發(fā)式算法作為未來(lái)的研究方向，希望其根據(jù)實(shí)現(xiàn)的問(wèn)題自動(dòng)選擇更有效的元啟發(fā)式算法。

國(guó)內(nèi)文獻(xiàn)早期將禁忌搜索算法應(yīng)用于應(yīng)急停機(jī)位調(diào)度領(lǐng)域，文獻(xiàn)[6]設(shè)計(jì)了禁忌搜索算法來(lái)實(shí)現(xiàn)計(jì)算機(jī)輔助停機(jī)位分配，解決了由于天氣等特殊原因?qū)е潞桨啻竺娣e延誤情況時(shí)機(jī)場(chǎng)正常起降后的停機(jī)位應(yīng)急調(diào)度問(wèn)題。為綜合考慮多目標(biāo)優(yōu)化問(wèn)題，文獻(xiàn)[53]建立數(shù)學(xué)模型并設(shè)計(jì)了求解該模型的禁忌搜索算法。經(jīng)過(guò)不斷發(fā)展，很多學(xué)者開始對(duì)該算法進(jìn)行改進(jìn)，并關(guān)注其對(duì)停機(jī)位分配魯棒性的影響。文獻(xiàn)[8]引入了改進(jìn)后的動(dòng)態(tài)禁忌搜索算法，并利用實(shí)例對(duì)此算法進(jìn)行演算，證實(shí)了突出可變禁忌長(zhǎng)度能夠縮短全局尋優(yōu)的循環(huán)次數(shù)，此算法可以得到更優(yōu)的停機(jī)位分配方案。文獻(xiàn)[54]也設(shè)計(jì)了求解模型的禁忌搜索算法對(duì)考慮緩沖時(shí)間成本停機(jī)位分配模型求解，提高了分配計(jì)劃的魯棒性。國(guó)內(nèi)外很多文獻(xiàn)[64]在實(shí)例中證明了禁忌搜索算法相對(duì)于其他經(jīng)典算法的高效性，這也促進(jìn)了其在停機(jī)位分配領(lǐng)域的廣泛應(yīng)用。

(3)蟻群算法(Ant Colony Optimization)

Dorigo等意大利學(xué)者在20世紀(jì)90年代初期通過(guò)模擬自然界中蟻群集體尋徑的行為，從而創(chuàng)立了一種啟發(fā)式仿生進(jìn)化算法，被稱為蟻群算法。國(guó)外文獻(xiàn)對(duì)蟻群算法的研究主要關(guān)注高效率地獲得全局最優(yōu)解，為了在特定程度上減少蟻群算法陷入局部最優(yōu)的可能，文獻(xiàn)[55]提出了一種修正的蟻群算法，對(duì)轉(zhuǎn)移概率進(jìn)行了修正，并證明其可以有效地提高收斂速度。很多文獻(xiàn)對(duì)蟻群算法的創(chuàng)新性應(yīng)用深入研究：文獻(xiàn)[56]將蟻群優(yōu)化算法和遺傳算法相結(jié)合，提出了一種兩階段混合算法，對(duì)延誤航班停機(jī)位重分配問(wèn)題進(jìn)行有效求解；文獻(xiàn)[57]在蟻群算法的基礎(chǔ)上創(chuàng)新性地提出了一種基于全局最優(yōu)候選的自適應(yīng)人工蜂群算法用來(lái)求解全局優(yōu)化問(wèn)題；為了充分利用精英策略、最小最大蟻群策略、共生機(jī)制、混合機(jī)制和協(xié)同進(jìn)化思想的優(yōu)勢(shì)，文獻(xiàn)[58]也提出了一種新的自適應(yīng)協(xié)同進(jìn)化蟻群并設(shè)計(jì)了一種基于互補(bǔ)優(yōu)勢(shì)的優(yōu)化算法(SCEACO)，該算法可以更好地獲得有效的停機(jī)位分配結(jié)果，并且為解決復(fù)雜優(yōu)化問(wèn)題提供了一個(gè)新的思路。

為了避免啟發(fā)式搜索容易陷入局部最優(yōu)的情況，文獻(xiàn)[11]設(shè)計(jì)了一種基于螞蟻徑路搜索規(guī)則的迭代尋優(yōu)算法，即通過(guò)設(shè)置鄰接矩陣，使每只螞蟻在可行域內(nèi)一步步構(gòu)建優(yōu)化解，最后驗(yàn)證了該算法的合理性。由于蟻群算法具有對(duì)擾動(dòng)下停機(jī)位分配的優(yōu)越性，大部分國(guó)內(nèi)文獻(xiàn)將蟻群算法應(yīng)用到隨機(jī)擾動(dòng)下的停機(jī)位再分配中。文獻(xiàn)[59]與文獻(xiàn)[56]提出一種類似的基于蟻群算法和遺傳算法的兩階段優(yōu)化算法，并研究了基于兩階段算法的延誤航班停機(jī)位再分配方案。而文獻(xiàn)[60]對(duì)全局人工蜂群算法進(jìn)行改進(jìn)，并在實(shí)例中驗(yàn)證了其對(duì)隨機(jī)擾動(dòng)下停機(jī)位分配的有效性和優(yōu)越性。近幾年國(guó)內(nèi)文獻(xiàn)逐漸將蟻群算法應(yīng)用到多目標(biāo)優(yōu)化模型中，文獻(xiàn)[61]綜合考慮旅客滿意程度，機(jī)場(chǎng)和航空公司效益最大化而建立了樞紐機(jī)場(chǎng)停機(jī)位分配優(yōu)化模型，提出了一種基于自適應(yīng)協(xié)同進(jìn)化蟻群優(yōu)化算法的解決辦法。文獻(xiàn)[62]也采用蟻群算法對(duì)多跑道航班協(xié)同調(diào)度的多目標(biāo)動(dòng)態(tài)規(guī)劃問(wèn)題進(jìn)行仿真取得較優(yōu)結(jié)果，同時(shí)提高了多目標(biāo)優(yōu)化問(wèn)題的求解速度。

(4)啟發(fā)式算法

啟發(fā)式算法通常建立在經(jīng)驗(yàn)和判斷的基礎(chǔ)之上，通過(guò)盡量削減解的搜索范圍，避免盲目搜索，同時(shí)又可以得到較好的近似最優(yōu)解。但該算法并不保證一定可以找到最優(yōu)解。從停機(jī)位分配問(wèn)題的研究文獻(xiàn)中可以看到，學(xué)者們開發(fā)出了多種啟發(fā)式算法對(duì)該問(wèn)題進(jìn)行求解。

停機(jī)位分配問(wèn)題本身可歸納為一種有限域約束滿足問(wèn)題(Constraint-Satisfaction Problem over finite domain)，文獻(xiàn)[63]引入了進(jìn)化啟發(fā)式進(jìn)化算法來(lái)解決CSP。國(guó)外文獻(xiàn)往往將啟發(fā)式算法與其他算法結(jié)合或?qū)Ρ?，進(jìn)而選出快速獲得較優(yōu)解的算法：文獻(xiàn)[64]提出一個(gè)基于劃分的搜索域編碼使單個(gè)或多個(gè)航班再分配的兩個(gè)鄰域交換，最后結(jié)合禁忌搜索和局部搜索的啟發(fā)式算法來(lái)解決最小化停機(jī)位再分配航班數(shù)量的問(wèn)題；文獻(xiàn)[33]提出使用兩種啟發(fā)式算法對(duì)模型進(jìn)行求解，并對(duì)所提出的模型和算法進(jìn)行測(cè)試，證實(shí)了所提出的方法可以在短時(shí)間內(nèi)提供高質(zhì)量解；文獻(xiàn)[65]研究了三種經(jīng)典的元啟發(fā)式算法和一種混合算法，通過(guò)實(shí)例證明了混合算法在解的質(zhì)量和計(jì)算時(shí)間方面更好，這為停機(jī)位分配的研究提供了發(fā)展方向。另外文獻(xiàn)[66]還用Pareto模擬退火法解決了停機(jī)位的多目標(biāo)分配問(wèn)題。由此可見，對(duì)多種算法的混合使用可以大大提高求解速度，需要進(jìn)一步研究。

近幾年國(guó)內(nèi)文獻(xiàn)常對(duì)貪婪算法、模擬退火算法等啟發(fā)式算法進(jìn)行對(duì)比或結(jié)合使用，文獻(xiàn)[67]設(shè)計(jì)了一種貪婪模擬退火算法用以求解樞紐機(jī)場(chǎng)的停機(jī)位分配問(wèn)題，得到了一個(gè)未分配停機(jī)位的航班數(shù)量最少的初始解，并利用經(jīng)典模擬退火算法求解得出最優(yōu)分配方案。部分文獻(xiàn)也對(duì)其他啟發(fā)式算法進(jìn)行設(shè)計(jì)，文獻(xiàn)[26]引入機(jī)位標(biāo)號(hào)函數(shù)和航班標(biāo)號(hào)函數(shù)進(jìn)而設(shè)計(jì)了一種停機(jī)位排序模型的標(biāo)號(hào)算法。文獻(xiàn)[35]設(shè)計(jì)了一種深度優(yōu)先搜索的啟發(fā)式算法應(yīng)用到不正常航班的飛機(jī)和機(jī)組調(diào)度中，而該算法可以對(duì)被破壞的機(jī)組任務(wù)進(jìn)行修復(fù)，使得飛機(jī)和機(jī)組任務(wù)配對(duì)在較短的時(shí)間內(nèi)恢復(fù)正常狀態(tài)?？梢姡瑔l(fā)式算法的豐富創(chuàng)新為不正常航班的快速恢復(fù)提供了解決方法。

2.3 系統(tǒng)仿真法

在獲得基礎(chǔ)數(shù)據(jù)以后，系統(tǒng)仿真法通過(guò)建立各種類型仿真系統(tǒng)，并使用仿真技術(shù)對(duì)機(jī)場(chǎng)的停機(jī)位進(jìn)行實(shí)時(shí)模擬，主要為解決航班在停機(jī)位上的沖突控制問(wèn)題[22]。

在系統(tǒng)仿真研究方面具有代表性的是Yu Cheng在1998年的研究，他提出對(duì)于繁忙機(jī)場(chǎng)來(lái)說(shuō)，由于許多不確定性因素的影響，飛機(jī)在機(jī)場(chǎng)空側(cè)區(qū)域經(jīng)常會(huì)發(fā)生停放位置和運(yùn)動(dòng)軌跡沖突的情況，對(duì)于這個(gè)問(wèn)題人為控制難以解決，必須充分利用仿真技術(shù)。為此，文獻(xiàn)[68]分析了航班起飛和降落、進(jìn)離港、登機(jī)門分配等活動(dòng)及其相關(guān)控制過(guò)程，在此基礎(chǔ)上提出了基于網(wǎng)絡(luò)技術(shù)和規(guī)則的停機(jī)位分配仿真模型，來(lái)解決此類沖突控制問(wèn)題。隨后文獻(xiàn)[69]提出了基于網(wǎng)絡(luò)技術(shù)的仿真模型，模擬飛機(jī)的起降過(guò)程及其約束條件，用以避免飛機(jī)在跑道上的沖突。但隨著航空運(yùn)輸業(yè)的發(fā)展，機(jī)場(chǎng)在對(duì)停機(jī)位預(yù)分配時(shí)就能提前避免大部分航班在停機(jī)位上的沖突，文獻(xiàn)[15]也提到停機(jī)位分配的一個(gè)主流研究方向集中在仿真和基于規(guī)則的專家系統(tǒng)構(gòu)建上，許多學(xué)者將注意力集中在所謂的基于規(guī)則的專家系統(tǒng)的設(shè)計(jì)上。此后國(guó)外文獻(xiàn)偏向用仿真實(shí)驗(yàn)的方法對(duì)停機(jī)位分配規(guī)則和決策進(jìn)行評(píng)估。文獻(xiàn)[70]設(shè)計(jì)了一個(gè)仿真框架，用來(lái)分析隨機(jī)航班延誤對(duì)靜態(tài)停機(jī)位分配的影響，并且達(dá)到了對(duì)緩沖時(shí)間和實(shí)時(shí)停機(jī)位分配規(guī)則評(píng)估的目的。文獻(xiàn)[71]提出了一種基于仿真的實(shí)驗(yàn)方法，該方法可以在航班延誤情況下計(jì)算出進(jìn)離港航班所需的最小停機(jī)位數(shù)量，并且提出了一個(gè)因果模型來(lái)評(píng)估不同的停機(jī)位分配政策和策略在緩解不良后果方面的優(yōu)缺點(diǎn)。

由于飛行區(qū)多跑道情況的復(fù)雜性，國(guó)內(nèi)文獻(xiàn)將計(jì)算機(jī)仿真應(yīng)用在多跑道機(jī)場(chǎng)中。文獻(xiàn)[72]綜合考慮場(chǎng)面運(yùn)行約束并建立模型，用以尋求場(chǎng)面滑行時(shí)間最短的分配方案，利用計(jì)算機(jī)進(jìn)行仿真模擬，并與隨機(jī)分配算法進(jìn)行比較，仿真結(jié)果說(shuō)明該算法降低了沖突探測(cè)與解脫次數(shù)，提高了多跑道機(jī)場(chǎng)的地面容量，還大大減少了航班延誤時(shí)間。隨后文獻(xiàn)[73]利用機(jī)場(chǎng)的運(yùn)行模式、地面網(wǎng)絡(luò)數(shù)據(jù)以及航班計(jì)劃等相關(guān)信息，用計(jì)算機(jī)仿真進(jìn)行了算法設(shè)計(jì)，并借助編程語(yǔ)言進(jìn)行了計(jì)算，將結(jié)果同機(jī)場(chǎng)地面容量評(píng)估系統(tǒng)中的停機(jī)位隨機(jī)分配模型進(jìn)行對(duì)比，表明仿真模型使得機(jī)場(chǎng)運(yùn)行效率與資源配置情況得到改善，所提模型與算法比較有效。由于多跑道機(jī)場(chǎng)系統(tǒng)運(yùn)行管理的復(fù)雜程度明顯超過(guò)單跑道機(jī)場(chǎng)，文獻(xiàn)[74]基于Flexsim仿真軟件建立的飛行區(qū)仿真模型大大提升了航班滑行效率，在可接受延誤水平下使得滑行系統(tǒng)服務(wù)航班量增加，當(dāng)服務(wù)航班量超過(guò)容量時(shí)使得航班滑行的平均延誤時(shí)間縮短。仿真軟件的不斷應(yīng)用為解決多跑道機(jī)場(chǎng)的停機(jī)位規(guī)劃問(wèn)題提供了技術(shù)支持，提升了機(jī)場(chǎng)的運(yùn)營(yíng)效率。

2.4 三種方法對(duì)比分析

以上三種方法在停機(jī)位分配問(wèn)題中較常使用，但各有優(yōu)劣。數(shù)學(xué)規(guī)劃法在理論上能夠獲得最優(yōu)分配方案，但在運(yùn)算時(shí)間上卻不能夠完全滿足實(shí)際需要，當(dāng)航班數(shù)量較多時(shí)，該方法往往得不到最優(yōu)解或滿意解，大部分研究都需借助優(yōu)化算法實(shí)現(xiàn)快速求解。其次，該方法不夠靈活，航班時(shí)刻發(fā)生的細(xì)微變化都會(huì)引起停機(jī)位分配的混亂，導(dǎo)致需要分配結(jié)果重新計(jì)算。

使用智能優(yōu)化算法對(duì)問(wèn)題進(jìn)行求解花費(fèi)時(shí)間較少、效率較高，但大多數(shù)算法未能考慮到延誤航班對(duì)停機(jī)位分配的重要性，而且該類算法目的是在允許時(shí)間范圍內(nèi)在計(jì)算時(shí)間和解的質(zhì)量之間折中計(jì)算出停機(jī)位分配問(wèn)題的滿意解，而不強(qiáng)求最優(yōu)解，所以求解的結(jié)果是往往只能達(dá)到局部最優(yōu)。其中每一種算法有自身的優(yōu)缺點(diǎn)：遺傳算法本身具有并行性，通過(guò)使用概率機(jī)制進(jìn)行迭代而具有隨機(jī)性，但是由于比較其依賴初始解的質(zhì)量，搜索速度較慢，還需要對(duì)問(wèn)題編碼和最優(yōu)解解碼，編程較為復(fù)雜；由于禁忌搜索算法的局部搜索能力很強(qiáng)，故可以實(shí)現(xiàn)全局迭代尋優(yōu)，且求解速度與其他經(jīng)典算法相比較優(yōu)，但其非常依賴初始化的局部領(lǐng)域；貪婪算法比較容易實(shí)現(xiàn)，計(jì)算效率較高，但得到的解往往也是局部最優(yōu)解；模擬退火算法具有漸近收斂性，但很難控制其內(nèi)部的參數(shù)，優(yōu)化的結(jié)果很大程度上依賴參數(shù)取值。而混合算法相對(duì)于單個(gè)經(jīng)典算法無(wú)論在求解速度還是求解質(zhì)量上都有較大優(yōu)勢(shì)，并且在研究中為大部分學(xué)者所接受并使用。

而使用模擬計(jì)算機(jī)仿真技術(shù)可以對(duì)機(jī)場(chǎng)的停機(jī)位分配進(jìn)行實(shí)時(shí)模擬，但必須保證模擬環(huán)境與實(shí)際環(huán)境較為相似。復(fù)雜系統(tǒng)問(wèn)題很難用一般的數(shù)學(xué)建模方法進(jìn)行建模，但是仿真技術(shù)可以通過(guò)采用智能體建模的方式將復(fù)雜系統(tǒng)中的各個(gè)要素以及各要素間的交互方式進(jìn)行仿真，將復(fù)雜系統(tǒng)的微觀行為和宏觀現(xiàn)象進(jìn)行有機(jī)結(jié)合，該方法是一種有效的、自底向上的仿真建模方式。

3 未來(lái)發(fā)展趨勢(shì)

3.1 實(shí)現(xiàn)動(dòng)態(tài)實(shí)時(shí)分配

根據(jù)機(jī)場(chǎng)實(shí)際操作過(guò)程所處的階段不同，停機(jī)位分配問(wèn)題可以分為停機(jī)位預(yù)分配和實(shí)時(shí)分配兩種。停機(jī)位預(yù)分配在停機(jī)位分配信息發(fā)布之前就做好制作計(jì)劃，而停機(jī)位實(shí)時(shí)分配則是對(duì)停機(jī)位當(dāng)前的運(yùn)行狀態(tài)進(jìn)行協(xié)調(diào)補(bǔ)充。然而目前國(guó)內(nèi)對(duì)于停機(jī)位實(shí)時(shí)分配的研究還相對(duì)較少。停機(jī)位分配本身是動(dòng)態(tài)的，它屬于應(yīng)急停機(jī)位調(diào)度范疇。在停機(jī)位動(dòng)態(tài)運(yùn)行的過(guò)程中，停機(jī)位的實(shí)時(shí)分配過(guò)程可能會(huì)受到天氣和空中流量管制等因素的影響，當(dāng)出現(xiàn)特殊情況尤其是航班延誤情況下時(shí)，停機(jī)位預(yù)分配策略可能會(huì)失效而需要大量機(jī)位調(diào)整。當(dāng)前在此類情況發(fā)生時(shí)，主要是依靠停機(jī)位分配員對(duì)當(dāng)時(shí)情況的綜合判斷進(jìn)行停機(jī)位再分配，缺乏科學(xué)理性的指導(dǎo)。所以提前做好停機(jī)位實(shí)時(shí)分配工作是停機(jī)位分配研究問(wèn)題的發(fā)展方向。

3.2 采取多目標(biāo)優(yōu)化

根據(jù)國(guó)內(nèi)外機(jī)場(chǎng)的特點(diǎn)，不同目標(biāo)優(yōu)化問(wèn)題之間相互制約、相互影響，這就為多目標(biāo)優(yōu)化問(wèn)題提供了現(xiàn)實(shí)依據(jù)，也印證了典型優(yōu)化問(wèn)題的局限性，因此在實(shí)際分析各優(yōu)化目標(biāo)的前提下應(yīng)考慮采取多目標(biāo)優(yōu)化決策模型。停機(jī)位的多目標(biāo)優(yōu)化問(wèn)題是機(jī)場(chǎng)調(diào)度研究的一個(gè)方向，因?yàn)樾枰紤]的因素較多，各種因素相互交叉，復(fù)雜性也較大。由于各優(yōu)化目標(biāo)之間往往存在著相互競(jìng)爭(zhēng)的關(guān)系，如何科學(xué)地選擇多目標(biāo)函數(shù)，針對(duì)多目標(biāo)優(yōu)化問(wèn)題進(jìn)行深入分析，并設(shè)計(jì)合適的算法求解，在得到最優(yōu)解的同時(shí)，又能縮短獲得最優(yōu)解的時(shí)間，是該領(lǐng)域未來(lái)研究工作中一個(gè)重點(diǎn)和難點(diǎn)。

3.3 合理賦予目標(biāo)權(quán)重

由于機(jī)場(chǎng)運(yùn)行過(guò)程的復(fù)雜性，一個(gè)停機(jī)位分配問(wèn)題選取的多個(gè)優(yōu)化目標(biāo)并不能包含需要考慮的全部方面，這就需要結(jié)合單個(gè)目標(biāo)進(jìn)行細(xì)致的權(quán)重考量，才能使理論結(jié)果更具有意義?，F(xiàn)有停機(jī)位分配文獻(xiàn)中的優(yōu)化目標(biāo)大多為單目標(biāo)優(yōu)化，考慮多目標(biāo)優(yōu)化時(shí)賦予參數(shù)的權(quán)重也沒(méi)有統(tǒng)一適用的方法，對(duì)于最優(yōu)權(quán)重比沒(méi)有科學(xué)有效的研究，通常都是憑經(jīng)驗(yàn)選擇。國(guó)內(nèi)外文獻(xiàn)對(duì)于多目標(biāo)模型求解方法的研究很少使用線性加權(quán)法以外的方法，而線性單目標(biāo)公式需要反復(fù)求解才能生成Pareto最優(yōu)解，因此求解方法上還有待進(jìn)一步的研究。

3.4 創(chuàng)新優(yōu)化算法

在算法上，由于停機(jī)位分配問(wèn)題是一個(gè)NP難問(wèn)題，約束條件和目標(biāo)函數(shù)不同就會(huì)有不同的優(yōu)化解。解決這類問(wèn)題而被廣泛使用的智能優(yōu)化算法有很多，這些算法都是通過(guò)不同的搜索方式來(lái)獲得局部最優(yōu)解，只是導(dǎo)致迭代次數(shù)和搜索的方向不同。因此，對(duì)于此類問(wèn)題的算法研究中，應(yīng)該結(jié)合問(wèn)題本身的特點(diǎn)綜合考慮各類因素，混合使用多種算法、創(chuàng)新算法或改進(jìn)現(xiàn)有算法，在出現(xiàn)大量航班和停機(jī)位分配時(shí)才能取得更好的效果。在實(shí)際使用啟發(fā)式的大趨勢(shì)下，將這些算法結(jié)合起來(lái)是非常有意義的。

3.5 考慮不確定因素

在實(shí)際的停機(jī)位調(diào)度過(guò)程中不確定因素時(shí)有發(fā)生，在考慮這些不確定因素或參數(shù)存在的前提下對(duì)停機(jī)位的調(diào)度問(wèn)題進(jìn)行研究，是未來(lái)研究的一個(gè)熱點(diǎn)。就停機(jī)位分配而言，可以盡量考慮預(yù)分配魯棒性、航線性質(zhì)、飛行任務(wù)、航班過(guò)夜、飛機(jī)的空中等待成本以及地勤工作人員的步行距離等更多的因素所產(chǎn)生的影響，并賦予合適的權(quán)重指標(biāo)來(lái)進(jìn)行合理評(píng)價(jià)，這樣才能使停機(jī)位分配計(jì)劃具有更強(qiáng)的魯棒性。

3.6 考慮多方面可控因素

在進(jìn)行停機(jī)位分配時(shí)如果不考慮飛行區(qū)域，分配結(jié)果很可能產(chǎn)生更多的跑道和滑行道沖突以及航班延誤，造成機(jī)場(chǎng)地面容量變小。盡管通過(guò)仿真技術(shù)可以對(duì)機(jī)場(chǎng)復(fù)雜的場(chǎng)面交通進(jìn)行引導(dǎo)，但機(jī)場(chǎng)的場(chǎng)面交通復(fù)雜多變，不但受到特殊航班、天氣等不可控因素的影響，機(jī)場(chǎng)、航空公司和機(jī)組調(diào)度等多方面可控因素也會(huì)對(duì)機(jī)場(chǎng)場(chǎng)面的實(shí)際運(yùn)行產(chǎn)生較大的限制，這些情況也是未來(lái)停機(jī)位分配問(wèn)題研究的方向。

4 結(jié)論

隨著民用航空事業(yè)的發(fā)展，停機(jī)位分配技術(shù)相關(guān)研究開始興起，研究停機(jī)位分配對(duì)提高服務(wù)質(zhì)量和機(jī)場(chǎng)運(yùn)營(yíng)效益具有極為重要的理論和實(shí)際意義。但國(guó)內(nèi)針對(duì)這方面的研究起步較晚，也不夠深入。本文對(duì)停機(jī)位分配問(wèn)題的特征、優(yōu)化目標(biāo)以及研究方法上的研究進(jìn)行了詳細(xì)綜述，為國(guó)內(nèi)停機(jī)位相關(guān)研究提供了綜述資料。最后分析了停機(jī)位分配問(wèn)題未來(lái)在實(shí)時(shí)分配、多目標(biāo)優(yōu)化、算法創(chuàng)新等方面的發(fā)展趨勢(shì)。