基于CS 的帶時(shí)間窗多技能人力資源路徑優(yōu)化

摘 要：針對帶時(shí)間窗多技能人力資源路徑優(yōu)化問題，分別構(gòu)建了兩種數(shù)學(xué)模型，利用改進(jìn)的布谷鳥搜索算法（Cuckoo Search Algorithm， CS）對模型進(jìn)行求解。求出不同類型客戶群企業(yè)或組織的運(yùn)作成本，并對模型的適用性進(jìn)行了討論，對密集型客戶適合模型Ⅱ，即先分區(qū)后指派；對分散型客戶適合模型Ⅰ，即直接指派。該研究可為企業(yè)或組織的決策提供參考，為員工的招聘和安排提供理論指導(dǎo)。

關(guān)鍵詞：布谷鳥搜索算法；人力資源路徑優(yōu)化；時(shí)間窗；多技能

中圖分類號(hào)： TP3 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1673-8462（2023）03-0086-05

0 引言

隨著勞動(dòng)力數(shù)量和質(zhì)量的雙變導(dǎo)致企業(yè)用工成本增加，給企業(yè)的經(jīng)營管理帶來巨大壓力。具備多技能的員工能適應(yīng)多種工作崗位，使企業(yè)的人員安排更加靈活，能有效降低企業(yè)的人力成本，因此，在企業(yè)實(shí)踐管理中，多技能員工越來越受到企業(yè)的青睞。然而，在不同技能員工的工作安排中涉及多個(gè)任務(wù)，每個(gè)任務(wù)有時(shí)間窗要求和所需不同技能，如何合理安排不同技能員工的工作任務(wù)，使企業(yè)的運(yùn)作成本最低，成為企業(yè)亟待解決的問題。

近年來，不少專家學(xué)者對人力資源管理從不同角度進(jìn)行研究，袁方潔等人［1］提出基于多階段遺傳算法的人力資源管理，針對企業(yè)員工雇傭計(jì)劃的優(yōu)化問題建立數(shù)學(xué)模型，通過合理控制不同時(shí)段解聘數(shù)量來提高雇員的平均工作能力，從而實(shí)現(xiàn)項(xiàng)目的人力資源優(yōu)化。李明等人［2-3］分別提出基于均衡優(yōu)化的項(xiàng)目多技能人力資源指派與調(diào)度方法和項(xiàng)目多技能人力資源指派與調(diào)度混合算法，其在文獻(xiàn)［2］中首先采用啟發(fā)式方法對項(xiàng)目進(jìn)行資源均衡化并建立整數(shù)規(guī)劃模型，通過編程計(jì)算驗(yàn)證了可以有效降低項(xiàng)目人力資源成本，在文獻(xiàn)［3］中將原問題分為指派問題和調(diào)度問題構(gòu)建模型，編程實(shí)現(xiàn)提高多技能人力資源的使用率。康麗等人［4］提出基于時(shí)間窗的家庭醫(yī)療護(hù)理人力資源分配，其在資源分配階段考慮時(shí)間窗約束和所提出的層次優(yōu)化算法，實(shí)驗(yàn)結(jié)果驗(yàn)證了模型的有效性。王一凡等人［5］提出求解多技能人力資源約束的項(xiàng)目調(diào)度問題的兩階段算法，實(shí)驗(yàn)結(jié)果顯示其是一種有效方法。段鵬飛等人［6］提出求解廣義優(yōu)先關(guān)系下多技能人員項(xiàng)目調(diào)度問題的改進(jìn)布谷鳥搜索算法，實(shí)驗(yàn)結(jié)果表明其是一種有效方法。李松等人［7］提出人力資源調(diào)度的蟻群算法模型，實(shí)例證明該算法能有效節(jié)省人力資源成本。沈國軍等人［8］提出基于改進(jìn)遺傳算法的人力資源指派模型，簡化了人力資源指派流程，產(chǎn)生較好的項(xiàng)目績效。伊雅麗等人［9］提出基于蟻群算法求解研發(fā)型多項(xiàng)目人力資源調(diào)度研究，為人力資源調(diào)度方案提供了新的解決途徑。但鮮有研究將時(shí)間窗與多技能約束統(tǒng)籌考慮，雖然文獻(xiàn)［10］將兩者綜合考慮，但未對客戶類型進(jìn)行細(xì)分研究。本文根據(jù)現(xiàn)實(shí)管理需求，建立兩種數(shù)學(xué)模型分別用CS 算法求解，通過六種不同類型客戶群的仿真實(shí)驗(yàn)，針對不同類型客戶群適合哪種數(shù)學(xué)模型企業(yè)的運(yùn)作成本最小給出了理論指導(dǎo)。

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

