考慮人車分離的機場客梯車調度問題研究

羅孟斐，陳慶新，毛 寧，吳植英，余龍水

（1.廣東工業大學廣東省計算機集成制造重點實驗室，廣州 510006；2.廣東機場白云信息科技有限公司，廣州 510470）

0 引言

階梯式旅客登機車（簡稱客梯車）是為旅客及工作人員提供上、下飛機的一種帶自動式結構設備的特種車輛，客梯車是保證旅客及工作人員上、下飛機的重要工具。客梯車機動靈活、用途廣泛、可以根據飛機停放情況前往不同地點進行作業[1]。機場客梯車調度問題可以看作一類帶時間窗的車輛路徑規劃問題（Vehicle Routing Problem with Time Windows，VRPTW）,也是組合優化問題和運籌學領域的研究熱點[2]。

車輛調度問題一般分為人車固定和人車分離兩種模式，人車固定模式下駕駛員和車輛之間有固定的配屬關系，在執行任務過程中駕駛員不可離開車輛，人車分離模式則允許駕駛員離開車輛[3]。目前關于機場客梯車的車輛調度算法大多采用人車固定模式，加油車、除冰車、行李車等都可以歸屬于人車固定模式下的機場車輛調度問題[4]。針對這類問題，辛超等[5]針對單一保障責任區內機場客梯車保障作業調度問題，根據費用轉換系數的未知性建立數學模型，實現機場客梯車的合理調度，減少了作業延誤，提高了運行效率。衡紅軍等[6]研究了對管線加油車帶硬時間窗的調度問題，建立了多目標優化模型，并提出了一種基于節約算法的解決方案，實現了車輛數目最小和任務量差異最小的目標。劉長有等[7]討論了考慮載油量的加油車調度的目標函數，即最小化加油車的運行成本與任務延誤的懲罰成本之和，并設計了蟻群算法進行求解，在啟發因子中考慮加油車輛的行駛距離因素；在狀態轉移概率中考慮了距離節約因素和反應滿足時間窗約束的變量，通過某機場加油車調度的實例進行了驗證。石旭東等[8]研究了飛機集中除冰作業過程中除冰車輛調度優化問題，考慮飛機的起飛順序、型號、每種型號飛機需要的除冰車數量、除冰液的噴灑速度等因素，建立了單目標優化模型。作業時間包括除冰時間和添加除冰液的時間，目標函數是合理安排除冰車，使總作業時間最短，并利用遺傳算法求解。王璐等[9]討論了行李車的單目標優化調度問題，目標函數是最小化所以航班等待行李服務的時間，并建立了整數規劃模型，用Cplex 對中小規模問題進行精確求解。仿真結果表明所建的模型能夠有效地解決行李車的服務調度問題，為機場管理提高決策支持。

人車分離模式的研究文獻較少，可以參考公交車輛調度問題。國外學者的求解策略是：在準備公交線路、運營時刻表和車輛需求數據的基礎上，首先完成車輛調度，再進行司機任務分配，最后編制司機輪班作業計劃。車輛調度是以車輛固定成本和運行成本為目標尋找最優的車輛行駛線路；司機排班將車輛行駛線路分割為若干段，根據司機工作制度和薪酬規定把線路段分派給司機，目標是以最小的司機成本完成公交班次任務。也有學者同時考慮車輛調度與司機排班，力求獲得作業成本更低的調度方案[10-12]。國內研究中，陳程[13]探討了兼顧車輛和司機的多目標公交車輛調度優化算法，尋找Pareto 最優集；陳明明[14]針對多種公交管理模式系統地討論了相關的問題模型和算法；劉濤[15]研究了以極小化總班次數量為目標的公交司機排班模型和算法。

在實際的機場客梯車業務中，客梯車駕駛員需要配合客梯車進行作業。目前客梯車執行過站航班任務的流程為：駕駛員駕駛客梯車到達飛機客艙門附近，將前端平臺對準艙門，接通取力器及液壓泵發動機的動力，調整活動旋梯、升降平臺。使平臺與飛機客艙門高度一致，然后讓梯身平臺前端同飛機艙門下沿緩慢柔性對接，最后放下撐腳、斷開液壓泵、關閉發動機，拉出平臺安全扶板。此時可以打開飛機艙門讓旅客和工作人員經過客梯臺階上、下飛機。撤離飛機時流程類似，先收回安全擋板，收回撐腳，緩慢倒車，離開飛機后再降下活動旋梯。

可知，客梯車在服務流程中有兩種狀態，一種狀態需要駕駛員操作客梯車，即需要客梯車和駕駛員兩種資源聯合完成，具體包括駕駛員駕駛客梯車在各個任務間轉移以及操作客梯車實現靠機和撤離，另一種狀態僅需客梯車，當客梯車在靠機和撤離之間這段時間，此時僅需客梯車資源便可完成人員上下機任務，這段時間內人力資源處于閑置狀態。為充分利用閑置人力資源，本文提出考慮人車分離的機場客梯車調度模式，在客梯車調度過程中增加駕駛員調度，提高駕駛員利用效率，可以大幅減少人力成本。

