周期性家庭護(hù)理人員分配問題研究

陸雨薇，袁 彪

（1.廣西科技大學(xué) 機(jī)械與交通工程學(xué)院，廣西 柳州 545006；2.上汽集團(tuán)人工智能實(shí)驗(yàn)室，上海 200038；3.賽可智能科技（上海）有限公司，上海 200038）

0 引言

家庭護(hù)理是指以醫(yī)院、社區(qū)和社會(huì)護(hù)理企業(yè)為主體，由其指定護(hù)理人員上門為客戶提供醫(yī)療、輔助醫(yī)療和生活照料等服務(wù).與傳統(tǒng)的住院醫(yī)療相比，家庭護(hù)理服務(wù)有如下幾個(gè)優(yōu)勢[1-2]：1）顧客足不出戶就能享受到個(gè)性化的醫(yī)療服務(wù)；2）減少住院等所需費(fèi)用；3）提高醫(yī)療資源（如醫(yī)院的病床等）利用率.目前家庭護(hù)理這一服務(wù)模式已經(jīng)得到了大家的認(rèn)可，且發(fā)展迅速.在此背景下，如何為家庭護(hù)理服務(wù)模式提供更科學(xué)的運(yùn)作管理理論，使這一服務(wù)模式得到更好地推廣與應(yīng)用，值得我們考慮.

家庭護(hù)理中的人員計(jì)劃與安排是決定服務(wù)質(zhì)量的重要決策活動(dòng)之一.客戶通常需要若干周的服務(wù)，并指定一周內(nèi)的服務(wù)次數(shù)以及允許服務(wù)日期，也稱作服務(wù)模式（Service pattern）.對于新客戶，需要確定為其服務(wù)的護(hù)理人員以及具體的護(hù)理計(jì)劃.而這一決策過程目前是由有經(jīng)驗(yàn)的護(hù)理人員提前一周靠手工完成，需消耗大量時(shí)間和精力.本文正是為解決這一問題而提出的，問題具體描述如下：給定一個(gè)計(jì)劃期（通常一周），一個(gè)客戶集合以及護(hù)理人員集合，需為客戶指定護(hù)理人員，確定護(hù)理人員的服務(wù)模式以及每個(gè)護(hù)理人員每天的訪問路徑.這一問題類似于經(jīng)典的周期性車輛路徑問題（Periodic Vehicle Routing Problem，PVRP）[3].與PVRP相比，考慮如下約束：1）多類型護(hù)理人員約束，不同的客戶需要不同類型的服務(wù)，如家庭保潔、注射和物理治療等，這些服務(wù)需要不同醫(yī)療護(hù)理技能.管理者會(huì)按照服務(wù)所需技能難度以及護(hù)理人員所擁有技能，將客戶和護(hù)理人員分類，構(gòu)成層次化多類型護(hù)理人員結(jié)構(gòu)，即最高層次護(hù)理人員能服務(wù)所有類型客戶，而最低層次護(hù)理人員只能服務(wù)僅需簡單技能類型的客戶；2）護(hù)理連續(xù)性約束，對客戶而言，應(yīng)盡量避免他們接觸不同的護(hù)理人員.在客戶的角度，他們不用在每次服務(wù)時(shí)都和不同護(hù)理人員建立新關(guān)系，可減少陌生和不適感，而在護(hù)理人員的角度，他們對客戶的身體狀態(tài)十分熟悉，可提供更專業(yè)的服務(wù).護(hù)理連續(xù)性約束可用客戶在護(hù)理公司接受服務(wù)時(shí)訪問他的不同護(hù)理人員數(shù)量小于或等于某一設(shè)定值表示；3）隨機(jī)路途時(shí)間和服務(wù)時(shí)間，在實(shí)際服務(wù)過程中，路途時(shí)間與具體的交通狀況相關(guān)，服務(wù)時(shí)間與客戶的身體狀態(tài)相關(guān)[4]，因此，需考慮隨機(jī)的路途時(shí)間和服務(wù)時(shí)間.

