樊小毛，熊紅林，趙淦森，3*

（1.華南師范大學計算機學院，廣州 510631；2.上海理工大學管理學院，上海 200093；3.華南師范大學廣州市云計算安全與測評技術重點實驗室，廣州 510631）

（*通信作者電子郵箱gzhao@m.scnu.edu.cn）

0 引言

清潔服務人員是保潔服務公司日常運營的基礎，科學合理地安排清潔人員的工作時間不僅能夠緩解其壓力，提高服務質(zhì)量，還能降低保潔服務公司的運營成本。因此，制定一個合理的清潔人員排班方案已成為保潔服務公司日常管理工作的重要內(nèi)容之一。在實際清潔排班問題中，往往存在諸多清潔任務約束，比如每周可用的清潔人員工作時間、清潔服務單位數(shù)量、清潔服務單位的清潔區(qū)域數(shù)量，清潔區(qū)域服務樓層數(shù)及不同的清潔服務要求等，使得清潔排班問題變得極其復雜，屬于一個典型的組合優(yōu)化NP難問題。近年來，國內(nèi)外研究較多的排班問題有護士排班問題［1-3］、航空公司飛機排班問題［4-7］、軌道交通線路排班問題［8-10］、排課問題［11-13］等，尚未見有對清潔排班問題進行討論。目前，保潔服務公司主要依靠人工排班，不僅需要花費大量的人力，而且人工給出的清潔排班方案質(zhì)量不穩(wěn)定，缺乏行之有效的優(yōu)化機制，難以綜合考慮不同地點、不同樓層、不同清潔服務要求的約束。迄今為止，還未見針對帶約束的清潔排班問題提出有效的數(shù)學模型，這正是本文的研究目的之一。

本文提出了帶有約束的清潔排班問題的通用數(shù)學模型。由于該問題屬于一個組合優(yōu)化NP 難問題，一般情況下，解決這類問題還未有通用的優(yōu)化方法。目前，通常采用啟發(fā)式智能優(yōu)化方法來解決類似問題，如模擬退火（Simulating Annealing，SA）算法［14］，蟻群優(yōu)化（Ant Colony Optimization，ACO）算法［15，19］，粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［11，20］、蜂群優(yōu)化（Bee Colony Optimization，BCO）算法［16-18，21］等。由于啟發(fā)式智能優(yōu)化算法在求解NP難問題過程中，除了具有強大的局部尋優(yōu)能力外，一般都有跳出局部最優(yōu)解的機制，使得其具有較好的跳出局部最優(yōu)解的能力并獲得較優(yōu)解甚至是全局最優(yōu)解。因此，本文利用上述SA、ACO、PSO 和BCO 對所提帶有約束的清潔排班模型進行求解，并以某清潔服務公司實際排班情況進行了實證分析，實驗結果表明本文提出的清潔排班模型和啟發(fā)式智能優(yōu)化算法求解具有較好的可行性和有效性。

1 清潔排班問題及數(shù)學模型

本文研究的清潔排班問題是指：在一系列的特定清潔服務約束條件下，編制一套排班周期（如一年或兩年）內(nèi)所有的清潔服務工作方案，使得各個清潔周期（可以周為單位）所需總清潔時長盡可能均衡，避免某個清潔周期所需清潔時間過多或者過少。

一般情況下，清潔排班方案受以下兩個條件約束：

1）針對某一個清潔區(qū)域，如果清潔級別要求高的清潔服務工作與清潔級別要求低的清潔服務工作安排在同一時期內(nèi)，選擇清潔級別要求高的清潔服務工作，清潔級別要求低的工作排班取消；如果在不同的清潔區(qū)域，則不受此限制。

2）由于不同級別要求的清潔服務工作其清潔所需周期不同，清潔級別要求低的清潔服務工作的周期短，清潔級別要求高的清潔服務工作的周期長（如大清潔一年一次或半年一次，小清潔一周一次或2 周一次）。不同級別的清潔服務工作在其清潔周期內(nèi)，必須安排一次對應的清潔服務工作，除非在同一時間內(nèi)，已經(jīng)安排了更高級別要求的清潔服務工作。

