實現(xiàn)多目標優(yōu)化的機場特種車輛調(diào)度算法

衡紅軍　晏曉東

(中國民航大學計算機科學與技術學院　天津 300300)

?

實現(xiàn)多目標優(yōu)化的機場特種車輛調(diào)度算法

衡紅軍晏曉東

(中國民航大學計算機科學與技術學院天津 300300)

為保證航班正常運行，機場特種車輛必須高效完成地面保障服務任務。目前機場特種車輛的調(diào)度方式是單車單航班服務的人工調(diào)度方式，成本較高，且效率較低。針對該問題提出一種基于節(jié)約算法的解決方案。該方案分為兩個階段：第一階段，利用節(jié)約算法求出滿足行駛總路程最短的子路徑集合；第二階段，通過構(gòu)建的新方法將每個子路徑任務合理分配給所有車輛，實現(xiàn)車輛數(shù)目最少和任務量差異最小的目標。以國內(nèi)某機場實際航班數(shù)據(jù)做算例進行實驗，與單車單航班服務相比，總路程節(jié)省49.28%；與不加任務量約束相比，任務均衡度由43.55%提高到95.16%。實驗結(jié)果表明，利用該算法調(diào)度特種車輛可大幅降低服務成本，且能實現(xiàn)任務均衡。

機場特種車輛調(diào)度節(jié)約算法任務均衡多目標優(yōu)化

0　引　言

航班在機場過站期間需要接受清潔、配餐、加水、燃油加注、裝卸行李貨物等一系列地面保障服務。這些服務主要通過一些不同類型的特種車輛(如清潔車、配餐車、加油車、行李車等)來完成。車輛調(diào)度方案的優(yōu)化對提高航班正點率和資源利用率至關重要。目前我國民航機場對特種車輛的調(diào)度大都是依靠人工調(diào)度，即單車單航班服務。這種低效率的調(diào)度方式往往導致車輛利用率不高，而且是造成航班延誤的重要因素。

機場特種車輛調(diào)度問題實質(zhì)上是一種車輛路徑問題VRP[1,2]。每個航班都有接受地面服務的需求。管理者需要組織合理的行車路線，使得每個航班的需求得到滿足，并能在一定的約束(車輛續(xù)駛路程、車輛載運量、航班時間窗等)下，達到路程最短、所需車輛最少、車輛任務量差異最小等目的。根據(jù)以往研究，解決此類問題以啟發(fā)式算法為主。如文獻[3,4]介紹了粒子群算法解決車輛路徑問題，文獻[5-7]利用各種改進遺傳算法解決多約束條件下的車輛路徑問題，文獻[8,9]將蟻群算法應用于此類問題，而文獻[10]聯(lián)合使用遺傳算法和蟻群算法來解決物流配送中的車輛路徑問題。

雖然解決此類問題的方法較多，但機場特種車輛調(diào)度問題具有其特殊性：一是航班對服務質(zhì)量要求較高，不允許保障車輛造成航班延誤，只能采用硬時間窗[11]約束(特種車輛必須在規(guī)定時間段內(nèi)完成保障任務)；二是對于大部分機場，進出港航班不夠密集，相鄰航班時間間隔較大(相對航班過站時間)，這對那些通過逐步選點來搜索最短路徑的算法影響較大(因為待選點往往不能滿足時間窗約束，這也是本文算法在解決該問題時無法在相同約束條件下與其他算法進行對比的原因，只與人工調(diào)度方式進行對比)。而節(jié)約算法[12]通過回路合并的方式搜索最短路徑，合并過程中即時更新回路中所有航班的服務時刻點，較適合解決此問題。并且聯(lián)合本文構(gòu)建的新方法使用時，可實現(xiàn)多目標優(yōu)化，實用性較強。

