多周期家庭護(hù)理的路徑規(guī)劃與調(diào)度算法

黃金瑤，劉同來(lái)，吳嘉鑫，武繼剛

（廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006）

0 概述

隨著我國(guó)社會(huì)人口老齡化日益加重，老齡群體對(duì)家庭醫(yī)療護(hù)理服務(wù)的需求不斷提高。研究表明，我國(guó)的老年人口將在2050 年達(dá)到4 億以上，其中，上億人口需接受長(zhǎng)期的家庭醫(yī)療護(hù)理服務(wù)［1］（Home Health Care，HHC）。HHC 是一種由家庭護(hù)理機(jī)構(gòu)負(fù)責(zé)管理及分配空閑的醫(yī)護(hù)人員以及醫(yī)療設(shè)備，為有需要的老人提供一定程度的醫(yī)療診治、生活照料等上門服務(wù)，能夠減少老人的住院開(kāi)銷，緩解醫(yī)療中心的服務(wù)壓力［2-3］。因此，促進(jìn)HHC 行業(yè)的發(fā)展對(duì)提高行動(dòng)不便的老人群體的醫(yī)療服務(wù)質(zhì)量具有重要意義。

申請(qǐng)HHC 的的具體步驟：老人首先向家庭護(hù)理機(jī)構(gòu)提交一段時(shí)間內(nèi)的服務(wù)申請(qǐng)，包括服務(wù)日期、服務(wù)時(shí)長(zhǎng)、服務(wù)項(xiàng)目等；接著家庭護(hù)理機(jī)構(gòu)根據(jù)需求為老人合理安排符合要求的護(hù)工提供上門服務(wù)；最后接到服務(wù)任務(wù)的護(hù)工將在指定時(shí)間內(nèi)從當(dāng)前所在位置出發(fā)到指定的位置為老人提供服務(wù)。由此可知，家庭護(hù)理路徑規(guī)劃與調(diào)度問(wèn)題（Home Health Care routing and scheduling Problem，HHCP）［4］指的是家庭護(hù)理機(jī)構(gòu)在同時(shí)滿足老人需求和護(hù)工工作時(shí)間的限制條件下，為護(hù)工安排合理的護(hù)理路徑，使家庭護(hù)理機(jī)構(gòu)的服務(wù)質(zhì)量最高的問(wèn)題。

HHCP 一般可劃分為單周期和多周期2 類。單周期HHCP 研究如何為護(hù)工安排周期為一天的護(hù)理路徑［5］，如文獻(xiàn)［6］認(rèn)為護(hù)工的工作時(shí)間對(duì)最終規(guī)劃路徑的適應(yīng)性存在重要影響，因此研究平衡各個(gè)護(hù)工的工作時(shí)間，但沒(méi)有考慮多周期的影響。與單周期HHCP 不同，多周期HHCP 則研究如何為護(hù)工安排2 天或2 天以上的護(hù)理路徑［7］。文獻(xiàn)［8］在考慮護(hù)理連續(xù)性約束的基礎(chǔ)上研究周期為一周的HHCP 問(wèn)題，并將原問(wèn)題分解成多個(gè)子問(wèn)題進(jìn)行求解。但隨著問(wèn)題規(guī)模的增大，多周期HHCP 問(wèn)題最優(yōu)解的獲取時(shí)間呈指數(shù)級(jí)增長(zhǎng)。當(dāng)問(wèn)題規(guī)模達(dá)到一定量級(jí)時(shí)，使用精確算法無(wú)法在規(guī)定時(shí)間內(nèi)得到最優(yōu)解。為保證算法所得到解的時(shí)效性，可采用啟發(fā)式算法對(duì)大規(guī)模多周期HHCP 進(jìn)行求解，如文獻(xiàn)［9］設(shè)計(jì)一種變鄰域搜索算法來(lái)求解具有超時(shí)收費(fèi)、偏好匹配等約束條件的HHCP 問(wèn)題。文獻(xiàn)［10］同時(shí)考慮不確定旅行時(shí)間、服務(wù)時(shí)間等因素并應(yīng)用禁忌搜索算法求解一個(gè)長(zhǎng)周期HHCP 問(wèn)題。