1.1 問題描述

在企業(yè)或管理者安排技術(shù)人員服務(wù)客戶時(shí)，多個(gè)客戶在地理位置上的分布一般較為不同，在同一時(shí)間內(nèi)，不同客戶所提需求也不盡相同，從而構(gòu)成一個(gè)復(fù)雜的服務(wù)網(wǎng)絡(luò)。本文以帶時(shí)間窗的多技能約束服務(wù)網(wǎng)絡(luò)為研究對象，網(wǎng)絡(luò)由一個(gè)服務(wù)總站，若干個(gè)客戶節(jié)點(diǎn)構(gòu)成，如圖1 所示。服務(wù)總站即圖中編號(hào)為0的節(jié)點(diǎn)，由其派遣多個(gè)專業(yè)技術(shù)人員為不同需求的客戶進(jìn)行服務(wù)，每個(gè)技術(shù)人員從服務(wù)總站出發(fā)，完成任務(wù)后返回出發(fā)點(diǎn)；每個(gè)客戶具有需求技能約束和時(shí)間窗約束，在圖1 中分別用不同形狀進(jìn)行表示。對管理者而言，如何合理安排各種專業(yè)技術(shù)人員在滿足各客戶技能約束和時(shí)間窗約束的基礎(chǔ)上，使組織的運(yùn)作成本最小化。

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

假設(shè)服務(wù)總站需派遣K （ k = 1，2，…，K ） 名技術(shù)人員服務(wù)L （ i = 1，2，…，L ） 個(gè)客戶，每個(gè)客戶的服務(wù)時(shí)間為si （ i = 1，2，…，L ），客戶i 到客戶j 的路徑成本為cij、行程時(shí)間為tij （ i，j = 0，1，2，…，L ），技術(shù)人員到達(dá)客戶i 的時(shí)間為Ti（ i = 1，2，…，L ），客戶i 的服務(wù)時(shí)間窗約束為[ ETi，LTi ]，技術(shù)人員的工資成本為f（k 不同技術(shù)人員工資標(biāo)準(zhǔn)參見表1），每個(gè)技術(shù)人員所服務(wù)的客戶數(shù)為Rk，顯然，在成本結(jié)構(gòu)上，除了路徑成本以外，還有人員工資成本、時(shí)間約束懲罰成本。其數(shù)學(xué)模型如下：

式（1）表示目標(biāo)函數(shù)，式（2）～式（4）表示每個(gè)客戶只能被一名技術(shù)人員服務(wù)，式（5）表示時(shí)間窗約束，式（6）～式（7）表示0-1 變量，式（8）中的a，b 分別表示早晚到懲罰系數(shù)。

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

由于客戶地理位置分布不同，通常的做法是將地理位置較近的客戶劃分為一個(gè)片區(qū)，然后再安排相關(guān)的技術(shù)人員對其進(jìn)行服務(wù)。假設(shè)L 個(gè)客戶需要?jiǎng)澐諯 個(gè)片區(qū)，使得K 個(gè)片區(qū)總距離最短及所需技能最少，每個(gè)客戶的技能需求為qi，每個(gè)客戶只能由一名技術(shù)人員服務(wù)，假設(shè)服務(wù)總站的技術(shù)人員足以滿足客戶群的技能需求。因此片區(qū)劃分?jǐn)?shù)學(xué)模型為：

式（9）表示片區(qū)劃分的目標(biāo)函數(shù)，distij 表示客戶i與客戶j 之間的距離，uij 為1 時(shí)表示第j 個(gè)客戶由第i名技術(shù)人員服務(wù)，式（10）～式（13）為約束條件。

2 算法設(shè)計(jì)

2.1 布谷鳥搜索算法

布谷鳥搜索算法（Cuckoo Search Algorithm，CS）由Yang 于2010 年提出，［11］該算法模擬布谷鳥尋窩產(chǎn)卵的過程來求解連續(xù)優(yōu)化問題，其位置更新公式為：

