林宇鵬，毛 寧，徐國寧，陳慶新，區(qū)樂穎

（1.廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣州 510006；2.廣東機(jī)場白云信息科技有限公司，廣州 510470）

0 引言

全球貨運(yùn)量和客運(yùn)量的持續(xù)增長給機(jī)場服務(wù)帶來了很大的挑戰(zhàn)。不斷增長的客機(jī)數(shù)量也給客艙清潔人員的調(diào)度帶來了巨大的壓力，當(dāng)前我國機(jī)場客艙清潔人員調(diào)度仍以人工調(diào)度為主，面臨的挑戰(zhàn)包括任務(wù)量大，約束條件復(fù)雜。

客艙清潔人員主要為飛機(jī)提供清潔服務(wù)，進(jìn)出港航班均需要進(jìn)行一定標(biāo)準(zhǔn)的客艙清潔服務(wù)。不同類型的航班所需的服務(wù)不同，大型飛機(jī)一般需要3～5組清潔人員，中小型航班一般需要2～3 組清潔人員。為保證清潔服務(wù)的質(zhì)量以及公平性一般要求所有清潔人員到位后才能開始清潔任務(wù)[1]。因此，機(jī)場客艙清潔人員調(diào)度問題本質(zhì)上是一個具有同步約束的人員路徑規(guī)劃問題（Manpower Routing Problem with Simultaneous Constraints,MRPSC），是經(jīng)典的帶時間窗的車輛路徑規(guī)劃問題的擴(kuò)展[2]。MRPSC 的任務(wù)需要若干人員到同一個地理位置執(zhí)行一組工作；同時每項任務(wù)都有1 個地點(diǎn)，1 個處理時間和1 個時間窗口，人員數(shù)量及技能需求。人員可以在不同的時間到達(dá)工作地點(diǎn)，但任務(wù)需在所有人員都到位后開始，即存在同步約束[3-4]。經(jīng)典車輛路徑規(guī)劃問題及其擴(kuò)展中，車輛路徑是獨(dú)立的，不受其他車輛的影響。然而，MRPSC 中的路線通常相互關(guān)聯(lián)，某人員路徑的改變可能使得其他人員的路徑不合法。MRPSC 是具有多重同步約束的（Vehicle Routing Problem，VRP）的一種類型，其中可能或必須使用一個以上的車輛或資源來完成一項任務(wù)[5]。

MRPSC 在很多領(lǐng)域得到了應(yīng)用。在港口服務(wù)領(lǐng)域，Li 等[6]研究了有時間窗和工作團(tuán)隊約束的人力配置問題，采用弧形流公式對該問題進(jìn)行建模，設(shè)計了一種方法來估計所用人員的數(shù)量下限，并采用模擬退火算法進(jìn)行求解。在移動醫(yī)療護(hù)理領(lǐng)域，通常需要多名工作人員共同服務(wù)一名病人，人員調(diào)度中同時需要考慮時間窗和人員同步約束[7]。類似地，在機(jī)場地面服務(wù)中，飛機(jī)停靠不同地點(diǎn)，不同職責(zé)的地勤人員被安排處理行李、飛機(jī)清潔和飛機(jī)維修檢查等工作[8]。文獻(xiàn)[9-11]分別使用自適應(yīng)大規(guī)模領(lǐng)域搜索算法（Adaptive Large-scale Neighborhood Search，ALNS）[12]求解VRP 問題的不同標(biāo)題，結(jié)果表明相對于其他算法，ALNS求解效率與質(zhì)量更好。

本文以某大型國際樞紐機(jī)場為例，綜合考慮服務(wù)時間窗約束，多需求同時服務(wù)等約束，設(shè)計出改進(jìn)的自適應(yīng)大規(guī)模鄰域搜索算法求解此復(fù)雜而實(shí)際的客艙清潔人員調(diào)度問題。并通過數(shù)值實(shí)驗和與Gurobi 優(yōu)化求解器求解結(jié)果比較表明，本文設(shè)計的ALNS 在求解客艙清潔人員調(diào)度問題上，其求解結(jié)果穩(wěn)定且優(yōu)質(zhì)。

1 問題描述與數(shù)學(xué)模型

機(jī)場客艙清潔人員調(diào)度問題可進(jìn)行如下描述。給定一個有向圖G=(V,A)，其中表示有向圖的弧集，tij為經(jīng)過弧(i,j)∈A的時間；為所有點(diǎn)集，0 點(diǎn)表示清潔人員的休息區(qū)，調(diào)度開始前所有清潔人員從休息區(qū)出發(fā)。每個清潔任務(wù)i∈N的資源需求為ri。