目前大部分多周期HHCP 研究工作集中于最大化家庭護(hù)理機(jī)構(gòu)的服務(wù)質(zhì)量，這些工作所定義的服務(wù)質(zhì)量由老人的服務(wù)需求是否已經(jīng)滿足［11-12］、服務(wù)是否及時(shí)［13-14］、老人對(duì)服務(wù)是否滿意［15-17］等因素構(gòu)成。然而除上述因素以外，還存在其他因素影響家庭護(hù)理機(jī)構(gòu)的服務(wù)質(zhì)量。例如：當(dāng)護(hù)工擁有更匹配的服務(wù)技能或曾經(jīng)對(duì)某一位老人進(jìn)行過(guò)多次護(hù)理時(shí)，可以有效提高該護(hù)工提供給老人的服務(wù)質(zhì)量；考慮到老人在護(hù)工選擇上的主觀因素，老人在申請(qǐng)護(hù)理服務(wù)時(shí)，可根據(jù)自身偏好提供一份黑名單，家庭護(hù)理機(jī)構(gòu)將不為老人安排名單內(nèi)的護(hù)工；當(dāng)服務(wù)技能、收費(fèi)、時(shí)間等客觀因素或黑名單約束未能安排護(hù)工給老人提供護(hù)理服務(wù)時(shí)，家庭護(hù)理機(jī)構(gòu)的服務(wù)質(zhì)量會(huì)因此降低。目前關(guān)于HHCP 的相關(guān)工作尚未考慮上述因素對(duì)家庭護(hù)理機(jī)構(gòu)的服務(wù)質(zhì)量影響。

本文提出帶服務(wù)約束的多周期家庭護(hù)理路徑規(guī)劃與調(diào)度問(wèn)題，并證明該問(wèn)題的NP 難解性。為了在老人提供的黑名單、必選服務(wù)技能、服務(wù)價(jià)格和服務(wù)時(shí)間的約束下提升家庭護(hù)理機(jī)構(gòu)的服務(wù)質(zhì)量，提出一個(gè)基于貪心策略的路徑規(guī)劃算法，該算法在滿足老人服務(wù)約束的前提下，優(yōu)先為開(kāi)始等待服務(wù)時(shí)間最早的老人安排能夠提供服務(wù)質(zhì)量最高的護(hù)工。在此基礎(chǔ)上，提出定制的遺傳算法，以獲得更優(yōu)的多周期護(hù)工路徑規(guī)劃方案。

1 本文模型

圖1 所示為家庭護(hù)理機(jī)構(gòu)為老人提供家庭護(hù)理服務(wù)的過(guò)程。本文針對(duì)家庭護(hù)理機(jī)構(gòu)的護(hù)工護(hù)理路徑規(guī)劃與調(diào)度問(wèn)題構(gòu)建數(shù)學(xué)模型。在本文模型中，假設(shè)家庭護(hù)理機(jī)構(gòu)進(jìn)行路徑規(guī)劃的日期集合為D，日期數(shù)量為g，護(hù)工的數(shù)量為a，老人的數(shù)量為b。令K={i|1 ≤i≤a}和P={j|1 ≤j≤b}分別表示護(hù)工集合和老人集合，設(shè)護(hù)工i的工作日期集合為老人j的請(qǐng)求服務(wù)日期集合為在護(hù)工的同一工作日期內(nèi)，護(hù)工可為一名或多名老人提供護(hù)理服務(wù)，而每名老人每天最多只能由一名護(hù)工服務(wù)。老人j向家庭護(hù)理機(jī)構(gòu)申請(qǐng)的預(yù)期服務(wù)請(qǐng)求次數(shù)為nj，每次請(qǐng)求服務(wù)時(shí)長(zhǎng)都為tj，以及經(jīng)過(guò)安排后一周內(nèi)實(shí)際被服務(wù)的次數(shù)為zj。

圖1 本文家庭護(hù)理服務(wù)模型Fig.1 Model of home health care in this paper

護(hù)理連續(xù)程度可反映護(hù)工對(duì)老人的熟悉程度。對(duì)于曾經(jīng)服務(wù)過(guò)老人的護(hù)工，其為老人提供服務(wù)的次數(shù)越多，相應(yīng)的護(hù)理連續(xù)程度就越高，護(hù)工對(duì)老人提供護(hù)理的服務(wù)質(zhì)量也越高。受文獻(xiàn)［18］啟發(fā)，令函數(shù)f(si,j)表示護(hù)工i與老人j之間的護(hù)理連續(xù)程度，其計(jì)算公式定義如下：

