徐 晨, 王笑天, 劉 博

(民航中南空管設(shè)備工程(廣州)有限公司, 廣州 510080)

航班地面保障是機(jī)場為了保證航班正常運(yùn)行而提供的一系列清潔、配餐和加油等活動(dòng)的服務(wù)。地面保障服務(wù)分別由不同部門和單位通過不同類型保障車輛來執(zhí)行,具有流程復(fù)雜、車輛資源受限和協(xié)同調(diào)度難度大等特點(diǎn)?，F(xiàn)如今越來越多的機(jī)場依托運(yùn)行經(jīng)驗(yàn),研究科學(xué)的地面保障車輛調(diào)度智能化系統(tǒng),解決機(jī)場和航空公司的地面保障資源信息不完全對稱、航班地面保障服務(wù)需求量和地面保障資源供應(yīng)量間不同程度失衡的問題。

機(jī)場地面保障車輛調(diào)度研究涉及:單種地面保障車輛的路徑與調(diào)度問題、多種地面保障車輛的協(xié)同調(diào)度問題和利用仿真軟件優(yōu)化車輛路徑與調(diào)度問題三個(gè)方面。

Norin等[1]設(shè)計(jì)了貪婪隨機(jī)自適應(yīng)搜索算法實(shí)現(xiàn)單種車輛調(diào)度的最小化航班延誤和最小化行駛里程;王一飛[2-3]、陳鑫和劉長有[3]應(yīng)用蟻群算法解決車輛調(diào)度動(dòng)態(tài)規(guī)劃問題;Christian和Asvin[4]以一種用于生成可行調(diào)度表的后向標(biāo)記方法研究車輛路線和車輛司機(jī)調(diào)度問題;鐘建華[5]采用基于改進(jìn)NSGA-Ⅱ算法求解飛機(jī)牽引車調(diào)度問題;王博等[6]基于機(jī)場協(xié)同決策系統(tǒng)提出了機(jī)坪牽引車調(diào)度方法。

Padrón等[7]、任子云[8]、王俊義[9]、樊偉等[10]、許晨晨和邵荃[11]考慮不同的車輛,結(jié)合多種車輛進(jìn)行結(jié)合考慮并優(yōu)化整個(gè)地面保障流程。以工作負(fù)荷相對均勻和資源節(jié)約為設(shè)計(jì)原則,綜合多種車輛相互運(yùn)作關(guān)系,得到優(yōu)化方案。

廖丹和黃寶軍[12]用AirTOp仿真建模,實(shí)現(xiàn)了機(jī)場地面保障車輛與航空器的聯(lián)合建模;衡紅軍和王芳[13]建立了基于多智能體系統(tǒng)(multi-agent system,MAS)的實(shí)時(shí)調(diào)度算法,分布式規(guī)劃服務(wù)車輛路徑并組合形成方案。

機(jī)場地面保障服務(wù)車輛調(diào)度問題隨著智能仿生算法的發(fā)展已日趨成熟,但大部分研究針對單一車輛或場景,無法很好地實(shí)現(xiàn)從基礎(chǔ)理論到實(shí)際復(fù)雜場景應(yīng)用的過渡。針對機(jī)場地面保障服務(wù)的流程和特點(diǎn),分析實(shí)際運(yùn)行中多種模式下各地服車輛與所保障航班的關(guān)聯(lián)性,解決多航班、多種地服車輛、多車庫中心、多目標(biāo)的復(fù)雜協(xié)同問題。采用Anylogic軟件進(jìn)行機(jī)場場面保障服務(wù)流程仿真,驗(yàn)證方案的合理性和實(shí)用性。

1 機(jī)場地面運(yùn)行保障分析

地面資源服務(wù)模式以航班運(yùn)行流程為主線進(jìn)行分類,包括始發(fā)、過站、過夜和快速過站航班4種模式的航空器流程保障標(biāo)準(zhǔn)。過站航班運(yùn)行模式所涉及的地面保障服務(wù)車輛最齊全且服務(wù)流程要求最高,需要航空器保障車輛、旅客服務(wù)車輛、場道保障車輛及應(yīng)急救援車輛為其提供服務(wù)。

1.1 航空器地面保障服務(wù)流程

地面保障服務(wù)從航空器到達(dá)本站前分配機(jī)位開始,至航空器撤輪檔后結(jié)束為止。每種車輛所需的提前到位等待、對接和服務(wù)時(shí)間各不相同。這些時(shí)間還與所服務(wù)航空器的機(jī)型和航空器停放機(jī)位屬性相關(guān)。

