衡紅軍，戚馨桐

(中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,天津 300300)

1 引言

車輛調(diào)度問題是多項(xiàng)式復(fù)雜程度的非確定性問題NP(Non-deterministic Polynomial)，求解該問題通常采用3大類算法，即啟發(fā)式算法、仿生算法和精確算法。啟發(fā)式算法構(gòu)造簡(jiǎn)單，對(duì)于求解較小規(guī)模數(shù)據(jù)較為有效，但對(duì)于較大規(guī)模數(shù)據(jù)往往表現(xiàn)欠佳[1 - 3]；仿生算法會(huì)因?yàn)橄萑刖植孔顑?yōu)的陷阱而無法得到最優(yōu)解，需要結(jié)合其他算法來提高前期搜索能力[4,5]；而精確算法可以獲得問題最優(yōu)解，卻是以龐大的計(jì)算量作為代價(jià)的，隨著計(jì)算機(jī)性能的提升，精確算法運(yùn)用在大規(guī)模調(diào)度問題上成為新趨勢(shì)[6 - 8]。目前，針對(duì)機(jī)場(chǎng)特種車輛調(diào)度問題的研究較少且以啟發(fā)式算法為主，衡紅軍等[9]利用節(jié)約值算法歸并回路搜索最短路徑；Wang等[10]提出一種基于貪婪策略的機(jī)場(chǎng)加油車調(diào)度算法AVSAGS(Airport Vehicle Scheduling Algorithm based on Greedy Strategy)求解該問題。

本文研究機(jī)場(chǎng)地面服務(wù)中的燃油加注服務(wù)。目前，機(jī)場(chǎng)地面服務(wù)仍停留在人工調(diào)度階段，采用單車單服務(wù)的方式(即：車輛從車場(chǎng)出發(fā)完成1個(gè)航班的燃油加注服務(wù)后便返回到車場(chǎng))會(huì)使得機(jī)場(chǎng)的地面資源利用率降低，同時(shí)難以確保加油員工作量均衡?？紤]在資源充足時(shí)，即當(dāng)值加油員與加油車為一一匹配關(guān)系，加油員駕駛加油車在過站航班和始發(fā)航班的進(jìn)港、出港時(shí)段提供燃油加注服務(wù)。由于過站航班的到達(dá)時(shí)刻易受到自然環(huán)境、航線流量等因素的影響，導(dǎo)致航班的實(shí)際時(shí)刻與計(jì)劃時(shí)刻相差較大，所以采取過站航班在臨近機(jī)場(chǎng)時(shí)發(fā)送的預(yù)計(jì)到達(dá)(進(jìn)港)時(shí)刻以及始發(fā)航班的預(yù)計(jì)出港時(shí)刻作為是否為航班安排服務(wù)的依據(jù)。

基于上述航班時(shí)刻特性，本文構(gòu)建了一種基于動(dòng)態(tài)規(guī)劃時(shí)間窗的實(shí)時(shí)車輛調(diào)度模型DVRPTW(Dynamic Vehicle Routing Problem with Time Window)[11]，通過航班預(yù)計(jì)時(shí)刻計(jì)算航班燃油加注服務(wù)時(shí)間窗，對(duì)服務(wù)開始時(shí)刻進(jìn)入到規(guī)劃時(shí)間窗的航班構(gòu)建DVRPTW模型，模型根據(jù)實(shí)際情況加入約束條件與目標(biāo)函數(shù)。之后將動(dòng)態(tài)調(diào)度問題轉(zhuǎn)化為連續(xù)時(shí)間片下的靜態(tài)調(diào)度問題[12]。在每個(gè)時(shí)間片下通過自適應(yīng)分支定價(jià)算法配置車輛、人員為航班服務(wù)，車輛根據(jù)不同航班的燃油加注服務(wù)的開始時(shí)刻與結(jié)束時(shí)刻進(jìn)行銜接，車輛完成1次任務(wù)(服務(wù)序列)返回車場(chǎng)。再通過貪婪策略將任務(wù)進(jìn)行銜接，最終實(shí)現(xiàn)車輛行駛時(shí)間最少，加油員的工作量均衡(差異最小)的目的。

