多中心社區(qū)居家養(yǎng)老服務(wù)調(diào)度與服務(wù)網(wǎng)絡(luò)優(yōu)化

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

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

0 引言

中國人口老齡化形勢日趨嚴峻。根據(jù)預(yù)測，中國將于2035年前后步入“深度老齡化”社會，屆時65歲及以上老年人口比重將超過21%[1]，而應(yīng)對老齡化的關(guān)鍵在于能否顯著改善和維護老年群體的健康[2]。社區(qū)居家養(yǎng)老服務(wù)作為一種新穎的養(yǎng)老模式，在解決中國老有所養(yǎng)的問題上發(fā)揮著重要作用。在社區(qū)居家養(yǎng)老日常服務(wù)中，社區(qū)醫(yī)療中心通常要解決為護工分配老人及規(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世紀90年代就開始受到學者的關(guān)注，但國內(nèi)針對此類問題的研究較少。袁彪等[3]以家庭醫(yī)療護理(Home Health Care,HHC)中的人員調(diào)度為研究對象，建立數(shù)學模型并設(shè)計出有效算法來解決所提問題。楊欣湩等[4]研究的中國居家養(yǎng)老問題，通過改進算法大幅減少了時間成本。此外，國外學者在HHC領(lǐng)域的學術(shù)成果較多。許多研究在隨機環(huán)境中定義問題[5-6]；此外，一些研究對護工的醫(yī)療資格作出分類[7-8]；還有部分文章考慮了客戶時間窗[9-11]。以上文獻大多只考慮一個醫(yī)療中心，但少數(shù)涉及多醫(yī)療中心問題特點[5,12]的研究則更加符合現(xiàn)實情況。

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

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

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é)點集G={N,φ}，其中N=I∪J是點集，φ={(i,j)|i,j∈N,i≠j}是弧集，經(jīng)過弧(i,j)∈φ的時間為tij。每位老人i∈J有護理需求ri(等級集合S={1,2,…，L})，服務(wù)時間τi和預(yù)約時間Ai。各醫(yī)療中心h∈I有Kh名護工參與服務(wù)(集合為Vh，護士總集合V={V1,V2,…，VH})，每名護工k∈V有護理水平qlk,(l∈S)和服務(wù)人數(shù)限制Q。

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

1.2 數(shù)學模型

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

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

決策變量：

其中，tij和τjk是服從截斷正態(tài)分布的隨機參數(shù)。老人j接受護工k服務(wù)的時間τjk可用公式(1)計算：

(1)

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

(2)

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

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

(3)

數(shù)學模型為

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

2 算法設(shè)計

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

2.1 基本的SSOA

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

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

(19)

(20)

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

(21)

(22)

2.2 改進策略

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

2.3 改進SSOA的框架

改進后的算法具體步驟如下。

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

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

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

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

圖1 交叉算子

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

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

3 算例分析

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

3.1 算例生成

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

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

本文設(shè)置牧羊人和馬的最大交叉率βmax=1。此外，SSOA的種群規(guī)模N、牧群規(guī)模n、牧羊人與羊的初始交叉率α0以及牧羊人與馬的初始交叉率β0的設(shè)置需通過正交實驗完成。各參數(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)的正交表，實驗基于100規(guī)模的C類算例，當總估值次數(shù)達到3 600次時停止搜索。對每組參數(shù)組合都獨立運行20次，并計算平均值作為平均響應(yīng)值(Average Response Value,ARV)。表2列出了每個參數(shù)的ARV。由表1和表2實驗結(jié)果可得一組效果較好的SSOA參數(shù)設(shè)置：N=30，n=10，α0=0.5，β0=0.8。

表1 正交表和實驗結(jié)果

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

3.3 算法比較

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

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

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

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

圖2表示SSOA和對比算法進行20次試驗后的箱線圖。分析發(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ī)模問題時同樣出色。綜上分析，改進SSOA在求解所研究的多中心社區(qū)居家養(yǎng)老問題方面效果顯著，其搜索到的解優(yōu)質(zhì)且穩(wěn)定。

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

4 結(jié)論

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