基于最鄰近算法的機場特種車輛調度應用研究

殷 龍，衡紅軍

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

基于最鄰近算法的機場特種車輛調度應用研究

殷 龍，衡紅軍

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

航班在機場過站期間需要接受清潔、配餐、加水、燃油加注、裝卸行李貨物等一系列地面保障服務。這些服務主要通過一些不同類型的特種車輛(如清潔車、配餐車、加油車、行李車等)來完成。車輛的優化調度對提高航班正點率和資源利用率至關重要。目前我國民航機場對特種車輛的調度大都是依靠人工調度，單車單航班服務。這種低效率調度方式的車輛利用率不高，并且也是造成航班延誤的重要因素。為保證航班正點運行，機場特種車輛必須高效完成地面保障服務任務。文中以燃油加注服務為研究對象，首先根據機場燃油加注服務的業務構建了帶時間窗約束的特種車輛調度的數學模型；然后研究利用最鄰近算法實現對模型的求解，并以國內某機場某天的實際數據為例，驗證了模型求解算法在該問題上的有效性；最后得出了最優的燃油加注任務分配結果。實驗結果表明，利用該算法調度特種車輛可大幅降低服務成本。

車輛路徑問題；最鄰近算法；時間窗；車輛調度；機場特種車輛

Key works:Vehicle Routing Problem (VRP);nearest neighbors algorithm;time window;vehicle scheduling;airport special vehicle

0 引 言

航班正點率、航空安全、航班延誤處理機制、航班的載運率等是衡量民航運輸質量的重要指標[1]。其中人為可控的對民航服務質量影響最大的一項為航班的正點率。隨著日益增長的航空運輸需求，航班延誤現象變得越來越普遍，導致航班正點率降低。而機場調度是機場管理的核心組成部分，因此，優化地面服務車輛調度對于提高航空運輸服務質量和保障航班正點率極為重要。

機場特種車輛調度問題[2]實質上是一種帯時間窗約束的車輛路徑優化問題[3-5](Vehicle Routing Problems with Time Windows，VRPTW)。每個航班都有接受機場提供的地面保障服務的需求。機場地面保障部門需要組織合理的行車路線，使得每個航班的需求得到滿足，并能在一定的約束(車輛續駛路程、車輛載運量、航班時間窗等等)下，達到路程最短、所需車輛最少、耗費時間最少等目的[6]。

文中以燃油加注服務為研究對象，首先，根據機場燃油加注服務的業務構建了特種車輛調度的數學模型；然后，利用最鄰近算法實現對模型的求解，并以國內某機場某天的實際數據為例，驗證了模型求解算法在該問題上的有效性。該方法同樣適用于配餐、加注清水等其他地面保障服務的特種車輛調度。

1 問題描述和數學模型

1.1 問題描述及條件假設

隨著航空交通運輸業的日益發展，增大了機場對航班地勤服務的需求。從地勤服務車輛調度問題中的車輛角度來考慮，由于車輛需要對航班進行服務資源的配送，有關車輛的一些約束需要被考慮，如部分服務車輛的容量限制、航班對服務資源的需求量以及對服務時間的要求等。鑒于此,嘗試用VRPTW[7-9]的建模方法來描述該實際情況：某機場車輛調度中心向n個航班提供特種服務(配餐、加油、加水等)，第i個航班貨物需求量為gi，車輛到達航班i的停機位時刻為si，最早允許特種車輛服務的時間為ai，最遲服務時間為bi，車輛在航班i的服務時間為ti，車輛在航班j的服務時間為tj，車輛由航班i的停機位行駛到航班j的停機位時間為tij，到達航班j的停機位時刻為sj，提前到達航班j的時間為Δaj，延遲到達航班j的時間為Δbj，車場與停機位、停機坪之間的運輸費用為cij，車輛車載容量為Q(Q>gi)，即車輛不允許超過自身最大載重量且必須在時間窗內服務航班。評價值為M,即選擇下一節點時務必使得M盡可能小。要求合理指派特種車輛，并確定每臺車的服務路線，使得總服務費用Z及航班延誤率最低[10]。

問題條件假設：

(1)調度問題是靜態的，即所有任務事先給定；

(2)所有運輸車輛在任何時刻一輛車上至多只能服務一個航班，該任務從車場(原點)作為起點直至相應到達停機坪；

(3)任務的時間窗應該被嚴格執行,即為硬時間窗；

(4)車輛服務路線必須是封閉的,即每輛車在執行完一條調度路線后必須再回到原來所在的位置(車場)。

變量定義：

1.2 模型構建

帶有時間窗約束的特種車輛機場調度模型如下：

目標函數為：

(1)

評價函數為：

M=w1*tij+w2*Δaj+w3*Δbj

w1+w2+w3=1

(2)

約束條件為：

(3)

(4)

(5)

(6)

(7)

Xijk=1→Si+ti+tij=Sj

(8)

Xijk=0(或i,j=0,1,…,m)

(9)