其中：si,j為護(hù)工i過(guò)去服務(wù)老人j的次數(shù)。

接下來(lái)將詳細(xì)介紹護(hù)工為老人服務(wù)所必須滿足的約束，包括服務(wù)時(shí)間約束、服務(wù)技能約束、服務(wù)價(jià)格約束、以及黑名單約束等。本文涉及的符號(hào)定義如表1 所示。

表1 符號(hào)定義Table 1 Symbol descriptions

1）服務(wù)時(shí)間約束與護(hù)工護(hù)理路徑的表示

2）服務(wù)技能約束

老人j對(duì)護(hù)工的服務(wù)技能需求包括必選技能Mjp和可選技能Oj，其中必選技能意味著服務(wù)老人j的護(hù)工i的專業(yè)技能Mik必須包含Mjp，即Mjp?Mik,?j?Xid,i?K。

3）服務(wù)價(jià)格約束

4）黑名單

老人j向家庭護(hù)理機(jī)構(gòu)中心發(fā)出護(hù)理服務(wù)請(qǐng)求時(shí)，將會(huì)附加黑名單Lj，家庭護(hù)理機(jī)構(gòu)將只安排不在該名單內(nèi)的護(hù)工為該老人服務(wù)，即：i?Lj,?j?Xid,d?i?K。

護(hù)工i為老人j提供護(hù)理的服務(wù)質(zhì)量由護(hù)工i掌握的技能與老人j可選服務(wù)技能的匹配度以及護(hù)工為老人服務(wù)的連續(xù)程度f(wàn)(si,j)2 個(gè)部分組成。令Hi,j表示護(hù)工i某一次為老人j提供護(hù)理的服務(wù)質(zhì)量，可得其中：α1、α2分別表示護(hù)工掌握的技能與老人可選服務(wù)技能的匹配度的權(quán)重，以及護(hù)理連續(xù)程度對(duì)護(hù)工服務(wù)質(zhì)量影響的權(quán)重。

本文定義家庭護(hù)理機(jī)構(gòu)提供給老人的服務(wù)質(zhì)量由以下2 個(gè)部分組成：所有護(hù)工一周內(nèi)為老人提供護(hù)理的服務(wù)質(zhì)量之和；老人未被滿足的服務(wù)請(qǐng)求次數(shù)（未被服務(wù)次數(shù)）。

令H表示家庭護(hù)理機(jī)構(gòu)提供的服務(wù)質(zhì)量，可得：

其中：α3表示老人未被服務(wù)的次數(shù)對(duì)家庭護(hù)理機(jī)構(gòu)服務(wù)質(zhì)量影響的權(quán)重。為了統(tǒng)一量綱，本文按照文獻(xiàn)［19］引入了系數(shù)γ和γ′，其中γ和γ′分別表示每滿足一個(gè)可選技能可提高的服務(wù)質(zhì)量，以及每未滿足一次服務(wù)請(qǐng)求所降低的服務(wù)質(zhì)量。

本文所研究的帶服務(wù)約束的多周期家庭護(hù)理路徑規(guī)劃與調(diào)度問(wèn)題（Multi-period Home Health care routing and Scheduling Problem with service constraints，MHHSP）的形式化描述如式（4）～式（10）所示：

如式（4）所示，MHHSP 的目標(biāo)為最大化家庭護(hù)理的服務(wù)質(zhì)量。式（5）表示護(hù)工需在老人的等待時(shí)間窗內(nèi)為老人提供護(hù)理服務(wù)。式（6）表示在護(hù)工所有有序的護(hù)理路徑中，護(hù)工必須按順序?yàn)槔先颂峁┓?wù)，即護(hù)工i服務(wù)路徑中的任意一個(gè)老人j的結(jié)束時(shí)間必須在護(hù)工i為下一個(gè)老人j′服務(wù)的開(kāi)始時(shí)間之前。式（7）表示護(hù)工的服務(wù)收費(fèi)不能超過(guò)老人所能接受的服務(wù)價(jià)格。式（8）表示護(hù)工的專業(yè)技能必須滿足老人的必選服務(wù)技能需求。式（9）表示服務(wù)老人的護(hù)工必須不在該老人提供的黑名單上。式（10）表示變量i、j和d的取值范圍。

