多中心社區居家養老服務調度與服務網絡優化

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

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

0 引言

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

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

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

1 問題描述及數學模型

1.1 問題描述

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

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

1.2 數學模型

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

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

決策變量：

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

(1)

護工在老人i與j間的輾轉和服務時間不確定，使護工到達時間zjk無法預估。可用公式(2)表示：

(2)

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

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

(3)

數學模型為

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

2 算法設計

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

2.1 基本的SSOA

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

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

(19)

(20)

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

(21)

(22)

2.2 改進策略

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

2.3 改進SSOA的框架

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

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

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

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

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

圖1 交叉算子

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

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

3 算例分析

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

3.1 算例生成

本文以Homberger[20]所提的VRPTW算例為基礎，重構適合所研究問題的算例，包含C，R和RC 3種類型。其中，C表示老人集中分布，R表示隨機分布，RC表示半集中混合分布。修改后的算例有如下特點：1)標準服務時間τj服從均值為90的截斷正態分布，標準差是均值的0.001倍；2)時間窗左端作為預約時間；3)5種服務需求比率為Rs={0.2,0.15,0.3,0.15,0.2}；4)旅行時間服從截斷正態分布，均值以兩點歐氏距離表示，標準差是均值的0.001倍。基于以上修改，對采用的VRPTW標準算例分別選取前50、100、150和200個節點作為老人坐標，并構造包括小、中、大3種規模在內的12組測試算例。

3.2 參數設置

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

表1 正交表和實驗結果

表2 各參數不同水平下的平均響應值和影響力

3.3 算法比較

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

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

表3 3種算法運行結果對比

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

圖2表示SSOA和對比算法進行20次試驗后的箱線圖。分析發現，SSOA在80%的算例結果中擁有最小的中位數，體現出SSOA穩定的搜索性能。在圖2a、2b中，SSOA的測試結果比對比算法更加集中；在圖2c、2d中，SSOA在所有大規模算例中有著更好的測試結果分布，如正態分布和左偏分布，都表明SSOA不僅能夠應對中小規模問題，而且在解決大規模問題時同樣出色。綜上分析，改進SSOA在求解所研究的多中心社區居家養老問題方面效果顯著，其搜索到的解優質且穩定。

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

4 結論

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