本文所做的工作是：首先，以燃油加注服務為研究對象，根據(jù)其業(yè)務特點建立機場加油車調(diào)度的數(shù)學模型；然后，利用節(jié)約值算法求出滿足加油車續(xù)駛路程和航班時間窗約束的最優(yōu)子路徑集合；最后，通過本文構(gòu)建的新方法將所有子路徑任務合理分配給加油車，既節(jié)省加油車數(shù)量，又考慮了加油車的任務均衡性。

由于本文方法是將整個問題分為兩個階段解決，獨立優(yōu)化總路程最短、任務均衡及車輛最少等目標，所以，實現(xiàn)負載均衡的同時并不會以增大總路程為代價。與2006年但正剛等人[13]提出的實現(xiàn)負載均衡的算法相比，本文方法更具優(yōu)勢。該方法同時也適用于配餐、加注清水等地面服務的特種車輛調(diào)度，只需根據(jù)實際情況調(diào)整約束條件(如最大續(xù)駛路程、時間窗規(guī)則及載運量等等)。

1　問題描述和數(shù)學模型

機場加油車是一種為航班提供燃油服務的車輛。機場鋪設有地下油管，連系到各個泊位下，飛機只須通過泵車加油。因此，與普通車輛路徑問題不同，該問題只有最大續(xù)駛路程和航班時間窗約束，而沒有最大載運量約束。

給定n個航班F={1,2,…,n}，l輛汽車V={1,2,…,l}，機場加油車最大續(xù)駛路程為Q。設計每輛加油車的行駛路線，每條行駛路線可能包含多個子路徑，要求滿足如下約束：每個航班恰好被服務一次；每條子路徑起始于加油車車場(編號：0)，終止于加油車車場(編號：n+1)，記N={0,1,…,n+1}；每條子路徑的行駛路程不能超過加油車的最大續(xù)駛路程；每個航班必須在其時間窗[ai,bi]內(nèi)被服務，否則會導致加油車等待或延遲服務。最終目標通常有三個：使所用的加油車數(shù)目最少；使所有加油車走過的總路程最短，使每輛加油車之間的任務量差異最小(即任務均衡度最大)。

參數(shù)定義：

Ti表示航班i需要的加油服務時間。

dij表示加油車從航班i所在停機位到航班j所在停機位的行駛距離。

sik表示加油車k開始為航班i服務的時間，令s0k=0；如果加油車k沒有為航班i服務，則sik沒有任何意義，k∈V。

ai表示時間窗下限。

bi表示時間窗上限。

數(shù)學模型表示為：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

sik+Ti+tij-ω(1-xijk)≤sjk?i,j∈N?k∈V

(9)

ai≤sik≤bi?i∈N?k∈V

(10)

xijk∈{0,1}?i,j∈N?k∈V

(11)

在上述表達式中，式(1)表示使所有加油車走過的路程最短；式(2)表示使需要的加油車數(shù)目最少；式(3)表示使每輛加油車之間的任務量差異最小；式(4)表示每個航班僅能被訪問一次；式(5)表示被調(diào)用的加油車都滿足最大續(xù)駛路程要求；式(6)-式(8)保證每輛加油車從出發(fā)點出發(fā)，訪問客戶后，最終回到出發(fā)點；式(9)表示加油車k在從航班i向航班j行駛的過程中，在時間sik+Ti+tij之前不能到達航班j，其中ω是一個較大的標量，若xijk=0則可保證式(9)的約束一定成立；式(10)表示加油車為航班i服務的時間必須在其時間窗口內(nèi)；式(11)是整數(shù)化約束。

該問題的解可以用一個整數(shù)序列表示。例如，假設有10個航班，它的一個解可以表示為整數(shù)序列{0 1 6 5 0 2 3 4 0 8 7 10 9 0}，其中R1={1,6,5}表示第一條路徑，R2={2,3,4}表示第二條路徑，R3={8,7,10,9}表示第三條路徑[14]。然后，在滿足時間要求前提下進行任務分配，第一輛加油車按照R2、R1路徑的順序為航班服務，第二輛加油車按照R3路徑為航班服務。

2　節(jié)約算法原理及算法設計

