虛擬養(yǎng)老服務(wù)人員調(diào)度多目標(biāo)優(yōu)化研究＊

廖 陽，孟豪南，李迎峰

(西安建筑科技大學(xué)管理學(xué)院，陜西 西安 710055)

0 引言

虛擬養(yǎng)老是在傳統(tǒng)居家養(yǎng)老的基礎(chǔ)上采用信息化、智能化的設(shè)備快速、精準(zhǔn)地把握老人的服務(wù)需求。近些年，虛擬養(yǎng)老院在我國多個城市落地，其市場需求擴(kuò)大的同時也對服務(wù)質(zhì)量提出了更高的要求。更好的服務(wù)、更低的成本是虛擬養(yǎng)老院能夠長期健康發(fā)展的關(guān)鍵。這其中，服務(wù)人員的調(diào)度問題是控制成本，提高服務(wù)質(zhì)量的關(guān)鍵一環(huán)。

虛擬養(yǎng)老具有服務(wù)的屬性，這就要求不能僅以成本大小作為評判調(diào)度方案優(yōu)劣的唯一標(biāo)準(zhǔn)。由于老人和服務(wù)人員都是重要的參與主體，對虛擬養(yǎng)老事業(yè)發(fā)展起到關(guān)鍵作用。因此在制定調(diào)度方案時，需要明確這兩者的利益追求，在控制成本的同時兼顧這兩者的利益。當(dāng)前針對虛擬養(yǎng)老問題的研究，學(xué)術(shù)界普遍是定性研究，其研究內(nèi)容主要包括對發(fā)展路徑[1]和存在問題[2]的總結(jié)。

本文研究的虛擬養(yǎng)老服務(wù)人員調(diào)度問題從屬于養(yǎng)老護(hù)工調(diào)度問題(home health care routing problem，HHCRP)[3]。當(dāng)前學(xué)術(shù)界已取得了一定的研究成果。從研究目標(biāo)來看，各研究的立足角度有所不同，包括但不限于立足服務(wù)機構(gòu)的成本優(yōu)化[4-6]和立足客戶的滿意度優(yōu)化[7-9]，無論是單目標(biāo)的成本優(yōu)化或是多目標(biāo)優(yōu)化都有較為豐富的研究成果值得借鑒。從求解算法來看，本問題同屬于NP-hard，當(dāng)前學(xué)者較多采用精確式算法[10-11]和元啟發(fā)式算法[12-17]。但隨著約束條件和問題研究的復(fù)雜化，精確式算法難以有效求解，相比之下，元啟發(fā)式算法更加適合本問題的求解，主要包括：蟻群算法[12]、遺傳算法[13]、布谷鳥算法[14]、螢火蟲算法[15]、模擬退火算法[16]和memetic 算法[17]等。此外，機器學(xué)習(xí)[18]也可用于問題求解。本文的研究從老人、服務(wù)中心和服務(wù)人員的角度出發(fā)，通過分析三者的利益追求，并以成本最優(yōu)、老人和服務(wù)人員滿意度最大為優(yōu)化目標(biāo)，建立多目標(biāo)優(yōu)化模型。

本文首先針對調(diào)度問題制定決策依據(jù)；其次把握老人服務(wù)需求信息，設(shè)計求解算法，提高算法的運行效率。本文的第一部分是對研究問題進(jìn)行數(shù)學(xué)建模，第二部分提出了求解本問題的優(yōu)化算法。第三部分通過求解算例來驗證算法的性能，第四部分總結(jié)本文的研究工作并提出研究展望。

1 優(yōu)化模型

1.1 滿意度函數(shù)

⑴老人的滿意度函數(shù)

由于老年人的身體和感情等原因，部分老人特別是需要醫(yī)療服務(wù)的老人會對服務(wù)開始的時間更加關(guān)注，因此能否在老人理想的時間段內(nèi)提供服務(wù)尤為重要。此外，對服務(wù)人員偏好也是影響老人滿意度的重要因素，一般來說，有的老人會對某一位或某幾位服務(wù)人員有特殊的情感，更樂于接受其服務(wù)。基于以上討論，本文構(gòu)建老人服務(wù)滿意度函數(shù)其中α1 和α2 為權(quán)重參數(shù)分別為老人的時間滿意度函數(shù)和對服務(wù)人員偏好的滿意度函數(shù)。

①時間滿意度函數(shù)：

其中，ti為老人i 接受服務(wù)的時間，同時采用混合時間窗，其中e'i和l'i為老人i 理想的服務(wù)時間段，在此期間老人接受服務(wù)滿意度為1，ei和li為老人能夠容忍的時間段，在此期間老人的服務(wù)滿意度會有所下降，當(dāng)開始服務(wù)時間超出這段范圍后，老人的滿意度為0，并將產(chǎn)生高額的懲罰成本。時間滿意度函數(shù)如圖1所示。

圖1 時間滿意度函數(shù)

②對服務(wù)人員偏好的滿意度函數(shù)：

