衡紅軍 晏曉東 王 芳 李海豐

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

基于多目標優(yōu)化的機場行李運輸車輛調(diào)度問題研究

衡紅軍 晏曉東 王 芳 李海豐

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

行李裝卸是指將旅客的托運行李裝上飛機或從飛機上卸載下來的一種機場地面保障服務，行李運輸車是民航使用的在機場地面運輸旅客托運行李的特種車輛。目前機場普遍采用的單車服務單航班的車輛調(diào)度方式，車輛的使用成本高、效率較低，且無法保證任務量的均衡。在建立的機場行李運輸車輛調(diào)度模型的基礎(chǔ)上，首先利用最鄰近算法構(gòu)建由一個出港航班和一個到港航班組成的車輛行駛總路程最短的子路徑集合；然后依據(jù)子路徑間的時間銜接關(guān)系對子路經(jīng)進行優(yōu)化組合，將所有子路徑任務合理分配給行李運輸車，實現(xiàn)所需車輛數(shù)最少和車輛任務量均衡的目標；最后，應用機場實際算例進行仿真試驗，通過對試驗結(jié)果的分析，驗證了所建模型及求解算法的合理性和有效性。

多目標優(yōu)化 車輛路徑問題 最鄰近算法

0 引 言

航班過站期間，將接受各種特種車輛服務，其中，行李裝卸服務是指將旅客的托運行李裝上飛機或從飛機上卸載下來的一種機場地面保障服務，而行李運輸車是民航使用的在機場地面運輸旅客托運行李的特種車輛[1]。對于出港航班，用行李運輸車將旅客的托運行李從候機樓行李分揀區(qū)運輸至旅客所乘航班的停機位；對于進港航班，用行李運輸車把從飛機上卸載下的旅客托運行李運輸至候機樓行李分揀區(qū)。機場地面服務保障部門需要在保證航班不延誤的前提下，合理地組織、調(diào)配行李運輸車輛，使得每個航班的行李裝卸需求得到滿足，并能在一定的約束(車輛續(xù)駛路程、車輛載運量、航班時間窗等等)下，達到車輛總行駛路程最短、所需車輛最少、每輛車的任務量均衡的目標。車輛的優(yōu)化調(diào)度對提高航班正點率和資源利用率至關(guān)重要。

目前我國民航機場對行李運輸車輛的調(diào)度大都還是依靠人工調(diào)度。行李運輸車在完成出港航班的旅客托運行李運輸裝載后，空載回到行李分揀區(qū)；對于服務于進港航班的運輸車，需要先空載行駛至航班所在的停機位，再將卸載的行李運輸至行李分揀區(qū)。這種單車服務單航班的方式，車輛的利用成本高、利用率低，在車輛資源緊張的情況下非常容易造成服務不及時的航班延誤。

行李運輸車輛調(diào)度雖然實質(zhì)上是一種帶時間窗約束的車輛路徑問題VRPTW(Vehicle Routing Problem with Time Window)[2]，但已有的有關(guān)VRPTW[5-20]的研究成果卻很難在機場行李運輸車輛調(diào)度中直接應用。這是因為：對于常規(guī)的純送貨、純?nèi)∝浕蛩腿』旌系能囕v路徑問題，車輛從車場(貨物集散中心)出發(fā)后，連續(xù)服務多個客戶才回到車場；而對于機場的出港或到港航班的行李裝卸服務，行李運輸車在完成每一個航班的行李運輸任務后，都必須要回到候機樓的行李分揀區(qū)(車場)，與多車場的車輛路徑問題[3]也不同。

本文首先依據(jù)機場行李裝卸服務的業(yè)務構(gòu)建了車輛調(diào)度的數(shù)學模型；然后，利用最鄰近算法對模型進行求解，先得到由一個出港航班和一個到港航班組成的，滿足航班時間窗約束的行駛總路程最短的子路徑集合；在此基礎(chǔ)上，再對集合中的所有子路徑進行優(yōu)化組合并合理地分配給行李運輸車輛，實現(xiàn)所需車輛數(shù)最少和每輛車的任務量均衡的目標。