定理1本文所提出的家庭護(hù)理資源調(diào)度和路徑規(guī)劃問(wèn)題MHHSP 為NP 難問(wèn)題。

證明本文所提出的家庭護(hù)理資源調(diào)度和路徑規(guī)劃問(wèn)題MHHSP 可以歸約為多車場(chǎng)車輛路徑優(yōu)化問(wèn)題（Multi-Depot Vehicle Routing Problem，MDVRP）。MDVRP 具體描述如下：已知客戶的位置、車輛的位置以及客戶的需求，如何為車輛安排合適的行車路徑，使路徑成本最小。針對(duì)本文所提出的問(wèn)題構(gòu)建一個(gè)特例，即不考慮式（7）～式（9）。在該特例中，將老人看作客戶，護(hù)工看作車輛，老人的需求看作客戶的需求，最大化家庭護(hù)理機(jī)構(gòu)的服務(wù)質(zhì)量等同于最小化路徑成本，因此所提出問(wèn)題的特例等價(jià)于MDVRP。由于MDVRP是NP-hard［20］，故所提出的問(wèn)題的特例也是NP-hard，即NP 難解問(wèn)題。因此，所提出的MHHSP 問(wèn)題具備NP 難解性。

2 本文算法

2.1 貪心算法

由于MHHSP 是一個(gè)NP 難解問(wèn)題，獲取最優(yōu)解的時(shí)間會(huì)隨求解問(wèn)題的規(guī)模呈現(xiàn)指數(shù)級(jí)增長(zhǎng)。為了在家庭護(hù)理機(jī)構(gòu)可接受的時(shí)間范圍內(nèi)得到一個(gè)可行且合理的解決方案，本文首先針對(duì)MHHSP 提出一個(gè)貪心算法來(lái)快速生成一個(gè)可行的初始解。該算法的基本思想是在每個(gè)工作日期內(nèi)，對(duì)老人集合按照開(kāi)始等待服務(wù)時(shí)間進(jìn)行升序排序，然后依次遍歷所有老人，優(yōu)先為開(kāi)始等待服務(wù)時(shí)間較早的老人分配空閑且服務(wù)質(zhì)量最高的護(hù)工。

貪心算法的求解步驟如下所示：

步驟1從D中選擇一天d作為待分配日期，設(shè)置護(hù)工i在工作日d的護(hù)理路徑Xid為空，以及該護(hù)工在第d天的最早工作時(shí)間為護(hù)工的上班時(shí)間，如算法1 第3 行所示。然后根據(jù)老人j的開(kāi)始等待服務(wù)時(shí)間，對(duì)老人集合進(jìn)行升序排序，并將排序后的老人添加到隊(duì)列R中，如算法1 第2 行～第5 行所示。

算法1貪心算法

步驟2從R中選擇開(kāi)始等待服務(wù)時(shí)間最早的老人j。計(jì)算不服務(wù)老人j時(shí)所得到的整體服務(wù)質(zhì)量為H。遍歷所有護(hù)工，計(jì)算不同護(hù)工為老人服務(wù)時(shí)的整體服務(wù)質(zhì)量H，并從中選擇使整體服務(wù)質(zhì)量最大且滿足式（7）～式（9）的護(hù)工i服務(wù)老人j。最后，將老人j添加到路徑Xid中。如算法1 第7 行～第22 行所示。重復(fù)步驟2，直至遍歷完R。

步驟3重復(fù)步驟1 和步驟2，直至遍歷完D。貪心算法的偽代碼描述如算法1 所示。

定理2本文提出的貪心算法時(shí)間復(fù)雜度為O(gba+gb×logab)。

