丁 鋒，付亞平，王 偉，王洪峰

(1.青島大學(xué)商學(xué)院，山東 青島 266071；2.東北大學(xué)信息科學(xué)與工程學(xué)院，沈陽 110819)

0 引言

中國人口老齡化形勢日趨嚴(yán)峻。根據(jù)預(yù)測，中國將于2035年前后步入“深度老齡化”社會，屆時65歲及以上老年人口比重將超過21%[1]，而應(yīng)對老齡化的關(guān)鍵在于能否顯著改善和維護(hù)老年群體的健康[2]。社區(qū)居家養(yǎng)老服務(wù)作為一種新穎的養(yǎng)老模式，在解決中國老有所養(yǎng)的問題上發(fā)揮著重要作用。在社區(qū)居家養(yǎng)老日常服務(wù)中，社區(qū)醫(yī)療中心通常要解決為護(hù)工分配老人及規(guī)劃服務(wù)路徑的問題，即社區(qū)居家養(yǎng)老調(diào)度與服務(wù)網(wǎng)絡(luò)優(yōu)化問題。這類問題屬于NP問題[3]。合理地調(diào)度服務(wù)人員，優(yōu)化服務(wù)次序與路線，對于充分利用人力和醫(yī)療資源、提升客戶滿意度和提高服務(wù)質(zhì)量等都具有重要的意義。

居家養(yǎng)老問題從20世紀(jì)90年代就開始受到學(xué)者的關(guān)注，但國內(nèi)針對此類問題的研究較少。袁彪等[3]以家庭醫(yī)療護(hù)理(Home Health Care,HHC)中的人員調(diào)度為研究對象，建立數(shù)學(xué)模型并設(shè)計(jì)出有效算法來解決所提問題。楊欣湩等[4]研究的中國居家養(yǎng)老問題，通過改進(jìn)算法大幅減少了時間成本。此外，國外學(xué)者在HHC領(lǐng)域的學(xué)術(shù)成果較多。許多研究在隨機(jī)環(huán)境中定義問題[5-6]；此外，一些研究對護(hù)工的醫(yī)療資格作出分類[7-8]；還有部分文章考慮了客戶時間窗[9-11]。以上文獻(xiàn)大多只考慮一個醫(yī)療中心，但少數(shù)涉及多醫(yī)療中心問題特點(diǎn)[5,12]的研究則更加符合現(xiàn)實(shí)情況。

實(shí)際上社區(qū)居家養(yǎng)老調(diào)度與服務(wù)網(wǎng)絡(luò)優(yōu)化問題與帶時間窗的車輛路徑規(guī)劃問題(Vehicle Routing Problem with Time Windows,VRPTW)在車輛調(diào)度和路網(wǎng)規(guī)劃方面具有相似性[13-14]。但本文提出的社區(qū)居家養(yǎng)老問題同時考慮了隨機(jī)環(huán)境、多醫(yī)療中心、預(yù)約服務(wù)時間和技能匹配等問題特點(diǎn)，與VRPTW仍有很大區(qū)別。文獻(xiàn)中為解決HHC問題提出了許多方法，分為3類：1)精確式算法[5]；2)啟發(fā)式[11]或元啟發(fā)式[9-10,12,15-16]方法；3)數(shù)學(xué)規(guī)劃方法[17]。本文為了提高老人的滿意度，還引入等待時間的機(jī)會約束，建立了一個帶機(jī)會約束的隨機(jī)期望規(guī)劃模型，并設(shè)計(jì)了改進(jìn)混合牧羊人優(yōu)化算法(Shuffled Shepherd Optimization Algorithm,SSOA)[18-19]求解此復(fù)雜但具現(xiàn)實(shí)意義的社區(qū)居家養(yǎng)老調(diào)度與服務(wù)網(wǎng)絡(luò)優(yōu)化問題。

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