2 問題描述與數(shù)學(xué)模型

2.1 問題描述

給定N+M個(gè)航班集合H={1,2,…,N,N+1,N+2,…,N+M}，其中N表示始發(fā)航班的數(shù)量，M表示過站航班的數(shù)量。集合V={1,2,…,T}表示車輛集合。規(guī)劃車輛為航班服務(wù)滿足以下約束：(1)每個(gè)航班僅被燃油加注服務(wù)1次；(2)所有航班僅可在其規(guī)定的燃油加注服務(wù)時(shí)間窗口內(nèi)被服務(wù)；(3)加油員駕駛加油車從車場(chǎng)出發(fā)，完成1次任務(wù)即返回車場(chǎng)。實(shí)現(xiàn)如下目標(biāo)：(1)車輛行駛時(shí)間最短；(2)加油員的工作量均衡。

2.2 數(shù)學(xué)模型

2.2.1 符號(hào)說明

(1)H0=H∪{0},Hn+1=H∪{n+1}，其中0和n+1分別表示將車場(chǎng)視為起點(diǎn)和終點(diǎn)。(2)L為執(zhí)行燃油加注任務(wù)派出的車輛次數(shù)。(3)ti,j為航班i所在停機(jī)位到航班j所在停機(jī)位的車輛行駛時(shí)間，其中t0,i和tj,n+1分別表示車輛從車場(chǎng)出發(fā)到達(dá)i和從j返回車場(chǎng)的時(shí)間。(4)xi,j,k表示弧的決策變量，若xi,j,k=1，則表示車輛k服務(wù)航班i后，立即對(duì)航班j進(jìn)行服務(wù)。(5)ci為航班i的服務(wù)時(shí)間。(6)si,k表示車輛k為航班i開始服務(wù)的時(shí)刻。(7)[ai,bi]為航班i的燃油加注服務(wù)時(shí)間窗，其中ai和bi分別表示服務(wù)的最早和最晚開始時(shí)間。(8)θ表示不滿足燃油加注服務(wù)時(shí)間窗的懲罰系數(shù)。

2.2.2 DVRPTW的混合整數(shù)規(guī)劃模型

(1)

(2)

(3)

(4)

(5)

(6)

si,k+ci+ti,j-θ(1-xi,j,k)≤sj,k,

?i,j∈H,?k∈V

(7)

ai≤si,k≤bi,?i∈H,?k∈V

(8)

xi,j,k∈{0,1},?i∈H0,?j∈Hn+1,?k∈V

(9)

其中，式(1)和式(2)為目標(biāo)函數(shù)表達(dá)式，分別表示車輛行駛時(shí)間最短和車輛之間的任務(wù)量差異最小。式(3)～式(9)為約束表式，分別表示：式(3)確保同一航班不被重復(fù)執(zhí)行燃油加注服務(wù)；式(4)～式(6)確保加油車從車場(chǎng)出發(fā)開始為航班服務(wù)，執(zhí)行完任務(wù)后，返回車場(chǎng)；式(7)確保車輛k為航班i服務(wù)后，從其所在停機(jī)位出發(fā)到達(dá)航班j所在停機(jī)位開始服務(wù)并確保開始服務(wù)時(shí)間在航班j的燃油加注服務(wù)時(shí)間窗口內(nèi)，xi,j,k=0時(shí)表達(dá)式依然成立；式(8)確保所有航班必須在其規(guī)定時(shí)間窗內(nèi)得到燃油加注服務(wù)；式(9)確保決策變量xi,j,k的取值為0或1。

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

3.1 算法設(shè)計(jì)思想

