唐 非， 劉樹安， 董昕禹

(1. 東北大學(xué) 信息科學(xué)與工程學(xué)院， 沈陽 110819； 2. 沈陽工業(yè)大學(xué) 軟件學(xué)院， 沈陽 110023； 3. 紐約州立大學(xué)石溪分校 計算機系， 美國 石溪 11790-2424)

多階段啟發(fā)式算法求解機場地勤服務(wù)優(yōu)化問題*

唐 非1，2， 劉樹安1， 董昕禹3

(1. 東北大學(xué) 信息科學(xué)與工程學(xué)院， 沈陽 110819； 2. 沈陽工業(yè)大學(xué) 軟件學(xué)院， 沈陽 110023； 3. 紐約州立大學(xué)石溪分校 計算機系， 美國 石溪 11790-2424)

針對保障航班離港無延誤的地勤服務(wù)調(diào)度優(yōu)化問題，建立了以特種車輛數(shù)最小化、無效服務(wù)時間比率最小化和特種車輛服務(wù)時間方差最小化的多目標(biāo)模型，提出了一種新的多階段啟發(fā)式算法.根據(jù)航班服務(wù)時間窗和特種車輛在航班間服務(wù)轉(zhuǎn)移的特點，該算法能夠為機場航班合理分配特種車輛，優(yōu)化航班服務(wù)序列.通過仿真實例驗證了模型及算法的正確性，結(jié)果表明，所提出的多階段啟發(fā)式算法提高了特種車輛的服務(wù)效率，減少了用車數(shù)量和無效服務(wù)時間，達到了特種車輛服務(wù)的負(fù)荷均衡.

延誤； 特種車輛； 無效服務(wù)時間； 時間方差； 服務(wù)時間窗； 多階段； 松弛時間； 負(fù)荷均衡

根據(jù)民航局統(tǒng)計，到2015年我國境內(nèi)有民用機場210個，其中有26個機場的乘客年吞吐量超過1 000萬人次、16個機場年起降架次超過20萬，導(dǎo)致機場旅客數(shù)量、航班到港頻次的快速增長和地面運行效率之間的矛盾越發(fā)明顯.航班延誤對社會和經(jīng)濟效益存在著顯性或隱性的影響，恢復(fù)延誤需要通過地勤保障作業(yè)、停機位分配、滑行道及路徑選擇等提高服務(wù)效率[1].其中，地勤服務(wù)作業(yè)是作業(yè)項目多環(huán)境影響較復(fù)雜的重要研究課題，主要包括單航班多服務(wù)優(yōu)化、多航班單服務(wù)優(yōu)化和多航班多服務(wù)優(yōu)化等問題.這些問題主要是對地勤服務(wù)進行合理優(yōu)化調(diào)度，降低航班延誤帶來的損失[2-4].地勤服務(wù)組優(yōu)化調(diào)度問題可以看作有時間窗的車輛路徑問題(vehicle routing problem with time windows，VRPTW)的一種延伸.VRPTW問題是NP難問題，多采用迭代搜索算法、鄰域搜索算法和元啟發(fā)式搜索算法等非精確算法[5-8].

與VRPTW相比，地勤服務(wù)優(yōu)化問題中特種車輛在航班間服務(wù)轉(zhuǎn)移時間相當(dāng)于VRPTW的路徑代價，但是到達航班停機位后需要根據(jù)航班的需求繼續(xù)進行服務(wù)保障，這是服務(wù)過程的重點.在機場地勤車輛調(diào)度的研究中，文獻[9]以地勤服務(wù)車輛最低數(shù)量為目標(biāo)，采用禁忌搜索算法進行求解，通過拖車服務(wù)調(diào)度結(jié)果可以看出存在一定的可調(diào)節(jié)時間余量.類似地勤服務(wù)優(yōu)化問題的文獻還有很多，但是通過對求解方法的分析并結(jié)合VRPTW問題的求解方法可知，地勤服務(wù)車輛調(diào)度問題很難求得精確最優(yōu)解.因此，為保障航班無延誤離港，本文在滿足航班過港服務(wù)時間窗約束下，建立了以服務(wù)特種車輛數(shù)最小化、無效服務(wù)時間比率最小化和特種車輛服務(wù)時間方差最小化的多目標(biāo)模型，并提出了一種新的多階段啟發(fā)式算法對問題進行求解.

