機(jī)場(chǎng)地勤保障車輛調(diào)度問題研究

李 琳，孟 嬌，袁多嘉，劉樹秋，柴 慧，宋薇薇

(1.沈陽航空航天大學(xué) 理學(xué)院，沈陽，110136；2.沈陽航空航天大學(xué) 民用航空學(xué)院，沈陽，110136；3.南方航空公司 北方分公司，沈陽，110169；4.北京新機(jī)場(chǎng)管理中心 商業(yè)管理部，北京，102602)

隨著我國民航事業(yè)的蓬勃發(fā)展，民用機(jī)場(chǎng)的進(jìn)港、過站及出港航班的數(shù)目逐年增多。較高的航班調(diào)度需求與有限的航空資源及運(yùn)營管理水平不足等之間的矛盾日益突出，并直接影響到航空運(yùn)輸?shù)陌踩?Safety)、準(zhǔn)時(shí)性(Punctuality)及盈利性(Profitability)[1]。航班的準(zhǔn)點(diǎn)率成為目前最受公眾關(guān)注的航空運(yùn)輸評(píng)估指標(biāo)之一[2-3]。

航空資源的有限性和運(yùn)營管理水平的不足不僅會(huì)導(dǎo)致本次航班延誤，而且會(huì)使延誤沿著相關(guān)的資源傳遞下去，從而導(dǎo)致其他航班隨之延誤。根據(jù)民航相關(guān)部門統(tǒng)計(jì)，影響航班準(zhǔn)點(diǎn)率的因素很多，主要有航空器狀況、安全措施及有效的空域情況(包括天氣和空域管制等因素)、機(jī)組、機(jī)場(chǎng)設(shè)施及地面服務(wù)、航班線路及時(shí)刻表規(guī)劃、空管、旅客及行李情況等[1]。為減少航班延誤，一方面需要增加相關(guān)航空資源，如近年來不斷增加的航空器數(shù)量和不斷增建和擴(kuò)建的機(jī)場(chǎng)、跑道、停機(jī)坪、航站樓等；另一方面，可通過提高運(yùn)營管理水平來提高航空資源的利用效率。同時(shí)，機(jī)場(chǎng)的地勤保障車輛調(diào)度失誤是航班延誤的重要原因之一[4]。機(jī)場(chǎng)地面保障車輛調(diào)度的效率是眾多機(jī)場(chǎng)地面保障服務(wù)效率的前提和重要組成部分。目前，我國大部分機(jī)場(chǎng)的地勤保障車輛依靠人工進(jìn)行調(diào)度，工作人員根據(jù)服務(wù)需求和車輛的服務(wù)狀態(tài)，通過目視、登記、語音對(duì)講等方式對(duì)符合條件的車輛進(jìn)行調(diào)度。在航班高峰時(shí)段，落后的信息獲取方式及決策過程導(dǎo)致調(diào)度人員調(diào)度效率低下，甚至產(chǎn)生決策失誤，使服務(wù)完成時(shí)間延后，影響航班的準(zhǔn)點(diǎn)率[4-6]。事實(shí)證明，高效的機(jī)場(chǎng)地面服務(wù)能夠吸收和緩解航班延誤，提高準(zhǔn)點(diǎn)率；而低效的機(jī)場(chǎng)地面服務(wù)卻能產(chǎn)生或加重航班延誤。因此，研究地勤保障車輛調(diào)度問題，提高地勤保障車輛調(diào)度效率對(duì)于提升航班準(zhǔn)點(diǎn)率、節(jié)約航運(yùn)成本、減少碳排放量、提高旅客的滿意度、提升航空產(chǎn)業(yè)的盈利能力等具有十分重要的意義。

1 機(jī)場(chǎng)地勤保障服務(wù)及流程

機(jī)場(chǎng)地勤保障服務(wù)是指航班在機(jī)場(chǎng)過站期間為保障后續(xù)的飛行任務(wù)能夠正常進(jìn)行而提供的加油、加水、配餐、清潔、裝卸行李、貨郵等一系列地面服務(wù)，可由不同類型的地勤保障車輛來提供。地勤保障服務(wù)的必需環(huán)節(jié)還包括引導(dǎo)入位、上輪檔、撤輪檔和放行推出，保障服務(wù)作業(yè)的對(duì)象分別是飛機(jī)、旅客、行李、貨郵[7]。以波音777飛機(jī)為例，其地勤保障車輛服務(wù)示意圖[8-9]如圖1所示。

圖1 波音777飛機(jī)地勤保障車輛服務(wù)示意圖

機(jī)場(chǎng)地勤保障服務(wù)具有服務(wù)內(nèi)容多、涉及的服務(wù)車輛種類多、參與人員數(shù)目龐大的特點(diǎn)。具體的服務(wù)對(duì)象、服務(wù)內(nèi)容及相關(guān)的人員、車輛類型及設(shè)備[7]等情況見表1。

表1 地勤保障服務(wù)對(duì)象、內(nèi)容、所需人員車輛設(shè)備表

航班地面保障作業(yè)要經(jīng)歷一個(gè)復(fù)雜的過程，其基本服務(wù)包括著陸、登機(jī)、裝卸行李、加油、餐飲、清潔、加水和清潔過程，需要各服務(wù)部門協(xié)調(diào)合作來完成。各作業(yè)間要遵循一定的先后順序來進(jìn)行服務(wù)，其主要地面保障服務(wù)流程[10-14]如圖2所示。

圖2 航班入港、出港主要地面保障服務(wù)流程圖

2 地勤保障車輛調(diào)度問題研究現(xiàn)狀