求解動(dòng)態(tài)規(guī)劃問題應(yīng)該首先將其轉(zhuǎn)化為多個(gè)連續(xù)時(shí)間片下的靜態(tài)調(diào)度問題。在每個(gè)時(shí)間片下，通過自適應(yīng)分支定價(jià)算法規(guī)劃車輛的行駛路徑，將航班的燃油加注服務(wù)進(jìn)行銜接形成服務(wù)序列，實(shí)現(xiàn)車輛行駛時(shí)間最短，車輛單次任務(wù)的工作量均衡的目的，在此過程中服務(wù)的銜接要滿足式(3)～式(9)的約束條件。由于在實(shí)際情況中，任務(wù)數(shù)量往往大于實(shí)際車輛數(shù)，在保證加油員有休息時(shí)間的條件下，通過貪婪策略有效地銜接任務(wù)，進(jìn)一步實(shí)現(xiàn)加油員工作量均衡的目的。

3.2 相關(guān)定義

定義1動(dòng)態(tài)規(guī)劃時(shí)間窗(t0+t)，t0表示當(dāng)前時(shí)刻，t表示時(shí)間窗的長(zhǎng)度。

定義2設(shè)k個(gè)連續(xù)時(shí)間片t1,t2,…,tk,每個(gè)時(shí)間片的長(zhǎng)度恒定為Δ，可以得到ti的時(shí)間區(qū)間為[(i-1)·Δ,i·Δ]。在ti的開始時(shí)刻讀取數(shù)據(jù)，經(jīng)過τ(τ<<Δ)計(jì)算時(shí)間生成調(diào)度方案，在區(qū)間[(i-1)·Δ+τ,i·Δ+τ]執(zhí)行調(diào)度方案。

定義3行駛時(shí)間=[行駛距離/行駛速度]。

定義4服務(wù)時(shí)間=燃油加注時(shí)間=[燃油加注量/燃油加注速度]，本文以服務(wù)時(shí)間作為衡量工作量的尺度。

3.3 工作流程

步驟1初始化預(yù)計(jì)航班集合、待排航班集合，將當(dāng)日所有航班標(biāo)記為“未訪問”。

步驟2在當(dāng)前時(shí)間片ti開始時(shí)刻讀取預(yù)計(jì)航班數(shù)據(jù)到預(yù)計(jì)航班集合，若集合不為空，則執(zhí)行步驟3。

步驟3計(jì)算預(yù)計(jì)航班集合中航班的燃油加注服務(wù)窗口，將服務(wù)窗口最早開始時(shí)刻進(jìn)入到動(dòng)態(tài)規(guī)劃時(shí)間窗口且標(biāo)記為“未訪問”的航班加入到待排航班集合，并將這些航班標(biāo)記為“已訪問”。

步驟4若當(dāng)天所有航班都安排完畢，則結(jié)束；否則，轉(zhuǎn)步驟5。

步驟5若待排航班為空，則轉(zhuǎn)步驟7；否則，轉(zhuǎn)步驟6。

步驟6通過自適應(yīng)分支定價(jià)算法配置車輛、人員進(jìn)行燃油加注服務(wù)。

步驟7時(shí)間片ti開始時(shí)刻讀取預(yù)計(jì)航班數(shù)據(jù)到預(yù)計(jì)航班集合，若集合不為空，則執(zhí)行步驟3。

4 自適應(yīng)分支定價(jià)算法

本文采用動(dòng)態(tài)列生成算法[13]以及分支策略[14]構(gòu)建一種新穎的自適應(yīng)分支定價(jià)算法。列生成算法通過DW(Dantzig-Wolfe)分解原理[15]將原問題分解為表達(dá)式簡(jiǎn)單但列變量數(shù)目龐大的主問題MP(Master Problem)以及含有資源約束的多目標(biāo)優(yōu)化路徑的子問題。由于無法枚舉出主問題的所有列變量，只需得到限制主問題RMP(Restricted Master Problem)，限制主問題的解屬于主問題解的凸子集，即同樣包含最優(yōu)解。每次迭代將松弛限制主問題模型轉(zhuǎn)化為其對(duì)偶模型，可減少變量基數(shù)，加快計(jì)算速度。求解對(duì)偶模型得到對(duì)偶值，重新定價(jià)子問題，從而指導(dǎo)列的生成，而對(duì)偶模型的檢驗(yàn)數(shù)判斷是否將列加入到限制主問題規(guī)模，直到子問題無法產(chǎn)生檢驗(yàn)數(shù)小于0的列，求解RMP即可得到浮點(diǎn)數(shù)最優(yōu)解。最后采取基于弧的分支策略得到整數(shù)最優(yōu)解。自適應(yīng)分支定價(jià)算法流程圖如圖1所示。