以某個保潔服務公司的清潔排班方案為例，總的排班周期為6 周（W1～W6），3 個清潔區(qū)域（b1～b3）和3 種不同級別要求清潔方法的清潔服務工作的排班方案，表1 是其二維表表示。在表1 中，每行表示在排班周期為6 周內(nèi)，某個清潔區(qū)域的某個級別的清潔服務工作的排班方案情況，“0”表示為不安排清潔工作，“1”表示安排清潔工作。如果表1 中排班方案滿足上訴特定約束，則為可行的清潔服務排班方案，否則為不可行清潔服務排班方案。

針對上述清潔排班問題，本文提出了如下的通用清潔排班數(shù)學模型：

其中：T表示為一個排班周期；aij表示為第j個清潔區(qū)域的第i種清潔方法；bj表示為第j個清潔區(qū)域的面積；xijk表示為第j個清潔區(qū)域的第i種級別的清潔工作在第k個時期內(nèi)是否安排排班，安排為1，否則為0；Sij表示為第j個清潔區(qū)域的第i種級別的清潔工作的開始時期；Fij表示為第j個清潔區(qū)域的第i種級別的清潔工作的周期；lij表示為大于等于0 的整數(shù)。式（1）定義了帶約束清潔排班問題的目標函數(shù)，即所有清潔區(qū)域的每時期的工作時總和與每時期的所有清潔區(qū)域的平均工作時之差的平方和最小，其中為所有清潔區(qū)域的每時期的總清潔工作時長總和，為每時期的所有清潔區(qū)域的平均工作時。式（2）保證了該排班方案符合約束條件（1）。式（3）表示xijk的取值情況，在滿足條件：對于任 何k=Sij+lijFij，且 滿 足lij∈N時，xijk取值為1，否則為0。

2 啟發(fā)式智能優(yōu)化算法思想

本文基于四種啟發(fā)式智能優(yōu)化算法即模擬退火優(yōu)化算法、蜂群優(yōu)化算法、蟻群優(yōu)化算法和粒子群優(yōu)化算法對帶約束的清潔排班進行求解。

2.1 SA算法

SA 算法［14］的思想是模擬加熱的固體慢慢冷卻直到結晶的過程。在非常高的溫度下，物體原子具有高能量，使其能夠自由重新組織物體結構；隨著溫度的下降，物體原子的能量減少，直到其能量降到最低狀態(tài)。在優(yōu)化算法層面，SA 算法的初始溫度始于非常高的溫度Tmax，使算法具有較大的范圍搜索解空間。SA 算法是一種貪心算法，因為在搜索過程中引入了一定的隨機因素。在迭代更新可行解時，以一定的概率來接受一個比當前解要差的解，因此有可能會跳出這個局部的最優(yōu)解，達到全局的最優(yōu)解。SA算法的計算步驟如下：

步驟1 初始化初始解S、初始最高溫度Tmax、最低溫度Tmin和迭代次數(shù)NGEN。

步驟2 迭代t=1，2，…，COUNTER，執(zhí)行步驟3～6。

步驟3 在鄰域內(nèi)隨機擾動，更新產(chǎn)生新的解Snew，其中，Snew=S+Rand×Range。Rand為隨機數(shù)，范圍在［0，1］；Range為變化范圍，本文Range參數(shù)設置為[-4，4]。

步驟4 計算適應度增量Fdelta=F(Xnew)-F(X)，其中F為適應度函數(shù)。

步驟5 若Fdelta小于0，接受Xnew作為新的解；否則，以概率接受Xnew作為新的解。

步驟6 如果滿足算法結束條件（如適應度值變化持續(xù)小于特定值），轉(zhuǎn)步驟2。

步驟7 溫度參數(shù)T逐漸降低，若T＞Tmin，轉(zhuǎn)步驟2，否則結束算法。