按照民用機(jī)場(chǎng)特種車輛、專用設(shè)備配備(MH/T5002-1996)標(biāo)準(zhǔn)規(guī)定，在民用機(jī)場(chǎng)所劃定區(qū)域內(nèi)，機(jī)場(chǎng)場(chǎng)道、機(jī)坪、航站樓、航空器和運(yùn)輸服務(wù)、應(yīng)急救援應(yīng)配備相應(yīng)品類與數(shù)量的特種車輛和專用設(shè)備。特種車輛也叫勤務(wù)車輛，根據(jù)其服務(wù)對(duì)象不同，大致可以分為四類：(1)服務(wù)旅客的車輛，如：擺渡車、客梯車、殘障旅客升降車、行李傳送車；(2)飛機(jī)保障車輛，如飛機(jī)牽引車、行李牽引車、清水車、食品車、加油車、地面電源車、空調(diào)車、垃圾車、飛機(jī)專用除冰車、驅(qū)鳥車；(3) 場(chǎng)道保障車輛，如掃雪車、壓路車、掃道車、除膠車、叉車、摩擦系數(shù)測(cè)試車；(4)應(yīng)急救援車輛，如應(yīng)急指揮車、消防救援車、醫(yī)療急救車等[15]。每類車輛都有自己的服務(wù)特點(diǎn)和規(guī)定的行駛路線。國內(nèi)外學(xué)者對(duì)地勤保障車輛調(diào)度問題的研究多集中在為旅客和飛機(jī)服務(wù)的特種車輛優(yōu)化調(diào)度方面。目前，國內(nèi)在相關(guān)方面的研究并不多，還處于起步階段。

地勤保障車輛的品類及數(shù)目較多，各種車輛的用途及使用頻率也不同，根據(jù)國內(nèi)外相關(guān)的研究成果可將地勤保障車輛調(diào)度問題分為單種車輛調(diào)度問題(如擺渡車、行李車、食品車等單一車型的調(diào)度問題)、多種車輛協(xié)同調(diào)度問題(如行李車與擺渡車協(xié)同調(diào)度、加油車與擺渡車協(xié)同調(diào)度等問題)及特種車輛統(tǒng)一調(diào)度問題(根據(jù)保障車輛的運(yùn)行及服務(wù)特點(diǎn)提煉出必要的約束條件，建立保障車輛的統(tǒng)一調(diào)度模型)。

2.1 單種車輛調(diào)度問題

2.1.1 擺渡車調(diào)度問題

機(jī)場(chǎng)飛機(jī)數(shù)量逐年增多，但是機(jī)位相對(duì)較少，許多飛機(jī)停留在遠(yuǎn)機(jī)位，需要通過機(jī)場(chǎng)擺渡車在候機(jī)廳與遠(yuǎn)機(jī)位飛機(jī)之間接送乘客。擺渡車還可用于航站樓與停車場(chǎng)之間、機(jī)場(chǎng)出發(fā)層與附近車站之間運(yùn)送乘客。

楊文東[16]等人考慮了旅客、擺渡車、遠(yuǎn)機(jī)位、航站樓遠(yuǎn)機(jī)位登機(jī)門、機(jī)坪出口和車輛行駛道路情況等因素，以擺渡車為對(duì)象建立了仿真模型，提出機(jī)坪擺渡車調(diào)度仿真的多目標(biāo)優(yōu)化方法。目標(biāo)函數(shù)是最小化擺渡車的總負(fù)荷差、最小化車輛行駛距離、在保證服務(wù)準(zhǔn)點(diǎn)率的同時(shí)減少擺渡車的使用數(shù)目，達(dá)到提高設(shè)備利用率、降低設(shè)備成本的目的。為均衡不同車輛間服務(wù)航班數(shù)的差別，當(dāng)存在多個(gè)備選車輛時(shí)，選取服務(wù)航班數(shù)最少的車輛進(jìn)行服務(wù)。為減少車輛行駛距離，利用貪婪算法在到達(dá)航班或出發(fā)航班發(fā)出擺渡車服務(wù)需求時(shí)，比較空閑擺渡車與航班預(yù)定的停機(jī)位之間的距離，選取距離最近的擺渡車進(jìn)行服務(wù)。為減少擺渡車使用次數(shù)，在保證航班服務(wù)質(zhì)量的情況下，通過綜合比較和分析，確定目標(biāo)機(jī)場(chǎng)最優(yōu)的擺渡車數(shù)量，設(shè)計(jì)了對(duì)接擺渡車仿真優(yōu)化路線的實(shí)時(shí)調(diào)度系統(tǒng)，實(shí)現(xiàn)了信息的無線傳輸、IC卡控制與人機(jī)交互，建立的仿真模型可以實(shí)現(xiàn)目標(biāo)函數(shù)之間的單一優(yōu)化與組合目標(biāo)優(yōu)化。

2.1.2 行李車調(diào)度問題

行李裝卸服務(wù)是指將旅客的托運(yùn)行李裝上飛機(jī)或從飛機(jī)上卸載下來的一種機(jī)場(chǎng)地面保障服務(wù)。行李車不同于加油車、客梯車等，不受其他車輛的影響，在完成出港航班的旅客托運(yùn)行李運(yùn)輸裝載后，空載回到行李分揀區(qū);服務(wù)于進(jìn)港航班的運(yùn)輸車，需要先空載行駛至航班所在的停機(jī)位，再將卸載的行李運(yùn)輸至行李分揀區(qū)。這種單車服務(wù)單航班的方式，車輛使用成本高、利用率低，在車輛資源緊張的情況下易造成服務(wù)不及時(shí)而導(dǎo)致航班延誤[17]。

王璐[17]等人討論了行李車的單目標(biāo)優(yōu)化調(diào)度問題。假設(shè)行李車到每個(gè)航班的距離和航班到行李轉(zhuǎn)盤處的距離是固定的，一個(gè)行李車一次只能服務(wù)一個(gè)航班，行李車只有處理完當(dāng)前航班的行李后，才能前往下一個(gè)航班進(jìn)行行李服務(wù)。建立目標(biāo)函數(shù)，最小化所有航班等待行李服務(wù)的時(shí)間，從而減少航班延誤，提高顧客滿意度，并建立了整數(shù)規(guī)劃模型，用CPLEX對(duì)中小規(guī)模問題進(jìn)行精確求解。仿真結(jié)果表明所建的模型能夠有效地解決行李車的服務(wù)調(diào)度問題，為機(jī)場(chǎng)管理提供決策支持。

