基于時(shí)間窗的機(jī)場(chǎng)地面保障車輛動(dòng)態(tài)調(diào)度

姜偉華, 張文靜, 袁琪, 姜雨

(1.南京航空航天大學(xué)金城學(xué)院, 南京 210000; 2.南京航空航天大學(xué)民航學(xué)院, 南京 210000)

隨著民航運(yùn)輸?shù)目焖侔l(fā)展,大型樞紐機(jī)場(chǎng)普遍進(jìn)入超負(fù)荷運(yùn)行狀態(tài),機(jī)場(chǎng)航班地面保障任務(wù)調(diào)度作為機(jī)場(chǎng)場(chǎng)面運(yùn)行的關(guān)鍵環(huán)節(jié)之一,已經(jīng)逐漸成為制約大型樞紐機(jī)場(chǎng)發(fā)展的新瓶頸。由于航班地面保障任務(wù)涉及多主體利益,天氣、流控等不確定性因素,更加大了動(dòng)態(tài)調(diào)度難度,面對(duì)逐步恢復(fù)的航空運(yùn)輸消費(fèi)量與有限機(jī)場(chǎng)資源,亟需對(duì)航班地面保障任務(wù)進(jìn)行動(dòng)態(tài)調(diào)度研究。

對(duì)航班地面保障任務(wù)的研究主要以對(duì)航班保障資源調(diào)度進(jìn)行合理建模并尋找有效的解決方法為主,近年來(lái)主要從模型構(gòu)建和求解算法兩方面進(jìn)行研究。地面保障資源調(diào)度模型構(gòu)建方面,主要基于帶時(shí)間窗的車輛路徑問(wèn)題(vehicle routing problem with time window, VRPTW),丁建立等[1]以車輛總使用費(fèi)用最低為目標(biāo),引入混合時(shí)間窗的概念,建立動(dòng)態(tài)特種車輛調(diào)度模型。Zeng等[2]以車輛行駛路徑最短、車輛到達(dá)時(shí)間和最早服務(wù)時(shí)間之間的差異最小、車輛使用總數(shù)最少為目標(biāo)建立了車輛調(diào)度模型。G?k等[3]以最小化總體延誤為目標(biāo),然后根據(jù)各服務(wù)部門工作將車輛分散到航班上,并利用約束規(guī)劃和混合整數(shù)規(guī)劃求解器求解。李欣[4]分析機(jī)場(chǎng)加油車運(yùn)行模式,以最小化車輛行駛距離,縮短加油車行駛時(shí)間與等待時(shí)間,任務(wù)分配相對(duì)均衡為目標(biāo)建立模型。吳枕[5]根據(jù)機(jī)場(chǎng)保障車輛實(shí)際服務(wù)流程,針對(duì)不同需求構(gòu)建了車輛協(xié)同與動(dòng)態(tài)調(diào)度模型。Bi等[6]則考慮高峰時(shí)段擺渡車資源緊張問(wèn)題,建立多目標(biāo)車輛調(diào)度模型求解。陳程等[7]以總時(shí)間成本最小為目標(biāo),提出實(shí)時(shí)需求下的帶時(shí)間窗移動(dòng)充電車調(diào)度模型。

求解方式可分為精確算法和啟發(fā)式算法,精確算法主要有:線性規(guī)劃法[8]、動(dòng)態(tài)規(guī)劃法[9]和分支定界法[10]等,常見啟發(fā)式算法有蟻群算法[11]、模擬退火算法[12]、遺傳算法[13]、禁忌搜索算法[14]和粒子群算法[15]等。針對(duì)機(jī)場(chǎng)地面保障資源調(diào)度問(wèn)題的特點(diǎn),中外有許多學(xué)者還基于常見啟發(fā)式算法進(jìn)行了改進(jìn),或嘗試其他算法進(jìn)行求解。Padrón等[16]提出了一種改進(jìn)的序列迭代方法減少計(jì)算量。朱新平等[17]考慮保障作業(yè)持續(xù)時(shí)間的不確定性,設(shè)計(jì)了遞階式單親遺傳算法。Guo等[18]提出一種新的基于合作博弈理論的車輛調(diào)度遺傳算法解決機(jī)場(chǎng)行李運(yùn)輸車輛調(diào)度問(wèn)題。Zhao等[19]對(duì)比分析發(fā)現(xiàn)面向多目標(biāo)的粒子群算法更加適合對(duì)問(wèn)題求解。郝群茹[20]等針對(duì)車輛路徑優(yōu)化問(wèn)題,在禁忌搜索算法的基礎(chǔ)上,設(shè)置 4 種鄰域變化規(guī)則來(lái)改進(jìn)局部搜索。Zampirolli等[21]利用模擬退火算法構(gòu)建初始解,同時(shí)使用迭代局部搜索算法進(jìn)行改進(jìn)。Zhang等[22]利用圖論對(duì)機(jī)坪建立拓?fù)淠Ｐ筒⑹褂酶倪M(jìn)蟻群算法進(jìn)行了求解。Zhao等[23]將車輛調(diào)度模型轉(zhuǎn)化成網(wǎng)絡(luò)最大流量問(wèn)題進(jìn)行求解。