對于所有清潔任務(wù)i,i∈N，其任務(wù)服務(wù)時長為wi，計劃開始服務(wù)時間窗為[ei,li]，清潔人員早于ei到達(dá)不能立即開始服務(wù)，晚于li到達(dá)開始計算延誤時長，并會產(chǎn)生延誤成本。對于清潔人員的休息區(qū)，s0= 0。設(shè)K為機(jī)場所有客艙清潔人員的集合。客艙清潔人員調(diào)度問題中涉及的成本分別為任務(wù)延誤成本和資源轉(zhuǎn)移成本。清潔任務(wù)i∈N的延誤成本由延誤時長與單位延誤成本所得，對清潔人員k∈K的轉(zhuǎn)移成本由轉(zhuǎn)移時長與單位轉(zhuǎn)移成本所得。

在上述問題描述的基礎(chǔ)上，引入以下變量并構(gòu)建問題的數(shù)學(xué)模型。

xijk：若xijk= 1，則表示清潔人員k執(zhí)行從任務(wù)i到任務(wù)j的服務(wù)路線，否則xijk= 0。

si：清潔任務(wù)i的開始服務(wù)時間。

di：清潔任務(wù)i的延誤時長。

目標(biāo)（1）是最小化客艙清潔任務(wù)延誤成本和清潔人員轉(zhuǎn)移成本，α和β分別是延誤時間和轉(zhuǎn)移時間的成本系數(shù)。式（2）表示保證所有客艙清潔任務(wù)滿足標(biāo)準(zhǔn)人力需求。式（3）表示清潔人員k 服務(wù)前后兩清潔任務(wù)必須滿足服務(wù)時間和轉(zhuǎn)移時間約束，其中M為極大值。式（4）～（5）表示所有客艙清潔人員從休息區(qū)出發(fā)，并最終返回到休息區(qū)。式（6）是客艙清潔人員的流平衡約束，表示清潔人員服務(wù)完成任務(wù)i后必須從任務(wù)i出發(fā)前往下一個任務(wù)進(jìn)行服務(wù)。式（7）表示客艙清潔任務(wù)的延誤時長，如果si≥li，di=si-li，否則di= 0。式（8） ～（10）表示各變量的取值范圍。

2 求解算法

2.1 算法架構(gòu)

本文中的VRPMS 問題是VRP 問題的拓展，因此也是一個NP-hard 問題。通過使用商業(yè)求解器對該問題的數(shù)學(xué)模型進(jìn)行求解可知，精確算法只能求解小規(guī)模數(shù)據(jù)，但實(shí)際應(yīng)用中的調(diào)度規(guī)模往往比較大，為了應(yīng)對實(shí)際中客艙清潔人員調(diào)度問題，本文設(shè)計了改進(jìn)的ALNS算法。

ALNS 算法的基本流程如圖1 所示。首先通過貪心算法構(gòu)建問題的初始解s，并設(shè)置為當(dāng)前解；然后在后續(xù)每一次迭代過程中，將q個任務(wù)隨機(jī)選擇一種移除算法從當(dāng)前解中移除，接著將這q個任務(wù)隨機(jī)選擇一種修復(fù)算法修復(fù)到當(dāng)前解中，進(jìn)而得到一個新解s′；將退火機(jī)制引入到新解s′的判斷中；最終迭代到指定次數(shù)后終止。

圖1 ALNS算法流程

本文ALNS 算法的移除和修復(fù)算法權(quán)重的更新主要使用輪盤賭的方式進(jìn)行選擇，假設(shè)wi為第i中方法的權(quán)重，開始迭代時所有算法的初始權(quán)重為w0。修復(fù)算法和移除算法權(quán)重的更新方式相同，但兩者的選擇相互獨(dú)立。迭代過程中，修復(fù)與移除算法權(quán)重的更新主要根據(jù)新解s′的表現(xiàn)進(jìn)行打分。打分情況分為新的最優(yōu)解、比當(dāng)前解好、比當(dāng)前解差但被接受了，得分為σ1,σ2,σ3。本文各方法的權(quán)重更新以50 次迭代為一周期，一個周期結(jié)束后對各種移除和修復(fù)算法進(jìn)行評分調(diào)整。設(shè)wij表示算法i在第j段中的權(quán)重；πij表示算法i在第j段中的總得分、θij表示算法i在第j段中被選用的次數(shù)，則算法i在第j+ 1段的權(quán)重更新如式（11）所示。

