機場飛行區(qū)無人駕駛清水車優(yōu)化調度方法*

張 鳳 湯曉鵬 劉兵飛

（1.中國民航管理干部學院機場管理系 北京 100102；2.中國民航大學航空工程學院 天津 300300；3.中國民航大學科技創(chuàng)新研究院 天津 300300）

0 引 言

隨著我國民航業(yè)務量的快速增長，航空運輸市場的不斷擴大，機場的運營和管理面臨著巨大挑戰(zhàn)。統計數據表明：有一半以上的航空投訴是關于航班服務不正常，其中一項就是低效的機場地面保障服務[1]，應用高新技術解決上述問題已成為相關行業(yè)的共識。機場的車輛調度工作受到來自航空公司、機場、乘客，以及貨物等多種因素的影響，調度過程涉及到的部門和人員繁多，錯綜復雜的飛行區(qū)場內運行設施、運行環(huán)境對飛行區(qū)車輛調度的效率和安全性提出更高的要求。無人駕駛技術應用于飛行區(qū)特種車輛將有效降低車輛調度過程中的人員流動和人為差錯，簡化調度流程，為航班服務爭取更多時間，從而降低因地面調度不合理而造成航班延誤的概率。目前，無人駕駛技術在機場的應用研究主要集中在某1種特種車輛的初步測試上[2]。法國戴高樂機場投放了2輛新秀科技公司Navya生產的無人駕駛小型載客車并展開測試；挪威法格納斯機場采用了Yeti Snow Technology科技公司研發(fā)的基于“應用自動化”原理的無人駕駛掃雪車來提升機場內的除雪作業(yè)；新加坡SATS正在測試無人駕駛行李裝運車、貨物裝運車；中國廣州白云機場與馭勢科技公司合作就機場擺渡車進行深度合作等。

在已知的機場飛行區(qū)車輛調度研究中，樊琳琳[3]提出多目標數學模型和基于2階段算法的求解，并對大型機場過站航班數據進行驗證；黃鸝詩[4]提出航班延誤最少和服務設備任務量均衡的雙目標優(yōu)化模型，并對擺渡車和加油車進行了調度仿真；何丹尼[5]分析了航班進出港流程并設計兩階段啟發(fā)式算法求解機場擺渡車多目標模型。李猷[6]利用改進NSGA-II算法求解機場加油車多目標模型，該方法通過引入改進的凝聚層次聚類策略增加了Pareto解的多樣性；由于多Agent的調度控制系統可以利用本地決策對動態(tài)變化和擾動及時做出反應，吳建波[7]利用此方法對機場特種車輛進行綜合調度；馮霞等[8]利用多目標遺傳算法對加油服務和擺渡服務進行了協同優(yōu)化；殷龍等[9]利用最鄰近算法對加油車調度模型進行求解，結果表明：該算法可大幅度降低服務成本；Xing等[10]基于博弈論對除冰車調度問題進行分析，通過仿真實驗對該方法進行了驗證；Du等[11]對過站航班拖車調度進行研究，以成本最低為目標建立MIP模型，并通過迭代啟發(fā)式算法對模型進行求解；Norin等[12]以航班延誤及行駛路程最小化為目標對除冰車進行調度優(yōu)化，并通過仿真論證了調度模型的有效性；Hess等[13]提出了1種基于編隊協同的掃雪車輛自動駕駛方法，該算法能在障礙物檢測中對編隊形狀進行自適應調整，提高了算法的可靠性；Zhao等[14]建立了以高峰時段或某一時段所需擺渡車輛數最少為目標的整數規(guī)劃模型，通過引入虛擬航班，創(chuàng)新性地構建了擺渡車輛共享網絡，將模型轉化為網絡最大流問題；Padron等[15]提出了1種新的雙目標優(yōu)化方法，對特種車輛最小化作業(yè)開始前的等待時間和最大限度地減少車輛周轉的總完成時間的目標進行求解；Sigler等[16]提出了1個新的優(yōu)化模型，當給定1組約束條件時能生成最佳機場班車路線；Bijjahalli等[17]設計了基于全球導航衛(wèi)星系統的機場特種車輛自主導航制導系統的體系結構，通過對系統信號的衰減現象進行建模，并根據實際機場運行場景中衛(wèi)星、接收天線和反射器之間的相對幾何關系計算了車輛位置誤差。