2.1節(jié)約算法原理

核心思想：依次將運輸問題中的兩個回路合并為一個回路，每次使合并后的總運輸距離減小的幅度最大，直至達到一輛車的最大續(xù)駛路程；再進行下一車輛的優(yōu)化，直到所有客戶的需求全部滿足。

由節(jié)約算法[15]，得到：

S(i,j)=di0+d0j-dij

(12)

即為把點i和點j連接在一起時相比i和j單獨各在一條線路上的路程節(jié)約值。在連接點對時，需考慮車輛的續(xù)駛路程約束和時間窗約束。

以EFj表示連接點i和點j所在的線路后，車輛到達j點的時間相比原線路上j點任務的開始時間的推遲(或提前)量，則EFj可由下式得到：

EFj=si+Ti+tij-sj

(13)

顯然，EFj<0時，j點任務的開始時間提前；EFj=0時，開始時間不變；EFj>0時，開始時間推遲。

(14)

(15)

2.2算法設計

具體步驟：

(1) 計算S(i,j)，令M={S(i,j)|S(i,j)>0}，并將M按S(i,j)從大到小進行排序。

(2) 令U={1,2,…,n}，表示待選顧客點集合。

(3) 若M=φ，則轉(zhuǎn)步驟(7)；否則對M內(nèi)第一項S(i,j)，考察對應的i、j，若滿足以下條件之一：

① 點i和點j均不在已構(gòu)成的線路上；

② 點i或點j在已構(gòu)成的線路上，但不是線路的內(nèi)點(即不與車場相連的點)；

③ 點i和點j位于已構(gòu)成的不同線路上，均不是內(nèi)點，且一個是起點，一個是終點。

轉(zhuǎn)下一步，否則轉(zhuǎn)步驟(7)。

(4) 考察點i和點j連接后的子路徑行駛總路程q，若q≤Q，則轉(zhuǎn)下一步，否則轉(zhuǎn)步驟(7)。

(5) 計算EFj：

① 若EFj=0，則轉(zhuǎn)步驟(6)；

(6) 連接點i和點j，U=U-{i,j}，轉(zhuǎn)步驟(7)。

(7) M=M-S(i,j)，轉(zhuǎn)步驟(3)；若U=φ，則終止，否則將剩余待選顧客點分別安排子路徑，即終止。

3　任務分配均衡性及其具體實現(xiàn)

雖然節(jié)約值算法找出了使總路程最短(即優(yōu)化第一目標，式(1))的子路徑集合，但在安排加油任務時，同一輛加油車在不同時刻可以重復利用，即一輛車在不同時刻可以完成多個子路徑的加油任務。因此，為了使所需車輛數(shù)目最少(即優(yōu)化第二目標，式(2))和使每輛加油車之間的任務量差異最小(即優(yōu)化第三目標，式(3))，還需將所有子路徑任務合理分配給每一輛加油車。

3.1任務分配均衡性

為加油車分配子路徑任務又是一個組合優(yōu)化問題，分配時要滿足兩個約束：一是同一輛車所分配的子路徑任務間在時間上不能重合；二是盡量考慮每輛車的任務均衡性。以服務航班數(shù)量總和來衡量每輛加油車任務量的大小；同時，本文提出任務均衡度的概念，來衡量總體任務均衡性。

參數(shù)定義：

θ：任務均衡度；

l：總車輛數(shù)；

Ci：第i輛加油車的總?cè)蝿樟?單位：航班數(shù))；

Ctotal：總加油任務量(單位：航班數(shù))；

以下式表示任務均衡度：

(16)

為達到各加油車任務均衡的目的，分配任務時需遵循兩個原則：一是開始服務時間早優(yōu)先原則，即子路徑任務開始時間越早，越優(yōu)先被分配；二是對每輛車加上任務量約束，設定一個閾值λ(單位：航班數(shù))，為每輛車分配加油任務時任務量均不應超過λ。

3.2具體實現(xiàn)