本文所提出的問題包含護(hù)理人員分配以及路徑優(yōu)化兩個(gè)子問題，可使用兩階段算法或集成式算法求解.本文選擇兩階段算法對問題求解，原因如下：1）盡管集成式算法可以求得問題的近優(yōu)或最優(yōu)解，但它只能求解規(guī)模很小的問題，并且所得的解可能會(huì)因?yàn)槿∠蛟黾幽骋豢蛻舻姆?wù)而變得很差或不可行；2）家庭護(hù)理人員日調(diào)度中的一些約束很難在集成式算法中考慮，如服務(wù)優(yōu)先次序約束[5].在所提出的兩階段算法中，使用啟發(fā)式算法估計(jì)護(hù)理人員的路途時(shí)間（即路徑優(yōu)化子問題），設(shè)計(jì)基于禁忌搜索和整數(shù)規(guī)劃的混合算法求解護(hù)理人員分配子問題.在求解護(hù)理人員分配子問題后，可以得到兩類信息：一是每個(gè)客戶由哪些護(hù)理人員服務(wù)；二是每個(gè)客戶選擇何種服務(wù)模式.以這兩類信息作為輸入構(gòu)建護(hù)理人員日路徑優(yōu)化問題，采用已有的一些算法對此問題求解，即可得到護(hù)理人員每天的訪問路徑.

在現(xiàn)有研究中，一些學(xué)者也提出兩階段算法對周期性護(hù)理人員分配問題求解.Begur等[6]研究了護(hù)理人員周調(diào)度問題，將問題分解為一系列獨(dú)立的日調(diào)度問題，然后使用簡單的啟發(fā)式算法求解，但并未考慮護(hù)理連續(xù)性約束.Borsani等[7]將問題表示為一個(gè)護(hù)理人員分配模型和調(diào)度模型，分配模型為新客戶確定護(hù)理人員，調(diào)度模型以分配模型的解為輸入，構(gòu)建護(hù)理人員一周的訪問計(jì)劃，值得注意的是他們假設(shè)路途時(shí)間與訪問順序無關(guān).Yal?inda?等[8]首先以均衡化護(hù)理人員負(fù)荷為目標(biāo)，確定最好的護(hù)理人員分配方案，然后通過求解一個(gè)帶服務(wù)模式的旅行商問題為每個(gè)護(hù)理人員確定一周的訪問路徑，同樣值得注意的是第一階段中護(hù)理人員工作負(fù)荷與訪問順序無關(guān)，后來，他們又提出了基于Kernel Regression的方法估計(jì)護(hù)理人員的路途時(shí)間[9].從以上文獻(xiàn)可以看出，目前提出的兩階段算法假設(shè)護(hù)理人員路途時(shí)間與訪問順序無關(guān)，只能適用于客戶分布在一個(gè)較小區(qū)域內(nèi)的情況.

1 問題描述

1.1 數(shù)學(xué)模型

本文所研究的問題可概括為：在計(jì)劃期H={1,…,h,…}內(nèi)，為每個(gè)客戶i?N選擇和確定滿足技能要求的護(hù)理人員k?K，K為護(hù)理人數(shù)最大數(shù).每個(gè)護(hù)理人員k?K擁有的技能或所屬類別為sk(sk=1,…,m)，每天正常工作時(shí)間長度為D.每個(gè)客戶i?N有技能要求si和服務(wù)模式集合Pi.客戶i的服務(wù)模式p?Pi定義了計(jì)劃期內(nèi)的訪問次數(shù)fi以及可訪問日期bph，如果在服務(wù)模式p中第h天需服務(wù)，則bph=1，反之，則為0.客戶i? N的服務(wù)時(shí)間tsi服從正態(tài)分布，即tsi～ N（μi，σi2）.客戶i與j間的路途時(shí)間ttij也服從正態(tài)分布，即ttij～N（μij，σij2）.每個(gè)客戶i?N只能被技能等于或高于其技能需求的護(hù)理人員k?K服務(wù)，即sk≥si.為滿足護(hù)理連續(xù)性要求，訪問同一客戶的護(hù)理人員數(shù)量不能超過設(shè)定值Q，即在客戶接受服務(wù)時(shí)，最多只有Q個(gè)護(hù)理人員-客戶對，同時(shí)需保證以前周期確定的護(hù)理人員-客戶對（i，k）?PNK在本周計(jì)劃時(shí)仍然滿足.為了構(gòu)造所提出的混合算法，建立基于集分割的數(shù)學(xué)模型，其中，Rhk表示護(hù)理人員k在第h天的路徑集合，chkr表示路徑r?Rhk的總成本，ahkri表示客戶i是否在路徑r?Rhk中，若在則為1，反之為0.決策變量定義如下：xhkr為0～1變量，表示最優(yōu)解中是否選擇路徑r?Rhk；yik為0～1變量，表示護(hù)理人員k是否服務(wù)客戶i；zip為0～1變量，表示客戶i是否選擇服務(wù)模式p?Pi.基于以上描述，定義的數(shù)學(xué)模型如下：