機場特種車輛的調度任務多數仍由人工操作完成，特種車輛種類繁多，缺少統一的智能控制方法，并且特種車輛和機場地面交通缺少完善的感知通訊系統，無法向調度中心反饋車輛完整的自身信息，進而無法實現完整的人-車-路-機信息閉環(huán)。但隨著智能交通和智慧網聯的快速發(fā)展[18-19]，筆者建立了機場無人駕駛特種車輛智能調度保障體系，其包含機場全局智能監(jiān)控中心、系統智能調度中心、全局信息調度集合和網聯特種車輛集群這4個系統，基于車輛的任務信息，對無人駕駛特種車輛進行統籌規(guī)劃，實時監(jiān)控機場地面狀況，優(yōu)化車輛服務路線和任務分配，智能控制車輛運行狀態(tài)，能夠實現大規(guī)模特種車輛集群的安全行駛，具體調度保障體系流程見圖1。此外，構建了機場飛行區(qū)無人駕駛清水車輛的調度優(yōu)化模型，與但正剛等[20]提出的實現負載均衡的算法相比，在實現任務量均衡的同時并不會增加總行駛路程，其對無人駕駛清水車輛，以及與其調度方式相似的食品車、垃圾裝卸車和污水車等在機場飛行區(qū)運行調度的實際應用具有重要參考意義。

圖1 機場無人駕駛特種車輛智能調度保障體系Fig.1 Intelligent dispatching guarantee system for airport driverless special vehicles

1 機場飛行區(qū)無人駕駛清水車調度模型

1.1 問題提出

機場飛行區(qū)航班服務需要不同類型的特種車輛共同完成，調度方式不合理極易影響航班的正常運行，甚至造成大面積航班延誤。由于特種車輛種類繁多，車輛調度方案的設計方式也不盡相同。例如，就加油車而言，機場在各個泊位下都鋪設輸油管道，飛機只需由泵車加油，因此，其約束條件只有最大續(xù)駛里程和航班時間窗約束，而無最大載運量約束；就行李運輸車而言，其工作過程主要是先空載行駛至進港航班停機位，再將卸載后的乘客行李運送至機場行李分揀區(qū)，只能實現單車單航班服務，僅需考慮航班時間窗和最大載運量的約束；就擺渡車而言，航班類型不同對擺渡車的數量需求也不盡相同，大型航班，乘客人數較多，通常安排2~3輛擺渡車進行服務，并且需要對每輛擺渡車的服務時間窗進行精準約束；就清水車而言，其工作方式主要是由車場行駛至航班所在停機位，服務結束后對其他航班進行連續(xù)服務，可實現單車多航班服務，需要同時考慮服務時間窗、最大載運量，以及車輛最大續(xù)駛里程的約束。不同類型特種車輛的工作方式和調度方式有所區(qū)別，因此，構建普適性高的車輛調度模型，可為不同特種車輛的調度算法設計提供理論支撐，對機場特種車輛服務航班效率和機場效益的提升具有重要的應用價值。

1.2 模型構建

筆者以無人駕駛清水車為例構建調度模型，與傳統人工駕駛清水車輛相比，無人駕駛清水車具備自主定位、環(huán)境感知、動作完成精度高等特點，按照恒定的速度在規(guī)定的路線上行駛，避免駕駛員人為因素的不利影響，提高工作效率。目標函數的建立主要從無人駕駛清水車自身的運行成本和航班服務水平這2個角度考量，最終將無人駕駛清水車行駛總路程最短、派出服務航班的車輛數量最少、車輛服務航班數量差異化最小以及實際開始服務時間與最早開始服務時間的差值最小即航班服務水平最高做為目標函數。

1.2.1 變量設置

1.2.2 目標函數與約束條件