上述研究主要是基于靜態(tài)需求來(lái)優(yōu)化機(jī)場(chǎng)地面保障車輛的調(diào)度,然而在實(shí)際運(yùn)行中,需求可能會(huì)受天氣和交通流量控制等實(shí)時(shí)因素的影響而改變。如何考慮到航班到達(dá)和離開的不確定性,實(shí)現(xiàn)機(jī)場(chǎng)地面保障車輛的動(dòng)態(tài)調(diào)度,仍然是一個(gè)需要解決的關(guān)鍵問(wèn)題。此外,當(dāng)前車輛路徑問(wèn)題的研究主要集中在車輛路徑優(yōu)化、總配送成本最小等方向,現(xiàn)將軟時(shí)間窗限制運(yùn)用到車輛路徑問(wèn)題中,建立帶軟時(shí)間窗的機(jī)場(chǎng)地面保障車輛調(diào)度模型,更能反映實(shí)際問(wèn)題。

因此現(xiàn)考慮機(jī)場(chǎng)航班延誤、提前等情況,針對(duì)航班信息的動(dòng)態(tài)變化特點(diǎn),且需求帶有時(shí)間窗要求的情形,研究帶時(shí)間窗的機(jī)場(chǎng)地面保障車輛動(dòng)態(tài)調(diào)度問(wèn)題,提出一種雙階段機(jī)場(chǎng)地面保障車輛調(diào)度模型,并運(yùn)用雙階段啟發(fā)式算法進(jìn)行求解,旨在實(shí)現(xiàn)機(jī)場(chǎng)地面保障車輛的協(xié)同作業(yè)與動(dòng)態(tài)調(diào)度,為機(jī)場(chǎng)航班實(shí)際地面保障任務(wù)調(diào)度提供理論依據(jù)和決策支持。

1 問(wèn)題描述

根據(jù)車輛路徑問(wèn)題的定義,結(jié)合機(jī)場(chǎng)航班地面保障服務(wù)工作的特點(diǎn),要研究的雙階段機(jī)場(chǎng)地面保障車輛調(diào)度問(wèn)題可抽象為帶時(shí)間窗的車輛路徑問(wèn)題(vehicle routing problem with time windows, VRPTW)。針對(duì)某一種類型的機(jī)場(chǎng)地面保障車輛,將航班抽象為需要被服務(wù)的客戶,每個(gè)i航班作業(yè)設(shè)置了允許進(jìn)行作業(yè)的時(shí)間窗口[ai,bi];各保障車輛若在ai之前抵達(dá)該航班所在機(jī)位,須等到ai才能為航班進(jìn)行服務(wù),并且需在bi之前完成服務(wù),同時(shí)車場(chǎng)和車輛也有相應(yīng)的工作時(shí)間窗,根據(jù)不同作業(yè)任務(wù)時(shí)間窗以及位置分布,車輛調(diào)度人員需要在運(yùn)行安全的前提下,對(duì)有限的保障設(shè)備或車輛進(jìn)行調(diào)度,最終得到每個(gè)車輛進(jìn)行服務(wù)的航班服務(wù)順序及地點(diǎn),即機(jī)場(chǎng)地面保障車輛初始調(diào)度。但在實(shí)際運(yùn)行過(guò)程中,隨著時(shí)間的推移,新的需求可能由于延誤、機(jī)位調(diào)動(dòng)、時(shí)間窗變動(dòng)等情況隨機(jī)產(chǎn)生,為保證航班正常性,在新的服務(wù)時(shí)間窗內(nèi),需要重新分配另一個(gè)車輛為其進(jìn)行服務(wù),尋找機(jī)場(chǎng)地面保障車輛的最佳線路,即機(jī)場(chǎng)地面保障車輛動(dòng)態(tài)調(diào)度。機(jī)場(chǎng)地面保障車輛動(dòng)態(tài)調(diào)度示例如圖1所示,圖1中矩形方框代表保障車輛停車場(chǎng),實(shí)心圓圈代表已服務(wù)的航班,空心圓圈代表待服務(wù)的航班,三角形代表新增或變更需求的航班,線段則代表相互連接的保障車輛服務(wù)路線。