步驟8 記錄最優(yōu)解和最優(yōu)值。

2.2 BCO算法

眾所周知，蜜蜂群體具有非常強的覓食行為，在方圓10 km 左右的范圍內(nèi)能夠搜索到大量的食物源［17，21］。最早，Seeley 教授提出了蜜蜂自組織模型和群體智能的自組織模擬模型，基于此模型，D.T.Pham建立了BCO算法［18］。BCO的基本原理是：較多的蜜蜂采集質(zhì)量高、數(shù)量相對多的食物源，而只有很少的蜜蜂去采集那些質(zhì)量低、數(shù)量相對較少的食物源。該算法具有簡單、魯棒性強等特點。

根據(jù)蜂群的采蜜主要行為特點，基本的BCO 算法模型是：搜索食物源、招募蜜蜂和放棄食物源。在開始覓食時，所有的蜜蜂都是偵察蜂，負責搜索所有可能的新食物源。搜索過程中，偵察蜂不斷地從一個食物源飛往另外一個食物源，搜索所有可能的食物源。即使在收獲季節(jié)，蜂群中還有一定數(shù)量的偵察蜂隨機地搜索新的食物源。當偵察蜂搜索到食物源的收益度（比如糖的含量）超過一定量的時候，它們會返回蜂巢，卸下蜂蜜并在舞蹈區(qū)跳“搖擺舞”。神奇的“搖擺舞”是蜂群交流信息的必要的工具，能使整個蜂群了解食物源的收益度和方位。跳舞完后的偵察蜂轉(zhuǎn)為引領蜂，帶領守候在蜂巢外的跟隨蜂飛往其相應的食物源采蜜。質(zhì)量高、數(shù)量相對多的食物源能夠招募到相對多的跟隨蜂前往采蜜。在采蜜時，評估其正在采蜜的食物源的質(zhì)量及數(shù)量，返回蜂巢時，與同伴分享其食物源的質(zhì)量及數(shù)量信息。如果食物源質(zhì)量及數(shù)量仍然較高，更多的跟隨蜂將前往采蜜；否則，將放棄當前食物源轉(zhuǎn)為跟隨蜂或者偵察蜂。

求解帶約束的清潔排班問題，也就是搜尋食物源的過程，每個食物源即代表一組可行解。

初始時刻，所有蜜蜂的角色都是偵察蜂。隨機搜索到食物源后，返回蜂巢的舞蹈區(qū)，通過比較食物源收益度的大小，偵察蜂轉(zhuǎn)變?yōu)樯鲜鋈我环N角色的蜜蜂。轉(zhuǎn)換規(guī)則如下：

1）當所采集食物源的收益度相對很低時，再次成為偵察蜂繼續(xù)搜尋蜂巢附近的食物源，其轉(zhuǎn)變結果是放棄上次采集的食物源；

2）當所采集食物源的收益度排名比例在臨界值theta后時，在舞蹈區(qū)觀察完舞蹈后，轉(zhuǎn)變?yōu)楦S蜂，并前往相應的食物源采蜜；

3）當所采集食物源的收益度排名在臨界值θ前時，它轉(zhuǎn)變?yōu)橐I蜂，帶領跟隨蜂前往相應的食物源采蜜。

在BCO 算法中，需要設置的參數(shù)為：蜜蜂總數(shù)（n）、食物源收益度排名臨界值（θ）和搜索鄰域（ngh）。

因此，BCO算法可歸納為：

步驟1 初始時刻，所有的蜜蜂（n）都是偵察蜂。

步驟2 評估食物源的收益度。

步驟3 選擇在收益度排名在前θ的食物源作為搜索鄰域的食物源（m），其中m為θ×n向下取整。

步驟4 確定搜索鄰域（ngh）。

步驟5 招募跟隨蜂到食物源（m）采蜜（收益度越高招募的跟隨蜂越多）。

步驟6 每個鄰域搜索的食物源只保留一個引領蜂。