1 多目標(biāo)模型

1.1 問題描述

一個時段內(nèi)N架航班進入指定停機位，航班過港時間及航班服務(wù)需求等信息均可知.機場有一定數(shù)量的資源保障航班的過港服務(wù)需求，如清潔車、行李車、加油車和食品車等，通過特種車輛的服務(wù)作業(yè)使航班滿足需求并滿足預(yù)計離港時間約束.

1.2 變量及假設(shè)

本文做出如下假設(shè)：

1) 航班需求量不同，服務(wù)時間不同，但只需一輛特種車輛完成；

2) 特種車輛同一時刻只能為一個航班提供服務(wù)，且一旦開始服務(wù)不可中斷.

其中，k∈M，l∈Nk.特種車輛k的航班服務(wù)集合及航班服務(wù)序列編號集合分別表示為Nk={xk，1，xk，2，…，xk，l，…，xnk}和Lk={1，2，…，l，…，nk}，且滿足

(1)

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

機場航班起降頻次逐年上升，為其提供地勤保障的特種車輛存在設(shè)備老化和維修等狀況，在保障不會因地勤服務(wù)作業(yè)導(dǎo)致航班發(fā)生延誤的情況下，確定地勤服務(wù)的最少用車數(shù)量尤為重要.此外，提高服務(wù)效率，減少特種車輛無效服務(wù)作業(yè)時間，并且盡量使特種車輛服務(wù)作業(yè)均衡也是地勤服務(wù)調(diào)度的關(guān)鍵指標(biāo).本文中無效服務(wù)時間指特種車輛在航班間服務(wù)的轉(zhuǎn)移和等待服務(wù)時間，相反，為航班提供服務(wù)作業(yè)的時間為有效作業(yè)時間.

本文以地勤服務(wù)特種車輛數(shù)最小化為第一目標(biāo)，無效服務(wù)時間比率最小化為第二目標(biāo)以及特種車輛服務(wù)時間方差最小化為第三目標(biāo)建立多目標(biāo)函數(shù)模型，其表達式分別為

Z1=minm

(2)

(3)

(4)

s.t

(5)

xk，l≠xk′，l′(k、k′∈M，l、l′∈Lk)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

xk，l=i(i∈N，k∈M，l∈Lk)

(15)

模型中式(2)～(4)表示目標(biāo)函數(shù)；式(5)、(6)表示所有的航班均得到服務(wù)，且每個航班只需一輛特種車輛服務(wù)；式(7)、(8)表示特種車輛k為航班提供服務(wù)的時間約束；式(9)～(12)表示特種車輛k為航班提供服務(wù)的結(jié)束時間、所有航班的最早服務(wù)時間、最晚結(jié)束服務(wù)時間和服務(wù)總時間；式(13)、(14)表示所有車輛的服務(wù)總時間及平均服務(wù)時間；式(15)表示航班i在特種車輛k的序列l(wèi)位置.

在模型中涉及到的sign(·)表示為

(16)

2 多階段啟發(fā)式算法設(shè)計

本文模型為多目標(biāo)非線性模型，在航班無延誤情況下，很難獲得特種車輛服務(wù)車輛數(shù)、無效服務(wù)時間和服務(wù)作業(yè)均衡最優(yōu)的精確解.根據(jù)這個特點基于兩階段啟發(fā)式算法的思想設(shè)計了新的多階段啟發(fā)式算法.

2.1 算法的基本思想

本文所設(shè)計算法的基本思想是特種服務(wù)車輛應(yīng)盡量滿負(fù)荷進行服務(wù)作業(yè)以減少服務(wù)車輛數(shù).在此基礎(chǔ)上減少無效服務(wù)時間，并盡量使車輛的服務(wù)作業(yè)均衡.因此，多階段啟發(fā)式算法包括構(gòu)造特種車輛航班服務(wù)序列初始分配階段、優(yōu)化服務(wù)系列階段和均衡特種車輛間服務(wù)作業(yè)階段.

算法的第一階段采用局部鄰域搜索方法實現(xiàn)航班的初始分配.航班集合在滿足航班離港需求前提下，將航班最大化數(shù)量分配給特種車輛，使其為航班提供服務(wù)作業(yè).因此，在航班集合中以最遲離港的航班來初始化特種車輛服務(wù)序列，以初始航班為基礎(chǔ)，采用局部鄰域搜索的方法以松弛時間最小優(yōu)先規(guī)則依次對滿足時間約束的航班進行初始分配，直到航班集合中沒有滿足條件的航班.松弛時間Δti是指特種車輛在服務(wù)序列相鄰的兩航班間等待服務(wù)的時間.根據(jù)式(8)和(15)，Δti的計算表達式為