圖1 機(jī)場(chǎng)地面保障車輛動(dòng)態(tài)調(diào)度示例Fig.1 An example of dynamic scheduling of airport ground support vehicles

2 模型構(gòu)建

考慮航班延誤、提前等情況,針對(duì)航班信息的動(dòng)態(tài)變化特點(diǎn),構(gòu)建雙階段機(jī)場(chǎng)地面保障車輛調(diào)度模型,雙階段車輛路徑規(guī)劃策略如圖2所示。

圖2 雙階段車輛路徑規(guī)劃策略Fig.2 Two-stage vehicle routing scheduling strategy

2.1 初始調(diào)度模型

2.1.1 模型假設(shè)

為簡(jiǎn)化模型,針對(duì)機(jī)場(chǎng)地面保障車輛初始調(diào)度問(wèn)題做出以下假設(shè)。

(1)有限時(shí)段假設(shè)。選取一定時(shí)間段的地面保障車輛調(diào)度問(wèn)題進(jìn)行研究,方便研究與建模。

(2)信息完備假設(shè)。模型中所需的坐標(biāo)位置、

資源需求量、行駛距離、行駛速度、車輛類型及容量等信息均可知且完備。

(3)運(yùn)行規(guī)則假設(shè)。假設(shè)每種車型的車場(chǎng)唯一,車輛必須從原車場(chǎng)出發(fā),并在規(guī)定時(shí)間內(nèi)返回車場(chǎng),計(jì)算時(shí)所用車輛數(shù)量=路徑數(shù)量。

2.1.2 模型建立

第一階段為機(jī)場(chǎng)地面保障車輛的初始調(diào)度。在當(dāng)天地面保障服務(wù)開啟后,對(duì)計(jì)劃內(nèi)的機(jī)場(chǎng)地面保障車輛進(jìn)行路徑設(shè)計(jì),依據(jù)規(guī)定的計(jì)劃進(jìn)離港時(shí)間,得到初始的調(diào)度方案。機(jī)場(chǎng)地面保障車輛初始調(diào)度模型為

(1)

(2)

(3)

(4)

(5)

(6)

sik+ti+hij-M(1-xijk)≤sjk, ?i,j∈F,k∈V

(7)

ai≤sik+ti≤bi, ?i∈F,k∈V

(8)

(9)

(10)

(11)

式中:F為航班集合;V為車輛集合;N為等待安排保障作業(yè)的航班數(shù)量;K為車輛總數(shù);dij為從航班i所到機(jī)位行駛到航班j所在機(jī)位的距離;qi為航班i所需要的資源量;Q為車輛對(duì)資源的最大容量;hij為車輛從航班i機(jī)位處行駛至航班j所需要的行駛時(shí)間;ti為對(duì)航班i機(jī)型保障服務(wù)所需時(shí)間;sik為車輛k對(duì)航班i的開始服務(wù)時(shí)間;M為極大值;ai為航班i的開始接受服務(wù)時(shí)間;bi為航班i的最遲結(jié)束服務(wù)時(shí)間;xijk為0-1變量,車輛k從航班i行駛到航班j處為1,否則為0;yik為0-1變量,航班i由第k輛車服務(wù)為1,否則為0;Zk為0-1變量,第k輛車被使用為1,否則為0。