步驟7 繼續(xù)在鄰域內(nèi)搜索，轉(zhuǎn)到步驟3 直到條件不滿足。

步驟8（n-m）個剩余的蜜蜂隨機搜索新的食物源。

步驟9 形成新的偵察蜂群體，轉(zhuǎn)到步驟2 直到條件不滿足。

步驟10 記錄最優(yōu)值。

2.3 ACO算法

ACO算法被M.Dorigo最早提出［19］，其算法思想是模擬蟻群覓食行為過程。最初的ACO 算法用于求解旅行商問題（Traveling Salesman Problem，TSP），其基本原理為：初始將M只螞蟻置于N個城市中的始發(fā)地，即可行解上，每只螞蟻以一定的概率到達下一個城市，螞蟻經(jīng)過的城市之間的路徑形成邊，且根據(jù)路徑的遠近釋放不同的信息素作為下一只螞蟻是否選擇該路徑的參考，整群螞蟻選擇的路徑作為待優(yōu)化的解空間。隨著時間的推移，距離短的路徑信息素越來越濃，距離長的路徑信息素稀少。最后，基于蟻群系統(tǒng)的正負反饋機制，整個蟻群可搜索到最佳路徑上，即問題的相對最優(yōu)解。由于本文求解的為組合優(yōu)化離散問題，標準的ACO 算法需做適當?shù)淖兓唧w步驟為：

步驟1 初始化M只螞蟻位置，即待優(yōu)化問題的初始解S，迭代次數(shù)NGEN，信息揮發(fā)系數(shù)ρ=0.4，信息釋放總量Q=1.0。

步驟2 初始化信息素τ為初始解S的適應度函數(shù)值F(S)，其信息轉(zhuǎn)移概率為Pi為整群螞蟻中最大的信息素τmax與當前螞蟻信息素τ的差值占τ的比重。

步驟3 迭代t=1，2，…，NGEN，執(zhí)行步驟4～7 的計算過程。

步驟4 根據(jù)概率Pi更新螞蟻的當前位置Snew，其更新規(guī)則為：若Pi小于轉(zhuǎn)移概率P0（為常數(shù)，本文設置為0.5），則螞蟻的當前位置Snew=S+rands×λ。否則，螞蟻當前位置更新為Sλ=S+rands×Range。本文中的rands為隨機數(shù)，范圍為[-1，1]；參數(shù)λ隨迭代次數(shù)的增加而降低，本文設置為λ=1/t；可行解搜索范圍參數(shù)Range設置為[-4，4]。

步驟5 計算待求解優(yōu)化問題的適應度函數(shù)值和當前迭代過程中的最優(yōu)解。

步驟6 根據(jù)當前信息素τ更新下一時刻的信息素τnew=(1-ρ) ×τ+Q×F(S)。

步驟7 根據(jù)更新后蟻群位置，轉(zhuǎn)到步驟3 直到算法不滿足。

步驟8 記錄算法求解最優(yōu)值。

2.4 PSO算法

PSO 算法［11，20］源于模擬鳥群尋找食物的過程，且食物源只有一處，整個鳥群均知它們至食物源的距離，但是不知道食物源的具體位置，最快找到食物的方法是在鳥周圍的區(qū)域?qū)ふ译x食物最近的鳥。在PSO 算法中，每個粒子都有一個速度V，其決定了粒子的飛行方向和距離。每個粒子跟隨最優(yōu)粒子在解空間中搜索最優(yōu)解。其算法步驟具體為：

步驟1 初始化粒子群大小M，初始位置S，初始速度V。

步驟2 迭代t=1，2，…，NGEN，執(zhí)行步驟3～5 的計算過程。

步驟3 計算每個粒子的適應度函數(shù)值，并找到當前粒子極值的最優(yōu)位置Pbest，同時計算獲得整個粒子群的最優(yōu)值位置Gbest。

步驟4 更新每個粒子的速度和位置，具體為如下：

粒子速度更新為：

粒子位置更新為：

其中：W為慣性因子；C1和C2為加速度常數(shù)；rand為隨機數(shù)，范圍為［0，1］。