(17)

如果存在等待服務(wù)分配的航班，則特種車輛k的局部鄰域搜索范圍為符合式(7)、(8)約束的航班.

算法的第二階段是在初始分配的基礎(chǔ)上，采用循環(huán)調(diào)整服務(wù)時間窗的方法盡可能減少無效服務(wù)時間，并采用插入法在所有Δtxk，l，k>0中以松弛時間最小優(yōu)先規(guī)則將符合時間約束的航班插入特種車輛服務(wù)序列的相應(yīng)位置.

通過調(diào)整服務(wù)開始時間循環(huán)調(diào)節(jié)服務(wù)時間窗的區(qū)間，調(diào)整后服務(wù)開始時間計算表達式為

(18)

算法的第三階段在前兩階段的基礎(chǔ)上以松弛時間最小優(yōu)先規(guī)則對特種車輛未進行服務(wù)的剩余服務(wù)時間重新調(diào)整航班的分配，盡量使特種車輛服務(wù)作業(yè)均衡.

2.2 多階段啟發(fā)式算法的實現(xiàn)

2) 對特種車輛服務(wù)序列進行初始分配.

① 如果N非空，則以N中最遲離港的任意航班初始分配為特種車輛k服務(wù)序列末尾位置，并在N中刪除該航班，轉(zhuǎn)步驟②；否則轉(zhuǎn)步驟4).

3) 對航班序列進行優(yōu)化.

② 判斷服務(wù)序列是否結(jié)束，如果是轉(zhuǎn)步驟①.

③ 航班集合N中搜索滿足時間約束且可插入特種車輛k服務(wù)序列的航班，如果有，以松弛時間最小為原則插入相應(yīng)位置，調(diào)整特種車輛的服務(wù)序列和從N中刪除該航班，否則轉(zhuǎn)步驟2).

圖1 算法流程圖Fig.1 Flow chart of algorithm

4) 均衡服務(wù)作業(yè).對于提前結(jié)束航班服務(wù)序列作業(yè)的特種車輛，搜索其他車輛服務(wù)序列中是否有滿足時間約束未開始服務(wù)的航班，如果有，按照松弛時間最小原則在車輛間調(diào)整服務(wù)序列，否則轉(zhuǎn)步驟5).

5) 輸出需要的目標(biāo)函數(shù)值Z1、Z2和Z3.

3 仿真結(jié)果與分析

算法運行環(huán)境為ThinkPad PC i7-4710MQ，CPU為2.50 GHz.

3.1 算例數(shù)據(jù)

機型h與服務(wù)時間之間的關(guān)系矩陣為

3.2 仿真結(jié)果

根據(jù)航班信息表1、轉(zhuǎn)移時間矩陣S和服務(wù)時間矩陣P的數(shù)據(jù)，運行系統(tǒng)得到地勤服務(wù)調(diào)度方案如表2所示，其中，tk為特種車輛k的服務(wù)時間，sg為在航班停機位轉(zhuǎn)移時間，tw為等待服務(wù)時間.目標(biāo)函數(shù)值為Z1=4，Z2=13.92%，Z3=16.86.根據(jù)表2的地勤服務(wù)調(diào)度方案，具體地勤服務(wù)作業(yè)時間計劃如圖2所示.

表1 航班數(shù)據(jù)Tab.1 Data of flights

表2 地勤服務(wù)調(diào)度方案Tab.2 Scheduling schemes for ground service

圖2 地勤服務(wù)作業(yè)時間計劃Fig.2 Working time plan for ground service

由表2和圖2可以看出，在保障航班無延誤情況下，至少需要4輛特種車輛，航班轉(zhuǎn)移和等待的無效服務(wù)時間比率較小，航班的工作效率較高，并且特種車輛間的服務(wù)負(fù)荷相對均衡.

3.3 結(jié)果比較

機場地勤服務(wù)調(diào)度問題作為VRPTW問題的一種延伸，很難獲得精確解，對于算法的有效性，本文采用VRPTW常用的啟發(fā)式算法和遺傳算法進行比較.