衡紅軍[18]等人研究了行李車的多目標(biāo)優(yōu)化調(diào)度問題。目標(biāo)函數(shù)是使行李車的總行駛路程最短、所用車輛數(shù)目最少、每輛車之間的任務(wù)量差異最小(以服務(wù)航班數(shù)量總和來衡量每輛行李運(yùn)輸車任務(wù)量的均衡性)。為行李車分配任務(wù)時(shí)，為保障服務(wù)作業(yè)的均衡性，采用子路徑任務(wù)開始時(shí)間越早的車輛優(yōu)先被分配任務(wù)。為每輛車的任務(wù)量設(shè)定一個(gè)閾值，保證為車輛分配的任務(wù)量不超過該閾值。采用最近鄰算法構(gòu)建車輛行駛總距離最短的子路徑集合，將一個(gè)出港航班與一個(gè)到港航班進(jìn)行組合，使用同一車輛進(jìn)行服務(wù)。根據(jù)子路徑間的時(shí)間約束，對(duì)子路徑進(jìn)行整合優(yōu)化，再將子路徑任務(wù)分配給行李運(yùn)輸車，實(shí)現(xiàn)所需車輛數(shù)最少和車輛任務(wù)量均衡的目標(biāo)。

2.1.3 食品車調(diào)度問題

航食配餐作業(yè)與其他作業(yè)流程銜接緊密，作業(yè)時(shí)間受到嚴(yán)格限制，在服務(wù)作業(yè)中需要不停往返于場(chǎng)內(nèi)和場(chǎng)外。與配餐有關(guān)聯(lián)的作業(yè)包括旅客下機(jī)(下機(jī)之后才能開始)、旅客登機(jī)(登機(jī)之前必須完成)和客艙清潔(回收毛毯、衛(wèi)生用品等)。食品車的調(diào)度要遵循相關(guān)行業(yè)規(guī)范，有相對(duì)確定的服務(wù)時(shí)間限制和操作順序。為保證配餐質(zhì)量及飛機(jī)安全，食品車的行駛路徑及速度固定，即食品車在機(jī)坪的作業(yè)時(shí)間很難縮減，食品車的服務(wù)需求時(shí)間離散分布，最終的登機(jī)人數(shù)不易確定，導(dǎo)致所需食品車數(shù)量的不確定性，且有可能因在入口艙門處排隊(duì)等待時(shí)間過長(zhǎng)，導(dǎo)致食品車不能及時(shí)到位，造成航班延誤[19]。

王琪[19]等人假設(shè)食品車在機(jī)坪上的作業(yè)時(shí)間固定，以航班等待時(shí)間和食品車行駛時(shí)間之和最小為目標(biāo)函數(shù)，建立帶有時(shí)間窗的食品車指派模型，采用列生成法和分枝定界法求解。列生成法適用于變量數(shù)遠(yuǎn)大于約束條件數(shù)的問題，基變量數(shù)相對(duì)于非基變量是較小的一部分。如果事先能確認(rèn)可行的基變量，就可以令其他變量等于零，使問題的規(guī)模大大減小。根據(jù)所研究問題的特點(diǎn)，先用分枝定界法得到可行的基變量，再用列生成算法進(jìn)行迭代，最終獲得最優(yōu)解。仿真結(jié)果表明，該方法能夠降低航班延誤率并縮短食品車行駛時(shí)間，達(dá)到降低航空公司成本的目的。

2.1.4 加油車調(diào)度問題

飛機(jī)的加油作業(yè)是由加油車完成的。加油車分兩種，即管線加油車和油罐車。管線加油車用于對(duì)近機(jī)位飛機(jī)進(jìn)行加油；油罐車又稱流動(dòng)加油車，用于對(duì)遠(yuǎn)機(jī)位的飛機(jī)進(jìn)行加油。近機(jī)位是指靠近航站樓的停機(jī)位，遠(yuǎn)機(jī)位是指遠(yuǎn)離航站樓的停機(jī)位。進(jìn)機(jī)位地底鋪有輸油管道，飛機(jī)加油時(shí)只需要管線加油車將管道中的油抽出輸送到飛機(jī)油箱中即可。遠(yuǎn)機(jī)位地下沒有輸油管道，需要油罐車為該位置飛機(jī)提供加油服務(wù)[20]。

殷龍[21]等人根據(jù)機(jī)場(chǎng)燃油加注服務(wù)的類型構(gòu)建了帶時(shí)間窗約束的特種車輛調(diào)度的數(shù)學(xué)模型，目標(biāo)函數(shù)是最小化費(fèi)用或車輛行駛距離等。采用硬時(shí)間窗約束，對(duì)提前或延遲到達(dá)服務(wù)機(jī)位的加油車采用將比重系數(shù)因素加入到對(duì)最短路徑的選擇中，最后得出的調(diào)度方案中車輛開始服務(wù)的時(shí)間均在時(shí)間窗約束內(nèi)，加油車不會(huì)造成航班延誤。以國內(nèi)某機(jī)場(chǎng)某天的實(shí)際數(shù)據(jù)為例，利用最鄰近算法[22-23]實(shí)現(xiàn)對(duì)模型的求解，得出最優(yōu)的燃油加注任務(wù)分配方案，驗(yàn)證了算法的有效性。

衡紅軍[24]等人對(duì)管線加油車帶硬時(shí)間窗的調(diào)度問題進(jìn)行了研究，建立了多目標(biāo)優(yōu)化模型。目標(biāo)函數(shù)是車輛行駛總路程最短、所需車輛數(shù)目最少、每輛加油車之間的任務(wù)量差異最小，從而提出一種基于節(jié)約算法的解決方案。該方案分為兩個(gè)階段:第一階段，利用節(jié)約算法求出滿足行駛總路程最短的子路徑集合;第二階段，通過構(gòu)建的新方法將每個(gè)子路徑任務(wù)合理分配給所有車輛，實(shí)現(xiàn)車輛數(shù)目最少和任務(wù)量差異最小的目標(biāo)。