本文所提出的解決方案分為兩個階段，分別獨立優(yōu)化并實現(xiàn)總行駛路程最短、車輛數(shù)最少和任務量均衡三個目標，與2006年但正剛等人提出的實現(xiàn)負載均衡的算法[4]相比，本文在實現(xiàn)任務量均衡的同時并不會增大總行駛路程。該解決方案同時也適用于機場貨郵裝卸服務的貨物運輸車輛調(diào)度，只需根據(jù)貨郵運輸服務的實際情況調(diào)整參數(shù)(如裝卸服務時長以及服務的時間窗規(guī)則)。另外，貨郵裝卸服務無須考慮貨郵在地面貨庫的裝載時長。

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

問題描述：給定N+M個航班F={1,2,…，N,1,2,…，M}(N表示出港航班數(shù)量，M表示到港航班數(shù)量)，L輛運輸車V={1,2,…,L}，航班的行李運輸量為q，運輸車最大載重量為Q，問題是設計每輛運輸車的行駛路線，每條行駛路線可能包含多個子路徑，要求滿足如下約束：每個航班恰好被服務一次；每條子路徑起止于行李分揀區(qū)；每條子路徑的行李總重量不能超過運輸車的最大載重量；每個航班必須在其時間窗[ai,bi]內(nèi)被服務，否則將導致運輸車等待或航班延遲。實現(xiàn)的目標：1)運輸車輛的總行駛路程最短；2)所用的運輸車輛數(shù)量最少；3)每輛運輸車之間的任務量差異最小(任務均衡度最大)。

參數(shù)定義：

Ti—表示航班i裝/卸行李的服務時長；

dij—表示運輸車輛從航班i所在停機位到航班j所在停機位的行駛距離；

tij—表示運輸車輛從航班i所在停機位到航班j所在停機位的行駛時間；

sik—表示行李運輸車k到達航班i所在停機位的時間，令s0k=0；k∈V；

ai—表示第i個航班裝/卸服務的最早開始時間；

bi—表示第i個航班裝/卸服務的最晚開始時間；

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

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

sik+Ti+tij-ω(1-xijk)≤sjk?ij∈F?k∈V

(9)

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

(10)

xijk∈{0,1} ?ij∈F?k∈V

(11)

在上述表達式中，式(1)表示運輸車的總行駛路程最短；式(2)表示所用的運輸車輛數(shù)量最少；式(3)表示每輛運輸車之間的任務量差異最??；式(4)表示每個航班僅能被服務一次；式(5)表示滿足運輸車的最大載重量要求；式(6)-式(8)保證每輛運輸車輛從出發(fā)點出發(fā)，服務航班后，回到出發(fā)點；式(9)表示運輸車輛k在從航班i的位置向航班j的位置行駛過程中，在時間sik+Ti+tij之前不能到達航班j，其中ω是一個較大的標量，若xijk=0，則可保證式(9)的約束一定成立；式(10)表示運輸車輛為航班i服務的時間必須在其時間窗口內(nèi)；式(11)是整數(shù)化的約束。

2 求解算法設計

2.1 最鄰近算法原理

最鄰近算法最早由Rosenkrantz和Stearns等人于1977年提出，與Dijkstra算法和Floyd算法一并用于求解物資配送最短路徑問題。該算法基本原理過程描述如下：1)取配送中心(或車場)作為線路的起點；2)尋找與上一次加進線路中的點距離最近的點，把此點加到線路中去；3)重復步驟2)，直到所有的點都已考慮，就得到了一條線路。

2.2 算法設計步驟

評價值函數(shù)：

Z=dij+w1×Twait+w2×Tdelay

(12)

其中：Twait=max(aj-sj,0), 表示由于車輛早到，需要等待的時間；Tdelay=max(sj-bj,0)，表示由于車輛晚到，延誤的時間；sj=si+Ti+Tij，表示車輛到達航班j的時間；w1為等待的懲罰系數(shù)，w2為延誤的懲罰系數(shù)。利用最鄰近算法構(gòu)造子路徑串的具體步驟如下：

第一步 以行李分揀區(qū)作為子路徑i的起點；

第二步 尋找與子路徑i起點相鄰的、評價值(式(12))最小的且未被訪問的出港航班Fdi,如找到，則把Fdi加入到子路徑i中，否則，轉(zhuǎn)第四步；

