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

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

0 引言

階梯式旅客登機車（簡稱客梯車）是為旅客及工作人員提供上、下飛機的一種帶自動式結(jié)構(gòu)設(shè)備的特種車輛，客梯車是保證旅客及工作人員上、下飛機的重要工具?？吞蒈嚈C動靈活、用途廣泛、可以根據(jù)飛機停放情況前往不同地點進行作業(yè)[1]。機場客梯車調(diào)度問題可以看作一類帶時間窗的車輛路徑規(guī)劃問題（Vehicle Routing Problem with Time Windows，VRPTW）,也是組合優(yōu)化問題和運籌學(xué)領(lǐng)域的研究熱點[2]。

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

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

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

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

1 問題描述

機場客梯車的實際調(diào)度過程包括客梯車調(diào)度和駕駛員調(diào)度。為了更好地描述機場客梯車的實際調(diào)度過程，假設(shè)當(dāng)前有4個航班任務(wù)需要客梯車去執(zhí)行，4個航班?？课挥诓煌瑱C位，各航班的計劃到港時間、計劃離港時間如表1所示。

表1 航班計劃時刻表

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

圖1 人車分離模式描述

2 模型建立

2.1 符號說明

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

表2 參數(shù)定義

表3 決策變量

2.2 客梯車調(diào)度模型

目標(biāo)函數(shù)如式（1）～（2）所示。

約束條件為：

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

2.3 駕駛員調(diào)度模型

目標(biāo)函數(shù)如式（8）～（10）所示。

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

3 實例分析

3.1 調(diào)度數(shù)據(jù)準(zhǔn)備和參數(shù)設(shè)置

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

表4 車輛和駕駛員成本參數(shù)

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

表5 航班任務(wù)數(shù)據(jù)

3.2 優(yōu)化結(jié)果分析

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

表6 客梯車調(diào)度結(jié)果

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

表7 駕駛員調(diào)度結(jié)果

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

表8 兩種方案調(diào)度結(jié)果對比

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

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

圖2 車輛與人員的最優(yōu)配置數(shù)量

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

圖3 兩種模式的總成本

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

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

4 結(jié)束語

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