通過2階段啟發(fā)式算法對無人駕駛清水車調度目標函數進行優(yōu)化。式（1）表示清水車行駛的總路程最短；式（2）表示從服務航班的清水車總數量最少；式（3）表示通過構造均方差求和公式使清水車服務航班數量差異化最小；式（4）表示通過將清水車服務航班硬時間窗與梯形模糊隸屬度函數Lj相結合構建航班服務水平函數，使得清水車實際開始服務的時間與最早開始服務時間的差值最小即航班服務水平最高。

Lj用于優(yōu)化航班服務水平，使實際開始服務時間盡可能接近最早開始服務時間，為后續(xù)航班服務提供盡可能多的時間，從而減少后續(xù)航班因地面服務不合理而造成的航班延誤，對于在時間窗內引起的航班服務水平的高低采用線性函數進行表示。另外，根據機場航班數據以及清水車服務航班時間的實際情況，規(guī)定當無人駕駛清水車在航班最早開始服務前5 min內到達停機位均可等待，航班服務水平不會受到影響，超過5 min不超過15 min時，航班服務水平呈線性下降，具體函數表達見式（5）。

式中：Sj表示航班j的實際開始服務時間。

就無人駕駛清水車而言，其工作方式主要是由停車場行駛至航班所在停機位，服務結束后對其他航班進行連續(xù)服務，可實現單車多服務的運送方式，需要同時考慮服務時間窗、最大載運量和車輛最大續(xù)駛里程的限制，具體約束條件如下。

式（6）表示每架航班都被1種車型服務1次且僅被服務1次；式（7）表示對任意1架航班進行服務的車輛，服務結束后必須駛離；式（8）表示每輛特種車輛的載運量均不能超過車輛的最大容量；式（9）表示車輛服務航班的總路徑不得超過車輛單次服務的最大行駛距離；式（10）表示服務航班j的時刻是在服務航班i的時刻與服務航班i的時間及從航班i到航班j所需的時間總和之后；式（11）表示車輛為航班i服務的時間在其服務時間窗范圍內；式（12）表示每輛車輛從同1個停車場o出發(fā)，航班服務結束后必須回到停車場T；式（13）表示航班j的航班服務水平應在[1,2]內。

2 算法實現

機場飛行區(qū)無人駕駛特種車輛調度問題可歸結于車輛路徑問題（vehicle routing problem，VRP）這一大類。與傳統車輛調度問題相比，機場飛行區(qū)無人駕駛特種車輛的調度問題在減少航班延誤、提高機場地面運行效率及安全性方面有更高的要求。算法設計分為2個階段：①在傳統C-W節(jié)約算法的基礎上進行適當的修改,將航班服務的硬時間窗與模糊隸屬度函數Lj相結合，并根據實際的航班信息規(guī)定當清水車在航班最早開始服務時刻前5 min內到達停機位，清水車可以原地等待，不會對航班服務水平造成影響，其目的是實現清水車總行駛路程最短以及實際開始服務時間與最早開始服務時間的差值最小即航班服務水平最高的目標；②在階段①計算結果的基礎上對未達到清水車容量極限的子線路進行進一步優(yōu)化，目的是實現派出服務航班的清水車數量最少、服務航班數量差異化最小的目標，新算法規(guī)定清水車在航班最早開始服務時刻前5 min但不超過15 min內到達停機位，清水車可以原地等待，但會對航班服務水平造成一定影響，下面對C-W節(jié)約算法的原理及算法設計的具體步驟進行綜述。

2.1 C-W節(jié)約算法的基本原理

將航班服務過程中2條航班線路合并為1條航班線路后使其總服務路程減少量最大，直至達到無人駕駛特種車輛的最大續(xù)駛里程或最大載運量，再進行下一車輛的線路優(yōu)化，直到完成所有航班服務。

以無人駕駛清水車為例，進行調度算法設計，理應同時考慮航班服務時間窗、清水車的最大載運量和最大續(xù)駛里程約束，但由于航班服務時間窗和最大載運量的約束起主要作用，因此本文算法設計主要考慮航班服務時間窗和最大載運量的約束，另外，在算法設計過程的時間變量單位均為分鐘。由C-W節(jié)約算法[15]知