Figure 1 Flow chart of branch and pricing algorithm圖1 分支定價(jià)算法流程圖

4.1 DW模型分解

4.1.1 符號(hào)及表達(dá)式

(1)λ1，λ2表示給2個(gè)目標(biāo)分配的不同權(quán)重。(2)?={b1,b2,…,bn}表示限制主問題規(guī)模中所有列的集合。(3)tr表示當(dāng)前列r所途經(jīng)路徑的行駛時(shí)間，tr=∑i∈H0∑j∈Hn+1ti,jxi,j。(4)Cr表示當(dāng)前列r的服務(wù)時(shí)間，Cr=∑i∈H0∑j∈Hcjxi,j。(5)dck表示列對(duì)應(yīng)車輛k已經(jīng)完成或正在進(jìn)行燃油加注服務(wù)的航班的總服務(wù)時(shí)間。(6)若列r包含航班i時(shí)ei,r=1，否則ei,r=0，∑i∈H0∑j∈Hxi,j=∑j∈H∑r∈?ej,r。(7)θr表示列的決策變量，解中包含服務(wù)序列r時(shí)為1，否則為0。(8)C表示每個(gè)航班服務(wù)序列的目標(biāo)燃油加注時(shí)間，C=∑i∈Hci/L。

4.1.2 限制主問題

將整數(shù)線性規(guī)劃模型式(1)～式(9)轉(zhuǎn)化為集合覆蓋模型作為限制主問題模型，再依據(jù)4.1.1節(jié)的公式推導(dǎo)，可以得到限制主問題模型，定義如下：

(10)

(11)

θr∈{0,1},r∈?

(12)

式(10)與式(1)和式(2)含義一致。式(11)和式(12)分別對(duì)應(yīng)式(3)和式(9)。

4.1.3 資源約束下的多目標(biāo)優(yōu)化路徑子問題

松弛后的限制主問題模型的對(duì)偶模型定義為：

(13)

(14)

0≤πi≤1,i∈H

(15)

對(duì)偶模型的檢驗(yàn)數(shù)為：

(16)

根據(jù)等價(jià)關(guān)系將式(16)細(xì)化為基于弧的表達(dá)式：

(17)

子問題模型定義為：

(18)

s.t.約束式(3)～式(9)

(19)

4.2 自適應(yīng)分支定價(jià)算法具體實(shí)現(xiàn)

4.2.1 符號(hào)說明

(1)W表示等待服務(wù)的航班集合，∪s∈?o(s)=W,其中o(s)表示服務(wù)序列s所包含的航班。(2)P表示新產(chǎn)生的檢驗(yàn)數(shù)小于0的列的集合。(3)Q=∪k∈Vqk表示車輛覆蓋集合，其中qk表示被車輛k所覆蓋的列集合。

4.2.2 動(dòng)態(tài)列生成算法

算法1動(dòng)態(tài)列生成算法

輸入：待排航班。

輸出：服務(wù)序列。

步驟1將待排航班加入到Ni集合。當(dāng)前時(shí)間片ti，若i≥2，轉(zhuǎn)步驟2；否則,轉(zhuǎn)步驟7。

步驟2車輛覆蓋集合Q中，若存在集合對(duì)應(yīng)車輛k為空閑狀態(tài)，則車輛k返回車場(chǎng)，銷毀屬于qk的所有列。

步驟3刪除所有列中已經(jīng)完成與正在進(jìn)行燃油加注的航班，更新W，?，Q。

(1)刪除后，若列不為空，則保持剩余航班相對(duì)順序；

(2)刪除后，若列為空且列不屬于Q，則銷毀列。

步驟4單純型算法求解RMP模型，并得到對(duì)偶變量πi,i∈W。

