大型機場地面服務車輛調度問題的研究

摘要：本文主要研究了我國影響飛機準點率的因素，通過研究發現提高機場地面服務車輛調度效率可提高飛機準點率，保證民航運輸效率。通過分析時間窗因素、地面服務車輛類型、地面服務流程等對地面服務車輛調度的影響，建立了適用于解決機場地面服務車輛調度問題的模型。通過研究解決此問題的兩種經典啟發式算法，尋找提高算法運行效率的方法。

關鍵詞：地面服務車輛；時間窗；車輛路徑問題；CW節約算法；鄰域搜索算法

1概述

隨著我國經濟的發展，飛機成為人們重要的交通工具之一。每年我國大型樞紐機場吞吐量都在不斷增加。2019—2023年我國民航運輸旅客吞吐量、貨郵吞吐量、飛機起降次數如表1所示。從表1中可以看出，2023年起，我國民航運輸市場正在逐步恢復，其中旅客吞吐量、貨郵吞吐量、飛機起降次數較上一年分別增長142.2%、15.8%、63.7%，旅客吞吐量和貨郵吞吐量基本恢復到2019年的標準。但與此同時航班延誤也頻繁出現，據統計造成航班延誤的原因之一是機場調度問題。

據研究發現，航空旅客投訴的重要原因是航班不正常服務，而航班延誤的主要原因一般分為內在和外在兩個因素。外在因素主要有惡劣天氣影響、空中交通管制、惡劣的航空安全狀況等。內在因素涉及航班機械維護、地面特種車輛調度效率等。從表2可以看出，2019—2023年影響航班不正常的原因除了天氣原因、空管原因這些外在因素以外，最重要的一項因素來自航空公司和機場方面，其中一項為低效率的地面服務車輛。

航班在降落之前和起飛以后，需要接受各種地面服務，如燃油加注、乘客擺渡、貨物運輸等，這些服務需要清潔車、擺渡車、加油車等地面服務車輛協調完成，若其中任一環節設計不合理都可能導致航班延誤、資源浪費、降低服務質量。因此為了提升民航業的服務質量，研究機場地面特種車輛的調度，找到影響特種車輛低效的原因，對保證航班的正常執行，提高航班運行效率，提升國民幸福度，改善航班延誤現狀具有非常重要的意義。

2影響因素分析

在航空運輸中，飛機每進行一次航空飛行任務，都需要在機場進行一系列的生產和地面準備工作，這稱為航班過站行為。而飛機在航班過站期間，進行的各種地面服務保障工作就是航班過站的地面服務。根據我國居民出行的主要特點并結合數據發現，我國各地大型樞紐機場的航班在一定時間內的起降存在高峰期，這種情況會導致航班到達波和離港波的出現，而航班的延誤具有網絡傳播效應，從而導致航班延誤的加劇。為了研究機場地面服務車輛調度問題，首先分析影響其調度效率的因素。

2.1考慮時間窗的影響

由于航班的抵港和起飛都需要按照航班時刻表進行，因此對地面服務車輛的服務時間有時間窗限制。首先，在航班不延誤的前提下，地面服務車輛的服務時間需要嚴格控制航班時刻表里航班抵港至起飛時間段內，這屬于硬時間窗問題。其次，航班有可能提前到達或者延遲離開，地面服務也允許在航班時刻表規定的時間外進行，屬于軟時間窗問題。此時在建立模型時，需要增加一個懲罰成本。

2.2考慮地面服務類型的影響

航班過站時，接受的地面服務大致可分為三類，分別是對飛機客艙、飛機外艙以及飛機外部進行后勤工作。而飛機接受的地面服務并不是全部都需要地面服務車輛設備來完成，其中飛機的加油、加水、電源車靠機作業、拖車作業等，這些服務需要地面服務車輛才能完成工作。而有的服務只需要地勤人員自己即可完成，如引導乘客下機、上機回收餐車、值機人員送艙單等服務。因此，本文在后續過程中，在不影響各環節順序的基礎上，將各流程進行簡化，僅考慮需要地面服務車輛調度的環節進行研究。

從地面服務車輛種類分析，主要可將其分為兩類，第一類是運輸資源的車輛，如垃圾車、污水車、食品車等，此類地面服務車輛具有一定的容量限制，車輛必須將資源運輸到停機坪才能保證工作的完成，并且車輛能夠提供的資源不能超過其運載的上界。另一類是不涉及資源運輸的車輛，如牽引拖車、升降車、管線加油車等，此類車輛的作業不受車輛運載容量上界所限制。

2.3考慮地面服務流程的影響

根據我國常用民用機型對地面服務項目的需求情況，航班過站時需要有地面服務車輛參與的地面服務項目有：（A）飛機到位，機務放輪擋；（B）清潔隊清潔客艙；（C）食品公司上機回收餐車并裝食品；（D）平臺車或傳送帶靠艙門，卸行李；（E）卸貨；（F）裝貨；（G）裝行李；（H）油料公司油車到位加油；（I）電源車靠機作業；（J）污水車、垃圾車、加水車靠機作業；（K）關艙門，拖車拖出飛機。