s(i,j)即表示清水車從航班i到航班j的距離相對于車輛從車場分別到航班i和航班j距離之和的路程節(jié)約值。清水車從航班i到航班j之前需要考慮無人駕駛清水車的最大載運量和航班服務時間窗的約束。

以EFj表示連接航班i和j所在的線路后，服務車輛到達航班j的時間相比于原線路中航班j服務開始時間的提前或延遲量，EFj可以式（15）表示。

由式（15）可知：EFj>0時，航班j的開始服務時間延遲，EFj<0時，航班j的開始服務時間提前，EFj=0時，航班j的開始服務時間不變。

2.2 算法設計

2.2.1 階段①具體步驟。

步驟1。計算s(i,j)，令M={s(i,j)|s(i,j)>0}，并將M按s(i,j)由大到小排序。

步驟2。若M=?,則終止算法，否則對M內s(i,j)的最大值進行分析，考慮對應的(i,j)，若滿足下列條件之一，轉步驟3，否則轉步驟6。

1）點i和點j均不在已構成的路徑上。

2）點i或點j在已構成的路徑上，但不是線路的內點。

3）點i和點j在已構成的不同路徑上，均不是內點，且1個是起點，1個是終點。

步驟3。計算點i和點j連接后子路徑的總需求量Q，若Q≤Qmax轉步驟4，否則轉步驟6。

步驟4。計算EFj，如下。

1）若EFj=0,轉步驟5。

步驟6。M=M-s(i,j)，轉步驟2，直至所有航班均安排到服務路徑中，即中止。

2.2.2 階段②具體步驟。

階段①只是使無人駕駛清水車行駛距離和實際開始服務的時間與最早開始服務時間的差值最小即航班服務水平最高達到最優(yōu)水平，但還需考慮無人駕駛清水車數量和服務車輛間的任務量的均衡性，為使服務車輛間的任務量差異最小，本文提出航班任務差異量評價值δ來衡量服務車輛間的任務量差異，具體見式（18）。

式中：m為從車場派出服務的車輛數；nl為從車場派出的第l輛車所服務的航班數。

根據階段①所獲得的子路徑結果R={R1,R2,…,Rn}，當任意子路徑Rs的航班服務量已經達到了無人駕駛清水車的容量極限時，其航班服務順序不變，當任意子路徑Rs的航班服務量未達到無人駕駛清水車的容量極限，需對其進行進一步的線路優(yōu)化。航班服務量未達到容量極限的子路徑集合為航班集合為I'={1,2,…,n'}，在對航班進行任務量差異最小化時需要考慮任務量的約束，設定1個閾值量λ（單位：架），使每輛車分配的任務量均不應超過λ，Ts(i)為線路i起始航班的開始服務時間，Te(i)為線路i的終止航班的服務開始時間，具體步驟如下。

步驟1。將R'按Ts(i)從小到大的順序進行排序。

步驟2。將R'的前m'個子路徑航班服務任務分別分配給m'輛車，初始時m'=1。

步驟3。依次為這m'輛車分配任務，計算出該車服務的最后1個子路徑Te(i)，在所有滿足Te(i)+5

步驟4。若分配完成后仍有子路徑航班未被分配，則m'=m'+1，轉步驟2，否則至少需要m'輛車才能完成所有服務，轉步驟5。

步驟5。按步驟4確定的m'值，加上任務量閾的約束，重復步驟3，直至算法終止。

3 算例分析

3.1 算例數據

采用國內某機場春運期間某天的航班計劃起飛時間在08：00—19：00的113架航班數據作為算例，實現對機場飛行區(qū)無人駕駛清水車的調度方案，由于不同類型的飛機對清水的需求量和服務時間有所區(qū)別，所以需要對飛機進行分類，筆者將飛機分為3類：C類機、D類機和E類機[4]，不同類型的飛機對清水的需求量和服務時間見表1，機場飛行區(qū)無人駕駛清水車輛平均可以容納5 m3的清水。

表1 飛機分類及服務參數Tab.1 Aircraft classification and service parameters