式（14）中xti 表示第i 鳥巢在第t 的位置，α 表示步長控制量，一般取值為0.01；⊕ 表示點(diǎn)乘，L （ λ ） 為Levy 飛行的搜索路徑，且L～u = t-λ，（ 1 lt; λ ≤ 3 ）。位置更新并評價(jià)目標(biāo)函數(shù)后，用隨機(jī)數(shù)r ∈ [ 0，1 ] 與棄巢概率pa 比較，如果r gt; pa，則對xt + 1i 位置隨機(jī)改變，否則不變。最后保留最優(yōu)鳥巢。

2.2 布谷鳥搜索算法離散化

顯然基本布谷鳥搜索算法不能直接求解離散優(yōu)化問題，因此，采用文獻(xiàn)［12］的方式將其離散化，現(xiàn)假設(shè)最優(yōu)解best＝［2 8 3 5 4 6 7 1］，第i 個(gè)Customer＝［2 1 8 3 5 7 4 6］，隨機(jī)產(chǎn)生num、Length∈ [ 1，8 ] 之間的兩個(gè)整數(shù)，比如num＝3，Length＝4，即將Cus?tomer 的值從第3 個(gè)位置開始取長度為4 的元素變換成最優(yōu)解best 一致，變換后的Customer'＝［2 1 3 5 46 8 7］，通過這種隨機(jī)選擇位置和改變長度的方式趨向最優(yōu)解。

2.3 編碼與解碼

編碼是智能算法求解問題的關(guān)鍵，它影響著算法的求解性能與效率，本文采用自然數(shù)的編碼方式。以圖1 為例，即需求技能r=3，則相應(yīng)的技術(shù)人員按表1 分為2r - 1=7 種類型：

那么，對一個(gè)有L 個(gè)客戶的帶時(shí)間窗多技能人力資源問題，設(shè)計(jì)雙倍L 編碼：假設(shè)客戶編號(hào)為Cus?tomer，技術(shù)人員編號(hào)為Staff。則圖1 所示的一個(gè)可行解可以表示為：

Customer：1，7，17，2，16，4，11，5，3，19，15，8，10，14，12，9，18，13，6。

Staff：1，2，4，5，1，3，2，4，5，1，5，3，2，4，1，3，5，2，3

其解碼過程為：

員工1：0–1–16–19–12–0

員工2：0–7–11–10–13–0

員工3：0–4–8–9–6–0

員工4：0–17–5–14–0

員工5：0–2–3–15–18–0

2.4 遺傳算法操作

由于本文算法采用雙倍體編碼方式，遺傳算法不能直接作用于客戶Customer 編碼上，如果這樣在交叉過程中會(huì)產(chǎn)生重復(fù)客戶編號(hào)，因此，將其作用于技術(shù)人員Staff 編碼方式上，這樣既可以減少客戶重復(fù)編碼的處理又可以改變技術(shù)人員服務(wù)不同的客戶。同時(shí)在遺傳算法的選擇、交叉和變異過程中均采用精英保留策略。

2.5 CS 算法求解步驟

（1） CS 算法求解帶時(shí)間窗多技能人力資源路徑優(yōu)化問題的實(shí)施步驟如下（簡稱算法1）。

Step1：參數(shù)初始化：種群規(guī)模n、棄巢概率pa ，交叉概率pc，最大迭代次數(shù)Iter max，遺傳算法迭代次數(shù)ga_num、計(jì)劃安排人數(shù)k 和導(dǎo)入客戶信息等數(shù)據(jù)。

Step2：按2.3 節(jié)介紹的編碼方式隨機(jī)產(chǎn)生客戶編號(hào)和員工編號(hào)，并按式（8）計(jì)算每個(gè)鳥巢的目標(biāo)函數(shù)值，求出最優(yōu)值及最優(yōu)解。

Step3：判斷迭代次數(shù)是否達(dá)到最大迭代次數(shù)，如果是，則退出循環(huán)，輸出結(jié)果；否則進(jìn)入Step4。

Step4：執(zhí)行離散布谷鳥搜索位置的更新，評價(jià)此時(shí)最優(yōu)值與最優(yōu)解；如果隨機(jī)數(shù)r gt; pa，則對xt + 1i 位置隨機(jī)改變，再評價(jià)此時(shí)最優(yōu)值與最優(yōu)解，然后再執(zhí)行一定次數(shù)遺傳算法操作并評價(jià)此時(shí)最優(yōu)值與最優(yōu)解。