根據各地面服務項目之間的關系，流程（B）（C）為圍繞飛機客艙展開的工作，并且清潔客艙和回收餐車的工作可以同時進行。流程（D）（E）（F）（G）為圍繞飛機外艙展開的作業，由于各項工作存在先后順序，因此不能同時進行。流程（H）（I）（J）是圍繞飛機外部進行各種地面作業，各項服務相互獨立，因此不能同時進行。三大種類的服務相互獨立，因此可以并行作業。

3問題描述和模型建立

結合地面服務車輛調度問題的影響因素，將機場地面服務車輛調度問題進行簡化，最終可將其歸結為帶有時間窗的車輛路徑問題（VRPTW）。在不考慮不同類型地面服務車輛對問題的影響下，設有同樣車輛的車隊V、一組客戶C和一個有向圖G，圖由|C|+2個頂點組成，其中客戶記為1，2，…，n，倉庫由頂點0（“駛出倉庫”）和n+1（“返回倉庫”）表示。頂點的集合記為N=0，1，2，…，n+1。集合弧A表示倉庫和顧客之間以及顧客之間的連接。沒有弧止于頂點0，也沒有弧起源于頂點n+1。對于每條弧線（i，j），其中i≠j，關聯一個成本cij和一個時間tij，其中可能包括在顧客i處的服務時間。每輛車有一個容量q，每個顧客i有一個需求di.每個顧客i都有一個時間窗口ai，bi。車輛必須在bi之前到達客戶，它可以在ai之前到達，但客戶不會在此之前得到服務。倉庫也有一個時間窗口a0，b0（假設倉庫的時間窗口是相同的），a0，b0稱為調度視界，車輛不得在a0之前離開倉庫，必須在bn+1或者之前返回。

假設q，ai，bi，di，cij為非負整數，而tij為正整數，cij和tij都滿足三角不等式。

定義兩組決策變量x和s對每條弧（i，j），其中i≠j，i≠n+1，j≠0，對每輛汽車k定義：

xijk=0，如果車輛k不從點i駛向點j；

1，如果車輛k從點i駛向點j。

sik為某個頂點i和每個車輛k的決策變量，表示車輛k開始為客戶i服務的時間，如果給定車輛k不為客戶i服務，sik沒有任何意義。并且假設a0=0，因此對于所有k，s0k=0。

為了使模型符合實際情況還應有如下假設：（1）對每輛服務車輛來說，每個顧客只得到一次服務；（2）每條服務路線都從頂點0出發，在頂點n+1結束；（3）時間窗和容量約束可以被觀察。現在以車輛運行路線成本最小作為目標函數建立模型：

min∑k∈V∑i∈N∑j∈Ncijxijk（1）

∑k∈V∑j∈Nxijk=1i∈C（2）

∑i∈Cdi∑j∈Nxijk≤qk∈V（3）

∑j∈Nx0jk=1k∈V（4）

s.t.∑i∈Nxihk-∑j∈Nxhjk=0h∈C，k∈V（5）

∑i∈Nxi，n+1，k=1k∈V（6）

sik+tij-K（1-xijk）≤sjki，j∈N，k∈V（7）

ai≤sik≤bii∈N，k∈V（8）

xijk∈0，1i，j∈N，k∈V（9）

其中，約束式（2）表示每個顧客僅被訪問一次。式（3）表示沒有車輛裝載超過其容量允許的貨物。式（4）、式（5）、式（6）確保每輛車離開0號倉庫，在顧客到達后再次離開，最終到達n+1號倉庫。式（7）表明如果車輛k從i行駛到j，則不可能在sik+tij之前到達j，這里K是一個大標量。式（8）表示汽車為顧客i服務的時間必須在時間窗內。式（9）是完整性約束。該模型通過設置參數可轉化為其他模型，當ai=0，bi取值很大時，問題退化為車輛路徑問題（VRP）；當V中只含一個元素時，問題退化為旅行商問題（TSP）。

4求解算法分析

有時間窗的車輛路徑問題已經被證明是NP難的，因此更多的是在研究解決此問題的啟發式算法，常用的有經典的啟發式算法和智能啟發式算法，常用的智能啟發式算法有遺傳算法、蟻群算法、模擬退火算法等。下面介紹求解此問題的兩類經典啟發式算法。

4.1CW節約算法

該算法最開始是為解決有條件的車輛路徑問題（CVRP）提出，而該算法在可行性的基礎上具有運行速度快、簡單、易于調整的特點，使得此方法在最初研究啟發式算法解決此類問題時，被廣泛使用。此方法采用將可行子路線進行合并的方法建立節約標準，即通過合并兩條路線使用一輛車，而不是兩輛車的方式來節約成本。現以一個倉庫、兩個顧客為例，節約算法的基本思想如下：設O為倉庫，y和z是兩個需要服務的顧客，將任意兩點間的距離定義為dij（i=O，y，z；j=O，y，z），車輛從倉庫O出發，服務兩個顧客存在兩種方案。第一種方案由一輛車完成整個服務過程，車輛從倉庫O出發，依次服務顧客y、z，最后返回倉庫，車輛行駛的總路程為D1=dOy+dyz+dzO；第二種方案是由兩輛車分別從倉庫出發，單獨服務顧客y和z，最后返回倉庫，此方案車輛行駛的總路程為D2=2dOy+2dzO。如果方案一車輛行駛的總路程小于方案二行駛的總路程，節省的距離為：