機場飛行區(qū)無人駕駛清水車需按指定線路和恒定速度在機場內運行，根據機場各停機位的地理位置，能夠確定任意2個停機位之間的距離，因此清水車服務任意2架航班之間的行駛距離是固定的。本文以車場和3個停機位為例，用矩陣Pij(i=j=0,1,2,3)表示車場與停機位以及停機位與停機位間的距離，具體見式（19）。

3.2 服務航班時間窗的確定

根據《航班安全運行保障標準》[21]可知，航空器應不晚于航班計劃關艙門時間/預計關艙門時間前70 min完成客梯車對接工作，清水操作在廊橋或客梯車對接完畢后即可開始，客梯車的對接時間不超過4 min，并且清水操作的完成時間不應晚于航班計劃關艙門時間/預計關艙門時間前15 min。本文同時考慮放置/撤離輪檔與錐筒以及牽引車與航空器的對接及推進/推出過程，確定航空器到港推進至停機位和推出停機位至離港不超過10 min，最終確定始發(fā)航班和過站航班的服務時間窗如下。

式中：Ta(min)為航班計劃到港時間；Tl(min)為航班計劃離港時間。

按照式（20）~（21）得到的清水車服務部分始發(fā)航班時間窗，見表2。

表2 部分始發(fā)航班時間窗Tab.2 Departure flight time window

按照式（22）~（23）得到的清水車服務部分過站航班時間窗，見表3。

表3 部分過站航班時間窗Tab.3 Partial transit flight time window

3.3 結果分析

通過MATLAB軟件對機場飛行區(qū)無人駕駛清水車的航班服務調度方案進行設計，得到了113架始發(fā)或離港航班的服務調度方案，表4表示本文算法共得到54個子路徑，其表明在08：00—19：00內需要從車場派出54車次完成航班的清水服務任務，與傳統的單車單航班服務相比，用車需求減少59車次，清水車的總的服務路程為108.24 km，與單車單服務的總路程為207.76 km相比，本文的研究算法路程節(jié)省了47.90%，大大降低了車輛運行成本，據式（5）和式（13）可知：航班服務水平達到95.71%，據式（18）可知：航班服務任務量的差異達到93.32%。

表4 無人駕駛清水車的服務子路徑結果Tab.4 Service sub-path results of driverless potable water vehicles

階段②考慮了航班服務任務量差異及無人駕駛清水車服務航班閾值λ的限制，有航班服務任務量約束的調度結果見表5。由表5可見：無人駕駛清水車服務航班的總路程為84.43 km，僅需派29車次進行清水服務，與階段①相比服務總路程節(jié)省21.20%，車輛使用減少25車次；而與單次單服務的調度方式相比，服務總路程節(jié)省了59.36%，車輛使用減少84車次，極大降低了車輛運行成本。據式（5）和式（13）可知：航班服務水平為93.78%。據式（18）可知：航班服務任務量的差異降至43.96%，與表5結果相比減少了49.36%。此外，與殷龍等[9]采用的最鄰近算法所得的機場加油車服務航班任務量評價值δ=2.72相比，本文算法所得的機場無人駕駛清水車服務航班任務量評價值僅為0.44，因此，本文算法在減少無人駕駛清水車服務航班總路程的同時顯著提高了車輛服務航班任務量的均衡性。

表5 任務量調整后的無人駕駛清水車服務子路徑結果Tab.5 Service sub-path results of driverless potable water vehicles after task volume adjustment

4 結束語

本文將航班服務時間窗與模糊隸屬度函數相結合，構建改進的機場飛行區(qū)無人駕駛清水車調度模型，將對時間復雜度低且求解速度較快的C-W節(jié)約算法與新構造算法相結合優(yōu)化無人駕駛清水車的4個目標函數，使得在計算時長較短的情況下得到1個接近最優(yōu)的解，滿足對當前機場飛行區(qū)特種車輛調度安全、高效的現實需求。但本文未考慮雨霧等惡劣天氣對無人駕駛車載傳感器系統的影響以及空域管制、旅客出行及飛機狀態(tài)等各方面不可控因素的干擾，因此,后期的調度研究需要進一步考慮航班及無人駕駛特種車輛信息的不確定性,對無人駕駛特種車輛的動態(tài)調度策略進行的深入研究,從而提升調度算法的魯棒性。