黃金瑤，劉同來，吳嘉鑫，武繼剛

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

0 概述

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

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

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

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

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

1 本文模型

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

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

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

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

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

表1 符號定義Table 1 Symbol descriptions

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

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

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

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

4）黑名單

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

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

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

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

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

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

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

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

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

2 本文算法

2.1 貪心算法

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

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

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

算法1貪心算法

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

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

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

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

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

2.2 定制遺傳算法

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

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

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

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

本文定制的遺傳算法中各個算子的具體操作過程如下。

1）交叉

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

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

2）變異

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

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

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

3 實驗結(jié)果與分析

3.1 實驗設(shè)置

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

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

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

3.2 結(jié)果分析

本文將貪心算法、定制的遺傳算法與基準算法和隨機算法在小、中、大這3 種規(guī)模的數(shù)據(jù)集中所得的結(jié)果進行對比，結(jié)果如圖5～圖7 所示。由圖5 可知，對于小規(guī)模的數(shù)據(jù)集，貪心算法和定制的遺傳算法所得到家庭護理機構(gòu)的平均服務(wù)質(zhì)量相較基準算法分別提高35.7%和89.7%，較隨機算法分別提高51.1%和111.4%。由圖6 可知，貪心算法和定制的遺傳算法在中規(guī)模數(shù)據(jù)集上所得到的平均服務(wù)質(zhì)量相較基準算法分別提高32.6%和94.5%，較隨機算法分別提高81.9%和166.9%。由圖7 可知，對于大規(guī)模的數(shù)據(jù)集，貪心算法和定制的遺傳算法所得到的平均服務(wù)質(zhì)量較基準算法分別提高30.4%和49.7%，較隨機算法分別提高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 中，對于任意規(guī)模的任意例子，貪心算法和定制的遺傳算法所得到的服務(wù)質(zhì)量均比隨機算法所得到的服務(wù)質(zhì)量高。整體而言，相比于基準算法，貪心算法和定制的遺傳算法的服務(wù)質(zhì)量分別提高了31.7%和65.7%；相較于隨機算法，貪心算法和定制的遺傳算法的服務(wù)質(zhì)量分別提高了79.8%和126.3%。這是因為在貪心算法中，老人按照開始等待服務(wù)時間升序排序，且服務(wù)時長較短的老人優(yōu)先被服務(wù)，在護工有限的工作時間下，可以服務(wù)更多的老人，從而減少老人未被服務(wù)的次數(shù)，提高家庭護理機構(gòu)的服務(wù)質(zhì)量。定制的遺傳算法以適應(yīng)度為衡量標準在種群中淘汰部分適應(yīng)度較差的個體，經(jīng)過多輪迭代后，得到的個體一定比初始種群中個體的適應(yīng)度更高。因此，貪心算法和定制的遺傳算法所得到的護工路徑使服務(wù)質(zhì)量更高，比基準算法和隨機算法的效果更好。

如圖8 所示，以小規(guī)模數(shù)據(jù)集的實例1 為例，隨著迭代次數(shù)的增加，觀察家庭護理機構(gòu)的服務(wù)質(zhì)量變化。當(dāng)?shù)螖?shù)范圍在0～84 時，服務(wù)質(zhì)量的最優(yōu)值和平均值顯著增長。當(dāng)?shù)螖?shù)大于84 時，服務(wù)質(zhì)量的最優(yōu)值和平均值保持不變。實驗結(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ī)模實例中從開始到結(jié)束的平均運行時間。由表3 可知，本文提出的遺傳算法與貪心算法的平均運行時間比隨機算法的運行時間長。從算法運行的循環(huán)次數(shù)來看，貪心算法需要一定時間對工作日期、老人集合以及護工集合進行3 層循環(huán)，而定制的遺傳算法需要進行100 次迭代，因此所提出的貪心算法、定制的遺傳算法和基準算法均比隨機算法的運行時間長，且所提出的貪心算法和基準算法的運行時間較接近。其中：隨機算法、貪心算法和定制的遺傳算法在小規(guī)模數(shù)據(jù)集上的平均運行時間分別為0.005 s、0.050 s 和83.150 s，貪心算法與隨機算法的運行時間比較接近，均小于1 s。

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

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

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

4 結(jié)束語

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