具體步驟：

(1) 根據(jù)子路徑方案R={R1,R2,…,Rs}，計算Ri的開始服務時刻tstart(i)和結(jié)束服務時刻tend(i)，i∈{1,2,…,s}。

(3) 將R的前l(fā)個子路徑任務分別分配給這l輛車，作為它們的第一個子路徑任務。

(4) 依次為這l輛車分配任務：找出當前為該車分配的最后一個子路徑的tend(i)，在所有滿足tstart(j)>tend(i)的待分配子路徑中找出一個tstart(j)最小的作為該車下一個子路徑任務，直到不存在滿足tstart(j)>tend(i)的待分配子路徑為止。

(5) 若分配完畢后還有子路徑任務未被分配，l=l+1，轉(zhuǎn)步驟(3)；否則，至少需要l輛加油車才能完成所有加油任務，轉(zhuǎn)步驟(6)。

(6) 按照上一步的l值，加上任務量λ約束，重復步驟(3)、步驟(4)。若分配完畢后仍有子路徑任務未被分配，λ=λ+1，轉(zhuǎn)步驟(6)；否則，算法終止。

4　算例分析

本文采用國內(nèi)某機場的航班數(shù)據(jù)做算例，實現(xiàn)對機場加油車的調(diào)度，驗證該算法的有效性。

4.1數(shù)據(jù)采集

該機場擁有客機停機位63個，每天進離港航班大約300架次。規(guī)定飛機加油車行駛速度為20 km/h，加油車最大續(xù)駛路程為50 km[16]。由于加油車一定會對離港航班進行加油服務，本文只選取該機場2014年9月4日00:00:00到2014年9月5日00:00:00之間的所有離港航班(124個)進行實驗，解決機場加油車輛調(diào)度問題。

4.1.1機型大小

由于不同類型飛機所需加油量和加油服務時間不同，所以必須對飛機進行分類，大概分為三類：小型飛機、中型飛機、大型飛機[17]。表1是不同類型飛機的載客量、燃油需求量、加油服務時間、過站時間。

表1　不同類型飛機的加油需求量和服務時間

4.1.2停機位距離

與普通物流車輛調(diào)度相比，機場加油車調(diào)度具有其特殊性，主要表現(xiàn)在車輛行駛路線上。在機場，特種車輛必須按照規(guī)定的路線(如圖1中路線)行駛，不得進入飛機行駛區(qū)域。

該機場現(xiàn)有63個客機停機位，分布于三個區(qū)域：遠機位、T1航站樓、T2航站樓(如圖1所示)。根據(jù)其鄰接關系，編號依次為：409、410、411、412、413、414、415、416、417、418、419、101、102、103、104、105、106、107、108、109、501、502、503、504、110、111、112、113、114、115、116、117、118、201、202、203、204、205、206、207、208、209、210、211、212、213、214、215、216、217、218、219、220、221、222、223、224、225、226、227、228、229、230。其中加油車車場位于停機位109和停機位501之間，其鄰接關系由其位置決定，相鄰停機位之間距離大約40米。表2列出了車場(編號：D)和其中8個停機位任意兩點之間的距離(單位：米)。

圖1　該機場停機位布局示意圖

D106107108109501502503504D016012080404080120160106160040801202002402803201071204004080160200240280108808040040120160200240109401208040080120160200501402001601208004080120502802402001601204004080503120280240200160804004050416032028024020012080400

4.1.3離港航班時間窗

時間窗即由服務車輛開始為該航班服務的最早開始服務時間(或稱時間窗下限)和最晚開始服務時間(或稱時間窗上限)限制的時間范圍。服務車輛必須在這個時間范圍內(nèi)開始為該航班服務，否則可能導致航班延誤。

民航局規(guī)定[16]：加油車應在旅客開始登機前5分鐘完成加油服務，載客加油或特殊情況下加油應在預計離港時間前5分鐘完成。即加油車必須至少在預計離港時間前5分鐘完成加油服務。