Step5：判斷若此時(shí)最優(yōu)值較Step2 中的最優(yōu)值優(yōu)越，則替換最優(yōu)值和最優(yōu)解，算法進(jìn)入Step3。

（2） CS 算法求解客戶片區(qū)劃分（簡稱算法2）。

算法2 的片區(qū)劃分的求解過程，只需要改變算法1 的編碼方式，采用文獻(xiàn)［13］編碼方式（其過程在此不再贅述），目標(biāo)函數(shù)值的計(jì)算采用式（9）即可，其余操作與算法1 相同。

（3） CS 算法求解片區(qū)內(nèi)客戶順序（簡稱算法3）。

將算法2 計(jì)算的片區(qū)劃分結(jié)果作為算法3 的輸入，其編碼方式依然采用自然數(shù)編碼，目標(biāo)函數(shù)值的計(jì)算采用式（8），其余操作與算法1 相同。

3 仿真實(shí)驗(yàn)與分析

為了將兩種不同數(shù)學(xué)模型+算法設(shè)計(jì)對企業(yè)所產(chǎn)生的成本進(jìn)行對比。由于本文所研究內(nèi)容業(yè)界尚缺乏標(biāo)準(zhǔn)的數(shù)據(jù)庫，故采用Solomn 提出的算例庫，其中包含C1、C2、R1、R2、RC1、RC2 六種類型，其中C類表示客戶位置是聚集分布的，R 類表示客戶位置是隨機(jī)分布的，RC 類表示客戶位置是混合分布的。另外，又將C，R，RC 類分為1 類和2 類：1 類表示客戶所處范圍較小，2 類表示客戶所處范圍較大。每種類型均包含服務(wù)總站、客戶坐標(biāo)、服務(wù)時(shí)間、貨物需求量和時(shí)間窗。所不同的是將貨物需求量改為客戶所需技能種類，技能種類在［1，3］之間隨機(jī)生成，其余不變。

所有的實(shí)驗(yàn)均運(yùn)行在操作系統(tǒng)為Win10，處理器為Intel（R） i6-6750H CPU， 2.60 GHZ 、內(nèi)存為8 G的PC 上，采用Matlab R2010a 編程。參數(shù)設(shè)置見表2所示，由于本文算法是啟發(fā)式算法，無法保證每次運(yùn)行結(jié)果一致，故取其運(yùn)行30 次結(jié)果中最好的一次進(jìn)行分析。所有實(shí)驗(yàn)假設(shè)安排10 名技術(shù)人員進(jìn)行服務(wù)。

3.1 C201 客戶類型測試

對C201 客戶類型進(jìn)行實(shí)例演算并詳細(xì)分析，先展示數(shù)學(xué)模型Ⅱ+算法2 的計(jì)算結(jié)果，片區(qū)的劃分結(jié)果如表3 所示，片區(qū)劃分示意圖如圖2 所示。采用算法3 優(yōu)化客戶順序及所支出成本結(jié)果如表4 所示。

再展示數(shù)學(xué)模型Ⅰ+算法1 的運(yùn)行結(jié)果，計(jì)算結(jié)果如表5 所示。

對客戶位置較分散的C201 客戶類型來說，從表4 和表5 可得出如下結(jié)論：

（1） 如果先分區(qū)再指派相應(yīng)的技術(shù)人員進(jìn)行片區(qū)服務(wù)與數(shù)學(xué)模型Ⅰ+算法1 求解結(jié)果比較可知，企業(yè)或組織所承擔(dān)的費(fèi)用需多支出4.1E+04。

（2） 從表3 可知，盡管將距離較近的客戶劃分成一個(gè)片區(qū)再由技術(shù)人員進(jìn)行服務(wù)，僅考慮了距離成本及所需技能，既沒有考慮技能需求的差異，也要求員工全部掌握3 種技能；而從表5 可知，各種技術(shù)人員的合理搭配比單純的路徑優(yōu)化重要，一組合理的人員搭配可以大大減少企業(yè)的運(yùn)作成本。因此在實(shí)踐管理中，不同種類的多技能員工合理搭配可以使企業(yè)員工調(diào)度更加靈活，并有效降低生產(chǎn)成本。

（3） 從表5 可知，在服務(wù)范圍和路徑順序不變的情況下，若全部派遣7 類人員則企業(yè)需要多支出的費(fèi)用。

3.2 其他客戶類型測試