第三步 以Fdi為起點，尋找與Fdi相鄰的、評價值最小的且未被訪問的進港航班Fai，如找到，則把Fai加入到子路徑i中，否則，轉(zhuǎn)第四步；

第四步 是否存在未被訪問的航班，如是，則i=i+1,轉(zhuǎn)第一步，繼續(xù)尋找下一條子路經(jīng)；如否，則算法結(jié)束。

3 任務分配及其均衡性

利用最鄰近算法找出了滿足車輛行駛總路程最短的子路徑集合，實現(xiàn)了對第一目標(即式(1))的優(yōu)化?？紤]運輸車輛可以重復使用，即一輛車在不同時刻可以完成多個子路徑的行李運輸任務，因此依據(jù)子路徑間的時間銜接關(guān)系，將所有子路徑任務合理地分配給每一輛運輸車，實現(xiàn)所需車輛數(shù)目最少和每輛運輸車之間的任務量差異最小的目標。

3.1 任務分配均衡性

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

參數(shù)定義：

θ—任務均衡度；

l—總車輛數(shù)；

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

Ctotal—總?cè)蝿樟?單位：航班數(shù))；

(13)

任務均衡度：

(14)

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

3.2 具體實現(xiàn)

具體步驟：

第一步 根據(jù)子路徑集合R={R1，R2，…,Rs}，計算Ri的開始服務時刻tstart(i)和結(jié)束服務時刻tend(i)，i∈{1,2,…,s}。計算tstart(i)時，須考慮在行李分揀區(qū)將行李裝上運輸車的時間，計算tend(i)時，須考慮從停機位回到行李分揀區(qū)的時間以及在行李分揀區(qū)將行李從運輸車上卸下的時間;

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

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

第五步 若分配完畢后還有子路徑任務未被分配，l=l+1，轉(zhuǎn)第三步；否則，至少需要l輛運輸車才能完成所有行李運輸任務，轉(zhuǎn)第六步；

第六步 按照上一步的l值，加上任務量τ約束，重復第三步和第四步，若分配完畢后仍有子路徑任務未被分配，則τ=τ+1，轉(zhuǎn)第六步；否則，算法終止。

4 算例分析

本文采用國內(nèi)某機場的航班數(shù)據(jù)做算例，實現(xiàn)對機場行李裝卸服務的調(diào)度，驗證方案的有效性。

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

該機場擁有客機停機位63個，每天進離港航班大約300架次。按規(guī)定[21]行李運輸車輛的行駛速度為20km/h，最大載重量為2噸。本文選取該機場2014年8月31日00:00到2014年8月31日23:59之間的所有288個航班進行實驗，其中出港航班147個，航班編號1-147；到港航班141個，航班編號148-288。

4.1.1 裝卸行李的服務時間

◎?qū)σ阴０被?百服嚀、泰諾林，別名撲熱息痛，也是可以用的，WHO也是推薦使用，但這個藥經(jīng)肝臟代謝，中國乙肝高發(fā)，所以在中國建議1歲以下慎用，父母明確無乙肝病史的可以放心用。

由于不同類型飛機的行李艙大小不同，所能承載的行李重量不同，因此，行李裝卸的服務時間由航班的機型確定。本文將飛機分為三類[22]：小型飛機、中型飛機、大型飛機。表1是不同類型飛機的載客量(單位：座)、行李艙載重量(單位：噸)、裝卸服務時間(單位：分鐘)。

表1 不同類型飛機的行李艙載重量和裝卸服務時間

4.1.2 停機位距離

在機場，所有地面車輛必須按照規(guī)定的路線行駛，不得進入飛機行駛區(qū)域。該機場現(xiàn)有63個客機停機位，大概分布于遠機位、T1航站樓、T2航站樓三部分(如圖1所示)，根據(jù)其鄰接關(guān)系，編號依次為：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，其中行李分揀區(qū)(車場)位于停機位109和停機位501之間，其鄰接關(guān)系由其位置決定，相鄰停機位之間距離大約40米。表2列出了行李分揀區(qū)(編號：D)和其中8個停機位任意兩點之間的距離(單位：米)。

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

D101113112415114102417107D03603202805603603204801201013600680640200720401202401133206800408804064080044011228064040084080600760400415560200880840092024080440114360720408092006808404801023204064060024068001602004174801208007608084016003601071202404404004404802003600