步驟5列衍生新列：

(1)插入操作。

①選擇1個(gè)列s∈?；

②選擇航班l(xiāng)∈Wo(s)嘗試插入到列s的任何位置，計(jì)算o(s)∪l后，o(s)航班服務(wù)的花費(fèi)zs=zsl-πl(wèi)；

③在列s上重復(fù)操作②，直到所有屬于Wo(s)的航班完成操作②；

⑤轉(zhuǎn)操作①，直到所有列都完成上述操作。

(2)刪除操作。

①選擇1個(gè)列w∈?;

②選擇航班l(xiāng)∈o(w),在列w中刪除航班l(xiāng)，計(jì)算o(w)l后，o(w)航班服務(wù)的花費(fèi)zwl=zwl+πl(wèi);

③在列w上重復(fù)操作②，直到所有l(wèi)∈o(w)的航班服務(wù)完成;

⑤轉(zhuǎn)操作①，直到所有列完成上述操作。

步驟6將P中列加入到?，清空P。

步驟7為Ni中每個(gè)航班生成1個(gè)新列,將新列加入?。

步驟8重復(fù)步驟4與步驟5，直到新生成的列達(dá)到基數(shù)上限或P為空。

步驟9單純型算法求解RMP模型。

步驟10利用分支策略優(yōu)化解，若最優(yōu)整數(shù)解中存在不屬于集合Q的列，則根據(jù)貪婪策略從車場(chǎng)指定加油車前往服務(wù)。

4.3 分支策略

由于將列的決策變量松弛為連續(xù)型變量，導(dǎo)致解中多個(gè)列包含同一航班。而整數(shù)規(guī)劃無法解決這一問題，因此采用基于弧的分支策略優(yōu)化解。假設(shè)2個(gè)服務(wù)序列，r1途徑弧(m,j)訪問j，r2途徑弧(h,j)訪問j。將弧值四舍五入取整，優(yōu)先選擇弧值變幅最大的弧，假設(shè)為弧(h,j)，則會(huì)產(chǎn)生2種分支。分支1：保留r2的弧(h,j)，其次將其他途徑j(luò)點(diǎn)的傳入、傳出弧的花費(fèi)設(shè)為非常大的值；分支2：將弧(h,j)花費(fèi)設(shè)為非常大。然后重新計(jì)算直到求解出最優(yōu)整數(shù)解。下面詳述分支策略的具體過程。

算法2分支策略

輸入：分支節(jié)點(diǎn)。

輸出：服務(wù)序列。

步驟1初始搜索樹S，加入根節(jié)點(diǎn)。

步驟2在搜索樹中選取1個(gè)節(jié)點(diǎn)s(分支策略)初始化RMP模型。

步驟3求解RMP模型，解為Y。

步驟4若Y為整數(shù)解，轉(zhuǎn)步驟5;否則,轉(zhuǎn)步驟6。

步驟5將解Y對(duì)應(yīng)的目標(biāo)值與上界作比較。如果小于上界，則更新上界，并進(jìn)行剪枝操作；否則，根據(jù)上界剪掉當(dāng)前分支。轉(zhuǎn)步驟7。

步驟6Y為浮點(diǎn)數(shù)解，判斷浮點(diǎn)數(shù)解對(duì)應(yīng)的目標(biāo)值是否小于上界，若小于，則選擇新的分支節(jié)點(diǎn)加入搜索樹，刪除當(dāng)前分支節(jié)點(diǎn)；否則，剪掉當(dāng)前分支。

步驟7如果搜索樹S≠?，轉(zhuǎn)步驟2；否則,當(dāng)前整數(shù)解即為RMP的最優(yōu)解。

4.4 貪婪策略

考慮到加油員每次任務(wù)間有一定的休息時(shí)間，安排給同一加油員的多個(gè)任務(wù)的窗口不能重疊，而且加油員執(zhí)行多個(gè)任務(wù)之間的休息時(shí)間不能低于40 min。在滿足上述條件的前提下，每次將新任務(wù)指派給累計(jì)工作量最少的加油員。