證明如算法1 所示，算法的整體結(jié)構(gòu)主要包括3 個(gè)嵌套的for 循環(huán)。外層循環(huán)的次數(shù)為工作日期數(shù)目g，時(shí)間復(fù)雜度為O(g)；中間層循環(huán)的次數(shù)為老人數(shù)目b，時(shí)間復(fù)雜度為O(b)；當(dāng)遍歷每個(gè)老人時(shí)，內(nèi)層循環(huán)需要遍歷所有護(hù)工并計(jì)算服務(wù)質(zhì)量，其循環(huán)次數(shù)為護(hù)工數(shù)目a，時(shí)間復(fù)雜度為O(a)，因此3 個(gè)嵌套的for 循環(huán)的時(shí)間復(fù)雜度為O(gba)；在為老人安排護(hù)工前，根據(jù)老人的服務(wù)時(shí)間進(jìn)行快速排序，排序的個(gè)數(shù)為老人數(shù)目b，按照排序的結(jié)果從小到大遍歷每一個(gè)老人，時(shí)間復(fù)雜度為O(b×logab)。快速排序與中間層循環(huán)同級(jí)，即整個(gè)算法的時(shí)間復(fù)雜度O(gba)+O(g) ×O(b×logab)=O(gba+gb×logab),因此貪心算法的時(shí)間復(fù)雜度為O(gba+gb×logab)。

為方便理解，本文通過(guò)一個(gè)例子來(lái)描述該算法的貪心策略。假設(shè)需要安排2 名護(hù)工（即k1和k2）為4 名老人（即p1、p2、p3和p4）提供服務(wù)，并且護(hù)工k1和k2均滿足老人p1、p2、p3和p4的服務(wù)技能需求、服務(wù)時(shí)間、服務(wù)價(jià)格和服務(wù)人員約束。貪心算法首先根據(jù)老人開(kāi)始等待服務(wù)的時(shí)間從早到晚對(duì)老人進(jìn)行排序。假設(shè)排序結(jié)果為p1、p2、p3和p4，則該算法將進(jìn)行4 輪調(diào)度，每輪調(diào)度選擇一位護(hù)工服務(wù)一位老人。具體地，在第1 輪調(diào)度時(shí)，優(yōu)先為老人p1安排服務(wù)。該算法遍歷所有護(hù)工，并從中選擇滿足要求且使服務(wù)質(zhì)量最高的護(hù)工（假設(shè)該護(hù)工為k1）為p1提供服務(wù)，同時(shí)更新護(hù)工k1的工作時(shí)間。第2 輪調(diào)度則為老人p2安排服務(wù)，重新遍歷所有護(hù)工，并從中選擇滿足服務(wù)要求且使得服務(wù)質(zhì)量最高的護(hù)工（假設(shè)為k2）為p2提供服務(wù)。經(jīng)過(guò)4 輪調(diào)度后，得出k1的護(hù)理路徑為的護(hù)理路徑為

2.2 定制遺傳算法

本文在貪心算法的基礎(chǔ)上提出一個(gè)定制的遺傳算法，對(duì)所生成的初始解作進(jìn)一步優(yōu)化。定制遺傳算法中的每個(gè)解（個(gè)體）可由一條染色體表示，多個(gè)個(gè)體組成一個(gè)種群［21］。本文用一個(gè)二維數(shù)組表示一條染色體，其中第一維表示日期，第二維表示某一天所有護(hù)工的護(hù)理路徑。圖2 展示了染色體編碼的一個(gè)示例，其中有5 名護(hù)工，40 名老人。在該例子中，本文將40 名老人編號(hào)為1～40，將5 名護(hù)工編號(hào)為41～45。由于一條護(hù)理路徑由護(hù)工以及這名護(hù)工所服務(wù)的所有老人組成，因此，在染色體中，每條護(hù)理路徑以護(hù)工的編號(hào)進(jìn)行分隔，即2 名護(hù)工之間的編號(hào)代表前一名護(hù)工的護(hù)理路徑。例如，路徑1 包括編號(hào)為41 的護(hù)工、編號(hào)為1、5、23 的老人，即編號(hào)為41 的護(hù)工在周一依次服務(wù)編號(hào)為1、5、23 的老人。

圖2 染色體編碼Fig.2 Encoding of chromosome

本文定制的遺傳算法基本思路是模擬自然界的優(yōu)勝劣汰過(guò)程，目的是選出其中最好的個(gè)體［22］。本文首先將貪心算法生成的初始解作為定制的遺傳算法初始種群，并對(duì)其進(jìn)行編碼；然后進(jìn)行交叉、變異、選擇操作得出下一代的種群，并循環(huán)上述步驟；最后，當(dāng)?shù)螖?shù)達(dá)到指定值時(shí)，終止循環(huán)并輸出迭代過(guò)程中所能找到適應(yīng)度最高的個(gè)體作為算法的解。

