邱旭勤 蔡延光 湯雅連 江澤東

(廣東工業(yè)大學 自動化學院，廣州 510006)

相對于傳統(tǒng)的農(nóng)業(yè)和工業(yè)而言，新興的家政服務業(yè)被稱為第三產(chǎn)業(yè)，該產(chǎn)業(yè)在20 世紀60年代后得到了長足發(fā)展。目前，以家庭及其成員為主要服務對象的家政服務業(yè)是第三產(chǎn)業(yè)的重要組成部分，它所提供的服務內(nèi)容從傳統(tǒng)的保潔、理家、照顧老人、孩子，到籌辦婚禮、喪禮、壽宴和各種家庭慶典，商品配送、電器維修、服裝裁剪、送餐上門、慶典用品出租、房屋維修等等，涉及人們生活的方方面面，為眾多的家庭和個人帶來了方便。隨著全民生活水平的提高，有約70%的城市居民對家政服務有需求，因此，家政服務業(yè)這一朝陽產(chǎn)業(yè)其發(fā)展前景和市場是極其廣闊的。諸如保育員、護理員、月嫂、管家，物業(yè)管理員、保潔員，家教、鐘點工、保潔、配送、管道疏通，家居裝飾、庭院美化，家居保潔，房屋維修，承辦婚禮、喪禮、壽宴和各種家庭慶典，出租慶典用品，家居用品配送、電器維修、服裝裁剪等均屬于家政服務業(yè)內(nèi)容，最專業(yè)的、最準時的家政服務讓顧客感受零家務的超值享受，讓顧客享受最舒適的生活，為了讓顧客滿意，合理的排班也變得尤為重要，因此研究的家政服務人員的排班問題具有實際應用意義。

目前，排班問題也得到了廣泛的研究。李獻忠等人［1］研究了乘務排班問題，通過最小費用最大流算法實現(xiàn);李躍鵬等人［2］應用遺傳算法求解公交車輛的智能排班問題，能夠在排班問題的巨大搜索空間中可靠地找到近似最優(yōu)解;李青等人［3］提出了排班問題的多目標優(yōu)化模型，并應用改進的基于信息熵的自適應遺傳算法求解模型，結果證明了模型的正確性和先進性;沈吟東等人［4］建立了帶有一系列勞動法規(guī)約束和護士級別差異的整數(shù)規(guī)劃模型，建立了更加人性化的擴展模型，實例驗證該模型與算法是可行有效的，有利于提高護士積極性和工作效益;張應輝等人［5］詳細描述了排班系統(tǒng)模型，并用模擬退火算法很好地解決了該問題，運行結果表明所提的模型和算法是合理而有效的;孫宏等人［6］描述了飛機排班問題的數(shù)學模型，結果表明飛機排班模式是解決單樞紐線性航線結構下的飛機排班問題的一種有效方法;王慶榮等人［7］結合公交車輛運營的特點，兼顧公交公司與乘客雙方的利益，建立了公交排班優(yōu)化模型，提出了基于改進的遺傳模擬退火算法，提高了優(yōu)化設計過程的求解效率。

1 家政服務人員排班的問題描述

為了快速響應客戶的需求，須將服務人員安排到顧客需求的不同時間段內(nèi)，通過服務人員的適當安排來調(diào)整服務能力，滿足不同時間段內(nèi)的不同服務負荷。公司為了人性化運營，制定人員排班計劃既要考慮客戶的需求，也要考慮服務人員的靈活需求，這兩方面均為排班優(yōu)化的主要約束條件，是為了獲得最大收益，盡量使使服務富余人數(shù)維持最低。

2 分支定界法

2.1 分支定界法的基本原理

分支定界法［8－9］是20 世紀60年代初由Land、Doig 和Dakin 等人提出的可用于求解純整數(shù)線性規(guī)劃問題的算法。其基本思想就是不斷將可行域分割成小的集合，不斷降低上界、提高下界，最后使得下界接近或者等于上界，逐步縮小搜索范圍，進而找到問題的最優(yōu)整數(shù)解。

2.2 分支定界法的步驟

將要求解的整數(shù)線性規(guī)劃問題稱為P，與其對應的線性規(guī)劃問題稱為Q。

幾個推論:

1)若Q 無可行解，則P 也一定無可行解;

2)若Q 的一個最優(yōu)解是整數(shù)解，則它就是P 的最優(yōu)解;

3)若Q 的最優(yōu)解不是整數(shù)解，則P 的最優(yōu)目標函數(shù)值不會好于Q 的最優(yōu)值;

4)若已經(jīng)找到一個整數(shù)解，則最優(yōu)整數(shù)解一定不會劣于該整數(shù)解，它也是最優(yōu)目標函數(shù)值的一個界，在最大化目標函數(shù)值時為下界，在最小化目標函數(shù)值時為上界。

分支定界法的求解步驟如下:

1)初始求解整數(shù)規(guī)劃的松弛問題，如果得到的解是整數(shù)解，該解即為整數(shù)規(guī)劃的最優(yōu)解，否則，所得到的線性規(guī)劃解可作為該問題最優(yōu)整數(shù)解的初始上界，此時，初始下界設為－∞;

2)分支。在Q 的最優(yōu)解中任選一個不符合整數(shù)條件的變量xj，設其值為vj，構造兩個約束條件:xj≤［vj］和xj≥［vj］+1 ，將這兩個條件分別加入問題Q，分成兩個子問題Q1和Q2，不考慮整數(shù)條件，求解Q1和Q2;

3)定界與剪枝。以每個后繼子問題為一分支并標明求解結果，與其他問題的解進行比較，不斷修正上界和下界，若無可行解，停止繼續(xù)分支;得到整數(shù)解，不必向下分支，如果該整數(shù)解是目前得到的最好整數(shù)解，則記錄下來，并作為新下界;得到非整數(shù)解，如果目標函數(shù)值大于剪枝界，則繼續(xù)分支，否則被剪枝;

4)按以上步驟進行搜索迭代，在搜索過程中，每次下界被修改后，必須檢查所有還沒有求解過的子問題并剪去那些目標函數(shù)值小于新下界的子問題，若沒有找到任何整數(shù)解，則該問題無整數(shù)解;否則，搜索過程中得到的最優(yōu)整數(shù)解就是該問題的最優(yōu)解。

3 基于自適應的混合遺傳算法設計

遺傳算法擅長全局搜索但是收斂速度慢，局部搜索擅長微調(diào)但容易陷入局部最優(yōu)，結合遺傳算法和局部搜索算法的優(yōu)點，遺傳算法用來執(zhí)行全局搜索以使解從局部最優(yōu)中逃離，局部搜索進行性能微調(diào)。并且，應用自適應遺傳算法求解，自適應遺傳算法［10－11］包括避免近親繁殖的雜交策略與改進的交叉概率，根據(jù)每代個體適應度的改變來自適應地改變交叉概率pc和變異概率pm，既保護了最優(yōu)個體又加快了較差個體的淘汰程度。

3.1 交叉算子

交叉算子主要用于產(chǎn)生新個體，實現(xiàn)算法的全局搜索能力。考慮到整個種群的變化趨勢及每個個體的變異機會，設計了與進化代數(shù)相關而與個體適應度無關的交叉概率計算公式，如式(1)。t 為當前進化代數(shù)，Tgen為預設的最大進化代數(shù)，pcmax為預設最大概率，pcmin為預設最小概率，pc(t)為當前種群的交叉概率。

3.2 變異算子

交叉算子起著全局搜索的作用，變異算子主要是產(chǎn)生新個體和抑制早熟。設計變異概率的總趨勢是逐漸減小而使群體迅速集中。式(3)所示為自適應變異概率，pmmax是預設的最大變異概率，pmmin是預設的最小變異概率，pm(t)是第t 代個體進行變異的概率。

3.3 求解步驟

求解步驟:

1)隨機產(chǎn)生N 個解構成初始種群。令t:=0。

2)采用基于列的表示的二進制編碼，由于該優(yōu)化問題的變量本質上是0－1 變量，所以采用二進制字符串作為染色體的結構，如表所示。其表達方法說明了編號為1、5、6、7、10、12、13 和14 的員工星期一上班，其余6 人休息。然后執(zhí)行局部搜索，評價適應值，選出最好的兩個解Q1和Q2。

3)采用自適應雜交算子組合Q1和Q2生成新解C。

4)自適應變異C 中k 個隨機的列，執(zhí)行局部搜索以改進染色體，評價，選出下一代種群C’。

5)采用啟發(fā)式算子確保C’可行，除去冗余列。

6)如果C’與種群中任意解相同，返回2)。否則t:=t+1，轉至7)。

7)從種群中隨機選出高于平均適應值的個體并用C’替代。

8)重復2)～7)，直到產(chǎn)生t=M 個不重復的個體。選出最小適應值的個體作為最優(yōu)解。

4 仿真分析

已知某小型家政公司一周內(nèi)的人員需求量如表1 所示，請為該公司的14 位員工制定一個保證每人能休息一天的排班計劃，員工分別以A、B、C、D、E、F、G、H、I、J、K、L、M 和N 表示。其中，G 星期五有事請假。

表1 一周內(nèi)的人員需求量

分別用分支定界法、遺傳算法和基于自適應的混合遺傳算法求解。在Intel(R)CoreTMi3 CPU2.53GHz、內(nèi)存為2.0G、安裝系統(tǒng)為win7 的PC 機上采用Matlab R2010b 編程實現(xiàn)。各運行20 次求解。