式中：λ為影響因子，表明權(quán)重受新評分影響的程度。

2.2 初始解與時間更新機(jī)制

2.2.1 構(gòu)建初始解

本文初始解的建立基于貪婪算法，客艙清潔人員調(diào)度模型中帶有軟時間窗約束，因此生成初始解時優(yōu)先考慮插入位置的延誤成本。初始解的主要構(gòu)建步驟如下。

（1）定義D為未安排資源的清潔任務(wù)，令D=N。（2）當(dāng) ||D＞0 時，①隨機(jī)選擇一個任務(wù)i∈D，②計算任務(wù)i插入到各資源路徑中的插入成本P(s)，③將任務(wù)i插入P(s)最小值對應(yīng)的位置，令D=D-{}i，返回步驟2。

（3）輸出初始解。

2.2.2 時間更新機(jī)制

由于多需求同時服務(wù)任務(wù)同時需要多個清潔人員繼續(xù)服務(wù)，這使得清潔人員的路徑通常是相互關(guān)聯(lián)的。當(dāng)此類任務(wù)的開始服務(wù)時間發(fā)生調(diào)整，將會影響該任務(wù)所涉及的資源路徑，這些資源路徑后續(xù)任務(wù)的開始服務(wù)時間理應(yīng)跟著發(fā)生調(diào)整，這種影響存在傳遞性。ALNS 算法在對當(dāng)前解進(jìn)行插入或者移除過程中，需要對插入或移除任務(wù)后當(dāng)前解中各任務(wù)節(jié)點(diǎn)的服務(wù)時間進(jìn)行更新，并且需要更新當(dāng)前路徑的成本。

為了實(shí)現(xiàn)快速調(diào)整任務(wù)發(fā)生變化后各節(jié)點(diǎn)時間的變化，將一種“時間更新機(jī)制”引入到算法中。當(dāng)有任務(wù)插入到現(xiàn)有解后，首先找到該任務(wù)的所有后續(xù)任務(wù)，假設(shè)為集合H，對集合H中的任務(wù)根據(jù)開始服務(wù)時間升序排列；然后，按照集合H的中任務(wù)順序依次更新任務(wù)的開始服務(wù)時間。以圖2 展示的插入例子為例，圖2 （a）中3 各清潔人員的服務(wù)路徑，其中線條表示路徑，圓表示任務(wù)，方框表示清潔人員休息區(qū)，現(xiàn)有路徑為A1:1 →3 →6,A2:2 →3 →5,A3:2 →4 →5。假設(shè)任務(wù)7插入到A2 路徑中，如圖2 （b）所示。首先獲取任務(wù)7的所有后續(xù)任務(wù)集合H={3,5,6}，對集合H進(jìn)行升序排列，按照任務(wù)開始服務(wù)時間順序逐個進(jìn)行服務(wù)時間更新。首先調(diào)整任務(wù)3，如圖2 （c）所示，最后調(diào)整任務(wù)5 和6，如圖2 （d）所示。

圖2 服務(wù)時間調(diào)整例子

2.3 移除算法

本節(jié)分別介紹隨機(jī)移除法、最壞路徑移除法、Shaw移除法和最壞值移除法。它們的共同目的是從當(dāng)前解中移除q個任務(wù)，并在移除后通過時間更新機(jī)制更新路徑中每一個任務(wù)的服務(wù)時間。其中，引入?yún)?shù)p增加Shaw移除法和最壞值移除算法的隨機(jī)性，以便擴(kuò)大搜索范圍、避免陷入局部最優(yōu)。

2.3.1 隨機(jī)移除法

隨機(jī)移除法從當(dāng)前解中隨機(jī)選擇q個任務(wù)，然后將這q個任務(wù)從解中移除。由于隨機(jī)性較高，修復(fù)后質(zhì)量不穩(wěn)定，但是運(yùn)算速度快。

2.3.2 最壞路徑移除法

最壞路徑移除法是從已有路徑中選擇成本最高的路徑，移除該路徑上所有任務(wù)。若移除的任務(wù)數(shù)少于q位，則再選擇成本次高的路徑進(jìn)行移除。重復(fù)此過程知道移除總數(shù)不小于q位。

2.3.3 Shaw移除法