劉長(zhǎng)有[20]等人討論了油罐車的調(diào)度問題。加油車輛從油庫出發(fā)，為多架飛機(jī)提供加油服務(wù)。假設(shè)每架飛機(jī)只能由一輛加油車為其服務(wù)，當(dāng)油罐車所載的油量不能滿足飛機(jī)的加油需求時(shí)，加油車需要返回油庫補(bǔ)充油量。目標(biāo)函數(shù)是最小化加油車的運(yùn)行成本與加油車提前或延后到達(dá)飛機(jī)的加油時(shí)間窗時(shí)產(chǎn)生的懲罰費(fèi)用之和。學(xué)者們?yōu)榇嗽O(shè)計(jì)了蟻群算法進(jìn)行求解，在啟發(fā)因子中考慮加油車輛的行駛距離因素；在狀態(tài)轉(zhuǎn)移概率中考慮了距離節(jié)約因素和反映滿足時(shí)間窗約束的變量，通過某機(jī)場(chǎng)油罐加油車調(diào)度的實(shí)例求得實(shí)際問題的優(yōu)化調(diào)度方案。

王璐[25]等人研究了油罐車的調(diào)度問題，建立了雙目標(biāo)規(guī)劃模型。目標(biāo)函數(shù)是最小化完成所有航班加油服務(wù)作業(yè)的時(shí)間以及最小化所有航班等待加油服務(wù)的時(shí)間。假設(shè)加油車勻速行駛，加油車加油時(shí)間不計(jì)，停機(jī)位之間的距離小于停機(jī)位到加油站的距離，使用Epsilon約束算法對(duì)所建立的雙目標(biāo)優(yōu)化模型進(jìn)行求解，得到Pareto最優(yōu)解。Epsilon約束法的思想是通過轉(zhuǎn)化一個(gè)目標(biāo)為約束條件，構(gòu)建并求解一系列Epsilon約束問題，這一系列Epsilon約束問題間是通過逐步減少的Epsilon 值聯(lián)系起來的。

衡紅軍[26]等人根據(jù)航班到港、出港的預(yù)計(jì)信息，將該問題歸結(jié)為一種動(dòng)態(tài)的帶時(shí)間窗的車輛路徑問題。在規(guī)劃時(shí)間窗內(nèi)，根據(jù)實(shí)際情況，選擇合適的約束條件，將動(dòng)態(tài)問題轉(zhuǎn)化為多個(gè)靜態(tài)問題。學(xué)者們建立了多目標(biāo)優(yōu)化模型，目標(biāo)函數(shù)是最小化加油車輛的行駛總路程、最小化車輛的使用數(shù)目和最小化加油車輛之間的任務(wù)量差異，設(shè)計(jì)了一種基于規(guī)劃時(shí)間窗的車輛實(shí)時(shí)調(diào)度算法，并用實(shí)際算例驗(yàn)證了算法的有效性。

2.1.5 除冰車調(diào)度問題

寒冷天氣時(shí)飛機(jī)表面會(huì)出現(xiàn)結(jié)冰情況，在飛機(jī)起飛前需要對(duì)飛機(jī)表面進(jìn)行除冰作業(yè)。除冰作業(yè)有分散除冰方式和集中除冰方式。采用分散除冰方式對(duì)飛機(jī)進(jìn)行除冰時(shí)，除冰車輛需要到飛機(jī)停放的地方對(duì)飛機(jī)進(jìn)行除冰作業(yè)。該除冰方式缺點(diǎn)包括：出現(xiàn)除冰不徹底的情況；加除冰液不及時(shí)(距離加液點(diǎn)遠(yuǎn))，影響除冰效率；除冰液沒有集中回收處理，導(dǎo)致停機(jī)坪使用壽命縮短以及影響周邊環(huán)境等[27]。目前國內(nèi)外多數(shù)大型機(jī)場(chǎng)已開始采用集中除冰方式對(duì)飛機(jī)進(jìn)行除冰。集中除冰方式是飛機(jī)集中在除冰坪上，多種、多輛除冰車對(duì)多個(gè)飛機(jī)同時(shí)進(jìn)行除冰作業(yè)。一個(gè)飛機(jī)可能需要多個(gè)除冰車輛同時(shí)進(jìn)行除冰作業(yè)，一個(gè)除冰車也可在一個(gè)加液周期內(nèi)對(duì)多架飛機(jī)進(jìn)行除冰作業(yè)。

石旭東[27]等人研究了飛機(jī)集中除冰作業(yè)過程中除冰車輛調(diào)度優(yōu)化問題，考慮飛機(jī)的起飛順序、型號(hào)、每種型號(hào)飛機(jī)需要的除冰車數(shù)量、除冰液的噴灑速度等因素，建立了單目標(biāo)優(yōu)化模型。作業(yè)時(shí)間包括除冰時(shí)間和添加除冰液的時(shí)間，目標(biāo)函數(shù)是合理安排除冰車，使總作業(yè)時(shí)間最短，并利用遺傳算法進(jìn)行求解。將目標(biāo)函數(shù)轉(zhuǎn)化成適應(yīng)值函數(shù)，采用輪盤賭選擇法選擇適應(yīng)值最大(即最佳)的個(gè)體，用其代替子代中適應(yīng)值最低的個(gè)體。用交叉遺傳的方法獲得較好的子代個(gè)體進(jìn)入種群，采用隨機(jī)變異率對(duì)子代進(jìn)行變異生成新的個(gè)體。當(dāng)最佳個(gè)體無法更新次數(shù)達(dá)到預(yù)先設(shè)定的一定代數(shù)時(shí)，停止算法，得到滿意的除冰車調(diào)度方案。