5 實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證算法解決實(shí)際問題的有效性，本文選取華北某機(jī)場(chǎng)的實(shí)際數(shù)據(jù)作為算例，分析并驗(yàn)證其可行性。

5.1 數(shù)據(jù)預(yù)處理

華北某機(jī)場(chǎng)有63個(gè)停機(jī)位為飛機(jī)提供地面服務(wù)，機(jī)場(chǎng)每天的進(jìn)、出港航班數(shù)量達(dá)到300架次左右。根據(jù)民航局相關(guān)文件規(guī)定：機(jī)場(chǎng)地面特種車輛的行駛速度不能超過20 km/h，由于機(jī)場(chǎng)地下鋪設(shè)的油管通道覆蓋所有停機(jī)位，因此加油車無需負(fù)載燃油即可為航班服務(wù)。實(shí)驗(yàn)選取2018年5月23日全天真實(shí)航班數(shù)據(jù)作為實(shí)驗(yàn)算例，共108個(gè)離港航班，其中過站航班81個(gè)，航班編號(hào)101～181；始發(fā)航班27個(gè)，航班編號(hào)201～227。

5.1.1 時(shí)序模型預(yù)測(cè)燃油加注量

在調(diào)度規(guī)劃時(shí)無法得知實(shí)際燃油加注量?？紤]到航線與燃油加注量的緊密關(guān)系，以及相同航線在不同自然環(huán)境下對(duì)燃油加注量的影響，所以不能單純采用平均值法進(jìn)行預(yù)測(cè)，因此本文利用長(zhǎng)短時(shí)記憶LSTM(Long Short-Term Memory)模型，根據(jù)2018年5月23日航班對(duì)應(yīng)航線的歷史數(shù)據(jù)，預(yù)測(cè)該日航班的燃油加注量。部分航班的航線的預(yù)測(cè)燃油加注量如表1所示。

Table 1 Forecasting fuel refueling volume on some routes

5.1.2 停機(jī)位的距離鄰接矩陣

航班在指定的停機(jī)位等待燃油加注服務(wù)。根據(jù)測(cè)算，2個(gè)相鄰?fù)C(jī)位的距離大約40 m，車輛在行駛的過程中必須按照指定的路線行駛且線路不存在交叉情況(如圖2所示)。則不同停機(jī)位之間的距離鄰接矩陣如表2所示，其中D表示車場(chǎng)。

Figure 2 Ground road map of an airport in north China圖2 華北某機(jī)場(chǎng)地面道路圖

Table 2 Distance adjacency matrix of the stand

5.1.3 航班預(yù)計(jì)消息

航班消息由民航空中交通管制部門掌控?？展懿块T會(huì)將航班進(jìn)、出港時(shí)刻以報(bào)文的形式發(fā)給機(jī)場(chǎng)。

5.1.4 燃油加注服務(wù)的時(shí)間窗

燃油加注服務(wù)時(shí)間窗，表示航班服務(wù)可以在航班服務(wù)的最早開始時(shí)間與航班服務(wù)的最晚開始時(shí)間的區(qū)間內(nèi)開始，航班服務(wù)過早或過晚會(huì)導(dǎo)致服務(wù)等待或航班延誤，因此航班服務(wù)的開始時(shí)間必須在其服務(wù)時(shí)間窗內(nèi)。計(jì)算時(shí)將時(shí)間類型轉(zhuǎn)化為十進(jìn)制類型。

始發(fā)航班燃油加注服務(wù)時(shí)間窗:

bi=td-ci-35

(20)

ai=bi-15

(21)

過站航班燃油加注服務(wù)時(shí)間窗:

ai=tad

(22)

bi=ai+10

(23)

上式中，td為始發(fā)航班預(yù)計(jì)離港時(shí)刻，tad為過站航班預(yù)計(jì)到達(dá)時(shí)刻。部分始發(fā)、過站航班的服務(wù)時(shí)間及服務(wù)窗口如表3所示。

5.2 結(jié)果分析

5.2.1 環(huán)境與參數(shù)設(shè)置