目標(biāo)函數(shù)（1）最小化總成本.約束（2）保證每個(gè)護(hù)理人員選擇一條路徑，注意Rhk中可能包含空路徑（即路徑上不包含任何服務(wù)人員）；當(dāng)從Rhk中選擇空路徑時(shí)，表示護(hù)理人員k在第h天不需工作.約束（3）和約束（4）表示護(hù)理人員在周期內(nèi)按照服務(wù)模式訪問客戶.約束（5）和約束（6）滿足客戶的護(hù)理連續(xù)性約束.約束（7）確保滿足以前周期所確定的護(hù)理人員與客戶關(guān)系.約束（8）預(yù)先將部分yik因?yàn)榧寄芗s束設(shè)定為0.約束（9）—約束（11）定義決策變量為0～1變量.

1.2 路徑總成本計(jì)算

路徑r總成本包含3個(gè)部分：路途成本T（r）、服務(wù)成本S（r）以及加班懲罰成本O（r）.以類型為l的護(hù)理人員路徑r={n0=0，n1，n2，…，ni，…，nr，nr+1=0}為例，ni表示路徑r上的第i個(gè)客戶，nr表示路徑r訪問客戶的數(shù)量，Ct表示單位時(shí)間路途成本，Csl表示類型為l的護(hù)理人員的單位時(shí)間服務(wù)成本，pc表示加班懲罰系數(shù).由于客戶間的路途時(shí)間以及客戶的服務(wù)時(shí)間服從正態(tài)分布并且相互獨(dú)立，護(hù)理人員訪問路徑r的總時(shí)間Tr仍然滿足正態(tài)分布，即，按期望值的定義，3種期望成本計(jì)算公式如下：

從式（12）—式（14）可看出，對包含相同客戶的路徑而言，路徑總成本只與期望路途時(shí)間相關(guān)，因此，計(jì)算一條路徑的總成本，只需確定該路徑的期望路途時(shí)間即可，而這一問題是一個(gè)旅行商問題，故采用最遠(yuǎn)插入法來求得期望路途時(shí)間，這部分將會(huì)在數(shù)值實(shí)驗(yàn)中討論.

2 混合算法

針對所研究的問題，設(shè)計(jì)以禁忌搜索和整數(shù)規(guī)劃為基礎(chǔ)的混合算法.

2.1 算法描述

本文所提出混合算法的主要思想為：收集和存儲(chǔ)禁忌搜索算法在迭代過程中產(chǎn)生的中間解或局部最優(yōu)解，使用它們構(gòu)建整數(shù)規(guī)劃模型（1）—模型（11），利用優(yōu)化軟件求解模型，一方面可以得到禁忌搜索算法在迭代過程中可能遺漏的較好解，另一方面，可以評價(jià)禁忌搜索算法最近搜索的效果，如果若干次迭代后，禁忌搜索算法或整數(shù)規(guī)劃模型無法得到更好的解，則說明要引入新解作為搜索的起點(diǎn).設(shè)nTS表示禁忌搜索算法連續(xù)nTS×1 000次迭代未改善當(dāng)前最好解，nIP表示Cplex連續(xù)nIP次未能改善當(dāng)前最好解，n1和n2是算法的基本參數(shù).混合算法步驟如下：

Step 1構(gòu)建初始解s0，并令當(dāng)前解s=s0；

Step 2以當(dāng)前解s為起點(diǎn)，使用禁忌搜索算法進(jìn)行搜索，并按照護(hù)理人員k和日期h將每次迭代中鄰域的最好解分解，保存在Rhk中；