李恩廣[28]建立了基于停機(jī)坪的飛機(jī)集中除冰系統(tǒng)，在同一地點(diǎn)同一時(shí)間用多輛除冰車對(duì)多架飛機(jī)進(jìn)行除冰作業(yè)，從而達(dá)到控制除冰時(shí)間、提高除冰效率的目的。因飛機(jī)的進(jìn)場(chǎng)順序不同、類型不同、各種除冰車的除冰速度不確定等因素，將除冰車輛調(diào)度問題歸結(jié)為信息不確定的優(yōu)化問題。目標(biāo)函數(shù)是在確定飛機(jī)數(shù)目的條件下使總的除冰時(shí)間最短，除冰時(shí)間是除冰車的工作時(shí)間和添加除冰液的時(shí)間之和，設(shè)計(jì)了蟻群算法求解該問題，按飛機(jī)的需求概率選擇需要除冰的飛機(jī)。飛機(jī)的需求概率中考慮了信息素、飛機(jī)所需的除冰液及飛機(jī)需要的除冰車的數(shù)量，優(yōu)化了飛機(jī)集中除冰策略中的調(diào)度問題。

Norin[29]等人研究了目標(biāo)函數(shù)為最小化航班延誤和除冰車的行駛距離的問題，討論了問題的復(fù)雜度，設(shè)計(jì)了貪婪隨機(jī)自適應(yīng)搜索算法進(jìn)行求解，該方法可以有效減少動(dòng)態(tài)仿真過程中除冰車輛的等待時(shí)間。

Xing[30]等人考慮到航班的出港時(shí)間、除冰次序和航線之間的均衡問題，基于合作博弈思想，為航班的除冰車調(diào)度問題建立了模型。根據(jù)優(yōu)先服務(wù)具有較高優(yōu)先級(jí)航班的原則分配除冰資源，利用Repast平臺(tái)開發(fā)了航班多Agent框架，實(shí)例仿真結(jié)果表明了所建模型的合理性和車輛調(diào)度方案的有效性。

陳鑫[31]等人討論了單加液中心，每架飛機(jī)只能由兩輛除冰車為其除冰，每輛除冰車都有一定的容量限制的除冰車調(diào)度問題，每架飛機(jī)有自己的接受除冰的時(shí)間窗，待除冰飛機(jī)對(duì)除冰車的到達(dá)時(shí)間要求是滿足給定的時(shí)間窗?？紤]了最小化除冰成本的單目標(biāo)優(yōu)化問題，除冰成本包括除冰車的行駛距離、在每架飛機(jī)規(guī)定的時(shí)間窗內(nèi)，除冰車提前到達(dá)的等待成本與延遲到達(dá)的延誤成本、因除冰車不能在規(guī)定的時(shí)間窗內(nèi)開始除冰而產(chǎn)生的延誤航班數(shù)量。采用改進(jìn)的蟻群算法進(jìn)行求解，在狀態(tài)轉(zhuǎn)移過程中考慮了信息素濃度、能見度、服務(wù)緊迫性(具有短服務(wù)時(shí)間窗的飛機(jī))和路程節(jié)約值因素。將所有路徑上的信息素范圍設(shè)定在某一區(qū)間內(nèi)，可以有效避免算法停滯或收斂到局部最優(yōu)。

2.1.6 拖車、加水車、清潔車、牽引車調(diào)度問題

Cheung[32]等人研究了航班保障維護(hù)服務(wù)中的拖車、加水車、清潔車的優(yōu)化調(diào)度問題。目標(biāo)函數(shù)是使各類服務(wù)車輛的利用率最大(最小化車輛的空閑時(shí)間)，達(dá)到減少運(yùn)作費(fèi)用的目的，設(shè)計(jì)了遺傳算法進(jìn)行求解，給出航班維護(hù)服務(wù)中合理有效的車輛調(diào)度方案。

Du[33]等人研究了拖車、牽引車的調(diào)度問題，建立了基于MIP(Mixed Integer Programming)的車輛調(diào)度模型，將不同類型的拖車分配給具有不同服務(wù)時(shí)間窗需求的航班。目標(biāo)函數(shù)是在滿足航班拖車服務(wù)作業(yè)約束的條件下，最小化牽引車的作業(yè)時(shí)間費(fèi)用(包括行駛時(shí)間和服務(wù)時(shí)間)和由于服務(wù)作業(yè)延誤導(dǎo)致的懲罰費(fèi)用之和。該模型適合多車輛中心和車輛多行程的問題，設(shè)計(jì)了列生成啟發(fā)式算法，計(jì)算結(jié)果表明使用列生成啟發(fā)式方法求解比用CPLEX求解MIP模型的效果更好。

2.2 多種車輛協(xié)同調(diào)度問題

Kenneth[34]等人研究了行李車與擺渡車的調(diào)度問題，提出混合整數(shù)規(guī)劃模型來最小化航班油耗成本和航班延誤費(fèi)用。目標(biāo)函數(shù)是最小化服務(wù)作業(yè)時(shí)間與車輛行駛距離的加權(quán)和。最小化服務(wù)作業(yè)時(shí)間即最小化航班延誤；當(dāng)限定服務(wù)車輛的行駛速度時(shí)，最小化車輛的行駛距離即最小化車輛的運(yùn)行時(shí)間?？紤]了同種車型的帶時(shí)間窗的動(dòng)態(tài)調(diào)度問題，根據(jù)航班到達(dá)調(diào)度情況設(shè)計(jì)了遺傳算法和貪婪算法來盡快求得靜態(tài)問題的近優(yōu)解，確定問題的上界。設(shè)計(jì)了分支定界算法，用以求得問題的精確解，根據(jù)航班的即時(shí)信息調(diào)整車輛調(diào)度方案，并用漢堡和達(dá)拉斯-沃斯堡機(jī)場(chǎng)的實(shí)例檢驗(yàn)了不同算法的運(yùn)算效果。