4.1.3 裝卸服務的時間窗

時間窗即由服務車輛開始為該航班服務的最早開始服務時間(或稱時間窗下限，單位：時刻)和最晚開始服務時間(或稱時間窗上限，單位：時刻)限制的時間范圍[19]。服務車輛必須在這個時間范圍內(nèi)開始為該航班服務，如早于最早開始服務時間到達，則需等待；如晚于最晚開始服務時間到達，將導致航班延誤。

民航局規(guī)定：所有機型應在飛機計劃/預計離港時間前5分鐘完成貨郵、行李的裝載；裝卸隊員及裝卸設備在航班計劃/預計到港時間前5分鐘到位；第一件行李的傳送時間不晚于飛機擋輪擋后30分鐘，最后一件行李傳送時間不晚于飛機擋輪擋后50分鐘[21]。

依據(jù)以上民航局制定的服務標準，確定離港和到港航班的裝載和卸載時間窗下限和時間窗上限等參數(shù)定義如下：

ai—時間窗下限；

bi—時間窗上限；

td—航班計劃離港時間；

ta—航班計劃到港時間；

ti0—第i個航班所在停機位到行李分揀區(qū)的行駛時間；

Ti—行李裝卸服務時間。

離港航班裝載行李時間窗：

bi=td-Ti-5

(15)

ai=bi-15

(16)

到港航班卸載行李時間窗：

ai=ta

(17)

bi=ta+30-Ti-ti0

(18)

按照式(15)和式(16)得到的離港航班時間窗(部分)如表3所示，同樣，按照式(17)和式(18)可得到到港航班時間窗。為了處理時方便，實際計算時均將24進制的時刻轉(zhuǎn)化為10進制的分鐘。

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

4.2 結(jié)果分析

利用Matlab編程工具實現(xiàn)本文所設計的算法，并將其應用于機場行李運輸車調(diào)度問題，得到了288個進出港航班接受行李裝卸服務的子路經(jīng)集合和每輛行李車的路徑安排方案。在利用最鄰近算法求解子路經(jīng)集合過程中，等待懲罰系數(shù)設定為250，延誤懲罰系數(shù)設定為600，行李裝卸服務不會造成航班延誤。

4.2.1 子路徑集合

表4列出了利用最鄰近算法產(chǎn)生的子路徑集合，共產(chǎn)生152個子路徑，這意味著在24小時內(nèi)的不同時刻需要152個車次來完成所有航班的行李裝卸運輸任務，而傳統(tǒng)的單車服務單航班方式，則需要288個車次。

表4 子路徑集合(全部)

續(xù)表4

按照出港航班與到港航班銜接來安排行李運輸車路徑，車輛總行駛路程為195.84km，而采用單車服務單航班方式的車輛行駛總路程則為226.64km。與其相比，本文算法節(jié)省了13.59%的路程，節(jié)約了車輛的服務成本。

4.2.2 行李裝卸任務分配

為每一輛車分配行李裝卸任務。先不考慮任務均衡性，即分配任務時不對每輛行李運輸車加任務量τ約束。表5列出了不考慮任務均衡性時行李運輸車的路徑方案。

由表5可以看出，僅按照開始時間早優(yōu)先分配原則，而不加任務量約束時，其任務均衡度(根據(jù)式(14)計算)為38.89%，行李運輸車間的任務量差異較大?？紤]任務均衡的結(jié)果如表6所示。

表5 不考慮任務均衡性的行李運輸車路徑方案(部分)

表6 考慮任務均衡性的行李運輸車路徑方案(全部)

通過施加任務均衡約束，任務均衡度提高至93.06%，大大縮小了每輛車間的任務量差異。

5 結(jié) 語

本文在建立的機場行李運輸車輛調(diào)度模型的基礎(chǔ)上，首先利用最鄰近算法構(gòu)建了由出港航班和到港航班組成的車輛行駛總路程最短的子路徑集合；然后依據(jù)子路徑間的時間銜接關(guān)系對子路經(jīng)進行優(yōu)化組合，將所有子路徑任務合理分配給行李運輸車，并實現(xiàn)了所需車輛數(shù)最少和車輛任務量均衡的目標。實驗結(jié)果驗證了方案的有效性。