在滿足規(guī)范要求的前提下,統(tǒng)計(jì)地服車輛的歷史服務(wù)時(shí)間,可初步確定各類地面保障車輛的標(biāo)準(zhǔn)作業(yè)時(shí)間。對國內(nèi)某大型樞紐機(jī)場2019年9月25日至2020年6月24日1 225架次航班的清水車作業(yè)時(shí)間進(jìn)行調(diào)研,得到服務(wù)近機(jī)位C類航空器清水配供作業(yè)時(shí)間統(tǒng)計(jì)圖(圖1)。同一類型車輛的服務(wù)時(shí)間存在不確定性,將95%箱體值作為服務(wù)于C類航空器的清水車標(biāo)準(zhǔn)作業(yè)時(shí)間。

圖1 清水車作業(yè)時(shí)間統(tǒng)計(jì)(C類)

同理得到其他各類地服車輛的標(biāo)準(zhǔn)作業(yè)時(shí)間,如表1所示。

表1 航空器保障車輛標(biāo)準(zhǔn)作業(yè)時(shí)間匯總

與旅客服務(wù)相關(guān)的地服保障標(biāo)準(zhǔn)作業(yè)時(shí)間,如表2所示。

表2 旅客服務(wù)車輛標(biāo)準(zhǔn)作業(yè)時(shí)間匯總

由機(jī)型(C、D、E、F)和航班停放機(jī)位類型(近/遠(yuǎn)機(jī)位),地服車輛服務(wù)最早/最晚開始時(shí)間、結(jié)束時(shí)間、標(biāo)準(zhǔn)作業(yè)時(shí)間及關(guān)鍵工序,可以確定航空器地面保障服務(wù)流程。停放近機(jī)位的C類航空器的過站地面保障流程如圖2所示。

圖2 航空器地面保障流程的關(guān)鍵工序示意圖

將航班保障涉及流程解析為26個(gè)時(shí)間節(jié)點(diǎn),歸納為地面保障流程的時(shí)間工序模型如圖3所示。

圖3 C類航空器過站航班地面保障流程(近機(jī)位)示例

各節(jié)點(diǎn)緊前、緊后工序等參數(shù)說明如表3所示。

表3 地面保障流程關(guān)鍵工序的時(shí)間參數(shù)說明

節(jié)點(diǎn)23～25為地服車輛的提前到位準(zhǔn)備工序。

針對地服車輛服務(wù)流程優(yōu)化,可有效地縮短航班過站時(shí)間,從而提高場面資源調(diào)度和運(yùn)行效率。

1.2 車輛路徑規(guī)劃問題

機(jī)場除了跑道、滑行道和聯(lián)絡(luò)道,還專門設(shè)有地服車輛的行駛道路、服務(wù)區(qū)域及車庫中心等區(qū)域,保證航空器飛行活動(dòng)安全有序進(jìn)行。地服車輛調(diào)度是經(jīng)典車輛調(diào)度問題(vehicle routing problems, VRP)的一種衍生問題。若干空閑車輛從車庫出發(fā),前往航空器所在機(jī)位提供地面保障服務(wù),服務(wù)完成后如有新的需求,則前往下一航空器所在機(jī)位提供服務(wù),否則返回車庫中心。地面保障車輛有使用限制,即服務(wù)完一定架次數(shù)量的航空器后,應(yīng)保留合適剩余油量前往指定地點(diǎn)(特種車輛加油站或補(bǔ)給中心)補(bǔ)充資源。

將這一過程歸納為帶容量和時(shí)間窗的多目標(biāo)車輛路徑規(guī)劃問題(capacitated vehicle routing problems with time windows, CVRPTW)。通過車輛數(shù)限制、車輛容量限制、服務(wù)時(shí)間窗限制等基本約束生成地服車輛服務(wù)航空器的順序集合、車輛數(shù)和車輛行駛距離的調(diào)度方案。

2 CVRPTW模型

CVRPTW模型包含一個(gè)車庫中心K,因?yàn)橥N地服車輛所屬不同地服公司其容量和服務(wù)時(shí)間也有差異,所以區(qū)分同一種地服車的不同屬性(如地服公司屬性)進(jìn)行建模。

2.1 目標(biāo)函數(shù)

模型包含三個(gè)基本目標(biāo),式(1)為總使用車輛數(shù)量最小、式(2)為行駛總路徑最短、式(3)為超出地面保障服務(wù)時(shí)間限制數(shù)目最小、式(4)為地服車輛服務(wù)次數(shù)差異最小。

(1)

(2)

(3)

(4)

式(3)中包含一個(gè)懲罰函數(shù)Nti,用于表征當(dāng)前車輛服務(wù)時(shí)間和計(jì)劃時(shí)間差值,按式(5)計(jì)算。

(5)