式(1)、式(2)為目標(biāo)函數(shù),在保證航班作業(yè)正點(diǎn)率的情況下,使用車輛數(shù)量最小和車輛行駛總距離最小;式(3)約束表示從車場(chǎng)中心出發(fā)的車輛數(shù)量不超過(guò)機(jī)場(chǎng)所擁有的該種類型的車輛總數(shù);式(4)表示每個(gè)航班作業(yè)任務(wù)只能由一輛車進(jìn)行服務(wù);式(5)表示每個(gè)客戶都需要被服務(wù);式(6)表示每個(gè)車輛運(yùn)載的資源量不能超過(guò)車輛容量;式(7)表示車輛對(duì)航班的服務(wù)開始時(shí)間需在上一航班結(jié)束服務(wù)并行駛到達(dá)之后;式(8)為作業(yè)時(shí)間窗約束;式(9)和式(10)保證車輛流量守恒;式(11)表示被使用車輛均從原車場(chǎng)出發(fā)并返回原車場(chǎng)。

2.2 動(dòng)態(tài)調(diào)度模型

2.2.1 模型假設(shè)

(1)每一時(shí)間段的開始調(diào)整時(shí)間為上一時(shí)間段內(nèi)最后一個(gè)服務(wù)任務(wù)完成時(shí)間。

(2)在時(shí)間段開始時(shí)刻正在進(jìn)行服務(wù)的車輛的位置,設(shè)置其為虛擬車場(chǎng),但車輛最終均需要回到原車場(chǎng)。

(3)航班停機(jī)位信息在每一個(gè)時(shí)間段更新,在該時(shí)間段內(nèi)不會(huì)再更改。

2.2.2 模型建立

第二階段為動(dòng)態(tài)優(yōu)化階段。在實(shí)際運(yùn)行過(guò)程中,對(duì)于場(chǎng)面較為忙碌的大型機(jī)場(chǎng),多種不確定因素將導(dǎo)致航班信息發(fā)生更改,據(jù)此所獲得的車輛初始調(diào)度方案將因?yàn)檫M(jìn)離港航班信息變化而受到擾動(dòng)。對(duì)于時(shí)間窗發(fā)生變化的航班,首先檢測(cè)其是否導(dǎo)致初始規(guī)劃車輛調(diào)度方案違背時(shí)間窗、容量等約束,若是,則獲取該時(shí)間航班服務(wù)時(shí)間窗和可用車輛信息,對(duì)該時(shí)間段進(jìn)行車輛的重新調(diào)度,即機(jī)場(chǎng)地面保障車輛的動(dòng)態(tài)調(diào)度優(yōu)化過(guò)程。機(jī)場(chǎng)地面保障車輛動(dòng)態(tài)調(diào)度模型為

(12)

(13)

(14)

(15)

(16)

(17)

sik+ti+hij-M(1-xijk)≤sjk, ?i,j∈Fh,
k∈V

(18)

ai≤sik≤bi, ?i∈Fh,k∈V

(19)

(20)

(21)

(22)

(23)

(24)

式中:Kt為t=ts時(shí)已經(jīng)派出的保障車輛;Qk為車輛k的剩余載重量;n為已完成服務(wù)的航班數(shù)量;m為正在進(jìn)行服務(wù)的航班數(shù)量;Nh為剩余待接受服務(wù)的航班數(shù)量;Fn為已完成服務(wù)的航班集合;Fh為需要服務(wù)的航班集合。

式(12)為目標(biāo)函數(shù),在保證時(shí)間窗約束等前提下,需盡可能減少對(duì)原指派計(jì)劃的變動(dòng)因此設(shè)置目標(biāo)為最小化因計(jì)劃調(diào)整而增加的行駛距離;式(13)約束表示從車場(chǎng)發(fā)出的車輛數(shù)不超過(guò)機(jī)場(chǎng)所擁有的該種類型的車輛總數(shù);式(14)和式(15)表示每個(gè)航班作業(yè)任務(wù)只能被單車進(jìn)行單次服務(wù);式(16)表示每個(gè)客戶都需要被服務(wù);式(17)表示每個(gè)車輛運(yùn)載的資源不能超過(guò)當(dāng)前車輛剩余容量;式(18)車輛對(duì)航班的服務(wù)開始時(shí)間需在上一航班結(jié)束服務(wù)并行駛到達(dá)之后;式(19)為作業(yè)時(shí)間窗約束;式(20)和式(21)保證車輛流量守恒;式(22)表示車輛均從原車場(chǎng)出發(fā)并返回原車場(chǎng);式(23)和式(24)表示虛擬車場(chǎng)只能發(fā)出車輛且最終車輛將回到原車場(chǎng)。