實際工作中，航班計劃易受到諸如天氣、空管流量以及機務維修等因素的影響，行李運輸車輛的調(diào)度方案也應及時做出調(diào)整[23]，我們下一步將對此作深入研究。

[1] 黃建偉，鄭?。窈降厍诜誟M]．北京：旅游教育出版社, 2007．

[2]DantzigGB,RamserJH．Thetruckdispatchingproblem[J]．ManagementScience, 1959, 6(1): 80-91．

[3] 殷脂，葉春明．多配送中心物流配送車輛調(diào)度問題的分層算法模型[J]．系統(tǒng)管理學報, 2014,23(4):602-606．

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

[5] 馬華偉，左春榮，楊善林．多時間窗車輛調(diào)度問題的建模與求解[J]．系統(tǒng)工程學報, 2009,24(5):607-613．

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

[7] 童行行，王凌，何京芮．旅行商問題基于參考點的相鄰插入法及其改進[J]．計算機工程與應用,2002,38(20):63-65．

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

[9] 高曉?。诟倪MQPSO算法的物流運輸路徑問題研究[J]．計算機仿真, 2013,30(8):169-172．

[10] 郎茂祥．物流配送車輛調(diào)度問題的模型和算法研究[D]．北京：北方交通大學,2002．

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

[12] 王旭坪，張凱，胡祥培．基于模糊時間窗的車輛調(diào)度問題研究[J]．管理工程學報, 2011,25(3):148-154．

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

[14] 修桂華，王俊鴻．求解帶硬時間窗車輛路徑問題的自適應蟻群算法[J]．計算機應用與軟件,2008,25(11):109-111．

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

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

[17] 費騰，張立毅，孫云山．基于DNA-蟻群算法的車輛路徑優(yōu)化問題求解[J]．計算機工程,2014,40(12):205-208,213．[18]DoyuranT,CatayB．ArobustenhancementtotheClarke-Wrightsavingsalgorithm[J]．JournaloftheOperationalResearchSociety,2011,62(1):223-231．

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

[20] 劉志碩，柴躍廷，申金升．蟻群算法及其在有硬時間窗的車輛路徑問題中的應用[J]．計算機集成制造系統(tǒng),2006,12(4):596-602．

[21] 中國民用航空局．航空公司航班正常運行標準(試行)：民航發(fā)[2013]83號[S]．2013．

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

[23] 張婷，賴平仲，何琴飛，等．基于實時信息的城市配送車輛動態(tài)路徑優(yōu)化[J]．系統(tǒng)工程，2015，33(7):58-64．

RESEARCH ON SCHEDULING OF AIRPORT BAGGAGE TRANSPORT VEHICLES BASED ON MULTI-OBJECTIVE OPTIMIZATION

Heng Hongjun Yan Xiaodong Wang Fang Li Haifeng

(CollegeofComputerScienceandTechnology,CivilAviationUniversityofChina,Tianjin300300,China)

Airport baggage handling is one of the ground support services that load passenger bags to the aircraft or unload passenger bags from the aircraft, and luggage transport vehicle is special vehicles which are used in civil aviation ground to transport checked baggage. The current method of scheduling for special vehicles is the artificial method that one car services one flight, which having high cost and low efficiency, thus it cannot be guaranteed for route balancing. On the basis of established scheduling model about airport baggage transport vehicle, firstly, nearest neighbors algorithm are used to built sub-routes set with the shortest route total distance, which composed by one departure flight and one arrival flight, then the combination of sub-route is optimized based on the time relationship between the sub-route. Assigning the sub-route to the luggage carrier reasonably so as to achieve the objectives of the minimum number of vehicles required and vehicle route balancing. Finally, the airport actual example of simulation test was applied, and the analysis of test results verifies the proposed model and algorithm are reasonable and effective.

Multi-objective optimization Vehicle routing problem(VRP) Nearest neighbors algorithm

2015-12-09。國家自然科學基金項目(U1333109)；國家青年科學基金項目(61305107)。衡紅軍，副教授，主研領(lǐng)域：智能決策支持。晏曉東，碩士生。王芳，碩士生。李海豐，博士。

TP249

A

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