圖4 懲罰函數(shù)

2.2 約束條件

約束條件如下所示。

(6)

(7)

(8)

(9)

?k∈K,?i,j∈C

(10)

?k∈K,?i∈C

(11)

(i=0,1,…,n+1)

(12)

(13)

(14)

(15)

3 CVRPTW問題的優(yōu)化

針對地服保障特點(diǎn),進(jìn)一步優(yōu)化CVRPTW模型,解決多種地服車輛、多航班、多車場、多目標(biāo)的復(fù)雜場面問題。

3.1 多車場的車輛調(diào)度問題

在上述地面保障服務(wù)協(xié)同調(diào)度模型基礎(chǔ)上增加每個(gè)車庫的車輛數(shù)量約束,如式16所示。

(16)

用國際Solomon算例C101進(jìn)行驗(yàn)證,結(jié)果如圖5和圖6所示。單車庫的最短行駛路徑為191.1,指定車庫中心的多車場情景(3個(gè)車庫)車輛的總行駛距離是109.8?？梢钥闯?多車庫中心比單車庫中心的車輛路徑規(guī)劃行駛距離更短,充分考慮機(jī)場地面保障資源的布局情況,從而有效減少耗油、碳排放和沖突等各種與距離成正比的成本。

圖5 單車庫中心最優(yōu)配送方案路線

圖6 單車庫中心最優(yōu)配送方案路線

此外,車庫中心的分布對車輛行駛路徑結(jié)果的影響也很大。實(shí)驗(yàn)表明,指定車庫的總行駛路徑迭代次數(shù)均高于未指定車庫中心的迭代次數(shù)。因此,對于新、改建機(jī)場,若未確定車庫中心位置,可采用距離分配法,通過行駛距離矩陣計(jì)算出多個(gè)較優(yōu)車庫中心位置,然后將待服務(wù)航班進(jìn)行分類,依次分別放入合適的車庫中心集合中,從而確定最佳車庫中心位置,為機(jī)場場面車庫規(guī)劃設(shè)計(jì)科學(xué)合理的指導(dǎo)建議。

3.2 高維多目標(biāo)車輛路徑規(guī)劃問題

CVRPTW模型是一個(gè)高維多目標(biāo)問題,即行駛距離最短、車輛數(shù)最少、超出時(shí)間窗懲罰函數(shù)最小和車輛任務(wù)均衡的多目標(biāo)。

以Eclipse-MOEA Framework 2.13 JDK 8為實(shí)驗(yàn)平臺,采用基于分解的多目標(biāo)進(jìn)化算法[14](multi-objective evolutionary algorithm based on decomposition, MOEA/D)的高維多目標(biāo)算法進(jìn)行求解。該算法得到的POF(Pareto optimal front,Pareto最優(yōu)前沿)效果較好,在使用車輛數(shù)盡可能小的情況下,無論是整體還是單個(gè)車輛的行駛距離都較小,車輛任務(wù)分布和時(shí)間窗違背函數(shù)(TWVariance)都很均勻,可以看作一組滿意解。

4 基于Anylogic的優(yōu)化仿真

以北京大興國際機(jī)場某天航班為例進(jìn)行驗(yàn)證,得到的多車輛、多航班、多車場動(dòng)態(tài)多目標(biāo)資源調(diào)度信息如下。

清水車、垃圾車車庫統(tǒng)稱特種車庫,加油車、污水車、行李車、配餐車有各自專用車庫,獲取車庫代號及坐標(biāo)。不同地服公司的車輛類型不同,每種車的初始位置和現(xiàn)有資源數(shù)量如表4所示。

表4 地服車輛信息

用代號“01”“02”和“03”分別表示東航地服、南航地服和首新地服,加油車服務(wù)不區(qū)分地服代理公司,由“04”表示。

地服車輛在各節(jié)點(diǎn)之間的行駛距離,如表5所示。

表5中對角線數(shù)據(jù)是地服車輛從車庫到機(jī)位的行駛時(shí)間,其他數(shù)據(jù)為車輛在機(jī)位間的行駛時(shí)間。

選取典型日航班計(jì)劃作為實(shí)驗(yàn)數(shù)據(jù),共計(jì)390個(gè)航班,其中C類航空器337架次,E類53架次,統(tǒng)計(jì)所有航班到達(dá)機(jī)位時(shí)間和離開機(jī)位時(shí)間,并以此時(shí)間節(jié)點(diǎn)作為地面保障服務(wù)流程整體開始時(shí)間和最晚結(jié)束時(shí)間設(shè)計(jì)資源調(diào)度和配置方案,航班和地服車輛信息如表6所示。

表6 航班時(shí)刻表(部分)