Sij=dOy+dzO-dyz。

將其定義為y、z兩顧客間的節省函數。

考慮外部因素的影響，可將節省函數進行優化，引入節省函數：

Sij=dOy+dzO-λdyz+μdOy-dzO+vcy+czc-。

其中λ是為了避免顧客分布導致原始CW算法構建從最外面顧客開始，向內部顧客前進的圓形路線的缺點，通過引入正參數λ來幫助重塑路線。公式的第二項是為了收集更多關于顧客的分布的信息，利用顧客y、z之間關于他們到倉庫距離不對稱信息，引入的一個正常數μ。而第三項是為了考慮顧客的需求以及總體平均需求，將需求較大顧客提供優先級。其中cy（cz）表示顧客y（z）的需求，c-表示平均需求，v是非負參數。由于CW節約算法并沒有考慮時間窗對問題的影響，因此在實際的使用過程中需要加入時間窗等約束條件。

4.2鄰域搜索算法

鄰域搜索算法最初是為了解決VRP問題提出，在給出初始解后，主要通過破壞算子破壞當前解的一部分，即從可行解變成不可行解，再由修復算子對被破壞的解進行重建，重新變成可行解的過程。而鄰域是一種與破壞算子和修復算子有關的隱式定義。由于鄰域的定義影響了算法的復雜度，一般情況下，鄰域選擇越大，得到局部最優解越好，從而得到全局最優解就越好。但鄰域選擇越大，每次迭代搜索所需要的時間也越長，因此鄰域的選擇非常重要。鄰域搜索算法的基本步驟為：

（1）設初始解為路徑σc=c1，c2，…，cn，其中ci∈C，cn為當前路徑最后服務的客戶。

（2）定義兩個客戶的相關性函數：R（i，j）=1cij+Vij，其中cij是從i到達j的成本，并且將所有的cij都在0，1范圍內歸一化；如果顧客i和j由不同車輛服務，并且減少車輛數量在成本函數中很重要，則Vij的計算結果為1，否則，計算結果為0。

（3）移除過程。將相關性大的顧客依次從σc移除放入集合S中，直至滿足假設條件，并定義從σc中移走集合S后，剩余的部分解為σ*。

（4）插入過程。將移走的數據集S依次重新插入部分解σ*中，直至數據集S里的元素全都插入部分解σ*，此過程生成許多待定解。

（5）將新生成的解與初始解進行比較，比較其運行路線成本，決定是否接受新生成的解。

（6）更新當前解及相關參數，重復迭代過程，設置終止條件，結束搜索時即可返回問題的最優解或近似最優解。

結語

CW節約算法和鄰域搜索算法都是解決VRPTW問題的重要經典啟發式算法。其中CW節約算法影響算法效率的主要因素有：節省函數Sij函數的選擇及參數設置；如何將時間窗因素加入CW節約算法模型中進行求解。而鄰域搜索算法首先需要考慮初值的選取方式，用此方法求解問題初始解可隨機給出，也可通過節約算法給出初始解。在于移除過程，相關函數的定義會影響移除的解的順序，插入過程采取的算法也會影響算法的復雜度。因此，優化移除過程和插入過程的算法，對提高算法效率有重要意義。

參考文獻：

［1］DantzigGB，RamserJH.TheTruckDispatchingProblem［J］.ManagementScience，1959，6（1）：8091.

［2］ShawP.UsingConstraintProgrammingandLocalSearchMethodstoSolveVehicleRoutingProblems［J］.PrinciplesandPracticeofConstraintProgrammingCP98，1999：417431.

［3］劉小蘭，郝志峰，汪國強，等.有時間窗的車輛路徑問題的近似算法研究［J］.計算機集成制造系統，2004，010（007）：825831.

［4］LarsenJ.ParallelizationoftheVehicleRoutingProblemwithTimeWindows［J］.Ph.d.thesisImmTechnicalUniversityofDenmark，2004：1145.

［5］RopkeS，PisingerD.AnAdaptiveLargeNeighborhoodSearchHeuristicforthePickupandDeliveryProblemwithTimeWindows［J］.TransportationScience，2006，40（4）：393546.

［6］衡紅軍，晏曉東.實現多目標優化的機場特種車輛調度算法［J］.計算機應用與軟件，2016，33（010）：238242.

［7］DoyuranT，CatayB.ArobustenhancementtotheClarkeWrightsavingsalgorithm［J］.JournaloftheOperationalResearchSociety，2011，62（1）：223231.

基金項目：校級青年基金項目（QJ2022106）資助

作者簡介：江婧（1995—），女，漢族，四川眉山人，碩士研究生，講師，主要研究最優化理論及算法。