Salma[9]等人討論了機(jī)場(chǎng)地面保障車輛采用分散管理方式進(jìn)行調(diào)度的問題。航空公司與地面服務(wù)車隊(duì)相互協(xié)作，每個(gè)航班的服務(wù)需求是模糊需求，對(duì)于每個(gè)航班的服務(wù)指派問題設(shè)計(jì)了啟發(fā)式求解方法，提出了一個(gè)地面服務(wù)車輛管理者、航空公司和機(jī)場(chǎng)調(diào)度人員之間協(xié)同調(diào)度的方案。

茍晶晶[35]以地勤保障車輛中的擺渡車、客梯車、清水車、污水車、垃圾車和拖車為例，綜合考慮多種車輛相互協(xié)作服務(wù)的特點(diǎn)，建立了帶硬時(shí)間窗的單目標(biāo)車輛調(diào)度優(yōu)化模型。目標(biāo)函數(shù)是最小化可以滿足服務(wù)需求的地勤保障車輛的數(shù)目之和，先通過已知航班信息采用貪婪算法產(chǎn)生一個(gè)使用車輛數(shù)最少的初始解和航班服務(wù)序列，再用禁忌搜索算法對(duì)初始解進(jìn)行改進(jìn)。該方法解決了機(jī)場(chǎng)車輛資源投資浪費(fèi)問題，可以求得工作負(fù)荷相對(duì)均衡的最低地勤保障車輛配置方案。

馮霞[36]等人分析機(jī)場(chǎng)過站航班保障的業(yè)務(wù)流程，確定加油服務(wù)與上客服務(wù)之間的時(shí)間約束關(guān)系，研究了遠(yuǎn)機(jī)位航班加油服務(wù)和上客服務(wù)的協(xié)同調(diào)度模型。假設(shè)每個(gè)航班接受加油服務(wù)和上客服務(wù)各一次，并且只需要一輛加油車和一輛擺渡車對(duì)其進(jìn)行服務(wù)；加油車和擺渡車的總服務(wù)時(shí)間沒有限制；服務(wù)作業(yè)一旦開始，就不許被中斷，直到相應(yīng)的服務(wù)作業(yè)全部完成。研究了多目標(biāo)優(yōu)化問題，即最小化所需的加油車和擺渡車數(shù)目總和、最小化航班服務(wù)總開始時(shí)間。設(shè)計(jì)了多目標(biāo)遺傳算法求得問題的Pareto最優(yōu)解，為業(yè)務(wù)部門提供協(xié)同決策參考，實(shí)現(xiàn)了加油車和擺渡車的協(xié)同調(diào)度。

衡紅軍[14]等人研究了加油車和行李車的服務(wù)模式，討論了相關(guān)車輛的實(shí)時(shí)調(diào)度問題。為使機(jī)場(chǎng)各部門之間能夠及時(shí)了解航班服務(wù)狀態(tài)，增強(qiáng)各部門的交互及時(shí)性，設(shè)計(jì)了基于MAS(Multi-agent system)[37-38]的機(jī)場(chǎng)特種車輛實(shí)時(shí)調(diào)度模型及求解算法。該算法在設(shè)定的時(shí)刻接收航班預(yù)計(jì)到港、離港消息，生成規(guī)劃時(shí)間窗內(nèi)待排航班集合，依次對(duì)待排航班集合中的每個(gè)航班規(guī)劃車輛的服務(wù)路徑。目標(biāo)函數(shù)是確定合理的車輛調(diào)度方案，使得服務(wù)車輛的總行駛路程最短、所用的車輛數(shù)最少、每輛運(yùn)輸車之間的任務(wù)量差異最小?；趧?dòng)態(tài)規(guī)劃時(shí)間窗的車輛調(diào)度算法有效地保證了特種車輛實(shí)時(shí)調(diào)度的高效性，極大地提高了車輛資源利用率。

2.3 特種車輛統(tǒng)一調(diào)度問題

Du[39]等人提出多目標(biāo)優(yōu)化模型，目標(biāo)函數(shù)是最小化車輛使用數(shù)目、航班服務(wù)開始時(shí)間總和、車輛使用時(shí)間流的總和。設(shè)計(jì)了最大-最小蟻群算法和基于排序的蟻群算法進(jìn)行求解。蟻群算法中嵌入了航班服務(wù)順序，遵循服務(wù)時(shí)間早到期先服務(wù)的原則，對(duì)異種車輛調(diào)度模式進(jìn)行了仿真實(shí)驗(yàn)，調(diào)度順序考慮了“大型-中型-小型”及“中型-大型-小型”兩種不同的車輛組合方式，為調(diào)度人員提供了不同的調(diào)度決策參考。

Ip[40]等人研究了最小化總的航班延誤問題，每個(gè)航班只能由一輛車為其進(jìn)行服務(wù)，設(shè)計(jì)了具有混合編碼方式的遺傳算法進(jìn)行求解。編碼方式采用正實(shí)數(shù)來表示染色體，整數(shù)部分表示為航班服務(wù)的車輛，小數(shù)部分表示目前車輛服務(wù)的順序。該編碼方式在一個(gè)數(shù)值中集成了指派與排序的信息，在遺傳算法的初始解生成及再生成過程中嵌入貪婪啟發(fā)式算法，仿真結(jié)果驗(yàn)證了算法的有效性。

Salma[11]等人研究了地面保障車輛的協(xié)同調(diào)度問題。目標(biāo)函數(shù)是最小化航班離港時(shí)的延誤和地勤保障車輛的運(yùn)作費(fèi)用。討論了集中式及分散式的多車隊(duì)管理問題，根據(jù)經(jīng)典的數(shù)學(xué)規(guī)劃模型提出混合優(yōu)化模型，設(shè)計(jì)了貪婪啟發(fā)式方法進(jìn)行求解，提出了地勤保障車輛、航空公司、機(jī)場(chǎng)管理局之間的合作調(diào)度方案。 樊瑋[41]等人分析了地勤保障車輛運(yùn)行的特點(diǎn)，考慮服務(wù)時(shí)間窗約束、車輛服務(wù)類型較多，將車輛的服務(wù)作業(yè)進(jìn)行了統(tǒng)一的轉(zhuǎn)化。建立多目標(biāo)帶時(shí)間窗非滿載統(tǒng)一的車輛調(diào)度模型。目標(biāo)函數(shù)是最小化服務(wù)車輛的總運(yùn)行距離，對(duì)于不同服務(wù)類型的用車量最少(由服務(wù)中心發(fā)出的服務(wù)車量最少)，將多Agent技術(shù)與求解TSP(Traveling salesman problem)的最近插入法結(jié)合起來并加以改進(jìn)，設(shè)計(jì)了基于多Agent的啟發(fā)式車輛調(diào)度方法。

