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

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

0 引言

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

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

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

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

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

1 問題描述

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

表1 航班計(jì)劃時(shí)刻表

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

圖1 人車分離模式描述

2 模型建立

2.1 符號(hào)說明

本文構(gòu)建兩階段模型來實(shí)現(xiàn)人車分離調(diào)度。第一階段建立機(jī)場客梯車的車輛調(diào)度模型，考慮最小化客梯車固定成本、行駛成本。第一階段模型確定客梯車調(diào)度路徑，即各個(gè)客梯車的任務(wù)鏈。第二階段建立駕駛員調(diào)度模型，考慮最小化駕駛員固定成本、轉(zhuǎn)移成本、駕駛員任務(wù)均衡。第二階段模型確定駕駛員的調(diào)度路徑。同時(shí)客梯車調(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)度滿足時(shí)間約束；式（6）表示客梯車總數(shù)約束；式（7）表示決策變量xij為0-1變量。

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

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

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

3 實(shí)例分析

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

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

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

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

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

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

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

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

求解第一階段的客梯車調(diào)度模型獲得各個(gè)客梯車的任務(wù)鏈，求解第二階段的駕駛員調(diào)度模型獲得駕駛員的調(diào)度結(jié)果。由駕駛員調(diào)度結(jié)果可知，需要8 名駕駛員執(zhí)行這一系列航班任務(wù)，具體的駕駛員執(zhí)行任務(wù)的路徑及服務(wù)次數(shù)如表7 所示。以1 號(hào)駕駛員為例，執(zhí)行任務(wù)的次序依次是：0-K3-C1-K13-C6-K20-C16-K27-C20-0，其中K 代表此航班任務(wù)的靠機(jī)任務(wù)，C 代表此航班任務(wù)的撤離任務(wù)，這里的K3 就代表航班任務(wù)3 的靠機(jī)任務(wù)，C1 代表航班任務(wù)1 的撤離任務(wù)，從第一階段的車輛調(diào)度結(jié)果可知，1 號(hào)客梯車在執(zhí)行完航班任務(wù)1 后需要接著執(zhí)行航班任務(wù)2，因此在第二階段的駕駛員調(diào)度模型中，也需要駕駛員在執(zhí)行完航班任務(wù)1 的撤離任務(wù)后繼續(xù)執(zhí)行航班任務(wù)13 的靠機(jī)任務(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)度過程。對(duì)于航班任務(wù)數(shù)為30 個(gè)的情況下，兩種方案的各項(xiàng)成本對(duì)比如表8所示。

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

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

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

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

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

圖3 兩種模式的總成本

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

圖4 兩種模式的駕駛員有效工時(shí)

4 結(jié)束語

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