在本文遺傳算法中，計(jì)算每個(gè)個(gè)體的適應(yīng)度等價(jià)于計(jì)算該個(gè)體所對(duì)應(yīng)解的服務(wù)質(zhì)量，選擇操作將根據(jù)個(gè)體的適應(yīng)度來(lái)選擇下一代的種群個(gè)體，適應(yīng)度越高的個(gè)體被選擇作為下一代種群的概率越高。

本文定制的遺傳算法中各個(gè)算子的具體操作過(guò)程如下。

1）交叉

交叉是指交換2 個(gè)不同染色體（個(gè)體）中的某個(gè)片段（護(hù)理路徑），從而產(chǎn)生新個(gè)體遺傳到下一代。本文定制的遺傳算法采用單點(diǎn)交叉方式，染色體之間有一定概率發(fā)生配對(duì)交叉。配對(duì)的2 個(gè)不同的個(gè)體一般從種群中隨機(jī)選擇，交換的片段從2 個(gè)染色體的同一行（同一天）隨機(jī)選擇。具體操作如圖3 所示：從群體中隨機(jī)選擇染色體1 作為父親，染色體2作為母親，并隨機(jī)選擇1 名護(hù)工作為分隔點(diǎn)，將父親染色體在分隔點(diǎn)前的片段以及母親染色體在分隔點(diǎn)后的片段交換位置，形成2 個(gè)新個(gè)體。

圖3 交叉示例Fig.3 Example of crossover

2）變異

變異主要由插入、交換和刪除3 種操作組成，每次迭代染色體均會(huì)隨機(jī)選擇3 種變異操作中的一種，發(fā)生一定概率的變異，產(chǎn)生新個(gè)體。具體地，插入操作是對(duì)于某一行中未出現(xiàn)（即未被服務(wù)）的老人，隨機(jī)選擇其中1 名，并將其插入到該行的隨機(jī)位置中。刪除操作是從染色體的某一行中隨機(jī)選擇1 個(gè)老人，并將其刪除。交換操作是在染色體的某一行中隨機(jī)選擇2 個(gè)不同的老人進(jìn)行位置交換。

圖4 以某條染色體為例，展示了3 種變異。插入操作、刪除操作和交換操作分別用符號(hào)+、?和X 來(lái)表示，（+，2，3，4）表示選擇編號(hào)為3 的老人，將其插入到該染色體周二的護(hù)理路徑中，插入的位置為4；（?，1，9）表示刪除該染色體周一的護(hù)理路徑中位置為9 的老人；（X，7，12，14）表示將該染色體周日的護(hù)理路徑中位置為12 和14 的老人進(jìn)行交換。

圖4 變異示例Fig.4 Example of mutation

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)置

本文在60 個(gè)實(shí)例的開(kāi)源數(shù)據(jù)集［23］上進(jìn)行實(shí)驗(yàn)，并以家庭護(hù)理機(jī)構(gòu)的服務(wù)質(zhì)量為指標(biāo)與基準(zhǔn)算法和隨機(jī)算法進(jìn)行比較。其中，基準(zhǔn)算法由文獻(xiàn)［18］基于MDVRP 提出，其貪心策略是優(yōu)先為服務(wù)時(shí)長(zhǎng)最長(zhǎng)的老人安排能夠提供服務(wù)質(zhì)量最高的護(hù)工。該數(shù)據(jù)集由3 組不同規(guī)模（包括小規(guī)模、中規(guī)模和大規(guī)模）的實(shí)例組成，每組有20 個(gè)具體實(shí)例。其中，每個(gè)小規(guī)模實(shí)例均包含40 名待分配的老人和5 名空閑的護(hù)工，中規(guī)模例子包含80 名老人和10 名護(hù)工，大規(guī)模例子包含150 名老人和20 名護(hù)工。

