殷 龍，衡紅軍

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

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

殷 龍，衡紅軍

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

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

車輛路徑問(wèn)題；最鄰近算法；時(shí)間窗；車輛調(diào)度；機(jī)場(chǎng)特種車輛

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]。其中人為可控的對(duì)民航服務(wù)質(zhì)量影響最大的一項(xiàng)為航班的正點(diǎn)率。隨著日益增長(zhǎng)的航空運(yùn)輸需求，航班延誤現(xiàn)象變得越來(lái)越普遍，導(dǎo)致航班正點(diǎn)率降低。而機(jī)場(chǎng)調(diào)度是機(jī)場(chǎng)管理的核心組成部分，因此，優(yōu)化地面服務(wù)車輛調(diào)度對(duì)于提高航空運(yùn)輸服務(wù)質(zhì)量和保障航班正點(diǎn)率極為重要。

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

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

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

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

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

問(wèn)題條件假設(shè)：

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

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

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

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

變量定義：

1.2 模型構(gòu)建

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

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

(1)

評(píng)價(jià)函數(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)用來(lái)確定，Z表示總服務(wù)費(fèi)用；式(2)表示選擇下一節(jié)點(diǎn)時(shí)的評(píng)價(jià)系數(shù)，即使得評(píng)價(jià)系數(shù)M最小；式(3)表示車輛k服務(wù)的任務(wù)之和應(yīng)小于車輛的載重量，即絕對(duì)不允許超載；式(4)表示航班i只能由特定的某輛車來(lái)提供相應(yīng)服務(wù)；式(5)表示對(duì)所有的點(diǎn)進(jìn)行服務(wù)需從配送中心(車場(chǎng))派出m輛車；式(6)表示該任務(wù)點(diǎn)必定只有某輛車來(lái)提供相應(yīng)服務(wù)，且也必有該輛車從另一點(diǎn)來(lái)提供服務(wù)；式(7)表示任務(wù)點(diǎn)必定由某1車輛來(lái)提供服務(wù)且必須去向另一點(diǎn)；式(8)表示從停機(jī)坪i到停機(jī)坪j所需的時(shí)間；式(9)表示變量的取值約束。

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

2.1 算法的基本原理

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

時(shí)間窗約束判斷條件為：

Sj=Si+Ti+Tij

顯然：

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

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

具體步驟如下：

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

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

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

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

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

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

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

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

3 算例分析

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

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

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

3.1.1 機(jī)型大小

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

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

3.1.2 停機(jī)位距離

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

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

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

3.1.3 離港航班時(shí)間窗

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

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

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

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

離港航班時(shí)間窗：

ai=bi-15

bi=td-Ti-35

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

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

3.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

[7] 楊燕霞,伍岳慶,姚 宇,等.帶時(shí)間窗車輛調(diào)度問(wèn)題的啟發(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].北京:中國(guó)物資出版社，2003．

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

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

[13] 中國(guó)民用航空局.民航發(fā)[2013]83號(hào),航空公司航班正常運(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

時(shí)間：2016-06-22

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

殷 龍(1991-)，男，研究方向?yàn)橛?jì)算機(jī)軟件開(kāi)發(fā)、構(gòu)造啟發(fā)式算法;衡紅軍，博士，副教授，研究方向?yàn)橹悄苄畔⑻幚?、機(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