根據(jù)本文算法，利用SQL2016對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，CPLEX Optimization Studio (64 bit) 12.6.3學(xué)術(shù)版對(duì)模型進(jìn)行規(guī)范化處理，通過Java編程計(jì)算。

Table 3 Service window for some flights

實(shí)驗(yàn)結(jié)合實(shí)際情況給出以下參數(shù)：車輛數(shù)為10；車速300 m/min；燃油加注速率300 kg/min；違反燃油加注服務(wù)窗口的懲罰系數(shù)設(shè)為1 000；t設(shè)為30 min，Δ設(shè)為10 min；系數(shù)λ1設(shè)置為15，系數(shù)λ2設(shè)置為10。關(guān)于序列目標(biāo)工作量C的設(shè)置：首先由于航班之間的服務(wù)時(shí)間差極大，設(shè)置過小則工作量難以均衡，過大則增加服務(wù)銜接進(jìn)而加大等待時(shí)間導(dǎo)致資源浪費(fèi)；其次已知所有航班總服務(wù)時(shí)間，為達(dá)到均衡目的希望任務(wù)次數(shù)是加油員數(shù)量的整數(shù)倍，基于以上2點(diǎn)并通過反復(fù)實(shí)驗(yàn)得出C為85。

5.2.2 實(shí)驗(yàn)結(jié)果分析

2018年5月23日部分實(shí)時(shí)航班規(guī)劃的結(jié)果如表4所示，其中R表示服務(wù)序列編號(hào)。

Table 4 Partial flight planning results

全天規(guī)劃結(jié)果以及每個(gè)加油員分配的服務(wù)序列結(jié)果分別如表5和表6所示。

Table 5 Full day flight planning results

2018年5月23日全天航班服務(wù)時(shí)間2 533 min，平均服務(wù)時(shí)長(zhǎng)為253.3 min，通過式(24)觀測(cè)每個(gè)加油員服務(wù)時(shí)間與平均服務(wù)時(shí)間的差異程度。其中，L表示加油員個(gè)數(shù)，gi表示第i個(gè)加油員的工作量，G表示平均工作量，由計(jì)算可知標(biāo)準(zhǔn)差為14.13。

Table 6 Full day flight and fueller planning results

(24)

根據(jù)最終的調(diào)度結(jié)果，可以得到車輛總行駛時(shí)間為215 min,所有加油員工作量的標(biāo)準(zhǔn)差為14.13，明顯優(yōu)于人工調(diào)度方式；在相同數(shù)學(xué)模型下與節(jié)約算法對(duì)比，自適應(yīng)分支定價(jià)算法在行駛時(shí)間、加油員工作量的均衡度與算法的運(yùn)行時(shí)間上同樣具有優(yōu)勢(shì)。如表7所示，其中t,σ,time分別表示車輛行駛時(shí)間(min)、加油員工作量標(biāo)準(zhǔn)差、程序運(yùn)行時(shí)間(s)。

Table 7 Comparison results

6 結(jié)束語(yǔ)

本文研究了機(jī)場(chǎng)航班的燃油加注服務(wù)，提出了一種基于動(dòng)態(tài)規(guī)劃時(shí)間窗的實(shí)時(shí)車輛調(diào)度算法，并通過實(shí)例驗(yàn)證了算法有效性，實(shí)現(xiàn)了行駛時(shí)間最短，加油員工作量均衡的目的。由于其他機(jī)場(chǎng)地面服務(wù)同樣依賴于航班的消息，所以對(duì)于其他服務(wù)(例如客艙清潔、行李運(yùn)輸?shù)?該算法同樣適用。但是，針對(duì)不同數(shù)據(jù)需要調(diào)整動(dòng)態(tài)規(guī)劃窗口以及時(shí)間片的大小，二者將直接影響調(diào)度結(jié)果的優(yōu)劣，同樣影響結(jié)果的還有算法計(jì)算時(shí)間，時(shí)間短則可以加快服務(wù)部署進(jìn)程，所以之后工作重點(diǎn)將放在算法的進(jìn)一步優(yōu)化上。