遺傳算法中參數(shù)設計:初始化種群N = 100 ，最大迭代次數(shù)gen = 500 ，交叉概率pc= 0.9 ，變異概率pm= 0.04 。采用均勻雜交，變異算子指單點變異。

混合遺傳算法參數(shù)設計:初始化種群N = 100 ，最大迭代次數(shù)gen = 500 ，pmmax= 0.2 ，pmmin=0.001 ，pcmin= 0.2 ，pcmax= 0.001 。

1)分支定界法求解。

數(shù)學模型

定義

建立數(shù)學模型

目標函數(shù):

目標函數(shù)如式(5)，約束條件如式(6)。

求解結果:員工安排計劃表如表2 所示，人員配備統(tǒng)計如表3 所示。由此可見，富余人員為0，已經(jīng)搜索到最優(yōu)解。程序運行一次的時間為0.007 s。

表3 人員配備統(tǒng)計

2)應用GA 和HGA 求解。

家政服務人員的排班優(yōu)化問題是集覆蓋問題，也屬于NP 問題。安排14 個服務人員一周的排班計劃，服務人員必須完成任務，目標函數(shù)是最小化員工薪酬之和。設k 為服務人員的編號，k =1，2，…，14。t 表示工作時間，t=1，2，…，7。ct(k)表示服務人員k 在t 時間工作應得到的薪酬，這里簡化為1個單位。家政服務人員調(diào)度示例如表4 所示，基于列的表示如表5 所示。

數(shù)學模型

目標函數(shù):

決策變量:

約束:

目標函數(shù)如式(7)，式(8)為決策變量，表示員工k 安排到t 時間上班。式(9)為約束，ait(k)=1 意味著k 個服務人員組成的第i 個班次，在t 時間為客戶服務。

表4 家政服務人員調(diào)度示意圖

表5 基于列的表示

圖1 應用GA 和HGA 求解的一次收斂過程

表6 兩種算法對比結果

求解結果:應用GA 和HGA 求解的一次收斂過程如圖1 所示，兩種算法對比結果如表6 所示。GA在第50 代搜索到最優(yōu)解，HGA 在第8 代就搜索到最優(yōu)解，最優(yōu)解為83 個單位。可見，HGA 相對于GA，收斂速度快，收斂效果也很好。

5 結語

通過分析家政服務人員的排班問題，介紹一種分支定界算法，并應用該分支定界算法求解。構造了基于自適應的混合遺傳算法，結合遺傳算法和局部搜索算法的優(yōu)點，遺傳算法可以跳出局部最優(yōu)，局部搜索可以進行性能微調(diào)。應用自適應策略改進算法，自適應遺傳算法包括避免近親繁殖的雜交策略與改進的交叉概率，根據(jù)每代個體適應度的改變來自適應地改變交叉概率和變異概率，既保護了最優(yōu)個體又加快了較差個體的淘汰程度。仿真結果表明，三種算法都可以得到最優(yōu)解，基于自適應的混合遺傳算法在收斂速度和性能方面最優(yōu)，該方法可以用來求解更大規(guī)模的排班優(yōu)化問題。

［1］李獻忠，徐瑞華. 基于時間耗費的城市軌道交通乘務排班優(yōu)化［J］. 鐵道學報，2007，29(1):21－25.

［2］李躍鵬，安濤，黃繼敏，等. 基于遺傳算法的公交車輛智能排班研究［J］. 交通運輸系統(tǒng)工程與信息，2003，3(1):41－44.

［3］李青，張軍，張學軍. 解決排班問題的多目標優(yōu)化模型及算法研究［J］. 北京航空航天大學學報，2003，29(9):821－824.

［4］沈吟東，蘇光輝. 帶約束的護士排班模型和基于變換規(guī)則的優(yōu)化算法［J］. 計算機工程與科學，2010，32(007):99－103.

［5］張應輝，饒云波，周明天. 模擬“退火”算法在多目標航空公司職員排班系統(tǒng)中的應用［J］. 計算機應用，2006，26(8):2001－2004.

［6］孫宏，杜文. 飛機排班數(shù)學規(guī)劃模型［J］. 交通運輸工程學報，2004，4(3):118－118.

［7］王慶榮，袁占亭，張秋余. 基于改進遺傳—模擬退火算法的公交排班優(yōu)化研究［J］. 計算機應用研究，2012，29(7):2461－2463.

［8］吳金榮. 求解課程表問題的分支定界算法［J］. 運籌與管理，2002，11(1):17－22.

［9］雷廣萍，袁威. 直線方向單組列車編組優(yōu)化的壓縮分枝定界法［J］. 鐵道學報，1989，11(1):26－38.

［10］魏明，蔡延光.一種基于混沌領域搜索的自適應遺傳算法［J］.計算機應用研究，2009，26(2):465－467.

［11］韓瑞鋒. 遺傳算法原理與應用實例［M］. 北京:兵器工業(yè)出版社，2009.