Step 3判斷禁忌搜索算法當(dāng)前1 000次迭代與前1 000次迭代中得到的最好可行解是否變小，如果變小，則說明目前的搜索是有效的，令nTS=0，繼續(xù)當(dāng)前搜索；反之，令nTS=nTS+1；

Step 4當(dāng)nTS≥n1時(shí)，構(gòu)建整數(shù)規(guī)劃模型，并使用Cplex求解模型；

Step 5判斷Cplex得到的解與當(dāng)前最好可行解的大小，如果Cplex的解小于當(dāng)前最好解，則令nIP=0，將Cplex得到的解作為當(dāng)前解和最好解，繼續(xù)搜索；反之，令nIP=nIP+1；

Step 6當(dāng)nIP≥n2時(shí)，使用擾動(dòng)機(jī)制對當(dāng)前最好可行解擾動(dòng)，擾動(dòng)后的解作為當(dāng)前解進(jìn)行搜索；

Step 7判斷計(jì)算時(shí)間是否超過設(shè)定值，若超過，則算法停止；反之，則繼續(xù)搜索.

2.2 禁忌搜索算法

禁忌搜索算法（Tabu Search，TS）由Glover于1986年提出，算法主要思想為：首先產(chǎn)生一個(gè)初始解s0作為當(dāng)前解s，然后在當(dāng)前解的鄰域NH（s）中使用移動(dòng)評價(jià)函數(shù)g（s）選擇最好解作為新的當(dāng)前解.同時(shí)，使用禁忌表記錄已搜索解的歷史信息以避免陷入循環(huán)和局部最優(yōu).目前，禁忌搜索算法已廣泛應(yīng)用于求解優(yōu)化問題，如定位——路徑優(yōu)化[10]和車輛路徑優(yōu)化[11]等.

本文使用的禁忌搜索算法與Cordeau等[12]在求解周期性車輛路徑問題時(shí)提出的相似，但有如下幾點(diǎn)區(qū)別：1）設(shè)置約束懲罰系數(shù)α在某一區(qū)間，避免搜索過程中深陷到不可行區(qū)域，而Cordeau等則沒有這一設(shè)置；2）使用最遠(yuǎn)插入法評價(jià)路途時(shí)間，而Cordeau等使用GENI（GENeralized Insertion）完成客戶的刪除、插入以及路途時(shí)間計(jì)算.本文主要介紹禁忌搜索算法中的重要組成部分：初始解構(gòu)造、禁忌表、特赦準(zhǔn)則、鄰域結(jié)構(gòu)以及移動(dòng)評價(jià)函數(shù).

2.2.1 初始解構(gòu)造

由于在禁忌搜索算法中我們只松弛了護(hù)理連續(xù)性約束，故構(gòu)造初始解時(shí)需滿足多類型護(hù)理人員約束，步驟如下：

Step 1按客戶位置與護(hù)理中心所成角度的升序排列客戶；

Step 2為每個(gè)客戶i隨機(jī)選擇一種服務(wù)模式p?Pi；

Step 3重復(fù)Step 4—Step 6，確定第h（h=1，2，…，|H|）天的訪問安排；

Step 4重復(fù)Step 5和Step 6，確定類型為l（l=m，m-1，…，1）的護(hù)理人員的訪問安排；

Step 5選擇距離護(hù)理中心最近的類型為l的客戶i?Nl={j|sj=l，j?N}；

Step 6按照Step 1中確定的客戶順序，將類型為l的客戶i?Nl分配給能服務(wù)他的護(hù)理人員，使目標(biāo)函數(shù)值增加最小.

2.2.2 禁忌表和特赦準(zhǔn)則

