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

唐 非， 劉樹安， 董昕禹

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

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

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

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

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

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

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

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

1 多目標模型

1.1 問題描述

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

1.2 變量及假設

本文做出如下假設：

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

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

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

(1)

1.3 數(shù)學模型

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

本文以地勤服務特種車輛數(shù)最小化為第一目標，無效服務時間比率最小化為第二目標以及特種車輛服務時間方差最小化為第三目標建立多目標函數(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)表示目標函數(shù)；式(5)、(6)表示所有的航班均得到服務，且每個航班只需一輛特種車輛服務；式(7)、(8)表示特種車輛k為航班提供服務的時間約束；式(9)～(12)表示特種車輛k為航班提供服務的結束時間、所有航班的最早服務時間、最晚結束服務時間和服務總時間；式(13)、(14)表示所有車輛的服務總時間及平均服務時間；式(15)表示航班i在特種車輛k的序列l(wèi)位置.

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

(16)

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

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

2.1 算法的基本思想

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

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

(17)

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

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

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

(18)

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

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

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

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

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

② 判斷服務序列是否結束，如果是轉步驟①.

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

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

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

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

3 仿真結果與分析

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

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

機型h與服務時間之間的關系矩陣為

3.2 仿真結果

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

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

表2 地勤服務調度方案Tab.2 Scheduling schemes for ground service

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

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

3.3 結果比較

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

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

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

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

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

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

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

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

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

4 結 論

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

[1] 丁建立，王新茹，徐濤.航班延誤恢復調度的混合粒子群算法 [J].交通運輸工程學報，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è)大學學報，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ù)量預測 [J].中國民航飛行學院學報，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.

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

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

* 本文已于2017-10-25 21∶13在中國知網(wǎng)優(yōu)先數(shù)字出版. 網(wǎng)絡出版地址： 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

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