本文模型的具體參數(shù)設(shè)置如表2所示。在定制的遺傳算法參數(shù)配置中，設(shè)置種群迭代次數(shù)為100 次，種群大小設(shè)為500個(gè)，交叉和變異概率均設(shè)為0.2，變異的3種操作發(fā)生概率均為1/3。本文使用Python實(shí)現(xiàn)所提出的貪心算法和定制的遺傳算法，在Windows 10、3.20 GHz Intel Core i7-8700 CPU 和16 GB 內(nèi)存的環(huán)境上進(jìn)行測(cè)試。

表2 參數(shù)設(shè)置Table 2 Parameters setting

3.2 結(jié)果分析

本文將貪心算法、定制的遺傳算法與基準(zhǔn)算法和隨機(jī)算法在小、中、大這3 種規(guī)模的數(shù)據(jù)集中所得的結(jié)果進(jìn)行對(duì)比，結(jié)果如圖5～圖7 所示。由圖5 可知，對(duì)于小規(guī)模的數(shù)據(jù)集，貪心算法和定制的遺傳算法所得到家庭護(hù)理機(jī)構(gòu)的平均服務(wù)質(zhì)量相較基準(zhǔn)算法分別提高35.7%和89.7%，較隨機(jī)算法分別提高51.1%和111.4%。由圖6 可知，貪心算法和定制的遺傳算法在中規(guī)模數(shù)據(jù)集上所得到的平均服務(wù)質(zhì)量相較基準(zhǔn)算法分別提高32.6%和94.5%，較隨機(jī)算法分別提高81.9%和166.9%。由圖7 可知，對(duì)于大規(guī)模的數(shù)據(jù)集，貪心算法和定制的遺傳算法所得到的平均服務(wù)質(zhì)量較基準(zhǔn)算法分別提高30.4%和49.7%，較隨機(jī)算法分別提高87.2%和114.9%。

圖5 不同算法在小規(guī)模數(shù)據(jù)集下的服務(wù)質(zhì)量Fig.5 Service quality of different algorithms on small data set

圖6 不同算法在中規(guī)模數(shù)據(jù)集下的服務(wù)質(zhì)量Fig.6 Service quality of different algorithms on medium data set

圖7 不同算法在大規(guī)模數(shù)據(jù)集下的服務(wù)質(zhì)量Fig.7 Service quality of different algorithms on large data set

在圖5～圖7 中，對(duì)于任意規(guī)模的任意例子，貪心算法和定制的遺傳算法所得到的服務(wù)質(zhì)量均比隨機(jī)算法所得到的服務(wù)質(zhì)量高。整體而言，相比于基準(zhǔn)算法，貪心算法和定制的遺傳算法的服務(wù)質(zhì)量分別提高了31.7%和65.7%；相較于隨機(jī)算法，貪心算法和定制的遺傳算法的服務(wù)質(zhì)量分別提高了79.8%和126.3%。這是因?yàn)樵谪澬乃惴ㄖ?，老人按照開(kāi)始等待服務(wù)時(shí)間升序排序，且服務(wù)時(shí)長(zhǎng)較短的老人優(yōu)先被服務(wù)，在護(hù)工有限的工作時(shí)間下，可以服務(wù)更多的老人，從而減少老人未被服務(wù)的次數(shù)，提高家庭護(hù)理機(jī)構(gòu)的服務(wù)質(zhì)量。定制的遺傳算法以適應(yīng)度為衡量標(biāo)準(zhǔn)在種群中淘汰部分適應(yīng)度較差的個(gè)體，經(jīng)過(guò)多輪迭代后，得到的個(gè)體一定比初始種群中個(gè)體的適應(yīng)度更高。因此，貪心算法和定制的遺傳算法所得到的護(hù)工路徑使服務(wù)質(zhì)量更高，比基準(zhǔn)算法和隨機(jī)算法的效果更好。

如圖8 所示，以小規(guī)模數(shù)據(jù)集的實(shí)例1 為例，隨著迭代次數(shù)的增加，觀察家庭護(hù)理機(jī)構(gòu)的服務(wù)質(zhì)量變化。當(dāng)?shù)螖?shù)范圍在0～84 時(shí)，服務(wù)質(zhì)量的最優(yōu)值和平均值顯著增長(zhǎng)。當(dāng)?shù)螖?shù)大于84 時(shí)，服務(wù)質(zhì)量的最優(yōu)值和平均值保持不變。實(shí)驗(yàn)結(jié)果表明，定制的遺傳算法在第84 代左右得到的適應(yīng)度基本穩(wěn)定，并且能夠在迭代次數(shù)為100 次內(nèi)快速獲得MHHSP 的較優(yōu)解。