禁忌表的目的是為了避免重復(fù)搜索并引導(dǎo)算法搜索解空間的其他區(qū)域，這是區(qū)別于其他局部搜索算法的重要特征之一.禁忌表中保存了已搜索過解的信息.本文定義每個(gè)解s對應(yīng)一個(gè)屬性集B（s）={（i，k，h）：客戶i在第h天由護(hù)理人員k服務(wù)}，這些屬性（即禁忌對象）被保存在禁忌表中.因此，禁忌表可以使用一個(gè)|N|×|K|×|H|的三維數(shù)組表示.解s的鄰居s'? NH（s）通過鄰域結(jié)構(gòu)刪除和添加B（s）中的部分屬性后得到.當(dāng)從護(hù)理人員k在第h天的訪問客戶列表中刪除客戶i時(shí)，屬性（i，k，h）被標(biāo)記為禁忌狀態(tài)，令禁忌長度為θ，表示在后面θ次迭代中不能在第h天將客戶i重新分配給護(hù)理人員k.當(dāng)包含某一禁忌屬性的可行解優(yōu)于當(dāng)前最優(yōu)解時(shí)，可使用特赦準(zhǔn)則對這一屬性解禁.特赦準(zhǔn)則是基于每個(gè)屬性的特赦水平（Aspiration level），特赦水平定義為搜索過程中包含這一屬性的最好可行解的目標(biāo)函數(shù)值.

2.2.3 鄰域結(jié)構(gòu)

禁忌搜索算法通過鄰域結(jié)構(gòu)產(chǎn)生新解，采用的鄰域結(jié)構(gòu)如下：1）在第h天，從護(hù)理人員k的客戶列表中刪除客戶i，并重新將客戶i分配給同一天能夠服務(wù)他的護(hù)理人員k'（k'≠k）；2）在第h天，如果護(hù)理人員k和k'（k'≠k）都能服務(wù)客戶i和j（j≠i），交換服務(wù)客戶i的護(hù)理人員k和服務(wù)客戶j的護(hù)理人員k'；3）從客戶i的服務(wù)模式集合Pi中重新選擇一種新服務(wù)模式p'代替當(dāng)前解中的服務(wù)模式p，如果第h天在服務(wù)模式p中卻不在服務(wù)模式p'中（即bph=1和bp'h=0），則將客戶i從這一天刪除，如果第h天不在服務(wù)模式p中卻在服務(wù)模式p'中（即bph=0和bp'h=1），則將客戶i分配給能服務(wù)他的護(hù)理人員使目標(biāo)函數(shù)值增加最小.以上各鄰域的大小分別為 O（|N||H|）、O（|N|2|H|）和.

2.2.4 移動(dòng)評價(jià)函數(shù)

移動(dòng)評價(jià)函數(shù)是為選取鄰域中的解而設(shè)計(jì)的一個(gè)評價(jià)公式，與遺傳算法中的適應(yīng)度函數(shù)相似.本文使用的移動(dòng)評價(jià)函數(shù)g（s'）包含3個(gè)部分：目標(biāo)函數(shù)值c（s'）、護(hù)理連續(xù)性約束違反懲罰值q（s'）和多樣性函數(shù)值d（s'），即g（s'）=c（s'）+αq（s'）+d（s'）.c（s'）定義為目標(biāo)函數(shù)值，包括路途成本、服務(wù)成本以及加班懲罰成本.q（s'）定義為護(hù)理連續(xù)性約束違反懲罰值，具體計(jì)算如下：對客戶i，如果解中分配給i的護(hù)理人員數(shù)量（包含以前周期確定的）小于或等于Q時(shí)，表示客戶i的護(hù)理連續(xù)性滿足，無需懲罰；如果分配給i的護(hù)理人員數(shù)量（包含以前周期確定的）大于Q，若以前確定的護(hù)理人員數(shù)量已等于Q，計(jì)算解中實(shí)際分配的護(hù)理人員（不包含以前周期確定的）訪問客戶i的總次數(shù)，并以此作為懲罰，若以前確定的護(hù)理人員數(shù)量小于Q，從解中選擇訪問i次數(shù)最多的護(hù)理人員作為虛擬的以前確定的護(hù)理人員，直到這一數(shù)量等于Q時(shí)，計(jì)算解中分配的其他護(hù)理人員訪問客戶i的總次數(shù)，并以此作為懲罰.d（s'）定義為多樣性函數(shù)值，只有當(dāng)鄰域中的解s'的目標(biāo)函數(shù)值c（s'）與護(hù)理連續(xù)性約束違反懲罰值q（s'）之和大于當(dāng)前解s時(shí)才使用，與c（s）、ρikh和的乘積相關(guān)，計(jì)算公式如下：其中，ρikh表示搜索過程中屬性（i，k，h）?B（s'）B（s）被添加到解中的次數(shù)，λ表示當(dāng)前的迭代次數(shù)，γ表示多樣性系數(shù).