下面根據(jù)該機場的計劃離港時間數(shù)據(jù)，確定其時間窗下限和時間窗上限。

參數(shù)定義：

ai：時間窗下限；

bi：時間窗上限；

td：計劃離港時間；

Ttotal：過站時間；

Ti：加油車服務時間。

離港航班時間窗：

ai=td-Ttotal

(17)

bi=td-Ti-5

(18)

按照式(17)和式(18)得到的部分離港航班時間窗如表3所示。實際處理時間參數(shù)時，均將24進制轉(zhuǎn)化為10進制，單位為分鐘。

表3　離港航班時間窗(部分)

4.2結(jié)果分析

通過Matlab編程實現(xiàn)本文算法，并將其應用于該機場加油車調(diào)度問題，得出了124個離港航班接受加油車服務的開始時間、結(jié)束時間及每輛加油車的路徑安排方案。

4.2.1航班接受加油服務的時間段

本文算法采用硬時間窗約束，最后得出的調(diào)度結(jié)果中開始服務時間均在時間窗內(nèi)，加油車不會造成航班延誤。以航班為對象，表4列出了部分航班接受加油服務的時間段。

表4　離港航班接受加油服務時間段(部分)

4.2.2子路徑方案

下面，以子路徑為對象，表5顯示了本文算法產(chǎn)生的子路徑方案，一共產(chǎn)生44個子路徑。這意味著在24小時內(nèi)不同時刻需要44個車次來完成所有加油任務，而傳統(tǒng)單車單航班服務方式，則需要124個車次。

表5　產(chǎn)生的子路徑方案(全部)

續(xù)表5

按照本文調(diào)度結(jié)果安排加油車路徑時，車輛總路程為44.8 km，而單車單航班服務方式總路程為88.32 km。與其相比，本文算法節(jié)省了49.28%的路程，大大降低了加油服務成本。

4.2.3加油車任務分配

下面，以加油車為對象，為每一輛車分配加油任務。先不考慮任務均衡性，即分配任務時不對每輛加油車加任務量λ約束。表6列出了不考慮任務均衡性時加油車的路徑調(diào)度方案。

表6　加油車任務分配方案(全部)

由表6可以看出，僅按照開始時間早優(yōu)先分配原則，而不加任務量約束時，其任務均衡度(根據(jù)式(16)計算)為43.55%，每輛加油車間的任務量差異較大，仍需調(diào)整。下面，利用本文構(gòu)建的新方法為每輛車分配任務時加上λ約束，結(jié)果如表7所示。

表7　均衡調(diào)整后的分配方案(全部)

通過以上加油任務分配，完成所有航班加油任務僅需4輛加油車，極大節(jié)省了加油車資源；并且將任務均衡度提高到95.16%，大大縮小了每輛加油車間的任務量差異。

5　結(jié)　語

本文將機場加油車調(diào)度問題建立數(shù)學模型，利用節(jié)約值算法得出使總路程最短的子路徑集合，然后通過本文構(gòu)建的新方法將所有子路徑任務合理分配給加油車。為避免因加油服務造成航班延誤，本文采用硬時間窗約束，使每個航班一定會在規(guī)定時間內(nèi)得到加油服務。最終，本文解決方案能同時優(yōu)化三個目標函數(shù)，并成功應用在機場加油車調(diào)度問題上。

該算法也有其局限性，例如，如果航班計劃受天氣、其他地勤服務等不確定因素影響而改變，加油車調(diào)度方案也應根據(jù)實際情況快速做出調(diào)整。而本文給出的是一個靜態(tài)調(diào)度方案，后期需對動態(tài)調(diào)度做進一步研究，以增強整個算法的魯棒性。

[1] Dantzig G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91.

[2] 侯玉梅,賈震環(huán),田歆,等.帶軟時間窗整車物流配送路徑優(yōu)化研究[J].系統(tǒng)工程學報,2015,30(2):240-250.