圖8 定制的遺傳算法每次迭代的服務(wù)質(zhì)量Fig.8 Service quality of per iteration of customized genetic algorithm

表3 所示為不同算法在不同規(guī)模實(shí)例中從開(kāi)始到結(jié)束的平均運(yùn)行時(shí)間。由表3 可知，本文提出的遺傳算法與貪心算法的平均運(yùn)行時(shí)間比隨機(jī)算法的運(yùn)行時(shí)間長(zhǎng)。從算法運(yùn)行的循環(huán)次數(shù)來(lái)看，貪心算法需要一定時(shí)間對(duì)工作日期、老人集合以及護(hù)工集合進(jìn)行3 層循環(huán)，而定制的遺傳算法需要進(jìn)行100 次迭代，因此所提出的貪心算法、定制的遺傳算法和基準(zhǔn)算法均比隨機(jī)算法的運(yùn)行時(shí)間長(zhǎng)，且所提出的貪心算法和基準(zhǔn)算法的運(yùn)行時(shí)間較接近。其中：隨機(jī)算法、貪心算法和定制的遺傳算法在小規(guī)模數(shù)據(jù)集上的平均運(yùn)行時(shí)間分別為0.005 s、0.050 s 和83.150 s，貪心算法與隨機(jī)算法的運(yùn)行時(shí)間比較接近，均小于1 s。

表3 不同算法在不同規(guī)模數(shù)據(jù)集下的運(yùn)行時(shí)間Table 3 Average running time of different algorithms on different scale data sets s

圖9 為在不同算法所得到的解中，不同服務(wù)次數(shù)的老人數(shù)量分布情況。其中，橫坐標(biāo)的“0”表示老人一周內(nèi)沒(méi)有被服務(wù)，“1”表示老人一周內(nèi)被服務(wù)一次，以此類推。由圖9 可知，當(dāng)服務(wù)次數(shù)范圍在0～2時(shí)，隨著老人服務(wù)次數(shù)的增加，老人的數(shù)量也在增長(zhǎng)；當(dāng)服務(wù)次數(shù)大于2 時(shí)，老人的數(shù)量隨之減少，這是因?yàn)榇蠖鄶?shù)老人的申請(qǐng)服務(wù)次數(shù)為2 次左右。當(dāng)服務(wù)次數(shù)大于2 時(shí)，貪心算法和定制的遺傳算法的解所分配的老人比基準(zhǔn)算法和隨機(jī)算法高，貪心算法和定制的遺傳算法可以提高老人一周內(nèi)被服務(wù)的次數(shù)。

圖9 服務(wù)次數(shù)的分布情況Fig.9 Distribution of service times

4 結(jié)束語(yǔ)

本文將多周期家庭護(hù)理路徑規(guī)劃與調(diào)度問(wèn)題歸約為多車場(chǎng)車輛路徑優(yōu)化問(wèn)題，證明其NP 難解性。同時(shí)利用貪心算法為服務(wù)開(kāi)始時(shí)間早的老人優(yōu)先安排服務(wù)質(zhì)量最高的護(hù)工，并將得到的結(jié)果作為初始解，通過(guò)定制的遺傳算法得到更優(yōu)的可行解。實(shí)驗(yàn)結(jié)果表明，相較于基準(zhǔn)算法和隨機(jī)算法，本文貪心算法和定制的遺傳算法可有效提高服務(wù)質(zhì)量。由于老人的服務(wù)需求存在不確定性，如新增1 個(gè)待服務(wù)老人、老人的服務(wù)時(shí)間改變、老人臨時(shí)取消服務(wù)等均會(huì)對(duì)家庭護(hù)理的服務(wù)質(zhì)量產(chǎn)生影響，因此下一步將考慮家庭護(hù)理中服務(wù)請(qǐng)求的動(dòng)態(tài)性，設(shè)計(jì)一個(gè)在線的低復(fù)雜度近似算法對(duì)護(hù)工路徑規(guī)劃方案進(jìn)行實(shí)時(shí)調(diào)整，從而完善本文算法。