2.3 擾動(dòng)機(jī)制

當(dāng)整數(shù)規(guī)劃模型無法得到更好解時(shí)，說明當(dāng)前搜索已陷入局部最優(yōu)，因此，使用擾動(dòng)機(jī)制[13]對當(dāng)前最優(yōu)解擾動(dòng)，以產(chǎn)生多樣性的解.具體過程如下：首先隨機(jī)選擇一個(gè)客戶i以及離客戶i最近的w個(gè)客戶，w為之間的隨機(jī)整數(shù)；然后將這w+1個(gè)客戶從當(dāng)前最優(yōu)解中的分配關(guān)系刪除，重新為他們分配新的服務(wù)模式；最后，按照隨機(jī)的順序?yàn)樗麄兎峙湫碌淖o(hù)理人員使目標(biāo)函數(shù)值增加最小.

3 數(shù)值實(shí)驗(yàn)

首先介紹期望路途時(shí)間估計(jì)算法，然后描述算例的生成過程，接著驗(yàn)證所提出算法的有效性，最后比較和分析多類型護(hù)理人員與護(hù)理連續(xù)性約束對總成本的影響.本文所提出的算法使用C++編程，整數(shù)規(guī)劃模型采用IBM ILOG Cplex 12.5求解，在Intel E5-2670 2.6 GHz CPU和10 GB內(nèi)存的電腦上測試，操作系統(tǒng)為Linux.

3.1 期望路途時(shí)間估計(jì)算法

為選擇合適的期望路途時(shí)間估計(jì)算法，比較了最遠(yuǎn)插入法[14]、不同鄰居個(gè)數(shù)np值下的GENI和GENIUS（Unstring and String）[15].在[0，100]2的平面上，出發(fā)點(diǎn)為（50，50），生成服從均勻分布的100個(gè)點(diǎn)，從中分別選擇5、8和10個(gè)點(diǎn)作為要訪問的客戶，隨機(jī)生成1 000個(gè)實(shí)例，使用以上算法構(gòu)建從出發(fā)點(diǎn)開始，訪問指定客戶點(diǎn)后，返回出發(fā)點(diǎn)的路徑并計(jì)算路途時(shí)間，np值設(shè)置在2～6.實(shí)例最優(yōu)解使用Cplex求解.表1列出了3種算法1 000個(gè)實(shí)例的平均路途時(shí)間和總計(jì)算時(shí)間、3種算法得到的最好解與最優(yōu)解之間的Gap（G-Gap、GU-Gap和FI-Gap）.

表1 不同啟發(fā)式算法求解1 000個(gè)實(shí)例的結(jié)果Tab.1 Result summary of 1 000 cases under different heuristics

表1 （續(xù)）Tab.1 （Continued）

表1表明：G-Gap、GU-Gap和FI-Gap分別小于0.43%、等于0和小于0.84%，GENIUS和np等于6時(shí)，GENI所得的解優(yōu)于最遠(yuǎn)插入法.但要取得如此好的解，需要比最遠(yuǎn)插入法消耗更多的時(shí)間，這將會(huì)大大增加混合算法的計(jì)算時(shí)間.而最遠(yuǎn)插入法的Gap相對較小，是可以接受的，因此，綜合解的質(zhì)量和計(jì)算時(shí)間，選擇最遠(yuǎn)插入法作為最終的路途時(shí)間估計(jì)算法.

3.2 算例生成方法