Silvia[13]等人研究了地勤保障車輛的雙目標(biāo)優(yōu)化問題。目標(biāo)函數(shù)是最小化服務(wù)作業(yè)等待時(shí)間與相應(yīng)的時(shí)間窗減少量之和的總和、最小化航班服務(wù)作業(yè)總的完工時(shí)間和。用Solomon的I3插入啟發(fā)式方法[42]求得初始解，使用基于約束規(guī)劃的大鄰域搜索和變鄰域搜索方法對(duì)解進(jìn)行改進(jìn)，設(shè)計(jì)了序列迭代法來改進(jìn)全局解，從而得到均衡考慮兩個(gè)目標(biāo)函數(shù)的解。

唐非[43]等人研究了特種車輛的多目標(biāo)優(yōu)化模型。假設(shè)航班需求量不同、需要服務(wù)的時(shí)間不同，只由一輛特種車輛完成服務(wù)，且特種車輛在同一時(shí)刻只能為一個(gè)航班提供不可中斷的服務(wù)。根據(jù)目標(biāo)函數(shù)的重要程度對(duì)其進(jìn)行排序，三個(gè)目標(biāo)函數(shù)分別是最小化用車數(shù)、無效服務(wù)時(shí)間比率和車輛服務(wù)時(shí)間方差。機(jī)場(chǎng)對(duì)到港航班進(jìn)行地勤服務(wù)調(diào)度所采用的啟發(fā)式算法為先到先服務(wù)，設(shè)計(jì)了三階段啟發(fā)式算法進(jìn)行求解。

地勤保障車輛調(diào)度的目標(biāo)是在滿足實(shí)際約束條件(如：車輛運(yùn)行及服務(wù)時(shí)間約束、車輛服務(wù)航班優(yōu)先次序及數(shù)目約束、車輛行駛路線規(guī)定及車輛可進(jìn)行服務(wù)的時(shí)間窗約束等)下，求得相應(yīng)問題的最優(yōu)解或近優(yōu)解，即得到合理的車輛調(diào)度方案。

綜合國內(nèi)外相關(guān)文獻(xiàn)的研究成果，對(duì)每類車輛調(diào)度問題，根據(jù)其數(shù)學(xué)模型中目標(biāo)函數(shù)的個(gè)數(shù)可以分為單目標(biāo)優(yōu)化及多目標(biāo)優(yōu)化問題。對(duì)于單目標(biāo)優(yōu)化問題，其目標(biāo)函數(shù)多集中在最小化車輛的行駛里程(或時(shí)間)、車輛的服務(wù)時(shí)間、航班等待車輛服務(wù)的時(shí)間、車輛使用數(shù)目、車輛運(yùn)行時(shí)間(包括行駛時(shí)間和服務(wù)航班的時(shí)間)與車輛的服務(wù)作業(yè)延后所導(dǎo)致的懲罰費(fèi)用之和、以及最大化服務(wù)車輛的利用率等等。多目標(biāo)優(yōu)化在于選取若干個(gè)重要的目標(biāo)函數(shù)，使得它們達(dá)到同時(shí)優(yōu)化的目的，如：同時(shí)考慮最小化車輛行駛距離、車輛使用數(shù)目和車輛總負(fù)荷差；同時(shí)最小化航班服務(wù)作業(yè)總完成時(shí)間、無效服務(wù)時(shí)間比率、車輛服務(wù)時(shí)間方差等目標(biāo)。求解多目標(biāo)優(yōu)化問題時(shí)，可以采用加權(quán)方法，將其轉(zhuǎn)化為單目標(biāo)優(yōu)化問題進(jìn)行求解，或求其Pareto最優(yōu)解。

在求解過程中，對(duì)于中小規(guī)模的問題，學(xué)者們多采用列生成、分支定界法、動(dòng)態(tài)規(guī)劃法或用CPLEX求得問題的最優(yōu)精確解；當(dāng)問題規(guī)模較大時(shí)，車輛調(diào)度問題為NP難問題，在有限的時(shí)間內(nèi)求得問題的最優(yōu)解比較困難，因此，不少學(xué)者采用啟發(fā)式方法求得問題的近優(yōu)解，如：最近鄰算法、節(jié)約算法、遺傳算法、蟻群算法及大鄰域變鄰域搜索算法等。

3 VRPTW問題及求解算法

航班的保障服務(wù)需求具有一定的時(shí)間限制，地面保障車輛必須在規(guī)定的時(shí)間內(nèi)完成保障服務(wù)作業(yè)，否則將會(huì)導(dǎo)致航班延誤[44]，給旅客、航空公司、機(jī)場(chǎng)帶來時(shí)間、經(jīng)濟(jì)、信譽(yù)等方面的損失。因此，研究相關(guān)車輛在進(jìn)行保障服務(wù)時(shí)，如何制定合理的服務(wù)飛機(jī)的順序、規(guī)劃車輛行駛路線，使其滿足航班的服務(wù)時(shí)間約束，即優(yōu)化車輛調(diào)度問題具有十分重要的意義。該問題可以歸結(jié)為滿足給定約束條件的帶時(shí)間窗的車輛路徑問題(VRPTW,Vehicle routing problem with time windows)。

VRPTW基本問題的數(shù)學(xué)模型[45]如下：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

sik+tij-K(1-xijk)≤sjk?i,j∈N?k∈V