機場對到港航班進行地勤服務(wù)調(diào)度所采用的啟發(fā)式算法為先到先服務(wù)(first come first service，F(xiàn)CFS)算法，在相同數(shù)據(jù)情況下，系統(tǒng)運行獲得的地勤服務(wù)調(diào)度方案如表3所示，目標(biāo)函數(shù)值為Z1=5，Z2=18.92%，Z3=8.03.根據(jù)表3地勤服務(wù)調(diào)度方案，先到先服務(wù)地勤服務(wù)作業(yè)具體時間安排如圖3所示.

表3 地勤服務(wù)調(diào)度方案(FCFS)Tab.3 Scheduling schemes for ground service(FCFS)

圖3 地勤服務(wù)作業(yè)時間計劃(FCFS)Fig.3 Working time plan for ground service (FCFS)

對于VRPTW研究中常采用的遺傳算法，在相同數(shù)據(jù)條件下，為保障航班無延誤時使用特種車輛數(shù)最少，采用逐次增加使用車輛數(shù)的方法，不斷調(diào)整參數(shù)多次運行系統(tǒng)，當(dāng)種群規(guī)模參數(shù)為500、交叉概率為0.65、變異概率為0.15、最大終止代數(shù)為2 000時，獲得地勤服務(wù)調(diào)度方案如表4所示，目標(biāo)函數(shù)值為Z1=5，Z2=18.25%，Z3=33.14.根據(jù)表4地勤服務(wù)調(diào)度方案，采用遺傳算法獲得的地勤服務(wù)作業(yè)時間計劃如圖4所示.

在本文所提算法中，特種車輛服務(wù)作業(yè)時間安排緊密、空閑時隙較小.三種算法所用地勤服務(wù)作業(yè)的特種車輛數(shù)目分別為4、5和5，目標(biāo)Z1優(yōu)勢明顯；無效服務(wù)時間比率分別為13.92%、18.92%和18.25%，目標(biāo)Z2優(yōu)勢比較明顯，另外三種算法的無效服務(wù)時間總和分別為104.7、141.8和203.1 min，從時間值上看優(yōu)勢也比較明顯，說明服務(wù)作業(yè)效率是比較有優(yōu)勢的.特種車輛服務(wù)作業(yè)時間方差分別為16.86、8.03和33.14，在目標(biāo)Z3服務(wù)作業(yè)均衡方面居中，比先到先服務(wù)算法的服務(wù)均衡性稍差.

表4 地勤服務(wù)調(diào)度方案(GA)Tab.4 Scheduling schemes for ground service (GA)

圖4 地勤服務(wù)作業(yè)時間計劃(GA)Fig.4 Working time plan for ground service (GA)

本文提出的多階段啟發(fā)式算法在不同計算機上運行時間基本在1～2 s之間，運行得到的調(diào)度方案也比較合理，有效減少了地勤服務(wù)用車數(shù)，減少了服務(wù)轉(zhuǎn)移及等待時間，降低了無效服務(wù)時間比率，并盡量使特種服務(wù)車輛的服務(wù)作業(yè)負(fù)荷均衡.

4 結(jié) 論

本文在機場到港航班頻次逐年上升環(huán)境下，考慮了滿足動態(tài)到港且服務(wù)時間窗約束的航班服務(wù)請求，在保障航班不會因地勤服務(wù)發(fā)生離港延誤情況下，提高地勤服務(wù)效率，盡量優(yōu)化地勤服務(wù)作業(yè)安排.根據(jù)服務(wù)時間窗的約束條件建立了多目標(biāo)優(yōu)化模型，主要考慮地勤服務(wù)作業(yè)的最少使用特種車輛問題、在不同航班間服務(wù)轉(zhuǎn)移及等待服務(wù)時間問題和特種車輛之間的服務(wù)負(fù)荷均衡問題.根據(jù)模型特點，在兩階段啟發(fā)式算法的基礎(chǔ)上，提出了一種新的多階段啟發(fā)式算法.研究結(jié)果表明，提出的模型及算法能夠快速反應(yīng)并較好地為機場提供地勤服務(wù)調(diào)度方案，提高了特種車輛的服務(wù)效率，減少了服務(wù)用車及無效的服務(wù)時間，保障了航班按時離港.此外，根據(jù)調(diào)度結(jié)果對機場在配置及維護特種車輛的管理方面也具有一定的參考意義.