其中，σi為老人i 偏好的服務(wù)人員集合，σk為服務(wù)中心安排給老人i 的服務(wù)人員。當(dāng)該服務(wù)人員屬于能夠滿足老人對服務(wù)人員的偏好時，老人的滿意度為1，當(dāng)不滿足時，老人的滿意度為0。

⑵服務(wù)人員的滿意度函數(shù)

從服務(wù)人員的角度來看，任務(wù)量分配是影響滿意度的重要因素。服務(wù)中心需合理的安排各服務(wù)人員的任務(wù)量，避免各服務(wù)人員之間任務(wù)量相差過大產(chǎn)生不滿情緒，進(jìn)而會影響服務(wù)質(zhì)量，因此，合理安排任務(wù)也是制定調(diào)度方案時必須考慮的重要因素。

本文構(gòu)建如下的服務(wù)人員滿意度函數(shù)如下：

當(dāng)服務(wù)人員k 的任務(wù)量未超出a 時，其滿意度為1；當(dāng)任務(wù)量超過a 而未超過b 時，此時其滿意度時其滿意度會降低；當(dāng)任務(wù)量超過b時，此時服務(wù)人員的滿意度為0，降為最低。服務(wù)人員滿意度圖像見圖2。

圖2 服務(wù)人員滿意度函數(shù)

1.2 模型構(gòu)建

式⑷為服務(wù)中心的總成本最低，其中的cf為懲罰成本。TD為當(dāng)前調(diào)度方案的總距離，cd為單位距離成本，α為單位等待成本，β為單位遲到成本。式⑸為所有老人的滿意度最大；式⑹為所有服務(wù)人員滿意度最大；式⑺和式⑻為服務(wù)人員從服務(wù)中心出發(fā)完成服務(wù)后回到服務(wù)中心式⑼為每位老人只接受一個服務(wù)服務(wù)；式⑽為服務(wù)時間窗約束，其取值范圍為老人所容忍的時間范圍，并將其設(shè)置軟約束；式⑾為0-1 決策變量表示服務(wù)人員k完成老人i服務(wù)后服務(wù)老人j。

2 多目標(biāo)鯨魚優(yōu)化算法

鯨魚優(yōu)化算法是Mirjalili 和Lewis 在2016 年提出的群體智能優(yōu)化算法[19]，具有操作簡單，調(diào)整的參數(shù)少以及跳出具有最優(yōu)等優(yōu)點。其思想是模擬自然界中鯨魚的捕食行為。在鯨魚群覓食過程中，通常會有一條或多條鯨魚率先發(fā)現(xiàn)獵物，此時其他鯨魚就會向該鯨魚靠近，從而完成捕食行為。傳統(tǒng)的鯨魚優(yōu)化算法一般用于連續(xù)性尋優(yōu)問題，而求解本文的離散化多目標(biāo)優(yōu)化問題需要加以改進(jìn)，具體的步驟如下。

⑴編碼與解碼

編碼和解碼是算法設(shè)計的前提工作，本文的研究是優(yōu)化目標(biāo)中求解服務(wù)人員的調(diào)度方案，屬于離散化問題求解，因此本文采用自然數(shù)編碼的形式，以代表老人的編號。以6 名老人和2 名服務(wù)人員為例，編碼方案如圖3所示。

圖3 編碼方案

圖4 中，服務(wù)人員1 的服務(wù)路線為0→1→4→5→6→0，服務(wù)人員2 的路線為：0→2→3→0，不同路徑中用101,102，……，用于分隔，其中分隔數(shù)的第三位數(shù)對應(yīng)著服務(wù)人員的編號，方便用于老人對服務(wù)人員偏好滿意度的求解。

⑵鯨魚群位置更新

傳統(tǒng)鯨魚優(yōu)化算法中，鯨魚群固定公式進(jìn)行位置更新，并根據(jù)A1的取值范圍來決定鯨魚i 靠近選擇。由于本文求解的連續(xù)性問題難以直接應(yīng)用本節(jié)研究，因此需要對鯨魚優(yōu)化算法的位置更新公式進(jìn)行改進(jìn)。在傳統(tǒng)鯨魚優(yōu)化算法中，優(yōu)化過程的前中期，鯨魚種群會更多的選擇隨機鯨魚個體靠近，以增加算法的全局搜索能力，而當(dāng)優(yōu)化過程進(jìn)入中后期，鯨魚種群會更多的向最優(yōu)鯨魚個體靠近，避免種群中優(yōu)良解遭到破壞。綜合以上考量，本文采用遺傳算法中的交叉算子來替代鯨魚的位置更新公式，通過設(shè)置動態(tài)概率為鯨魚個體選擇待交叉?zhèn)€體。

⑶局部搜索算子

本文采用4種局部搜索算子(insert,swap,inverse,2-opt),來提高算法的局部搜索能力，下面介紹這4 種搜索算子。

①insert算子：隨機選擇兩個節(jié)點i，j，并將i插入j之后。

②swap 算子：隨機選擇兩個節(jié)點i，j，并交換i 和j的位置。