(7)

ai≤sik≤bi?i∈N?k∈V

(8)

xijk∈{0,1} ?i,j∈N?k∈V

(9)

(1)表示目標(biāo)函數(shù)是最小化車輛的服務(wù)費(fèi)用。(2)表示車輛k服務(wù)完客戶i后服務(wù)客戶j。(3)表示車輛的容量約束。(4)、(5)、(6)分別表示車輛從配送中心出發(fā)、依次服務(wù)客戶點(diǎn)、返回配送中心。sik表示車輛k為客戶i開始服務(wù)的時(shí)間。(7)表示車輛k為客戶j開始服務(wù)的時(shí)間要不早于車輛k為客戶i開始服務(wù)的時(shí)間與車輛k從i行駛到j(luò)的時(shí)間之和。(8)表示開始服務(wù)的時(shí)間窗約束。(9)表示如果車輛k服務(wù)完客戶i后服務(wù)客戶j，則xijk=1，否則xijk=0。

VRPTW問題的研究?jī)?nèi)容較為豐富，國內(nèi)外學(xué)者對(duì)相關(guān)問題進(jìn)行了廣泛的研究。根據(jù)所研究問題的具體特點(diǎn)，該問題可有不同的分類方式。根據(jù)優(yōu)化目標(biāo)函數(shù)的個(gè)數(shù)分類，該問題可以分為單目標(biāo)及多目標(biāo)問題[46-47]。根據(jù)優(yōu)化問題獲取信息的狀態(tài)，該問題可以分為靜態(tài)及動(dòng)態(tài)優(yōu)化問題[48-49]。根據(jù)給定的時(shí)間窗個(gè)數(shù)，該問題可以分為單時(shí)間窗及多時(shí)間窗問題[50]。根據(jù)車輛服務(wù)時(shí)間是否允許超出時(shí)間窗約束，該問題可以分為硬時(shí)間窗[51-52]與軟時(shí)間窗問題[53]。根據(jù)顧客服務(wù)需求，該問題可以分為確定需求、隨機(jī)需求、模糊需求[54-56]等。按服務(wù)車輛類型，該問題可以分為同種車輛、異種車輛調(diào)度問題[57]。按車場(chǎng)數(shù)目分類，該問題可以分為單車場(chǎng)及多車場(chǎng)問題[58]。按照車輛完成服務(wù)任務(wù)后是否返回車場(chǎng)，該問題可以分為封閉式及開放式車輛路徑問題[59]等等。對(duì)于實(shí)際問題，約束條件的種類也很多，如：車輛行駛距離約束、車輛容量約束、車輛負(fù)載約束、車輛間任務(wù)均衡約束[60-62]等。

求解VRPTW的算法可以分為精確算法與啟發(fā)式算法。精確算法包括分支定界法、動(dòng)態(tài)規(guī)劃法、列生成及切平面法等[63]。因該問題是NP難問題，當(dāng)問題規(guī)模較大時(shí)，用精確算法在可接受的時(shí)間內(nèi)求得問題的最優(yōu)解比較困難。因此，學(xué)者們多采用元啟發(fā)式算法，如：模擬退火[45]、遺傳算法[46]、禁忌搜索算法[64]、蟻群算法[65]等，力求在合理的時(shí)間內(nèi)求得問題的近優(yōu)解。

4 結(jié)論及研究展望

盡管國內(nèi)外學(xué)者對(duì)地勤保障車輛調(diào)度問題及VRPTW問題進(jìn)行了有益的探索研究，但仍有許多實(shí)際問題亟待解決。在模型方面，現(xiàn)有的目標(biāo)函數(shù)主要集中在研究最小化保障車輛行駛距離、車輛使用數(shù)目最少、航班延誤時(shí)間最短、延誤航班數(shù)目最少及車輛任務(wù)均衡化等方面。近年來，我國民航部門開始致力于推進(jìn)節(jié)能減排，探索綠色機(jī)場(chǎng)、低碳機(jī)場(chǎng)、智慧機(jī)場(chǎng)的發(fā)展道路[4]。因此，在未來的模型中，可以考慮最小化保障車輛的碳排放量、降低出勤車次；根據(jù)新能源車輛(如電動(dòng)車)的特點(diǎn)，建立相應(yīng)的優(yōu)化調(diào)度模型。人們對(duì)航空公司的評(píng)價(jià)會(huì)影響其經(jīng)濟(jì)效益，在優(yōu)化為旅客服務(wù)的保障車輛調(diào)度方案時(shí)，可以考慮顧客的滿意度函數(shù)，以此來評(píng)價(jià)航空公司的服務(wù)水平和服務(wù)質(zhì)量。在求解算法方面，求解VRPTW問題的算法豐富多樣，可以借鑒用來求解地勤保障車輛調(diào)度問題。但因機(jī)場(chǎng)的內(nèi)部道路結(jié)構(gòu)復(fù)雜、停機(jī)坪的位置情況不同以及人員、車流量較大的特點(diǎn)，對(duì)車輛行駛路徑有嚴(yán)格要求，需要根據(jù)機(jī)場(chǎng)的具體特點(diǎn)設(shè)計(jì)符合實(shí)際的高效求解算法。

目前的車輛調(diào)度方法多基于人工調(diào)度，在航班起落的高峰時(shí)段、停機(jī)位臨時(shí)變更等情況下易出現(xiàn)調(diào)度失誤導(dǎo)致航班延誤。因此，未來還需開發(fā)具有強(qiáng)大功能的、可準(zhǔn)確有效傳遞信息、可視化的實(shí)時(shí)車輛調(diào)度監(jiān)控系統(tǒng)，使得不同類型的地勤保障車輛之間可以協(xié)同運(yùn)作，提高車輛調(diào)度效率?？傊?，機(jī)場(chǎng)地勤保障車輛調(diào)度問題還有很多內(nèi)容需要進(jìn)行深入的研究，該問題的求解算法具有廣泛的應(yīng)用前景。