[1] 丁建立，王新茹，徐濤.航班延誤恢復(fù)調(diào)度的混合粒子群算法 [J].交通運輸工程學(xué)報，2008，8(2)：90-95.

(DING Jian-li，WANG Xin-ru，XU Tao.Hybrid particle swarm optimization arithmetic for recovery sche-duling of flight delays [J].Journal of Traffic and Transportation Engineering，2008，8(2)：90-95.)

[2] Berrittella M，F(xiàn)ranca L L，Zito P.An analytic hierarchy process for ranking operating costs of low cost and full service airlines [J].Journal of Air Transport Management，2009，15(5)：249-255.

[3] Lp W H，Wang D，Cho V.Aircraft ground service scheduling problems and their genetic algorithm with hybrid assignment and sequence encoding scheme [J].IEEE Systems Journal，2013，7(4)：649-657.

[4] Ravizza S，Atkin J A D，Burke E K.A more realistic approach for airport ground movement optimisation with stand holding [J].Journal of Scheduling，2014，17(5)：507-520.

[5] Cattaruzza D，Absi N，F(xiàn)eillet D，et al.An iterated local search for the multi commodity multi trip vehicle routing problem with time windows [J].Computers & Operations Research，2014，51(3)：257-267.

[6] Michallet J，Prins C，Amodeo L，et al.Multi-start ite-ated local search for the periodic vehicle routing problem with time windows and time spread constraints on services [J].Computers & Operations Research，2014，41：196-207.

[7] Jin J，Crainic T G， L?kketangen A.A cooperative parallel metaheuristic for the capacitated vehicle routing [J].Computers & Operations Research，2014，44：33-41.

[8] 劉艷秋，曹歌，張穎，等.基于分組策略的補貨配送問題優(yōu)化模型 [J].沈陽工業(yè)大學(xué)學(xué)報，2017，39(2)：165-169.

(LIU Yan-qiu，CAO Ge，ZHANG Ying，et al.Optimization model for replenishment and distribution problems based on grouping strategy [J].Journal of Shen-yang University of Technology，2017，39(2)：165-169.)

[9] 茍晶晶.機場規(guī)劃所需地勤保障車輛最低數(shù)量預(yù)測 [J].中國民航飛行學(xué)院學(xué)報，2015，27(2)：50-53.

(GOU Jing-jing.Prediction of the minimum requirement of ground vehicles for airport planning [J].Journal of Civil Aviation Flight University of China，2015，27(2)：50-53.)

Multi-phaseheuristicalgorithmforsolvingairportgroundserviceoptimizationproblem

TANG Fei1,2, LIU Shu-an1, DONG Xin-yu3

(1. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China; 2. School of Software, Shenyang University of Technology, Shenyang 110023, China; 3. Computer Science Department, Stony Brook University, Stony Brook 11790-2424, USA)

Aiming at the ground service scheduling optimization problem without the departure delay in airport, a multi-objective model which could minimize the quantity of special vehicles, the ratio of invalid service time and the service time variance for special vehicles was established, and a multi-phase heuristic algorithm was proposed. According to the features of airline service time window and the mobility of special vehicles service between flights, the allocation of special vehicles for the airpaort flights could be arranged with the proposed algorithm, and the flight service sequence could be optimized. Through the simulation examples, the correctness of both model and algorithm was proved. The results show that the proposed multi-phase heuristic algorithm improves the service efficiency of special vehicles, reduces the quantity of used vehicles and the time of invalid service, and achieves the workload balance of special vehicles.

delay; special vehicle; invalid service time; time variance; service time window; multi-phase; slack time; workload balance

2017-03-06.

國家自然科學(xué)基金面上項目(71571037).

唐 非(1975-)，女，遼寧北鎮(zhèn)人，講師，博士生，主要從事系統(tǒng)建模、系統(tǒng)優(yōu)化與分析等方面的研究.

* 本文已于2017-10-25 21∶13在中國知網(wǎng)優(yōu)先數(shù)字出版. 網(wǎng)絡(luò)出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20171025.2113.072.html

10.7688/j.issn.1000-1646.2017.06.12

TP 18

A

1000-1646(2017)06-0664-06

(責(zé)任編輯：鐘 媛 英文審校：尹淑英)