虛擬養(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)老院在我國多個(gè)城市落地，其市場需求擴(kuò)大的同時(shí)也對(duì)服務(wù)質(zhì)量提出了更高的要求。更好的服務(wù)、更低的成本是虛擬養(yǎng)老院能夠長期健康發(fā)展的關(guān)鍵。這其中，服務(wù)人員的調(diào)度問題是控制成本，提高服務(wù)質(zhì)量的關(guān)鍵一環(huán)。

虛擬養(yǎng)老具有服務(wù)的屬性，這就要求不能僅以成本大小作為評(píng)判調(diào)度方案優(yōu)劣的唯一標(biāo)準(zhǔn)。由于老人和服務(wù)人員都是重要的參與主體，對(duì)虛擬養(yǎng)老事業(yè)發(fā)展起到關(guān)鍵作用。因此在制定調(diào)度方案時(shí)，需要明確這兩者的利益追求，在控制成本的同時(shí)兼顧這兩者的利益。當(dāng)前針對(duì)虛擬養(yǎng)老問題的研究，學(xué)術(shù)界普遍是定性研究，其研究內(nèi)容主要包括對(duì)發(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ù)機(jī)構(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]等。此外，機(jī)器學(xué)習(xí)[18]也可用于問題求解。本文的研究從老人、服務(wù)中心和服務(wù)人員的角度出發(fā)，通過分析三者的利益追求，并以成本最優(yōu)、老人和服務(wù)人員滿意度最大為優(yōu)化目標(biāo)，建立多目標(biāo)優(yōu)化模型。

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

1 優(yōu)化模型

1.1 滿意度函數(shù)

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

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

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

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

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

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

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

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

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

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

當(dāng)服務(wù)人員k 的任務(wù)量未超出a 時(shí)，其滿意度為1；當(dāng)任務(wù)量超過a 而未超過b 時(shí)，此時(shí)其滿意度時(shí)其滿意度會(huì)降低；當(dāng)任務(wù)量超過b時(shí)，此時(shí)服務(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ù)中心式⑼為每位老人只接受一個(gè)服務(wù)服務(wù)；式⑽為服務(wù)時(shí)間窗約束，其取值范圍為老人所容忍的時(shí)間范圍，并將其設(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)點(diǎn)。其思想是模擬自然界中鯨魚的捕食行為。在鯨魚群覓食過程中，通常會(huì)有一條或多條鯨魚率先發(fā)現(xiàn)獵物，此時(shí)其他鯨魚就會(huì)向該鯨魚靠近，從而完成捕食行為。傳統(tǒng)的鯨魚優(yōu)化算法一般用于連續(xù)性尋優(yōu)問題，而求解本文的離散化多目標(biāo)優(yōu)化問題需要加以改進(jìn)，具體的步驟如下。

⑴編碼與解碼

編碼和解碼是算法設(shè)計(jì)的前提工作，本文的研究是優(yōu)化目標(biāo)中求解服務(wù)人員的調(diào)度方案，屬于離散化問題求解，因此本文采用自然數(shù)編碼的形式，以代表老人的編號(hào)。以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ù)對(duì)應(yīng)著服務(wù)人員的編號(hào)，方便用于老人對(duì)服務(wù)人員偏好滿意度的求解。

⑵鯨魚群位置更新

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

⑶局部搜索算子

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

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

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

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

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

⑷非支配排序

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

3 仿真分析

3.1 算例求解

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

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

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

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

3.2 算法性能對(duì)比

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

表3 算法性能對(duì)照

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

圖5 箱型圖

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

4 結(jié)論與展望

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