[3] 高曉巍.基于改進QPSO算法的物流運輸路徑問題研究[J].計算機仿真,2013,30(8):169-172.

[4] 張耀軍,諶昌強.基于改進量子PSO算法的可約束車輛路徑優(yōu)化[J].計算機測量與控制,2014,22(9):2875-2878.

[5] 李鋒,魏瑩.求解隨機旅行時間的C-VRP問題的混合遺傳算法[J].系統(tǒng)管理學報,2014,23(6):819-825,831.

[6] 李華,趙冬梅,崔國成.具有模糊可選時間窗的VRPSPD問題及其混合遺傳算法[J].物流技術,2013,32(5):315-318.

[7] 葛顯龍,王旭,代應.基于混合量子遺傳算法的隨機需求車輛調(diào)度問題[J].系統(tǒng)工程,2011,29(3):53-59.

[8] 徐毅,李章維.蟻群算法在電力巡檢路線規(guī)劃中的應用[J].計算機系統(tǒng)應用,2015,24(5):135-139.

[9] 費騰,張立毅,孫云山.基于DNA-蟻群算法的車輛路徑優(yōu)化問題求解[J].計算機工程,2014,40(12):205-208,213.

[10] 陳印,徐紅梅.混合算法在車輛路徑優(yōu)化問題中的應用[J].計算機仿真,2012,29(5):356-359.

[11] 王蓮花,彭鑫.帶時間窗的配送車輛路徑問題模型及算法[J].物流技術,2015,34(3):95-97,238.

[12] 李軍.有時間窗的車輛路線安排問題的啟發(fā)式算法[J].系統(tǒng)工程,1996,14(5):45-50.

[13] 但正剛,蔡臨寧,杜麗麗,等.車輛路徑優(yōu)化問題的均衡性[J].清華大學學報:自然科學版,2006,46(11):1945-1948.

[14] 劉小蘭,郝志峰,汪國強,等.有時間窗的車輛路徑問題的近似算法研究[J].計算機集成制造系統(tǒng),2004,10(7):825-831.

[15] Doyuran T,Catay B.A robust enhancement to the Clarke-Wright savings algorithm[J].Journal of the Operational Research Society,2011,62(1):223-231.

[16] 中國民用航空局.航空公司航班正常運行標準(試行)(民航發(fā)[2013]83號)[S].北京:民航局綜合司,2013.

[17] 樊琳.大型機場地勤服務中的車輛調(diào)度問題的初步研究[D].沈陽:東北大學,2009.

IMPLEMENTING AIRPORT SPECIAL VEHICLES SCHEDULING ALGORITHM WITH MULTI-OBJECTIVE OPTIMISATION

Heng HongjunYan Xiaodong

(CollegeofComputerScienceandTechnology,CivilAviationUniversityofChina,Tianjin300300,China)

In order to ensure normal operation of flights, airport special vehicles have to accomplish ground support services efficiently. Current scheduling method for special vehicles is the artificial method in which one car services one flight only, it has high cost and low efficiency. Aiming at this problem, we put forward a saving algorithm-based solution. The solution has two steps. First, we calculated the subpath set satisfying shortest total driving distance with saving algorithm. Secondly, we assigned each subpath task to all vehicles reasonably by the new constructed method to achieve the goal of least vehicle number and smallest load difference between vehicles. Experiments have been carried out using actual flights data as the numerical example in a certain domestic airport. Compared with the service in one-car-one-flight way, the total driving distance saved 49.28%; and compared with the method without load restriction, the load balancing degree increased from 43.55% to 95.16%. Experimental results showed that to apply this algorithm in special vehicle scheduling can greatly reduce the service cost, and realise the load balance as well.

Airport special vehicle schedulingSaving algorithmLoad balanceMulti-objective optimisation

2015-06-27。國家自然科學基金項目(U1333109)。衡紅軍，副教授，主研領域：智能決策支持。晏曉東，碩士生。

TP301

A

10.3969/j.issn.1000-386x.2016.10.053