模型中，式(1)為目標函數，它的含義隨著目標的變化而變化，可以為費用、距離等，一般根據該模型的實際應用來確定，Z表示總服務費用；式(2)表示選擇下一節點時的評價系數，即使得評價系數M最小；式(3)表示車輛k服務的任務之和應小于車輛的載重量，即絕對不允許超載；式(4)表示航班i只能由特定的某輛車來提供相應服務；式(5)表示對所有的點進行服務需從配送中心(車場)派出m輛車；式(6)表示該任務點必定只有某輛車來提供相應服務，且也必有該輛車從另一點來提供服務；式(7)表示任務點必定由某1車輛來提供服務且必須去向另一點；式(8)表示從停機坪i到停機坪j所需的時間；式(9)表示變量的取值約束。

2 最鄰近算法原理及算法設計

2.1 算法的基本原理

最鄰近法最早由Rosenkrantz和Stearns等于1977年提出，與Dijkstra算法和Floyd算法一并用于求解物資配送最短路徑問題[11-12]。該算法基本原理描述如下：從配送中心(或車場、原點)出發尋找與其評價值最小的且為未訪問的節點作為第一個節點，同時將其設置為已訪問。然后以該節點為起點進行搜索，找出與之相鄰的、評價值最小的、未訪問的節點，檢查是否滿足約束條件，即加上該節點該環路上的貨物量之和不會超出車輛的最大載重量。該點符合時間窗約束(詳細判斷條件如下)，則將點加入到線路中并將該節點設為已訪問，否則結束該條線路。以剛加入的點作為搜索的起點繼續遍歷，直到找不到未訪問的、相鄰的節點為止，此時結束該條路線，回到配送中心(車場)。重復以上步驟，直到所有節點全被訪問，則算法結束。

時間窗約束判斷條件為：

Sj=Si+Ti+Tij

顯然：

當車輛延遲到達服務點j時，說明航班會延誤，此時將點j從當前路徑中刪除，剩余節點構成一條服務路徑，并再次從初始點出發尋找下一條路徑。

2.2 算法的實現步驟

具體步驟如下：

第一步：擬定配送中心(車場或原點)，計算任意節點到該中心的距離，生成距離矩陣。

第二步：從該距離矩陣中取出離配送中心最近的未訪問節點vk，將該節點設為已訪問，形成一個往返式的子回路。

第三步：以該節點為中心進行搜索，找出與之相鄰的、未訪問的節點，檢查是否滿足以下條件：

(1)該節點未訪問。

(2)計算子回路和vk的總貨運量Q，若Q≤qi，則繼續第四步，否則轉到第一步，尋找新的一條回路。

(3)sk∈[ak,bk]，即到達新任務點的時間在時間窗內，則繼續第四步，否則轉到第一步，尋找新的一條回路。

第四步：將節點vk插入到子回路中，即將兩條新弧(i,k),(k,j)代替原來的(i,j)，同時將該節點設為已訪問，并重新計算車輛到達各項任務的時間。

第五步：跳轉到第二步，檢查所有節點直到所有節點都加入到某一子回路中。

3 算例分析

文中采用國內某機場的航班數據做算例，實現對機場加油車的調度，驗證該算法的有效性。

3.1 數據采集

該機場擁有客機停機位63個，每天進離港航班大約300架次。規定飛機加油車行駛速度為20 km/h，加油車最大行駛路程為50 km[13]。由于加油車一定會對離港航班進行加油服務，文中只選取該機場2014年8月31日00:00:00到2014年9月1日00:00:00之間的實際數據，該天共有航班147個，實驗要解決機場加油車輛調度問題。

3.1.1 機型大小

由于不同類型飛機所需加油量和加油服務時間不同，所以必須對飛機進行分類，大概分為三類：小型飛機、中型飛機、大型飛機。不同類型飛機的加油需求量和服務時間見表1。

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

3.1.2 停機位距離

與普通物流車輛調度相比，機場加油車調度具有特殊性，主要表現在車輛行駛路徑上。在機場，地勤車輛必須按照規定路徑行駛，不得進入飛機行駛區域。

該機場現有63個客機停機位，根據其鄰接關系，編號依次為：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 m。表2列出了車場(編號：D)和其中8個停機位任意兩點之間的距離(單位：m)。

表2 車場和其中8個停機位任意兩點之間的距離

3.1.3 離港航班時間窗

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

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

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

參數定義：ai為時間窗下限；bi為時間窗上限；td為計劃離港時間；Ti為加油車服務時間。

離港航班時間窗：

ai=bi-15

bi=td-Ti-35

部分離港航班時間窗見表3。實際處理時間參數時，均將24進制轉化為10進制，單位為min。

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

3.2 結果分析

通過Java編程實現文中算法，并將其應用于該機場加油車調度問題，得出了147個離港航班接受加油車服務的開始時間、結束時間及每輛加油車的路徑安排方案。

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

文中算法采用硬時間窗約束，對提前或延遲到達服務機位的加油車采用比重系數加入到對最短路徑選擇中，最后得出調度結果中開始服務時間均在時間窗內，加油車不會造成航班延誤。以航班為對象，表4列出部分航班接受加油服務的時間段(單位：時刻)。

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