③inverse 算子：隨機選擇兩個節(jié)點i，j，并將i 與j之間的節(jié)點進(jìn)行反轉(zhuǎn)。

④2-opt 算子：隨機選擇兩個節(jié)點i，j，并將包括兩個節(jié)點在內(nèi)的節(jié)點進(jìn)行反轉(zhuǎn)。

⑷非支配排序

不同于單一目標(biāo)優(yōu)化問題，多目標(biāo)優(yōu)化問題求解過程中其各個目標(biāo)往往會產(chǎn)生矛盾，導(dǎo)致難以衡量解的優(yōu)劣，通常情況下可以通過求解該問題的非支配解構(gòu)成的Pareto最優(yōu)解集來達(dá)到目標(biāo)。第三代非支配排序遺傳算法(NSGA-III)是Deb[20]在NSGA-II 算法的基礎(chǔ)上做出改進(jìn)。兩種算法都是針對多目標(biāo)優(yōu)化問題，其算法流程大致相同，但兩種算法的選擇機制有所不同，NSGA-II 利用擁擠距離來選擇相同等級個體,而NSGA-III 利用分布良好的參考點來維持種群的多樣性。已有的研究佐證，NSGA-III 相較于NSGA-II 在求解多目標(biāo)優(yōu)化問題能夠取得更好的結(jié)果[21]?？紤]到本文求解的三目標(biāo)優(yōu)化問題，我們采用NSGA-III 算法中的快速非支配排序和選擇機制。因受限于篇幅，具體的步驟可見文獻(xiàn)[22]，本文在此不再贅述。

3 仿真分析

3.1 算例求解

本文通過求解算例來驗證設(shè)計算例的有效性。由于沒有測試的標(biāo)準(zhǔn)例題庫，故本文選擇標(biāo)準(zhǔn)例題中C101中35個客戶點作為本文的求解算例[23]，并在原算例的基礎(chǔ)上對所有老人添加了服務(wù)人員的偏好集合以及老人可容忍的時間窗。在某市的二維平面內(nèi)，有一處虛擬養(yǎng)老服務(wù)中心位于(40,50)，該服務(wù)中心共有6 名服務(wù)人員，共有35 個老人分布在該平面上。本文在Windows10 操作系統(tǒng)，內(nèi)存為8G，處理器為英特爾Core i7-6700HQ 的計算機上采用Matlab R2016a 來編程。文中設(shè)置的參數(shù)見表2。

表2 模型和算法參數(shù)設(shè)置

經(jīng)過求解，共求得23 個Pareto 最優(yōu)解，由于篇幅限制，本文從中選擇出成本最優(yōu)的調(diào)度路線圖解用于展示，其服務(wù)路線圖如圖4所示。

圖4 成本最優(yōu)的服務(wù)路線圖

3.2 算法性能對比

為了驗證本文構(gòu)建的DMO-WOA 算法的優(yōu)越性，本文同時采用NSGA-II 和NSGA-III 算法作為參照，并采用Spacing和C兩個指標(biāo)評價算法的性能。其中Spacing指標(biāo)表示解集分布的均勻性，指標(biāo)值越小則說明得到的解集分布越均勻,C 指標(biāo)計算的是一個解集中的解至少被另一個參照解集中的一個解弱支配的比例，用于衡量的是兩個解集之間的重合程度，結(jié)果如表3所示。

表3 算法性能對照

從表3 能夠看出，無論是最優(yōu)解的數(shù)量或是接解得空間的分布，本文設(shè)計的DMO-WOA 算法相較于NSGA-II 和NSGA-III 具有良好的性能，為了更直觀地對比這三種算法的性能，本文繪制了三種算法求解的箱型圖如圖5所示。

圖5 箱型圖

從結(jié)果來看，相較于對照的NSGA-II 和NSGAIII 算法，本文DMO-WOA 算法在控制服務(wù)中心成本、提升老人滿意度上有顯著效果。由于服務(wù)人員滿意度目標(biāo)取值空間較前兩者更緊湊些，所以，箱形圖并未表現(xiàn)出明顯優(yōu)勢?？傮w來看，本文的DMO-WOA算法對于求解本文問題具有顯著優(yōu)勢。

4 結(jié)論與展望

本文針對虛擬養(yǎng)老服務(wù)人員調(diào)度問題，通過分析老人、虛擬養(yǎng)老服務(wù)中心和服務(wù)人員的利益追求，并以成本最優(yōu)、老人滿意度最大和服務(wù)人員滿意度最大構(gòu)建多目標(biāo)優(yōu)化模型；設(shè)計了離散化多目標(biāo)鯨魚優(yōu)化算法，同時利用NSGA-II 算法和NSGA-III 算法進(jìn)行對比分析，并通過求解算例驗證了本文算法的優(yōu)越性。本文的研究是針對老人需求確定情況下的服務(wù)人員調(diào)度問題，未來將從動態(tài)視角對服務(wù)人員實時調(diào)度問題展開研究。