3 算法設(shè)計(jì)

機(jī)場(chǎng)地面保障車輛調(diào)度問(wèn)題屬于典型的NP-hard問(wèn)題,本文考慮不同啟發(fā)式算法的優(yōu)劣,根據(jù)前文構(gòu)建的雙階段機(jī)場(chǎng)地面保障車輛調(diào)度模型的特點(diǎn),設(shè)計(jì)雙階段啟發(fā)式算法進(jìn)行求解。在初始調(diào)度階段,采用局部搜索改進(jìn)遺傳算法,得到車輛初始調(diào)度方案;在動(dòng)態(tài)調(diào)度階段,采用基于破壞重建思想[24]的鄰域搜索算法進(jìn)行求解,得到動(dòng)態(tài)再優(yōu)化的調(diào)度方案。主要算法步驟如下。

3.1 改進(jìn)遺傳算法

步驟1染色體編碼。采用整數(shù)編碼方式。

步驟2生成初始群體。隨機(jī)生成含有若干初始個(gè)體的種群。

步驟3適應(yīng)度函數(shù)。采用線性加權(quán)法并引入懲罰函數(shù),將時(shí)間窗約束與容量約束進(jìn)行轉(zhuǎn)化,只有違反的約束越少,個(gè)體的適應(yīng)度才更高。

步驟4選擇操作。采用應(yīng)用最廣泛的輪盤賭方式。

步驟5交叉與變異。交叉操作采用改進(jìn)兩點(diǎn)交叉的方式。變異操作采用對(duì)稱變異方法隨機(jī)選擇任意兩個(gè)對(duì)稱的基因位置并交換位置。

步驟6局部搜索優(yōu)化。為加快遺傳算法的收斂速度,本文基于大規(guī)模鄰域搜索算法(large neighborhood search,LNS)中的破壞和修復(fù)的思想,在傳統(tǒng)遺傳算法中加入局部搜索機(jī)制,以求獲得更高質(zhì)量的解。

步驟7若達(dá)到終止準(zhǔn)則,算法終止,否則,回到步驟4。

遺傳算法(genetic algorithm, GA)模仿生物淘汰、遺傳和進(jìn)化的規(guī)則,有適用問(wèn)題范圍廣和較好的全局搜索能力,但通常需要較長(zhǎng)時(shí)間才能收斂到近似全局最優(yōu)解。因此本文采用局部搜索改進(jìn)遺傳算法,通過(guò)局部搜索可在可行空間的某個(gè)局部范圍內(nèi)快速的找到局部最優(yōu)解,從而加快收斂速度。

3.2 破壞重建算法

步驟1破壞操作。首先搜索動(dòng)態(tài)需求中由于使用原方案而導(dǎo)致違反時(shí)間窗或容量約束的任務(wù)點(diǎn),然后從中隨機(jī)選擇其中一個(gè)點(diǎn)進(jìn)行破壞,并計(jì)算剩余任務(wù)點(diǎn)與該任務(wù)點(diǎn)的相關(guān)度,選擇相關(guān)度較大的任務(wù)點(diǎn)構(gòu)成破壞任務(wù)點(diǎn)集合,為避免陷入局部最優(yōu),仍然加入隨機(jī)算子進(jìn)行選擇;若不存在違反約束的任務(wù)點(diǎn),則從所有任務(wù)點(diǎn)中隨機(jī)選擇任務(wù)點(diǎn)進(jìn)行破壞。

步驟2重建操作。基于最佳插入原則,即對(duì)每個(gè)被移除的個(gè)體選擇不違反容量和時(shí)間窗約束,并使得插入后新增距離最小的位置進(jìn)行插入。

步驟3計(jì)算對(duì)新生成的解計(jì)算其目標(biāo)函數(shù),若新解優(yōu)于原解,則進(jìn)行最優(yōu)解更新,反復(fù)迭代直到達(dá)到最大迭代次數(shù)。