社區(qū)居家養(yǎng)老日常調(diào)度和服務(wù)網(wǎng)絡(luò)優(yōu)化問題可以描述如下：某社區(qū)有H個醫(yī)療中心(集合為I)共同為C位老人提供服務(wù)(集合為J)，構(gòu)成一個有向網(wǎng)絡(luò)節(jié)點(diǎn)集G={N,φ}，其中N=I∪J是點(diǎn)集，φ={(i,j)|i,j∈N,i≠j}是弧集，經(jīng)過弧(i,j)∈φ的時間為tij。每位老人i∈J有護(hù)理需求ri(等級集合S={1,2,…，L})，服務(wù)時間τi和預(yù)約時間Ai。各醫(yī)療中心h∈I有Kh名護(hù)工參與服務(wù)(集合為Vh，護(hù)士總集合V={V1,V2,…，VH})，每名護(hù)工k∈V有護(hù)理水平qlk,(l∈S)和服務(wù)人數(shù)限制Q。

根據(jù)問題描述，對模型進(jìn)行假設(shè)：1)各中心服務(wù)人數(shù)固定；2)護(hù)工從所屬中心出發(fā)，并最終回到該中心；3)每名護(hù)工的服務(wù)人數(shù)不超過Q；4)護(hù)工技能水平須與老人需求匹配，技能水平須大于等于需求等級；5)每位老人僅可被一名護(hù)工服務(wù)；6)老人接受服務(wù)時長與護(hù)工技能水平相關(guān)。

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

基于以上，引入以下常量、變量、參數(shù)及數(shù)學(xué)模型。

M：一個很大的常數(shù)；Aj：老人j的預(yù)約開始服務(wù)時間；chl：中心h負(fù)責(zé)服務(wù)需求等級為l的老人數(shù)量；zjk：護(hù)工k服務(wù)第j個老人的到達(dá)時間；K：所有中心參與服務(wù)的護(hù)工總數(shù)；sjk：護(hù)工k服務(wù)第j個老人的開始時間；tij：護(hù)工從節(jié)點(diǎn)i前往節(jié)點(diǎn)j所需旅行時間；D：預(yù)設(shè)延遲到達(dá)目標(biāo)老人的允許時間上限；τjk：老人j接受護(hù)工k服務(wù)所需的服務(wù)時長；φ：護(hù)工到達(dá)延遲時間不大于D的置信度。

決策變量：

其中，tij和τjk是服從截?cái)嗾龖B(tài)分布的隨機(jī)參數(shù)。老人j接受護(hù)工k服務(wù)的時間τjk可用公式(1)計(jì)算：

(1)

護(hù)工在老人i與j間的輾轉(zhuǎn)和服務(wù)時間不確定，使護(hù)工到達(dá)時間zjk無法預(yù)估?？捎霉?2)表示：

(2)

若護(hù)工k早于老人i的預(yù)約時間到達(dá)，需等待至Ai開啟服務(wù)。護(hù)工空閑時間可按公式(3)計(jì)算：

(Ai-zik)+=max{(Ai-zik),0}

(3)

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

(4)

s.t.

(5)

(6)

|cil-cjl|

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

τjk≥0,j∈J,k∈V

(17)

xijk∈{0,1},yik∈{0,1},i,j∈N,k∈V

(18)

上述模型中，式(4)為期望目標(biāo)函數(shù)；式(5)表示護(hù)工服務(wù)人數(shù)限制；式(6)表示各中心協(xié)同服務(wù)；式(7)保證分配合理性；式(8)表示護(hù)工總數(shù)；式(9)表示各中心有多條訪問回路；式(10)保證每位老人僅由1名護(hù)工服務(wù)；式(11)表示護(hù)工可服務(wù)多位老人；式(12)表示每名護(hù)工只屬于一個中心；式(13)表示技能約束；式(14)保證各中心的訪問路徑不超過其護(hù)工數(shù)；式(15)表示老人的開始服務(wù)時間；式(16)保證老人的總等待時間小于給定值的概率大于或等于給定置信度；式(17)表示非負(fù)約束；式(18)表示決策變量為0-1變量。

2 算法設(shè)計(jì)

現(xiàn)有居家醫(yī)療護(hù)理研究中，多采用元啟發(fā)式方法進(jìn)行求解，如基于種群的遺傳算法(Genetic Algorithm,GA)[10,12]、粒子群算法(Particle Swarm Optimization,PSO)[12,16]等。Kaveh和Zaerreza[18]提出一種先分割后合并、基于種群的優(yōu)化算法，稱為混合牧羊人優(yōu)化算法，本文也將基于該算法對問題進(jìn)行求解。