為了測試算法的性能，生成包含100和200個(gè)客戶的算例各5個(gè).具體過程如下：在二維平面[0，100]2隨機(jī)產(chǎn)生|N|個(gè)點(diǎn)，護(hù)理中心的坐標(biāo)為（50，50）.令兩點(diǎn)間的路途時(shí)間均值μij等于其歐幾里德距離，標(biāo)準(zhǔn)差σij=0.25μij，單位時(shí)間路途成本ct為1.0.客戶和護(hù)理人員分為3類，類型為1、2和3的客戶比例分別為50%、30%和20%，對應(yīng)的護(hù)理人員數(shù)量與客戶總數(shù)量的比值分別為4%、2%和2%，單位時(shí)間服務(wù)成本cs1、cs2和cs3分別為0.6、0.8和1.0.客戶服務(wù)時(shí)間的均值μi從均勻分布[15，30]中隨機(jī)產(chǎn)生，標(biāo)準(zhǔn)差σi=0.25μi.護(hù)理人員正常工作時(shí)間長度D為300，加班懲罰系數(shù)pc為5.0.一個(gè)計(jì)劃周期包含5天，客戶服務(wù)模式分為4類，包含訪問次數(shù)、組合數(shù)、可能組合以及每種模式所占百分比，如表2所示，“可能組合”中的值表示了客戶允許服務(wù)的日期，以服務(wù)模式3中的“21”為例，將它轉(zhuǎn)化為二進(jìn)制數(shù)“10101”，表示客戶只在周一、周三和周五接受服務(wù).對于護(hù)理連續(xù)性約束以及以前確定的護(hù)理人員-客戶對，設(shè)Q=2，40%的客戶已經(jīng)分配了2個(gè)護(hù)理人員，20%的客戶已分配了1個(gè)護(hù)理人員.

表2 4種服務(wù)模式介紹Tab.2 Introduction of four service mode

3.3 算例結(jié)果

通過一系列測試，本文所提出混合算法的參數(shù)取值如下：禁忌搜索算法中的禁忌長度θ為[7.5lg|N|]，多樣性系數(shù)γ為0.015，護(hù)理連續(xù)性約束懲罰系數(shù)α的初始值、最小值和最大值分別為200、0.000 1和1 000，懲罰系數(shù)α的更新系數(shù)為0.5，混合算法中Cplex每次最長求解時(shí)間為1 000 s，n1和n2均等于2，預(yù)定計(jì)算時(shí)間為0.2|N|min.

為了驗(yàn)證所提出混合策略的有效性，比較使用和未使用這一策略的禁忌搜索算法，分別用TSIP和TS表示，兩種算法的計(jì)算結(jié)果見表3.表3中列出了TS得到目標(biāo)函數(shù)的最小值和平均值，TSIP得到目標(biāo)函數(shù)的最小值和平均值，兩種方法最小值之間的相對偏差（Gap%），構(gòu)成最大整數(shù)規(guī)劃模型的平均列數(shù)以及搜索過程中多次求解整數(shù)規(guī)劃模型總時(shí)間的平均值（IP CPU）.

表3 計(jì)算結(jié)果比較Tab.3 Results comparison

表3所示結(jié)果表明，對所有實(shí)例而言，TSIP得到目標(biāo)函數(shù)的最小值都要比TS小，兩者之間Gap的均值為1.24%，最大的Gap為2.51%（R203）；同時(shí)，TSIP計(jì)算目標(biāo)函數(shù)的平均值也優(yōu)于TS.綜合以上結(jié)果可以看出，所提出的混合策略確實(shí)改善了禁忌搜索算法的性能.在整數(shù)規(guī)劃模型方面，構(gòu)成最大整數(shù)規(guī)劃模型（即搜索過程中最后一次構(gòu)成的整數(shù)規(guī)劃模型）的平均列數(shù)為17 991.33，搜索過程中所有整數(shù)規(guī)劃模型的平均求解時(shí)間為245.03 s（約4.08 min），相對于算法的總計(jì)算時(shí)間（20 min和40 min），這一求解時(shí)間還是比較合理的，即在合理的時(shí)間內(nèi)整數(shù)規(guī)劃模型能為禁忌搜索算法提供新解或評估搜索效果.

3.4 成本比較與分析

本文所研究的問題主要考慮了多類型護(hù)理人員和護(hù)理連續(xù)性兩個(gè)約束，前者是為了合理地利用人力資源及節(jié)約運(yùn)營成本，而后者是為了提高服務(wù)質(zhì)量以及客戶滿意度.以R201為例，分別對原問題中的這兩個(gè)約束松弛，討論它們對服務(wù)成本、路途成本、加班懲罰成本以及總成本的影響.仍然使用本文所提出的算法對松弛約束后的兩個(gè)問題求解，選擇10次計(jì)算中最好的解比較，具體成本見圖1.