在動(dòng)態(tài)調(diào)度階段,為達(dá)到快速響應(yīng)的目的,要求信息處理的時(shí)間盡可能短,采用基于破壞重建思想的鄰域搜索算法進(jìn)行求解,可以避免局部搜索算法在面對(duì)大規(guī)模算例時(shí)的局限性,同時(shí)又可以快速求解以獲得方案的實(shí)時(shí)性與可執(zhí)行性。

4 仿真驗(yàn)證

為驗(yàn)證模型及算法的有效性,以中國(guó)廣州白云機(jī)場(chǎng)為研究對(duì)象,以食品車和清水車為例進(jìn)行實(shí)例驗(yàn)證與分析。該機(jī)場(chǎng)目前機(jī)位布局圖如圖3所示。

圖3 機(jī)場(chǎng)基本布局圖Fig.3 Basic layout of the airport

根據(jù)機(jī)場(chǎng)地面保障車輛運(yùn)行相關(guān)規(guī)定[25],將25 km/h設(shè)置為仿真實(shí)例中車輛行駛的平均速度,將食品車容量設(shè)置為600 份/輛,最大使用車輛數(shù)為15 輛,清水車容量設(shè)置為5 000 L/輛,最大使用車輛數(shù)為10 輛。

通過(guò)多次仿真驗(yàn)證,改進(jìn)遺傳算法的參數(shù)設(shè)置如下:種群大小為100,最大迭代次數(shù)為120,交叉概率為0.9,變異概率為0.08;破壞重建算法的參數(shù)設(shè)置如下:最大迭代次數(shù)為50,初始解規(guī)模為50。

算法采用MATLAB (版本:R2018a)編寫程序,使用計(jì)算機(jī)配置為Intel(R) Core(TM) i5-10200H CPU @2.40 GHz,8 GB RAM,操作系統(tǒng)為Windows 10(x64)系統(tǒng)。

4.1 基礎(chǔ)算例求解

以該大型樞紐機(jī)場(chǎng)7月份某天的航班運(yùn)行數(shù)據(jù)為算例,選取計(jì)劃進(jìn)港時(shí)間在08:20—14:00之間的航班數(shù)據(jù)共254 條、即127 個(gè)航班對(duì)。將08:00設(shè)置為計(jì)時(shí)開始時(shí)刻。

4.1.1 初始調(diào)度階段

實(shí)驗(yàn)首先基于航班的計(jì)劃進(jìn)離港時(shí)間對(duì)作業(yè)任務(wù)進(jìn)行初始調(diào)度。使用改進(jìn)遺傳算法求解得到清水車與食品車具體初始規(guī)劃路線,結(jié)果如表1和表2所示。清水車初始規(guī)劃在第8次迭代后即可找到可行解,最終得到清水車初始規(guī)劃方案使用車輛數(shù)為5輛,行駛總距離為28 585 m。食品車初始規(guī)劃在第19 次迭代后可找到可行解,最終得到食品車初始規(guī)劃使用車輛數(shù)11輛,行駛總距離為71 330 m。

表1 清水車初始規(guī)劃結(jié)果Table 1 Initial scheduling results of potable water service equipment

表2 食品車初始規(guī)劃結(jié)果Table 2 Initial scheduling results of aviation catering vehicle

4.1.2 動(dòng)態(tài)優(yōu)化階段

根據(jù)實(shí)際情況,當(dāng)開啟當(dāng)天保障服務(wù)時(shí),動(dòng)態(tài)服務(wù)時(shí)間窗也隨之開啟,即進(jìn)入第二階段——?jiǎng)討B(tài)優(yōu)化階段,產(chǎn)生新的需求變化,通過(guò)破壞重建算法對(duì)實(shí)時(shí)調(diào)度方案進(jìn)行重新調(diào)整。

本文設(shè)置航班計(jì)劃更新時(shí)間間隔為120 min。將08:00設(shè)置為計(jì)時(shí)開始時(shí)刻,則第一次更新時(shí)刻為10:00,假設(shè)在10:00前可獲取接下來(lái)兩小時(shí)內(nèi)進(jìn)港航班的預(yù)計(jì)進(jìn)港時(shí)間,識(shí)別可能發(fā)生早到或延誤的航班,基于此對(duì)未來(lái)兩小時(shí)時(shí)間段內(nèi)進(jìn)港的航班各作業(yè)重新進(jìn)行時(shí)間規(guī)劃,該時(shí)間段內(nèi)的航班保障作業(yè)新時(shí)間窗將進(jìn)行更新,代表新的需求,將發(fā)生機(jī)位更改和服務(wù)時(shí)間的更改將一并輸入到模型中,從而得到新的路線規(guī)劃方案。