2.1 基本的SSOA

SSOA首先會隨機(jī)生成一個種群，候選解視為羊。其次，將羊按其目標(biāo)值升序排列(最小化問題)，選出前m(牧群數(shù)量)只羊，分別隨機(jī)放入一個牧群，重復(fù)執(zhí)行，直到分配完畢。接著，按公式(19)和(20)為每個牧羊人計(jì)算步長及臨時位置：

Stepsizei=α×rand°(Xj-Xi)+β×rand°(Xd-Xi)

(19)

(20)

其中，Xi，Xd，Xj分別為牧羊人、馬以及羊的個體解；rand是隨機(jī)向量，所有分量都是[0,1]上的隨機(jī)數(shù)；α=α0(初始參數(shù))，可用公式(21)更新；β=β0(初始參數(shù))，可用公式(22)更新；符號“°”表示向量的逐元素乘法。如果牧羊人的新位置不比之前差，則更新為當(dāng)前位置(替換策略)，所有牧群都會重復(fù)執(zhí)行此過程。最后，將所有牧群重新合并為種群。重復(fù)上述過程，直到滿足停止條件。

(21)

(22)

2.2 改進(jìn)策略

本文提出的社區(qū)居家養(yǎng)老問題是典型的離散優(yōu)化問題。公式(19)是牧羊人步長計(jì)算公式。第一項(xiàng)α×rand°(Xj-Xi)表示牧羊人走向羊；第二項(xiàng)β×rand°(Xd-Xi)表示牧羊人驅(qū)趕羊走向馬。改進(jìn)SSOA的關(guān)鍵在于根據(jù)離散問題特點(diǎn)重新定義步長公式。設(shè)計(jì)的改進(jìn)將α×rand°(Xj-Xi)視為當(dāng)前解與差解的概率交叉，α為交叉率；將β×rand°(Xd-Xi)視為當(dāng)前解和優(yōu)解的概率交叉，β為交叉率。

2.3 改進(jìn)SSOA的框架

改進(jìn)后的算法具體步驟如下。

步驟1確定編碼機(jī)制，生成初始種群。對于有H個中心，C位老人的HHC問題，編碼方式如下：首先按約束(7)確定各中心的老人；接著，各中心按約束(5)和(13)確定護(hù)工類型和數(shù)量，共有K人；然后，各中心再將老人分給合適的護(hù)工；最后，護(hù)工按預(yù)約訪問。將老人編號為1～C，中心編號為1～H，護(hù)工根據(jù)其所屬的中心和技能水平編號，例如第1中心的技能水平為3的護(hù)工可以表示為“1003”。

步驟2計(jì)算種群中個體的適應(yīng)度值。取M1次試驗(yàn)結(jié)果的平均值作為評價依據(jù)。在此基礎(chǔ)上，根據(jù)機(jī)會約束(16)，得M1次試驗(yàn)中共有M2次未超出老人等待時間上限D(zhuǎn)。若(M2/M1)<φ，則該解不滿足機(jī)會約束，即為不可行解，需對其進(jìn)行懲罰，令其適應(yīng)度值乘上懲罰系數(shù)ε，并以此作為其新適應(yīng)度值。

步驟3分離種群，構(gòu)建牧群。根據(jù)個體適應(yīng)值，對種群從小到大(最小化問題)排列，選擇前m頭羊放入多牧群向量集第一列，作為每個牧群的第一頭羊，并且每一行都表示一個牧群。重復(fù)以上過程n次(牧群大小n，種群大小N=m×n)，直至牧群構(gòu)建完成。