3.2.2 加油車任務分配結果

以加油車為對象，為每一輛車分配加油任務。先不考慮任務均衡性，即分配任務時不對每輛加油車加任務量λ約束。由于路徑調度分配受評價系數的影響，經過測試不同系數的比重，得出了最優的系數分配方案。表5列出了不考慮任務均衡性時加油車的路徑調度方案。

表5 不考慮任務均衡性時加油車的路徑調度方案

從表中可以看出，最優的排班結果中，車輛行駛總距離為60 960m，加油車等待航班的總時間為1 000min左右，沒有延誤時間，而傳統單車單航班服務方式，則需要147個車次，總的行駛距離達到8萬多米。

通過以上加油任務分配并結合各自路徑的服務時間可得出，完成所有航班加油任務僅需7輛加油車，極大節省了加油車資源。

4 結束語

文中將機場加油車調度問題建立數學模型，利用最鄰近算法結合時間窗約束算出使總路程最短的路徑集合，將所有航班任務合理分配給加油車。采用硬時間窗約束，只允許等待，不允許延誤，使每個航班盡可能在規定時間內得到加油服務。最終，文中方案能成功應用在機場加油車調度問題上。

對于實際問題，該方案也有其局限性。例如，如果航班受天氣、其他地勤服務等因素影響做出動態調整，加油車調度方案也應及時做出調整。而文中給出的只是一個靜態調度方案，后期需對動態調度做進一步研究[14]。

[1] 黃建偉.民航地勤服務[M].北京:旅游教育出版社，2007.

[2] 樊琳琳.大型機場地勤服務中的車輛調度問題的初步研究[D].沈陽:東北大學，2009.

[3]DantzigG,RamserJ.Thetruckdispatchingproblem[J].ManagementScience,1959,6:80-91.

[4] 郎茂祥．物流配送車輛調度問題的模型和算法研究[D].北京:北京交通大學,2002.

[5] 方金城,張岐山.物流配送車輛路徑問題(VRP)算法綜述[J].沈陽工程學院學報：自然科學版,2006,2(4):357-360.

[6] 龔 濤,劉 山,何永明.民航過站飛機的地面作業調度算法研究[J].中國民航學院學報,2002,20:15-16.

[7] 楊燕霞,伍岳慶,姚 宇,等.帶時間窗車輛調度問題的啟發式算法研究與應用[J].計算機應用,2013,33(A01):59-61.

[8]DesrochersM,DesrosiersJ,SolomonM.Anewoptimizationalgorithmforthevehicleroutingproblemwithtimewindows[J].OperationsResearch,1992,40(2):342-354.

[9]KallehaugeB,LarsenJ,MadsenOBG,etal.Vehicleroutingproblemwithtimewindows[M].US:Springer,2005.

[10] 李 軍，郭耀煌.物流配送車輛優化調度理論與方法[M].北京:中國物資出版社，2003．

[11] 李坤穎,楊 揚,侯凌霞.應急物流配送優化的改進最鄰近算法研究[J].交通信息與安全,2011,29(3):40-42.

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

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

[14]GhannadpourSF,NooriS,Tavakkoli-MoghaddamR,etal.Amulti-objectivedynamicvehicleroutingproblemwithfuzzytimewindowsmodel,solutionandapplication[J].AppliedSoftComputing,2014,14(1):504-527.

Research on Application of Airport Special Vehicles Scheduling Based on Nearest Neighbors Algorithm

YIN Long，HENG Hong-jun

(College of Computer Science and Technology,Civil Aviation University of China,Tianjin 300300,China)

During the flight over the airport station,it will be in need of a series of ground support service such as cleaning,catering,water adding,refueling,cargo loading and unloading,which is finished with up some kind of different types of vehicles such as cleaning cars,catering trucks,fuel trucks,luaggage cars,etc.Optimal scheduling is of great importance in improving the punctuality rate and resources utilization for flight.At present,most of scheduling of the airport in China to the special vehicle is manual,single vehicle with single flight service.This inefficient approach makes the low usage of the vehicle,thus it becomes one of the important factor of the delaying for a flight.In order to ensure the punctuality of the flight,airport special vehicles must finish the ground support service efficiently.Putting refueling service as the object,first of all,a mathematical model with time window constraints according to the business of the airport refueling service is built in this paper.After that,the research of using the nearest neighbor algorithm on the solution of the model is given,and taking the actual flight data of a domestic airport as an example,the model is verified the effectiveness on the issue.At last,the optimum fuel filler task allocation result is obtained.Experimental results show that the algorithm can greatly reduce the service cost for special scheduling vehicles.

2015-11-03

2016-03-03

時間：2016-06-22

國家自然科學基金資助項目(U1333109);國家級大學生創新創業訓練項目(201510059014)

殷 龍(1991-)，男，研究方向為計算機軟件開發、構造啟發式算法;衡紅軍，博士，副教授，研究方向為智能信息處理、機器學習、民航信息系統。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0844.044.html

TP249

A

1673-629X(2016)07-0151-05

10.3969/j.issn.1673-629X.2016.07.032