對(duì)清水車和食品車的動(dòng)態(tài)調(diào)度問(wèn)題分別進(jìn)行連續(xù)5 次求解,找到求解結(jié)果如表3所示。由表3可知,5 次求解結(jié)果中,清水車在調(diào)整后的最優(yōu)方案行駛距離為28 935 m,行駛總距離包括已經(jīng)完成服務(wù)航班任務(wù)的距離,平均距離成本為29 867 m,且平均在進(jìn)行3 次迭代后即可找到可行解。而食品車在調(diào)整后的最優(yōu)方案行駛距離為73 665 m,平均行駛距離成本為75 907 m,由于食品車容量相對(duì)較小,航班需求量較多,在調(diào)整時(shí)容量約束對(duì)求解的限制較大,需要迭代更多次才能找到可行方案;為了保障時(shí)間窗變化較大的航班可以及時(shí)得到服務(wù),動(dòng)態(tài)調(diào)度在初始規(guī)劃的基礎(chǔ)上新增了車輛,但算法運(yùn)行時(shí)間仍然在1 min之內(nèi),且能收斂到較優(yōu)解。實(shí)驗(yàn)結(jié)果表明,所使用的動(dòng)態(tài)求解算法對(duì)問(wèn)題的穩(wěn)定性較好,所得結(jié)果均在可接受范圍內(nèi)。

表3 最優(yōu)解結(jié)果Table 3 The optimal solution

清水車在動(dòng)態(tài)調(diào)整后的具體調(diào)度方案甘特圖如圖4所示,框內(nèi)數(shù)字代表作業(yè)任務(wù)序號(hào)。面對(duì)航班任務(wù)新需求,清水車初始調(diào)度方案有3 個(gè)航班任務(wù)發(fā)生車輛占用沖突,為了保證每個(gè)航班及時(shí)進(jìn)行服務(wù),動(dòng)態(tài)調(diào)整后清水車使用數(shù)量相較初始規(guī)劃增加一輛,但調(diào)整后增加的車輛總行駛距離僅為350 m。由于食品車配送任務(wù)較多,原初始規(guī)劃方案對(duì)新規(guī)劃的時(shí)間窗發(fā)生車輛占用沖突的航班數(shù)較多,因此各路線在符合新規(guī)劃的時(shí)間窗約束的條件下,進(jìn)行了較多調(diào)整,但綜合來(lái)看,行駛總距離僅新增3.2%,且運(yùn)算時(shí)間降低了8 min,驗(yàn)證了本文采用的調(diào)度方法在面對(duì)需求較大和動(dòng)態(tài)變化較多的算例時(shí)仍能保證實(shí)時(shí)性和運(yùn)行效率。實(shí)驗(yàn)結(jié)果表明,所使用的動(dòng)態(tài)求解算法對(duì)問(wèn)題的穩(wěn)定性較好,所得結(jié)果均在可接受范圍內(nèi)。

圖4 清水車動(dòng)態(tài)調(diào)度方案Fig.4 Dynamic scheduling scheme of clean water vehicle

4.2 算法性能

為了體現(xiàn)在初始調(diào)度階段采用的改進(jìn)遺傳算法GA(LNS)的優(yōu)越性,增加基于先到先服務(wù)(first come first service,FCFS)策略以及傳統(tǒng)遺傳算法的求解結(jié)果作為比較。采用不同算法得到的結(jié)果如表4所示。

表4 不同算法結(jié)果對(duì)比Table 4 Comparison of the different algorithms results