步驟4交叉算子，更新種群位置。根據(jù)步長公式(19)的新定義，將牧羊人(當(dāng)前解)先后與其對應(yīng)的羊(較差解)、馬(較好解)進(jìn)行概率交叉，交叉方式采用改進(jìn)的部分匹配交叉(Partial Mapped Crossover,PMX)。如圖1所示，對參與交叉的兩個個體，首先隨機(jī)選中相同位置的兩條子路徑并構(gòu)造映射關(guān)系：對有相同需求的節(jié)點(diǎn)構(gòu)建映射，且相同節(jié)點(diǎn)優(yōu)先對應(yīng)；然后整體交換兩條選中子路徑的節(jié)點(diǎn)；最后，對交換后的個體做沖突檢驗(yàn)，并根據(jù)映射關(guān)系替換舊路徑中的重復(fù)節(jié)點(diǎn)。經(jīng)過與羊、馬的交叉，可以得到牧羊人的臨時位置，若不差于之前位置，則接受新位置。重復(fù)此過程，完成種群位置的更新。

圖1 交叉算子

步驟5更新參數(shù)。依據(jù)公式(21)和(22)對參數(shù)α，β進(jìn)行更新。

步驟6判斷是否滿足停止條件。若未滿足停止條件，則轉(zhuǎn)步驟2；否則，算法停止搜索。

3 算例分析

在本節(jié)中，首先生成問題的測試算例；然后為算法設(shè)置參數(shù)，并進(jìn)行算例試驗(yàn)；最后，通過比較、分析實(shí)驗(yàn)結(jié)果，驗(yàn)證算法的有效性。本文所有程序均通過C++實(shí)現(xiàn)，運(yùn)行于Visual Studio 2017。

3.1 算例生成

本文以Homberger[20]所提的VRPTW算例為基礎(chǔ)，重構(gòu)適合所研究問題的算例，包含C，R和RC 3種類型。其中，C表示老人集中分布，R表示隨機(jī)分布，RC表示半集中混合分布。修改后的算例有如下特點(diǎn)：1)標(biāo)準(zhǔn)服務(wù)時間τj服從均值為90的截?cái)嗾龖B(tài)分布，標(biāo)準(zhǔn)差是均值的0.001倍；2)時間窗左端作為預(yù)約時間；3)5種服務(wù)需求比率為Rs={0.2,0.15,0.3,0.15,0.2}；4)旅行時間服從截?cái)嗾龖B(tài)分布，均值以兩點(diǎn)歐氏距離表示，標(biāo)準(zhǔn)差是均值的0.001倍?；谝陨闲薷模瑢Σ捎玫腣RPTW標(biāo)準(zhǔn)算例分別選取前50、100、150和200個節(jié)點(diǎn)作為老人坐標(biāo)，并構(gòu)造包括小、中、大3種規(guī)模在內(nèi)的12組測試算例。

3.2 參數(shù)設(shè)置

本文設(shè)置牧羊人和馬的最大交叉率βmax=1。此外，SSOA的種群規(guī)模N、牧群規(guī)模n、牧羊人與羊的初始交叉率α0以及牧羊人與馬的初始交叉率β0的設(shè)置需通過正交實(shí)驗(yàn)完成。各參數(shù)均設(shè)置4個水平：N={30,60,60,90}，n={3,6,10,15}，α0={0.1,0.3,0.5,0.7}，β0={0.2,0.4,0.6,0.8}。表1是規(guī)模為L16(44)的正交表，實(shí)驗(yàn)基于100規(guī)模的C類算例，當(dāng)總估值次數(shù)達(dá)到3 600次時停止搜索。對每組參數(shù)組合都獨(dú)立運(yùn)行20次，并計(jì)算平均值作為平均響應(yīng)值(Average Response Value,ARV)。表2列出了每個參數(shù)的ARV。由表1和表2實(shí)驗(yàn)結(jié)果可得一組效果較好的SSOA參數(shù)設(shè)置：N=30，n=10，α0=0.5，β0=0.8。

表1 正交表和實(shí)驗(yàn)結(jié)果

表2 各參數(shù)不同水平下的平均響應(yīng)值和影響力

3.3 算法比較

在求解HHC問題方面，GA和PSO分別作為進(jìn)化算法和群體智能優(yōu)化算法的代表，已經(jīng)得到了廣泛應(yīng)用[10,12,16]，且效果顯著。因此，本文選擇GA和PSO作為對比算法。

