帶約束的清潔排班問(wèn)題模型及其求解

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

（1.華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣州 510631；2.上海理工大學(xué)管理學(xué)院，上海 200093；3.華南師范大學(xué)廣州市云計(jì)算安全與測(cè)評(píng)技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣州 510631）

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

0 引言

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

本文提出了帶有約束的清潔排班問(wèn)題的通用數(shù)學(xué)模型。由于該問(wèn)題屬于一個(gè)組合優(yōu)化NP 難問(wèn)題，一般情況下，解決這類(lèi)問(wèn)題還未有通用的優(yōu)化方法。目前，通常采用啟發(fā)式智能優(yōu)化方法來(lái)解決類(lèi)似問(wèn)題，如模擬退火（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難問(wèn)題過(guò)程中，除了具有強(qiáng)大的局部尋優(yōu)能力外，一般都有跳出局部最優(yōu)解的機(jī)制，使得其具有較好的跳出局部最優(yōu)解的能力并獲得較優(yōu)解甚至是全局最優(yōu)解。因此，本文利用上述SA、ACO、PSO 和BCO 對(duì)所提帶有約束的清潔排班模型進(jìn)行求解，并以某清潔服務(wù)公司實(shí)際排班情況進(jìn)行了實(shí)證分析，實(shí)驗(yàn)結(jié)果表明本文提出的清潔排班模型和啟發(fā)式智能優(yōu)化算法求解具有較好的可行性和有效性。

1 清潔排班問(wèn)題及數(shù)學(xué)模型

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

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

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

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

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

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

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

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

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

2.1 SA算法

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

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

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

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

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

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

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

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

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

2.2 BCO算法

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

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

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

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

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

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

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

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

因此，BCO算法可歸納為：

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

步驟2 評(píng)估食物源的收益度。

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

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

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

步驟6 每個(gè)鄰域搜索的食物源只保留一個(gè)引領(lǐng)蜂。

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

步驟8（n-m）個(gè)剩余的蜜蜂隨機(jī)搜索新的食物源。

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

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

2.3 ACO算法

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

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

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

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

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

步驟5 計(jì)算待求解優(yōu)化問(wèn)題的適應(yīng)度函數(shù)值和當(dāng)前迭代過(guò)程中的最優(yōu)解。

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

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

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

2.4 PSO算法

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

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

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

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

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

粒子速度更新為：

粒子位置更新為：

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

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

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

3 案例計(jì)算

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

1）基準(zhǔn)排班方法。

根據(jù)現(xiàn)行某保潔服務(wù)公司的實(shí)際情況，需安排一個(gè)專(zhuān)業(yè)人員對(duì)該公司服務(wù)的區(qū)域進(jìn)行清潔人員排班，使得每周清潔工作人力需求時(shí)盡可能少且每周的人力需求時(shí)變化幅度盡可能小。若需獲得一個(gè)相對(duì)合理的清潔排班方案，需要工作人員大約1～2 天的工作量。一般情況下，給出每項(xiàng)清潔工作的起始周WKstart，根據(jù)清潔排班問(wèn)題約束即可退出具體的清潔排班方案?，F(xiàn)有一個(gè)工作人員手工排班相對(duì)較優(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，具體排班人力需求結(jié)果如圖1（a）所示。

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

2）SA算法求解。

SA 算法需要設(shè)置的參數(shù)包括：初始最高溫度Tmax=1e5，初始最低溫度Tmin=1e-3，溫度退化系數(shù)k=0.98，迭代次數(shù)NGEN=1000。模擬退火優(yōu)化算法求解清潔排班問(wèn)題結(jié)束后，獲得的最優(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 算法自組織、自適應(yīng)等特點(diǎn)求解，需要設(shè)置的參數(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，具體的清潔排班結(jié)果如圖1（c）所示。

4）ACO算法求解。

ACO算法需要設(shè)置的初始化參數(shù)包括：蟻群大小M=500，迭代次數(shù)NGEN=200，信息素?fù)]發(fā)系數(shù)ρ=0.4，信息素釋放總量Q=1.0。ACO 算法求解清潔排班問(wèn)題獲得最優(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，具體的清潔排班結(jié)果如圖1（d）所示。

5）PSO算法求解。

PSO 算法求解清潔排班問(wèn)題需要設(shè)置的參數(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，具體的清潔排班結(jié)果如圖1（e）所示。

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

6）清潔排班方案對(duì)比與討論。

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

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

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

4 結(jié)語(yǔ)

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