殷 龍，衡紅軍

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

基于最鄰近算法的機(jī)場特種車輛調(diào)度應(yīng)用研究

殷 龍，衡紅軍

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

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

車輛路徑問題；最鄰近算法；時間窗；車輛調(diào)度；機(jī)場特種車輛

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

0 引 言

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

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

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

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

1.1 問題描述及條件假設(shè)

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

問題條件假設(shè)：

(1)調(diào)度問題是靜態(tài)的，即所有任務(wù)事先給定；

(2)所有運(yùn)輸車輛在任何時刻一輛車上至多只能服務(wù)一個航班，該任務(wù)從車場(原點(diǎn))作為起點(diǎn)直至相應(yīng)到達(dá)停機(jī)坪；

(3)任務(wù)的時間窗應(yīng)該被嚴(yán)格執(zhí)行,即為硬時間窗；

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

變量定義：

1.2 模型構(gòu)建

帶有時間窗約束的特種車輛機(jī)場調(diào)度模型如下：

目標(biāo)函數(shù)為：

(1)

評價函數(shù)為：

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

2 最鄰近算法原理及算法設(shè)計(jì)

2.1 算法的基本原理

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

時間窗約束判斷條件為：

Sj=Si+Ti+Tij

顯然：

當(dāng)車輛延遲到達(dá)服務(wù)點(diǎn)j時，說明航班會延誤，此時將點(diǎn)j從當(dāng)前路徑中刪除，剩余節(jié)點(diǎn)構(gòu)成一條服務(wù)路徑，并再次從初始點(diǎn)出發(fā)尋找下一條路徑。

2.2 算法的實(shí)現(xiàn)步驟

具體步驟如下：

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

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

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

(1)該節(jié)點(diǎn)未訪問。

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

(3)sk∈[ak,bk]，即到達(dá)新任務(wù)點(diǎn)的時間在時間窗內(nèi)，則繼續(xù)第四步，否則轉(zhuǎn)到第一步，尋找新的一條回路。

第四步：將節(jié)點(diǎn)vk插入到子回路中，即將兩條新弧(i,k),(k,j)代替原來的(i,j)，同時將該節(jié)點(diǎn)設(shè)為已訪問，并重新計(jì)算車輛到達(dá)各項(xiàng)任務(wù)的時間。

第五步：跳轉(zhuǎn)到第二步，檢查所有節(jié)點(diǎn)直到所有節(jié)點(diǎn)都加入到某一子回路中。

3 算例分析

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

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

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

3.1.1 機(jī)型大小

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

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

3.1.2 停機(jī)位距離

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

該機(jī)場現(xiàn)有63個客機(jī)停機(jī)位，根據(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，其中加油車車場位于停機(jī)位109和停機(jī)位501之間，其鄰接關(guān)系由其位置決定，相鄰?fù)C(jī)位之間距離大約40 m。表2列出了車場(編號：D)和其中8個停機(jī)位任意兩點(diǎn)之間的距離(單位：m)。

表2 車場和其中8個停機(jī)位任意兩點(diǎn)之間的距離

3.1.3 離港航班時間窗

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

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

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

參數(shù)定義：ai為時間窗下限；bi為時間窗上限；td為計(jì)劃離港時間；Ti為加油車服務(wù)時間。

離港航班時間窗：

ai=bi-15

bi=td-Ti-35

部分離港航班時間窗見表3。實(shí)際處理時間參數(shù)時，均將24進(jìn)制轉(zhuǎn)化為10進(jìn)制，單位為min。

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

3.2 結(jié)果分析

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

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

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

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

3.2.2 加油車任務(wù)分配結(jié)果

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

表5 不考慮任務(wù)均衡性時加油車的路徑調(diào)度方案

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

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

4 結(jié)束語

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

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

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

[2] 樊琳琳.大型機(jī)場地勤服務(wù)中的車輛調(diào)度問題的初步研究[D].沈陽:東北大學(xué)，2009.

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

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

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

[6] 龔 濤,劉 山,何永明.民航過站飛機(jī)的地面作業(yè)調(diào)度算法研究[J].中國民航學(xué)院學(xué)報(bào),2002,20:15-16.

[7] 楊燕霞,伍岳慶,姚 宇,等.帶時間窗車輛調(diào)度問題的啟發(fā)式算法研究與應(yīng)用[J].計(jì)算機(jī)應(yīng)用,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] 李 軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京:中國物資出版社，2003．

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

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

[13] 中國民用航空局.民航發(fā)[2013]83號,航空公司航班正常運(yùn)行標(biāo)準(zhǔn)(試行)[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

國家自然科學(xué)基金資助項(xiàng)目(U1333109);國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項(xiàng)目(201510059014)

殷 龍(1991-)，男，研究方向?yàn)橛?jì)算機(jī)軟件開發(fā)、構(gòu)造啟發(fā)式算法;衡紅軍，博士，副教授，研究方向?yàn)橹悄苄畔⑻幚怼C(jī)器學(xué)習(xí)、民航信息系統(tǒng)。

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