實(shí)現(xiàn)多目標(biāo)優(yōu)化的機(jī)場(chǎng)特種車輛調(diào)度算法

衡紅軍　晏曉東

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

?

實(shí)現(xiàn)多目標(biāo)優(yōu)化的機(jī)場(chǎng)特種車輛調(diào)度算法

衡紅軍晏曉東

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

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

機(jī)場(chǎng)特種車輛調(diào)度節(jié)約算法任務(wù)均衡多目標(biāo)優(yōu)化

0　引　言

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

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

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

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

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

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

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

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

參數(shù)定義：

Ti表示航班i需要的加油服務(wù)時(shí)間。

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

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

ai表示時(shí)間窗下限。

bi表示時(shí)間窗上限。

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

(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)

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

該問題的解可以用一個(gè)整數(shù)序列表示。例如，假設(shè)有10個(gè)航班，它的一個(gè)解可以表示為整數(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]。然后，在滿足時(shí)間要求前提下進(jìn)行任務(wù)分配，第一輛加油車按照R2、R1路徑的順序?yàn)楹桨喾?wù)，第二輛加油車按照R3路徑為航班服務(wù)。

2　節(jié)約算法原理及算法設(shè)計(jì)

2.1節(jié)約算法原理

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

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

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

(12)

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

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

EFj=si+Ti+tij-sj

(13)

顯然，EFj<0時(shí)，j點(diǎn)任務(wù)的開始時(shí)間提前；EFj=0時(shí)，開始時(shí)間不變；EFj>0時(shí)，開始時(shí)間推遲。

(14)

(15)

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

具體步驟：

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

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

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

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

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

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

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

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

(5) 計(jì)算EFj：

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

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

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

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

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

3.1任務(wù)分配均衡性

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

參數(shù)定義：

θ：任務(wù)均衡度；

l：總車輛數(shù)；

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

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

以下式表示任務(wù)均衡度：

(16)

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

3.2具體實(shí)現(xiàn)

具體步驟：

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

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

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

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

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

4　算例分析

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

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

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

4.1.1機(jī)型大小

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

表1　不同類型飛機(jī)的加油需求量和服務(wù)時(shí)間

4.1.2停機(jī)位距離

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

該機(jī)場(chǎng)現(xiàn)有63個(gè)客機(jī)停機(jī)位，分布于三個(gè)區(qū)域：遠(yuǎn)機(jī)位、T1航站樓、T2航站樓(如圖1所示)。根據(jù)其鄰接關(guān)系，編號(hào)依次為：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。其中加油車車場(chǎng)位于停機(jī)位109和停機(jī)位501之間，其鄰接關(guān)系由其位置決定，相鄰?fù)C(jī)位之間距離大約40米。表2列出了車場(chǎng)(編號(hào)：D)和其中8個(gè)停機(jī)位任意兩點(diǎn)之間的距離(單位：米)。

圖1　該機(jī)場(chǎng)停機(jī)位布局示意圖

D106107108109501502503504D016012080404080120160106160040801202002402803201071204004080160200240280108808040040120160200240109401208040080120160200501402001601208004080120502802402001601204004080503120280240200160804004050416032028024020012080400

4.1.3離港航班時(shí)間窗

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

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

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

參數(shù)定義：

ai：時(shí)間窗下限；

bi：時(shí)間窗上限；

td：計(jì)劃離港時(shí)間；

Ttotal：過站時(shí)間；

Ti：加油車服務(wù)時(shí)間。

離港航班時(shí)間窗：

ai=td-Ttotal

(17)

bi=td-Ti-5

(18)

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

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

4.2結(jié)果分析

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

4.2.1航班接受加油服務(wù)的時(shí)間段

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

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

4.2.2子路徑方案

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

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

續(xù)表5

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

4.2.3加油車任務(wù)分配

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

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

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

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

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

5　結(jié)　語

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[14] 劉小蘭,郝志峰,汪國(guó)強(qiáng),等.有時(shí)間窗的車輛路徑問題的近似算法研究[J].計(jì)算機(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] 中國(guó)民用航空局.航空公司航班正常運(yùn)行標(biāo)準(zhǔn)(試行)(民航發(fā)[2013]83號(hào))[S].北京:民航局綜合司,2013.

[17] 樊琳.大型機(jī)場(chǎng)地勤服務(wù)中的車輛調(diào)度問題的初步研究[D].沈陽:東北大學(xué),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。國(guó)家自然科學(xué)基金項(xiàng)目(U1333109)。衡紅軍，副教授，主研領(lǐng)域：智能決策支持。晏曉東，碩士生。

TP301

A

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