步驟5 判斷是否達到終止條件（如相鄰兩次迭代的偏差在指定的范圍1e-5），否則轉(zhuǎn)到步驟2。

步驟6 記錄算法求解最優(yōu)值。

3 案例計算

本文基于Java v1.6.0_10_rc2 和Python v3.7.7 實現(xiàn)四種啟發(fā)式智能優(yōu)化算法求解所提出的清潔排班模型，并且在某保潔服務公司實際清潔排班數(shù)據(jù)上進行了驗證，獲得了比較理想的結果。一個具體的帶約束的清潔排班案例為：排班周期為53 周(T=53)；10 個清潔區(qū)域，有4 種不同級別的清潔方法，具體排班約束數(shù)據(jù)見表2。針對此清潔排班問題，本文探索了SA、BCO、ACO 和PSO 進行問題求解，并且與基準排班方法（人工手動排班）進行比較。

1）基準排班方法。

根據(jù)現(xiàn)行某保潔服務公司的實際情況，需安排一個專業(yè)人員對該公司服務的區(qū)域進行清潔人員排班，使得每周清潔工作人力需求時盡可能少且每周的人力需求時變化幅度盡可能小。若需獲得一個相對合理的清潔排班方案，需要工作人員大約1～2 天的工作量。一般情況下，給出每項清潔工作的起始周WKstart，根據(jù)清潔排班問題約束即可退出具體的清潔排班方案。現(xiàn)有一個工作人員手工排班相對較優(yōu)的清潔排班方案，其起始周WKstart=［1，20，13，5，2，4，4，32，3，11，2，34，34，1，6，3，5，10，6，2，36，9］。該清潔排班方案的平均每周需清潔人力為87 h，每周最高需清潔人力為211.97 h，總清潔人力需4 612.20 h，具體排班人力需求結果如圖1（a）所示。

表2 某保潔服務公司排班的實際案例數(shù)據(jù)Tab.2 Real scheduling instance data of a cleaning service company

2）SA算法求解。

SA 算法需要設置的參數(shù)包括：初始最高溫度Tmax=1e5，初始最低溫度Tmin=1e-3，溫度退化系數(shù)k=0.98，迭代次數(shù)NGEN=1000。模擬退火優(yōu)化算法求解清潔排班問題結束后，獲得的最優(yōu)清潔排班方案的起始周為WKstart=［48，4，12，8，21，1，2，7，3，18，1，24，12，4，5，1，10，15，7，2，1，7］。該清潔排班方案的周平均需清潔人力82.9 h，周最高需清潔人力180.39 h，清潔人力總共需4 393.58 h，具體清潔排班人力需求如圖1（b）所示。

3）BCO算法求解。

利用BCO 算法自組織、自適應等特點求解，需要設置的參數(shù)為：n=100，θ=50%，ngh=16，nc=100（迭代次數(shù)）。BCO 算法獲得的最優(yōu)清潔排班方案的起始周WKstart=［32，8，20，4，13，1，1，6，2，19，3，23，11，3，4，8，22，46，6.2，2，12］。基于蜂群優(yōu)化算法排班方案的周平均需清潔人力為77.3 h，周最高需清潔人力177.04 h，總共需要清潔人力為4 098.89 h，具體的清潔排班結果如圖1（c）所示。

4）ACO算法求解。

ACO算法需要設置的初始化參數(shù)包括：蟻群大小M=500，迭代次數(shù)NGEN=200，信息素揮發(fā)系數(shù)ρ=0.4，信息素釋放總量Q=1.0。ACO 算法求解清潔排班問題獲得最優(yōu)值的起始周WKstart=［51，22，10，2，24，4，3，6，2，1，3，12，4，8，1，1，11，5，9，1，15，9］。ACO 算法排班方案的周平均需清潔人力為82.30 h，周最高需清潔人力192.72 h，總共需要清潔人力為4 362.92 h，具體的清潔排班結果如圖1（d）所示。