根據(jù)文獻(xiàn)[12]設(shè)置PSO參數(shù)：粒子數(shù)P=75，慣性權(quán)重w=0.54，學(xué)習(xí)因子c1=0.7，c2=1.42；設(shè)置GA參數(shù)：種群Npop=76，交叉率pc=0.5，變異率pm=0.27。每個算法的試驗(yàn)都獨(dú)立運(yùn)行20次，并以總估值次數(shù)150C作為停止條件。試驗(yàn)結(jié)果如表3所示，Gap%是對比算法與SSOA結(jié)果均值的相對偏差。此外，還通過95%置信度下的t檢驗(yàn)方法，分析了試驗(yàn)結(jié)果的差異性。符號“+”、“-”分別表示SSOA結(jié)果顯著優(yōu)于或劣于對比算法，符號“～”代表SSOA與對比算法的結(jié)果無顯著差異。

表3 3種算法運(yùn)行結(jié)果對比

從表3可以看出，在50和100規(guī)模的試驗(yàn)中，SSOA絕對優(yōu)于對比算法；隨著規(guī)模擴(kuò)大到150和200，結(jié)果差距略有縮小。進(jìn)一步分析均值的相對偏差，PSO和SSOA的偏差在大規(guī)模算例中明顯增大，最高偏差達(dá)20%；而SSOA與GA的偏差則保持在3%以內(nèi)。通過以上分析，SSOA明顯優(yōu)于PSO，略優(yōu)于GA，且比GA有更好的適應(yīng)性。表3還展示了試驗(yàn)中達(dá)到的最小值。分析發(fā)現(xiàn)，SSOA在多數(shù)算例中達(dá)到最小值，反映出SSOA良好的全局搜索能力。分析t檢驗(yàn)結(jié)果，SSOA顯著優(yōu)于PSO；且SSOA在75%的試驗(yàn)中，顯著優(yōu)于GA。t檢驗(yàn)結(jié)果表明SSOA不僅擁有高效的搜索性能，還兼具卓越的搜索穩(wěn)定性。

圖2表示SSOA和對比算法進(jìn)行20次試驗(yàn)后的箱線圖。分析發(fā)現(xiàn)，SSOA在80%的算例結(jié)果中擁有最小的中位數(shù)，體現(xiàn)出SSOA穩(wěn)定的搜索性能。在圖2a、2b中，SSOA的測試結(jié)果比對比算法更加集中；在圖2c、2d中，SSOA在所有大規(guī)模算例中有著更好的測試結(jié)果分布，如正態(tài)分布和左偏分布，都表明SSOA不僅能夠應(yīng)對中小規(guī)模問題，而且在解決大規(guī)模問題時同樣出色。綜上分析，改進(jìn)SSOA在求解所研究的多中心社區(qū)居家養(yǎng)老問題方面效果顯著，其搜索到的解優(yōu)質(zhì)且穩(wěn)定。

圖2 3種算法求解12個算例的箱線圖

4 結(jié)論

中國人口老齡化和醫(yī)療資源不平衡等問題加劇了社區(qū)居家養(yǎng)老需求。本文研究了隨機(jī)環(huán)境下的多中心社區(qū)居家養(yǎng)老調(diào)度與服務(wù)網(wǎng)絡(luò)優(yōu)化問題，建立了帶機(jī)會約束的隨機(jī)規(guī)劃模型。根據(jù)問題特點(diǎn)，設(shè)計(jì)了整體編碼方法進(jìn)行老人分配和路徑規(guī)劃。所提的改進(jìn)SSOA，通過引入交叉算子，賦予原步長公式新解釋，使步長更新仍然基于當(dāng)前和其他個體的位置信息，使其可用于解決本文所研究的具有離散特點(diǎn)的社區(qū)居家養(yǎng)老問題。最后，測試了最大規(guī)模為200的一系列算例，結(jié)果表明改進(jìn)SSOA在絕大多數(shù)情況中都能得到優(yōu)于對比算法的結(jié)果，驗(yàn)證了所提算法的有效性。在此研究基礎(chǔ)上，后續(xù)工作可以在考慮同步服務(wù)和選址-路徑問題等方面作出擴(kuò)展；還將繼續(xù)改進(jìn)算法，使其在解決大規(guī)模問題時更加高效和穩(wěn)定。