1 問題描述

機場客梯車的實際調度過程包括客梯車調度和駕駛員調度。為了更好地描述機場客梯車的實際調度過程，假設當前有4個航班任務需要客梯車去執行，4個航班停靠位于不同機位，各航班的計劃到港時間、計劃離港時間如表1所示。

表1 航班計劃時刻表

圖1展示了完成4個航班任務的人車分離調度的具體流程。若1位駕駛員只能駕駛同1輛客梯車，即人車固定調度模式下，滿足航班任務時間約束下最少需要2位駕駛員和2臺客梯車，2位駕駛員駕駛客梯車從車場出發，執行任務的路徑分別為航班1到航班3與航班2到航班4。而實際執行任務過程中，駕駛員僅需完成駕駛車輛抵達機位、客梯車靠機及撤離3 個步驟。因此可以利用閑置時間，將駕駛員調度到其他客梯車執行上述3個步驟，即人車分離調度模式。如圖1所示，在人車分離調度模式下，只需1位駕駛員和2臺客梯車，駕駛員駕駛1號客梯車從車場出發，抵達航班1所在機位執行完航班1的靠機任務后，調度至車場駕駛2 號客梯車前往至航班2 所在機位，執行航班2的靠機任務，完成后再調度回航班1所在機位，操作1號客梯車執行航班1的撤離任務，完成后駕駛員繼續駕駛1號客梯車去航班3所在機位執行航班3的靠機任務，完成后調度至航班2所在機位操作2號客梯車執行航班2的撤離任務，接著繼續駕駛2號客梯車前往航班4所在機位執行航班4的靠機任務，在執行完航班4的靠機任務后調度至航班3所在機位操作1號客梯車執行航班3的撤離任務，最后調度至航班4所在機位操作2號客梯車執行航班4的撤離任務。此模式下駕駛員在不同機位之間的轉移過程稱為駕駛員調度，駕駛員駕駛客梯車在不同機位之間的轉移過程稱為客梯車調度，人車分離模式相較于人車固定模式增加了駕駛員調度過程，從而減少了人力需求。

圖1 人車分離模式描述

2 模型建立

2.1 符號說明

本文構建兩階段模型來實現人車分離調度。第一階段建立機場客梯車的車輛調度模型，考慮最小化客梯車固定成本、行駛成本。第一階段模型確定客梯車調度路徑，即各個客梯車的任務鏈。第二階段建立駕駛員調度模型，考慮最小化駕駛員固定成本、轉移成本、駕駛員任務均衡。第二階段模型確定駕駛員的調度路徑。同時客梯車調度模型與駕駛員調度模型之間具有同步性約束。模型中的相關參數與決策變量如表2～3所示。

表2 參數定義

表3 決策變量

2.2 客梯車調度模型

目標函數如式（1）～（2）所示。

約束條件為：

其中：式（1）表示本文以客梯車啟用成本最小化為目標；式（2）表示最小化客梯車的調度成本；式（3）表示所有航班任務均被服務，且只被客梯車服務一次；式（4）表示流量平衡約束；式（5）客梯車調度滿足時間約束；式（6）表示客梯車總數約束；式（7）表示決策變量xij為0-1變量。

2.3 駕駛員調度模型

目標函數如式（8）～（10）所示。

其中：式（8）表示本文以最小化駕駛員啟用成本最小化為目標；式（9）表示最小化駕駛員的調度成本；式（10）為駕駛員的任務量均衡；式（11）表示所有的靠機及撤離任務均被服務，且只被服務一次；式（12）～（14）表示駕駛員從起點出發，途中滿足流量平衡約束，并回到起點；式（15）表示駕駛員調度滿足時間約束；式（16）為駕駛員總數約束；式（17）表示對于駕駛員調度模型還有基于客梯車調度模型的同步性約束，即：對于同一輛客梯車前后連續執行的撤離任務及靠機任務需要由同一駕駛員執行；式（18）表示決策變量ymnk為0-1變量。

3 實例分析

3.1 調度數據準備和參數設置

為了驗證以上模型的有效性，本文以白云機場為研究對象，根據地勤公司的調研數據，本文設定啟用一輛客梯車的成本Cp為200 元∕d，啟用一名駕駛員的固定成本Ck為600 元∕d。此外，設定客梯車調度成本pv為1 元∕min，駕駛員調度成本pk為0.5 元∕min，得到客梯車及駕駛員基本費用如表4所示

表4 車輛和駕駛員成本參數

本文的測試數據采用的是白云機場的航班數據庫，對于不同時間段，航班任務數不同。為了研究不同任務數下系統的調度結果，對輸入航班任務數分別為10、20、30、40 的實例進行分析，并且對比分析人車分離和人車固定兩種模式下的調度結果。以輸入航班任務數等于20為例，車場編號設置為0，關于航班任務的編號，航班停機位，計劃到港時刻、計劃離港時刻的詳細信息如表5所示。