5）PSO算法求解。

PSO 算法求解清潔排班問題需要設置的參數(shù)有：粒子群大小M=200，迭代次數(shù)NGEN=100，慣性系數(shù)W=1.0，加速度常數(shù)C1=C2=2.0。PSO 算法獲得最優(yōu)排班方案的起始周為WKstart=［12，24，12，4，22，2，1，10，2，51，3，1，13，5，2，6，32，8，16，4，3，11］。PSO 算法排班方案的周平均清潔人力需78.60 h，周最大清潔人力需174.17 h，總清潔人力需4 165.86 h，具體的清潔排班結果如圖1（e）所示。

圖1 手工排班與四種啟發(fā)式算法求解的每周清潔工作實際人力需求Fig.1 Actual manpower requirements for weekly cleaning work solved by manual scheduling and four heuristic algorithms

6）清潔排班方案對比與討論。

如表3 所示，四種啟發(fā)式智能優(yōu)化算法在周平均清潔人力需求時、周最大清潔人力時和總清潔人力時等3 個清潔排班方案評價指標上均超過基準排班方法（手工清潔排班）。結果表明，在一個清潔排班周期內(nèi)，與手工清潔排班方法對比，SA 算法和ACO 算法求解清潔排班問題周平均清潔人力時需求降低了超過4 h，周最大清潔人力需求降低了超過19 h，總清潔人力時則降低了超過218 h。根據(jù)中國勞動法要求，人均工作8 h/天。因此，SA 算法和ACO 算法清潔排班每周可節(jié)省超過0.5 人天，一年可節(jié)省超過27 人天。BCO 算法和PSO 算法在求解帶約束的清潔排班問題上具有明顯的優(yōu)勢，可節(jié)省更多的清潔人力需求：平均每周工作時可以減少超過8 h，實際最大周工作時減少超過35 h，總工作時減少了446 h。即每周清潔人力需求可減少1 人天，周最大清潔人力需求可減少超過4 人天，一個清潔周期內(nèi)總清潔人力需求可減少55.7 人天。在求解帶約束的清潔排班問題上，BCO 算法和PSO 算法比SA算法和ACO算法更具優(yōu)勢。

表3 啟發(fā)式智能優(yōu)化算法排班與手工排班對比 單位：hTab.3 Comparison between scheduling by heuristic intelligent optimization algorithms and manual scheduling unit：h

因此，利用啟發(fā)式智能優(yōu)化算法求解清潔排班問題，一方面可以使排班人員從繁瑣的排班細節(jié)擺脫出來，提高了工作效率；另一方面，在一個排班周期內(nèi)，啟發(fā)式智能優(yōu)化求解的排班方案具有更短的總工作時，周平均工作時、最大的周工作時都有所減少。同時，筆者已經(jīng)實現(xiàn)了BCO 清潔排班算法基于Java 語言封裝成清潔排班工具包，并在某保潔服務公司正式使用，有效地節(jié)省了該保潔服務公司人力資源。

4 結語

本文提出了帶約束的清潔排班問題通用數(shù)學模型，探索了四種啟發(fā)式智能優(yōu)化算法進行求解，并在一個實際的保潔服務公司的排班數(shù)據(jù)上進行實證分析。與手工排班方案進行對比，實驗結果表明啟發(fā)式智能優(yōu)化算法求解帶約束的清潔排班問題具有明顯的優(yōu)勢。特別地，在一個53 周的清潔排班周期內(nèi)，與手工排班對比，蜂群優(yōu)化算法和粒子群優(yōu)化算法可節(jié)省清潔人力超過446.34 h（約55.7 人天）。其中，蜂群優(yōu)化算法清潔排班節(jié)省總清潔工作時最多，可高達513.3 h（約64.16 人天）。同時，啟發(fā)式智能優(yōu)化算法具有較好的收斂特性和尋優(yōu)能力，在實際操作上是可行的，同時為設計出求解清潔排班問題更優(yōu)的算法奠定了基礎。