由表4可知,基于FCFS的方法雖然可以得到可行解,但無(wú)法考慮車輛在路線與距離上的全局最優(yōu),不利于環(huán)境和成本的節(jié)省;使用傳統(tǒng)GA算法可使清水車路線方案總距離比FCFS減少44.61%,食品車路線方案總距離比FCFS減少31.72%,但由于航班數(shù)量多,隨機(jī)組合方式多樣,導(dǎo)致尋找可行解需要花費(fèi)大量時(shí)間;對(duì)于本文采用的GA(LNS),可以快速找到可行解,其算法雖然加入了鄰域搜索的過(guò)程,也仍然可以在計(jì)算時(shí)間相對(duì)較短的情況下獲得較優(yōu)解,同時(shí)其得到的最優(yōu)解相比FCFS和GA有大幅下降,不僅可使用更少的車輛數(shù),節(jié)約車輛使用與維護(hù)成本,其求解的清水車方案行駛總距離較FCFS和GA分別減少55.31%和19.31%,食品車方案行駛總距離較FCFS和GA分別減少47.38%和22.93%,驗(yàn)證了本文改進(jìn)遺傳算法的可行性與有效性。

分別選擇5 次試驗(yàn)表現(xiàn)最好的清水車和食品車在經(jīng)過(guò)動(dòng)態(tài)調(diào)整后的調(diào)度方案,將其指標(biāo)與初始車輛調(diào)度方案進(jìn)行對(duì)比,如表5所示,以此來(lái)驗(yàn)證本文在動(dòng)態(tài)調(diào)度階段采用的破壞重建算法的性能。由表5可知,采用本文設(shè)計(jì)的基于破壞與修復(fù)算子的動(dòng)態(tài)求解算法,可使得各車輛路線在符合新規(guī)劃時(shí)間窗約束的條件下,求解的運(yùn)行時(shí)間大大降低,雖然清水車在調(diào)整后新增總行駛距離1.2%,食品車總行駛距離新增3.2%,但均在可接受范圍之內(nèi),驗(yàn)證了本文采用的求解算法滿足地面保障車輛動(dòng)態(tài)調(diào)度問(wèn)題的實(shí)時(shí)性要求。

表5 初始調(diào)度與動(dòng)態(tài)調(diào)度結(jié)果對(duì)比Table 5 Comparison of initial scheduling and dynamic scheduling results

5 結(jié)論

基于航班信息動(dòng)態(tài)變化的特點(diǎn),且需求帶有時(shí)間窗要求的情形,針對(duì)帶時(shí)間窗的機(jī)場(chǎng)地面保障車輛動(dòng)態(tài)調(diào)度問(wèn)題,考慮機(jī)場(chǎng)航班延誤、提前等情況,構(gòu)建了雙階段機(jī)場(chǎng)地面保障車輛調(diào)度模型,并設(shè)計(jì)雙階段啟發(fā)式算法進(jìn)行求解,最后以清水車和食品車調(diào)度為例分別進(jìn)行仿真實(shí)驗(yàn),得到如下結(jié)論。

(1)在初始調(diào)度階段采用的改進(jìn)遺傳算法GA(LNS),雖然加入了鄰域搜索的過(guò)程,也仍然可以在計(jì)算時(shí)間相對(duì)較短的情況下獲得較優(yōu)解,同時(shí)其得到的最優(yōu)解相比FCFS和GA有大幅下降,不僅可使用更少的車輛數(shù),節(jié)約車輛使用與維護(hù)成本,其求解的清水車和食品車行駛總距離較FCFS和GA都大幅減少,驗(yàn)證了本文改進(jìn)遺傳算法的可行性與有效性。

(2)采用本文設(shè)計(jì)的基于破壞與修復(fù)算子的動(dòng)態(tài)求解算法,可使得各車輛路線在符合新規(guī)劃時(shí)間窗約束的條件下,求解的運(yùn)行時(shí)間大大降低,雖然行駛距離有所增加,但均在可接受范圍之內(nèi),驗(yàn)證了本文采用的調(diào)度方法在面對(duì)需求較大和動(dòng)態(tài)變化較多的算例時(shí)仍能保證實(shí)時(shí)性和運(yùn)行效率。

目前本文僅考慮單車場(chǎng)調(diào)度,但在實(shí)際運(yùn)行過(guò)程中,將可能存在多個(gè)車庫(kù),比如食品將由多個(gè)航食公司進(jìn)行配送,因此未來(lái)可以研究考慮時(shí)間窗的多車場(chǎng)地面保障車輛調(diào)度問(wèn)題,進(jìn)一步細(xì)化模型。