表5 航班任務數據

3.2 優化結果分析

實例的模型建立及求解過程均在IntelliJ IDEA 2019.3.3軟件上進行，使用java編寫代碼，基于Gurobi求解器求解，計算機操作系統為Windows·10，CPU 主頻為2.70 GHz，內存為16 GB。本文以輸入數據為30 航班為例對求解結果進行分析，由客梯車調度結果可知，12 輛客梯車執行上文中的航班任務時客梯車成本最少，具體的車輛調度路徑及服務次數如表6所示。

表6 客梯車調度結果

求解第一階段的客梯車調度模型獲得各個客梯車的任務鏈，求解第二階段的駕駛員調度模型獲得駕駛員的調度結果。由駕駛員調度結果可知，需要8 名駕駛員執行這一系列航班任務，具體的駕駛員執行任務的路徑及服務次數如表7 所示。以1 號駕駛員為例，執行任務的次序依次是：0-K3-C1-K13-C6-K20-C16-K27-C20-0，其中K 代表此航班任務的靠機任務，C 代表此航班任務的撤離任務，這里的K3 就代表航班任務3 的靠機任務，C1 代表航班任務1 的撤離任務，從第一階段的車輛調度結果可知，1 號客梯車在執行完航班任務1 后需要接著執行航班任務2，因此在第二階段的駕駛員調度模型中，也需要駕駛員在執行完航班任務1 的撤離任務后繼續執行航班任務13 的靠機任務，同理，C6 與K20、C16 與K27也需安排給同一駕駛員連續執行。

表7 駕駛員調度結果

根據上述調度結果可知，人車固定模式下的客梯車和駕駛員具有固定的配屬關系，因此客梯車數量與駕駛員數量相同，即只執行第一階段的客梯車調度，駕駛員的調度路徑和客梯車相同。在人車分離模式下，增加了駕駛員調度過程。對于航班任務數為30 個的情況下，兩種方案的各項成本對比如表8所示。

表8 兩種方案調度結果對比

由表8 可知，在滿足任務約束的情況下，人車固定模式總成本為9 767 元，人車分離模式總成本為7 409.5元，在結果上體現為：人車分離模式下雖然增加了人員調度成本，但減少了人員固定成本，而對于機場地勤公司來說，人員固定成本為主要成本，調度成本相對很低。對于輸入航班數為30 的案例，人車固定模式需要客梯車12 輛、駕駛員12 人，而人車分離模式需要客梯車12 輛、駕駛員8人。相比人車固定模式，人車分離模式的人員固定成本大幅減少，人員調度成本少量增加，總成本降低。

圖2 為任務需求變化下車輛與人員的最優配置數量。從圖可知，隨著任務需求的增加，最優的車輛配置數量從4增加到16，而最佳人員配置數量從3 增加到9。計算可得單位需求人員數量從0.3 減少到0.225，人力需求平均減少了36.6%，造成這種變化的本質原因是隨著任務需求的增加，任務與任務之間更容易實現無縫銜接，使資源利用效率逐漸提高。

圖2 車輛與人員的最優配置數量

圖3為任務需求變化下兩種模式的總成本對比。由圖可知，任務需求從10增加到40，人車分離模式下的總成本均小于人車分離模式，運營成本平均減少26.4%。同時，隨著任務需求量的增加，人車分離模式總成本與人車固定模式總成本的比值也從0.824下降到0.684，說明隨著任務需求量的增加，人車分離模式表現出更優的成本節約效應。

圖3 兩種模式的總成本

圖4 為任務需求變化下兩種模式的駕駛員有效工時占比的對比。從圖可知，任務需求量從10增加到40，人車分離模式下的駕駛員有效工時占比均高于人車分離模式。同時，在人車固定模式下，隨著任務需求量的增加，駕駛員的有效工時占比保持在同一水平；而在人車分離模式下，隨著任務需求量的增加，駕駛員的有效工時占比也有明顯的提升，這是由于在人車分離模式下增加了駕駛員的調度過程，提高了人力資源利用效率。

圖4 兩種模式的駕駛員有效工時

4 結束語

為了減少機場客梯車運營成本，本文依據機場客梯車實際運行情況建立考慮人車分離的調度模型。通過構建兩階段模型的方式來實現人車分離，第一階段以最小化車輛固定成本、行駛成本為目標函數構建車輛調度模型，第二階段以最小化駕駛員固定成本、轉移成本和駕駛員任務均衡為目標函數，構建駕駛員調度模型。在此基礎上引入不同任務需求下的實例，基于Gurobi求解器對模型進行求解，并對人車數量的配置，以及調度路徑的走向情況等優化結果進行分析。結果顯示：隨著任務需求增加，人車分離模式表現出更優的成本節約效應，對比傳統人車固定模式，人車分離模式下人力需求平均減少36.6%，運營成本平均減少26.4%，取得了良好的優化效果，具有一定實際意義。