圖1 不同約束間的成本比較Fig.1 Cost comparison under different constraints

從圖1中可以看出，只使用一種類型護(hù)理人員時(shí)，服務(wù)成本增加了32.50%，路途成本和加班懲罰成本分別下降了0.91%和34.56%，總成本增加了12.73%.服務(wù)成本增加的原因在于：使用一種類型護(hù)理人員時(shí)只能使用最高層次護(hù)理人員，而最高層次護(hù)理人員的單位時(shí)間服務(wù)成本cs3是最大的（為1.0）.路途成本和加班懲罰成本減小是因?yàn)椋鹤罡邔哟巫o(hù)理人員可以服務(wù)任何類型的客戶，因此，護(hù)理人員可以按最優(yōu)路徑（忽略類型）服務(wù)客戶，而不用因?yàn)榧寄懿蛔阒荒芊?wù)更遠(yuǎn)的客戶.從總成本來看，雖然單一類型護(hù)理人員減小了路途成本和加班懲罰成本，卻大大提高了服務(wù)成本，從而增加了總成本，故使用多類型護(hù)理人員確實(shí)能夠減少公司總運(yùn)營成本.

從圖1中也可看出，無護(hù)理連續(xù)性約束時(shí)，服務(wù)成本增加了1.43%，路途成本和加班懲罰成本分別下降了11.05%和15.35%，總成本減小了5.76%.服務(wù)成本增加可能是因?yàn)椋耗承└邔哟巫o(hù)理人員在他們的服務(wù)路徑上訪問了一些低層次的客戶，而這些低層次客戶如果被對應(yīng)層次的護(hù)理人員服務(wù)，雖然服務(wù)成本有所下降，但路途成本會(huì)增加更多，因此，應(yīng)用這些高層次護(hù)理人員可使總成本增加最小.而路途成本和加班懲罰成本下降的原因在于：松弛護(hù)理連續(xù)性約束后，護(hù)理人員可以選擇服務(wù)的客戶集變大，即客戶不再因?yàn)橐逊峙涞牟煌o(hù)理人員數(shù)量達(dá)到設(shè)定值而拒絕某一護(hù)理人員服務(wù).從總成本來看，松弛護(hù)理連續(xù)性約束的確減少了總成本，但成本減少是以降低客戶服務(wù)質(zhì)量以及滿意度為代價(jià)的，故公司管理者在決策時(shí)需考慮總成本和客戶滿意度間的平衡.

4 結(jié)束語

研究了考慮多類型護(hù)理人員、護(hù)理連續(xù)性和隨機(jī)時(shí)間約束的周期性護(hù)理人員分配問題，針對問題的分配和路徑優(yōu)化部分，分別采用基于禁忌搜索和整數(shù)規(guī)劃的混合算法以及最遠(yuǎn)插入算法進(jìn)行求解.取得了如下成果：1）在周期性家庭護(hù)理人員分配問題中首次同時(shí)考慮了多類型護(hù)理人員、護(hù)理連續(xù)性和隨機(jī)時(shí)間3個(gè)約束；2）將問題分解為一個(gè)分配子問題和若干個(gè)路徑優(yōu)化子問題，分別使用基于禁忌搜索和整數(shù)規(guī)劃的混合算法以及最遠(yuǎn)插入算法求解；3）定量地比較和分析多類型護(hù)理人員以及護(hù)理連續(xù)性約束對總運(yùn)營成本的影響，為管理者提供了明確的決策依據(jù).

以本文研究的問題為基礎(chǔ)，以后的研究可從以下兩個(gè)方面展開：1）以本問題的解為輸入構(gòu)建每天的護(hù)理人員調(diào)度與路徑優(yōu)化問題，并設(shè)計(jì)相應(yīng)的優(yōu)化算法；2）尋找更有效的路途時(shí)間估計(jì)算法；3）設(shè)計(jì)更多的元啟發(fā)式算法求解所提出的問題，如蟻群算法[16]、遺傳算法[17]或粒子群算法[18]等.