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

(廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州 510006)

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

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

1 家政服務(wù)人員排班的問(wèn)題描述

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

2 分支定界法

2.1 分支定界法的基本原理

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

2.2 分支定界法的步驟

將要求解的整數(shù)線(xiàn)性規(guī)劃問(wèn)題稱(chēng)為P，與其對(duì)應(yīng)的線(xiàn)性規(guī)劃問(wèn)題稱(chēng)為Q。

幾個(gè)推論:

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

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

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

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

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

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

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

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

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

3 基于自適應(yīng)的混合遺傳算法設(shè)計(jì)

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

3.1 交叉算子

交叉算子主要用于產(chǎn)生新個(gè)體，實(shí)現(xiàn)算法的全局搜索能力?？紤]到整個(gè)種群的變化趨勢(shì)及每個(gè)個(gè)體的變異機(jī)會(huì)，設(shè)計(jì)了與進(jìn)化代數(shù)相關(guān)而與個(gè)體適應(yīng)度無(wú)關(guān)的交叉概率計(jì)算公式，如式(1)。t 為當(dāng)前進(jìn)化代數(shù)，Tgen為預(yù)設(shè)的最大進(jìn)化代數(shù)，pcmax為預(yù)設(shè)最大概率，pcmin為預(yù)設(shè)最小概率，pc(t)為當(dāng)前種群的交叉概率。

3.2 變異算子

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

3.3 求解步驟

求解步驟:

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

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

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

4)自適應(yīng)變異C 中k 個(gè)隨機(jī)的列，執(zhí)行局部搜索以改進(jìn)染色體，評(píng)價(jià)，選出下一代種群C’。

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

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

7)從種群中隨機(jī)選出高于平均適應(yīng)值的個(gè)體并用C’替代。

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

4 仿真分析

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

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

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

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

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

1)分支定界法求解。

數(shù)學(xué)模型

定義

建立數(shù)學(xué)模型

目標(biāo)函數(shù):

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

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

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

2)應(yīng)用GA 和HGA 求解。

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

數(shù)學(xué)模型

目標(biāo)函數(shù):

決策變量:

約束:

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

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

表5 基于列的表示

圖1 應(yīng)用GA 和HGA 求解的一次收斂過(guò)程

表6 兩種算法對(duì)比結(jié)果

求解結(jié)果:應(yīng)用GA 和HGA 求解的一次收斂過(guò)程如圖1 所示，兩種算法對(duì)比結(jié)果如表6 所示。GA在第50 代搜索到最優(yōu)解，HGA 在第8 代就搜索到最優(yōu)解，最優(yōu)解為83 個(gè)單位?？梢?jiàn)，HGA 相對(duì)于GA，收斂速度快，收斂效果也很好。

5 結(jié)語(yǔ)

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

［1］李獻(xiàn)忠，徐瑞華. 基于時(shí)間耗費(fèi)的城市軌道交通乘務(wù)排班優(yōu)化［J］. 鐵道學(xué)報(bào)，2007，29(1):21－25.

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

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

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

［5］張應(yīng)輝，饒?jiān)撇?，周明? 模擬“退火”算法在多目標(biāo)航空公司職員排班系統(tǒng)中的應(yīng)用［J］. 計(jì)算機(jī)應(yīng)用，2006，26(8):2001－2004.

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

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

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

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

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

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