以清水車(01)資源配置和調(diào)度為例展示方案。圖7中1～129號為航班服務(wù)順序,130～133為4個(gè)車庫中心,得到21 861個(gè)Pareto前沿。POF解集的使用車輛數(shù)為11,行駛距離為60 541.23(相對距離無量綱),最優(yōu)解的平均推遲時(shí)間為11.77s(推遲時(shí)間以最早服務(wù)開始時(shí)間為標(biāo)準(zhǔn)進(jìn)行計(jì)算,所有清水調(diào)度未造成延誤),車輛間服務(wù)方差為8.31。

圖7 北京大興國際機(jī)場地服車輛調(diào)度信息(01清水車)

基于AnyLogic軟件工具驗(yàn)證車輛調(diào)度算法,生成地服車輛的實(shí)時(shí)調(diào)度信息表,驗(yàn)證方案的可行性。

Anylogic是一款基于JAVA語言的仿真軟件,支持迅速拖曳建模。創(chuàng)建航班、停機(jī)位和航班調(diào)度需求等7個(gè)智能體,構(gòu)建地服車輛智能體系統(tǒng)模型架構(gòu),如圖8所示。

圖8 基于Anylogic的地服車輛模型多智能體面板

仿真規(guī)則設(shè)定為航空器按航班計(jì)劃時(shí)間到達(dá)指定機(jī)位,向車庫中心發(fā)送地面保障服務(wù)需求消息,車庫調(diào)度中心接收消息,根據(jù)機(jī)型匹配信息、車輛所在位置、車輛服務(wù)狀態(tài)和車輛服務(wù)規(guī)則等因素搜索合適車輛,生成調(diào)度計(jì)劃并給相應(yīng)車輛轉(zhuǎn)發(fā)消息。指定車輛前往航空器所在機(jī)位提供地面保障服務(wù),服務(wù)完成后判斷車庫中心是否有新的需求訂單,若有,則前往下一航空器所在機(jī)位提供服務(wù),否則返回車庫中心。

仿真得到航班計(jì)劃所需各地服車輛數(shù)量、行駛距離、延誤累計(jì)等情況,如表7所示。

表7 仿真結(jié)果——地服車輛使用情況統(tǒng)計(jì)

地服車輛調(diào)度信息如表8所示。

表8 仿真結(jié)果-地服車輛服務(wù)時(shí)間統(tǒng)計(jì)(部分)

通過Anylogic軟件仿真界面實(shí)時(shí)監(jiān)控地服車輛使用情況、車輛調(diào)度時(shí)間、車輛調(diào)度情況和車輛調(diào)度情況。

仿真結(jié)果顯示,所有車輛均在航班待服務(wù)時(shí)間窗內(nèi),未造成航班延誤,同時(shí)車輛調(diào)度方案與實(shí)際運(yùn)行中航空公司地服資源車輛與航班相互匹配的復(fù)雜情況相符合,具有較好的實(shí)用價(jià)值。

5 結(jié)論

對地面保障資源的類型、特點(diǎn)、分類和服務(wù)模式進(jìn)行全面的概述,確定了“合理使用、超前配置”的原則,針對過站航班構(gòu)建帶容量和時(shí)間窗的車輛行駛路徑規(guī)劃CVRPTW模型。

優(yōu)化CVRPTW地面保障車輛調(diào)度模型,實(shí)現(xiàn)多種地服車輛、多航班、多車場和多目標(biāo)的車輛路徑規(guī)劃問題研究,可減少由于地服車輛調(diào)度造成的航班延誤和運(yùn)行成本。

1)提出預(yù)先分配車庫中心和計(jì)算車庫中心兩種情境的CVRPTW解決方案。研究發(fā)現(xiàn)多車庫且可計(jì)算車庫位置的情境下車輛使用數(shù)量和行駛距離均較短,可為機(jī)場規(guī)劃建設(shè)地面保障車輛車庫中心設(shè)置提供科學(xué)可靠的理論依據(jù)。

2)用基于分解的進(jìn)化算法MOEA/D求解車輛數(shù)、行駛距離、時(shí)間窗懲罰函數(shù)和任務(wù)數(shù)均衡的4維多目標(biāo)問題,能得到較為滿意解集。

3)基于Anylogic仿真軟件進(jìn)行方案驗(yàn)證。統(tǒng)計(jì)服務(wù)于390架次航班的6種/16類地服車輛(共288輛)使用情況,實(shí)時(shí)監(jiān)測地服車輛的調(diào)度信息和機(jī)位占用情況。結(jié)果顯示,所得到的理論研究對于實(shí)際地面保障服務(wù)復(fù)雜情景較符,具備應(yīng)用價(jià)值。