上述僅對一種客戶類型進(jìn)行實(shí)驗(yàn)演算，下面對其他五種類型進(jìn)行同樣實(shí)驗(yàn)，計(jì)算結(jié)果如表6 所示。

從表6 可知，對地理位置分布較小的客戶群C101、R101 和RC101 來說，模型Ⅰ + 算法設(shè)計(jì)所求成本高于模型Ⅱ + 算法設(shè)計(jì)；即該類客戶群適用于先分區(qū)后指派員工，即適合采用模型Ⅱ+算法2+算法3，由于客戶所處位置分布較小，優(yōu)化距離比優(yōu)化多技能員工的合理搭配效果更明顯。而對地理位置分布較大的客戶群C201、R201 和RC201 來說，模型Ⅰ + 算法設(shè)計(jì)所求成本低于模型Ⅱ + 算法設(shè)計(jì)；即該類客戶群適合采用模型Ⅰ+算法1，而且越分散優(yōu)化效果越好，多技能員工的合理搭配效果顯著。因此，對不同類型客戶群需采用不同數(shù)學(xué)模型和算法進(jìn)行求解，可以有效降低企業(yè)運(yùn)作成本。

4 結(jié) 語

本文利用改進(jìn)的布谷鳥搜索算法求解帶時(shí)間窗的多技能人力資源路徑優(yōu)化問題，考慮了路徑成本、人力成本、等待成本和延誤成本，更加符合實(shí)際情況。通過六種不同類型客戶群，驗(yàn)證了模型的有效性。同時(shí)對模型的適用性進(jìn)行了討論，對密集型客戶適合模型Ⅱ，即先分區(qū)后指派；對分散型客戶適合模型Ⅰ，即直接指派。該研究可為企業(yè)或組織的決策提供參考，為員工的招聘和安排提供理論指導(dǎo)。

［參考文獻(xiàn)］

[1] 袁方潔，張佳萍. 基于多階段遺傳算法的人力資源管理[J].云南民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，25（3）：275-279.

[2] 李明，徐哲. 基于均衡優(yōu)化的項(xiàng)目多技能人力資源指派與調(diào)度方法[J]. 工業(yè)工程，2016，19（1）：108-114.

[3] 李明，李前進(jìn). 項(xiàng)目多技能人力資源指派與調(diào)度混合算法[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2017，47（19）：20-28.

[4] 康麗，馬塔·安德瑞. 基于時(shí)間窗的家庭醫(yī)療護(hù)理人力資源分配[J]. 工業(yè)工程與管理，2017，22（3）：83-92.

[5] 王一帆，劉士新，陳迪. 求解多技能人力資源約束的項(xiàng)目調(diào)度問題的兩階段算法[J]. 東北大學(xué)學(xué)報(bào)（ 自然科學(xué)版），2014，35（2）：184-189.

[6] 段鵬飛，余杰，聶慧，等．求解廣義優(yōu)先關(guān)系下多技能人員項(xiàng)目調(diào)度問題的改進(jìn)布谷鳥搜索算法[J]. 計(jì)算機(jī)應(yīng)用研究，2018，35（5）：1315-1319．

[7] 李松，姜楠. 人力資源調(diào)度的蟻群算法模型[J]. 遼寧工程技術(shù)大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，33（5）：679-682.

[8] 沈國軍. 基于改進(jìn)遺傳算法的人力資源指派模型及方法[J]. 統(tǒng)計(jì)與決策，2014（16）：52-55.

[9] 伊雅麗. 研發(fā)型企業(yè)多項(xiàng)目人力資源調(diào)度研究——基于蟻群優(yōu)化的超啟發(fā)式算法[J]. 工業(yè)工程，2018，21（4）：104-109.

[10] 吳建林. 含時(shí)間窗和多技能約束的人力資源路徑問題模型與算法研究[D]. 武漢：華中師范大學(xué)，2018.

[11] YANG X S， DEB S.Cuckoo search via Levy flights [C]／／proceedings of World Congress on nature amp; Biologically In?spired Computing，India：IEEE Publications，2009：210-214.

[12] 魏小迪，鄭洪清. 求解帶時(shí)間窗車輛路徑問題的改進(jìn)離散花朵授粉算法[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)， 2020， 50（2）：193-200．

[13] 劉敏. 改進(jìn)的花朵授粉算法在物流配送中心選址問題中的應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用與軟件，2019，36（6）：277-281，361．

［責(zé)任編輯 蘇琴］