Shaw 移除法是由Shaw[13]在1997年提出，通過任務(wù)之間的共同屬性計算不同任務(wù)的相似度，從當(dāng)前路徑中移除相似度較高的任務(wù)。實(shí)驗表明，移除相似的任務(wù)可以幫助后續(xù)路徑修復(fù)得到更優(yōu)的解，而移除相似度較低的任務(wù)會得到較差或原來的結(jié)果。

本文任務(wù)間相似度的定義是通過任務(wù)的最早開始服務(wù)時間、服務(wù)時長以及相對距離同時引入φ、ω和τ作為三者的權(quán)重計算而得。具體的計算公式如式（11）所示。

圖3 為Shaw 移除法的算法流程。首先在路徑任務(wù)集合L中隨機(jī)選擇一個任務(wù)r，并將r放入移除任務(wù)集合D中；接著，在移除任務(wù)集合D中隨機(jī)一個任務(wù)i，計算當(dāng)前路徑任務(wù)集合L中所有任務(wù)與任務(wù)i的相似度R(i,j)，然后根據(jù)公式選擇一個相似度較高的任務(wù)移除路徑，其中y是服從[0,1）均勻分布的隨機(jī)數(shù)，p是增加算法隨機(jī)性的參數(shù)。

2.3.4 最壞值移除法

最壞值移除法是將當(dāng)前解中移除成本較高的任務(wù)移出當(dāng)前路徑。圖4 為該方法的算法流程。計算所有任務(wù)從當(dāng)前解移出后的成本減少量ci，然后根據(jù)選擇一個移出成本較高的任務(wù)進(jìn)行移出，其中y是服從[0,1）均勻分布的隨機(jī)數(shù)，p是增加算法隨機(jī)性的參數(shù)。

圖4 最壞移除法的流程

2.4 修復(fù)算法

本節(jié)介紹的修復(fù)算法主要由貪婪修復(fù)法和后悔值修復(fù)法，按一定優(yōu)先規(guī)則將已移除的任務(wù)重新插入到當(dāng)前路徑中并產(chǎn)生新解，每次插入過程中需要對任務(wù)進(jìn)行時間調(diào)整。

2.4.1 貪婪修復(fù)法

貪婪修復(fù)法的具體步驟如圖5 所示。首先計算在移出集合D中所有任務(wù)插入現(xiàn)有路徑后總成本的增加量，Δg(i)為所有增量中的最小值，h(i)代表Δg(i)對應(yīng)的最優(yōu)位置。選擇集合D所有任務(wù)中Δg(i)最小的值相應(yīng)的任務(wù)r，將任務(wù)r的插入到h(r)對應(yīng)的位置上。重復(fù)上述過程，直到所有任務(wù)都被重新插入為止。

圖5 貪婪修復(fù)法的流程

2.4.2 后悔值修復(fù)法

后悔值修復(fù)法的具體步驟如圖6 所示。該算法參考貪婪修復(fù)法計算每一位在移除集合D中的任務(wù)i插入到現(xiàn)有服務(wù)路徑各位置后路徑總成本的增加量。然后將各增量升序,第i位的值為Δgj(i)，h(i)代表Δg1(i)對應(yīng)的最優(yōu)位置。任務(wù)i插入到最優(yōu)位置的后悔值計算公式為：

圖6 后悔值修復(fù)法的流程

選擇集合D所有任務(wù)中Δr(i)最小的值相應(yīng)的任務(wù)r，將任務(wù)r的需求插入到h(r)對應(yīng)的位置上。重復(fù)以上的步驟，直到所有移除集合D中的所有任務(wù)都重新插入到路徑中。

2.5 接受新解和算法終止

產(chǎn)生新解s′后，還需對s′進(jìn)行判斷能否被接受。為了避免算法陷入局部最優(yōu)，本文算法引入了退火機(jī)制。對于比當(dāng)前解s差的新解s′，以一定的概率f接受s′。f的計算方法如式（14）所示。本算法采用最大迭代數(shù)作為算法的終止準(zhǔn)則。

3 算法實(shí)驗

本文的實(shí)驗數(shù)據(jù)選取某大型機(jī)場的航班信息，對應(yīng)的客艙清潔任務(wù)整理生成多種規(guī)模算例進(jìn)行求解實(shí)驗。并通過與Gurobi9.5 求解器的求解結(jié)果進(jìn)行對比，驗證了混合整數(shù)規(guī)劃模型的正確性和ALNS 算的有效性與高效性。程序都在Windom 環(huán)境下，硬件環(huán)境包括AMD（R） Core （TM） 3700X CPU @ 3.60 GHz，16.00 GB 內(nèi)存。Gurobi限定求解時間為3 600 s，ALNS限制最大迭代次數(shù)為3 000次。

3.1 算例說明和參數(shù)設(shè)置

算例數(shù)據(jù)來源于機(jī)場實(shí)際的客艙清潔人員調(diào)度背景，為了驗證算法在不同規(guī)模下的有效性與高效性，分別設(shè)計小、中、大3 種規(guī)模。小規(guī)模的清潔人員數(shù)量Knum∈{15,20}，清潔任務(wù)數(shù)量Nnum∈{15,20,25} ；中規(guī)模清潔人員數(shù)量Knum∈{35,40} ， 清潔人員數(shù)量Nnum∈{40,45,50} ；大規(guī)模清潔人員數(shù)量Knum∈{45,50}，清潔人員數(shù)量Nnum∈{}80,100,120 。利用18 個算例對σ1,σ2,σ3,p,λ做參數(shù)測試，結(jié)合參考文獻(xiàn)[14-16]，最終算法的參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)定

3.2 實(shí)驗結(jié)果對比分析

本節(jié)將Gurobi求解結(jié)果與本文ALNS算法的求解結(jié)果進(jìn)行對比分析。比較結(jié)果如表2 所示，其中“UB”和“LB”分別表示Gurobi結(jié)果的可行解和下界；“Time”為兩者方法的求解時間；“Gap”通過可行解和下界計算得來；“Best”表示10次求解結(jié)果中的最優(yōu)值，Avg表示10次求解結(jié)果的平均值，Time表示10次求解平均耗時；表中“精度”列表示ALNS相對于Gurobi的結(jié)果提升了程度；“—”表示Gurobi 未能在規(guī)定時間內(nèi)找到可行解，“*”表示Gurobi找到最優(yōu)解，加粗的結(jié)果表示兩者中結(jié)果較好的一個。

表2 ALNS算法與Gurobi求解結(jié)果比較

由表2 可知，本文設(shè)計的所有18 個算例中，ALNS算法的求解結(jié)果大部分都優(yōu)于或等于Gurobi的求解結(jié)果。對于小規(guī)模算例，Gurobi都能在1 s內(nèi)找到最優(yōu)解，同樣的ALNS 也能在較短的時間內(nèi)找到最優(yōu)解，同時10 次求解平均結(jié)果與最優(yōu)解也十分接近。對于中規(guī)模的6 個算例和大規(guī)模的6 個算例，Gurobi 均無法在3 600 s 內(nèi)求得任一精確解，同時大規(guī)模算例中有3 個算例Gurobi 無法在規(guī)定時間內(nèi)找到可行解。在中大規(guī)模的12 個算例中，Gurobi 僅有4 個算例的結(jié)果優(yōu)于ALNS，同時ALNS 的算法的平均結(jié)果與Gurobi 可行解的精度相差在8%以內(nèi)，其余8 個算例ALNS 的求解結(jié)果均優(yōu)于Gurobi 求解結(jié)果。在運(yùn)行效率上，Gurobi 對于中大規(guī)模的算例相對比較耗時，求解效率不高，ALNS 算法的求解時間雖然也會因規(guī)模的變大而增大，但總體求解時間相對較低。

綜上所述，無論是有效性還是求解效率上，ALNS算法的結(jié)果更優(yōu)。

4 結(jié)束語

本文描述了帶任務(wù)服務(wù)時間窗和多需求同時服務(wù)的客艙清潔人員的調(diào)度問題，建立其混合整數(shù)規(guī)劃數(shù)學(xué)模型，為求解該問題設(shè)計了一種結(jié)合貪婪算法生成初始解的自適應(yīng)大規(guī)模領(lǐng)域搜索算法。結(jié)果表明，ALNS 算法能夠得到該問題穩(wěn)定且優(yōu)質(zhì)的調(diào)度方案，對實(shí)際的清潔人員調(diào)度有很強(qiáng)的指導(dǎo)意義。從與Gurobi 對比的實(shí)驗結(jié)果可以看出，該算法的設(shè)計合理且高效，其求解結(jié)果無論是在效率和質(zhì)量上均優(yōu)于大型商業(yè)求解器，對日常的客艙清潔人員調(diào)度問題提供了新的解決方案。當(dāng)前的研究主要集中在任務(wù)到達(dá)、任務(wù)服務(wù)時長靜態(tài)的條件下，而在不確定性方面，可以繼續(xù)開展在任務(wù)到達(dá)與作業(yè)時長隨機(jī)條件下的客艙清潔人員調(diào)度方面的研究。