基于ALNS算法的機(jī)場(chǎng)客艙清潔人員調(diào)度研究

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

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

0 引言

全球貨運(yùn)量和客運(yùn)量的持續(xù)增長(zhǎng)給機(jī)場(chǎng)服務(wù)帶來(lái)了很大的挑戰(zhàn)。不斷增長(zhǎng)的客機(jī)數(shù)量也給客艙清潔人員的調(diào)度帶來(lái)了巨大的壓力，當(dāng)前我國(guó)機(jī)場(chǎng)客艙清潔人員調(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ì)量以及公平性一般要求所有清潔人員到位后才能開(kāi)始清潔任務(wù)[1]。因此，機(jī)場(chǎng)客艙清潔人員調(diào)度問(wèn)題本質(zhì)上是一個(gè)具有同步約束的人員路徑規(guī)劃問(wèn)題（Manpower Routing Problem with Simultaneous Constraints,MRPSC），是經(jīng)典的帶時(shí)間窗的車(chē)輛路徑規(guī)劃問(wèn)題的擴(kuò)展[2]。MRPSC 的任務(wù)需要若干人員到同一個(gè)地理位置執(zhí)行一組工作；同時(shí)每項(xiàng)任務(wù)都有1 個(gè)地點(diǎn)，1 個(gè)處理時(shí)間和1 個(gè)時(shí)間窗口，人員數(shù)量及技能需求。人員可以在不同的時(shí)間到達(dá)工作地點(diǎn)，但任務(wù)需在所有人員都到位后開(kāi)始，即存在同步約束[3-4]。經(jīng)典車(chē)輛路徑規(guī)劃問(wèn)題及其擴(kuò)展中，車(chē)輛路徑是獨(dú)立的，不受其他車(chē)輛的影響。然而，MRPSC 中的路線通常相互關(guān)聯(lián)，某人員路徑的改變可能使得其他人員的路徑不合法。MRPSC 是具有多重同步約束的（Vehicle Routing Problem，VRP）的一種類型，其中可能或必須使用一個(gè)以上的車(chē)輛或資源來(lái)完成一項(xiàng)任務(wù)[5]。

MRPSC 在很多領(lǐng)域得到了應(yīng)用。在港口服務(wù)領(lǐng)域，Li 等[6]研究了有時(shí)間窗和工作團(tuán)隊(duì)約束的人力配置問(wèn)題，采用弧形流公式對(duì)該問(wèn)題進(jìn)行建模，設(shè)計(jì)了一種方法來(lái)估計(jì)所用人員的數(shù)量下限，并采用模擬退火算法進(jìn)行求解。在移動(dòng)醫(yī)療護(hù)理領(lǐng)域，通常需要多名工作人員共同服務(wù)一名病人，人員調(diào)度中同時(shí)需要考慮時(shí)間窗和人員同步約束[7]。類似地，在機(jī)場(chǎng)地面服務(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 問(wèn)題的不同標(biāo)題，結(jié)果表明相對(duì)于其他算法，ALNS求解效率與質(zhì)量更好。

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

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

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

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

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

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

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

di：清潔任務(wù)i的延誤時(shí)長(zhǎng)。

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

2 求解算法

2.1 算法架構(gòu)

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

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

圖1 ALNS算法流程

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

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

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

2.2.1 構(gòu)建初始解

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

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

（3）輸出初始解。

2.2.2 時(shí)間更新機(jī)制

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

為了實(shí)現(xiàn)快速調(diào)整任務(wù)發(fā)生變化后各節(jié)點(diǎn)時(shí)間的變化，將一種“時(shí)間更新機(jī)制”引入到算法中。當(dāng)有任務(wù)插入到現(xiàn)有解后，首先找到該任務(wù)的所有后續(xù)任務(wù)，假設(shè)為集合H，對(duì)集合H中的任務(wù)根據(jù)開(kāi)始服務(wù)時(shí)間升序排列；然后，按照集合H的中任務(wù)順序依次更新任務(wù)的開(kāi)始服務(wù)時(shí)間。以圖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}，對(duì)集合H進(jìn)行升序排列，按照任務(wù)開(kāi)始服務(wù)時(shí)間順序逐個(gè)進(jìn)行服務(wù)時(shí)間更新。首先調(diào)整任務(wù)3，如圖2 （c）所示，最后調(diào)整任務(wù)5 和6，如圖2 （d）所示。

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

2.3 移除算法

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

2.3.1 隨機(jī)移除法

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

2.3.2 最壞路徑移除法

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

2.3.3 Shaw移除法

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

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

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

2.3.4 最壞值移除法

最壞值移除法是將當(dāng)前解中移除成本較高的任務(wù)移出當(dāng)前路徑。圖4 為該方法的算法流程。計(jì)算所有任務(wù)從當(dāng)前解移出后的成本減少量ci，然后根據(jù)選擇一個(gè)移出成本較高的任務(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)生新解，每次插入過(guò)程中需要對(duì)任務(wù)進(jìn)行時(shí)間調(diào)整。

2.4.1 貪婪修復(fù)法

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

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

2.4.2 后悔值修復(fù)法

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

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

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

2.5 接受新解和算法終止

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

3 算法實(shí)驗(yàn)

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

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

算例數(shù)據(jù)來(lái)源于機(jī)場(chǎng)實(shí)際的客艙清潔人員調(diào)度背景，為了驗(yàn)證算法在不同規(guī)模下的有效性與高效性，分別設(shè)計(jì)小、中、大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 個(gè)算例對(duì)σ1,σ2,σ3,p,λ做參數(shù)測(cè)試，結(jié)合參考文獻(xiàn)[14-16]，最終算法的參數(shù)設(shè)置如表1所示。

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

3.2 實(shí)驗(yàn)結(jié)果對(duì)比分析

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

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

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

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

4 結(jié)束語(yǔ)

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