李 艷, 許 簫, 王付宇

(1.安徽工業(yè)大學管理科學與工程學院 安徽 馬鞍山 243032; 2.上海理工大學管理學院 上海 200093)

隨著老齡化社會的到來,養(yǎng)老問題成了突出的民生問題,迅速激增的養(yǎng)老需求是擺在社會現(xiàn)實面前的一大難題。家庭養(yǎng)老和居住養(yǎng)老院等傳統(tǒng)的養(yǎng)老模式難以應對老齡化帶來的養(yǎng)老壓力,居家養(yǎng)老模式應運而生。但目前我國專業(yè)的家庭醫(yī)療護理人員極其缺乏,為了合理利用有限的家庭醫(yī)療資源,提供給老年人更滿意的居家養(yǎng)老服務,如何調度家庭醫(yī)療人員以及合理安排他們的服務路徑是居家養(yǎng)老服務運作管理研究領域中的熱點問題。

關于家庭醫(yī)療人員調度模型的研究有許多,其研究重點各有側重。在成本方面,一般通過縮短服務時間或行駛路徑來降低成本。S E Moussavi等[1]利用經典的VRP與AP模型對居家醫(yī)療調度問題進行建模,采用元啟發(fā)式算法為每位醫(yī)護人員尋求最佳服務時間和最短行駛距離。Yang Zhan等[2]認為居家醫(yī)療調度問題的關鍵就是人員分配以及路徑規(guī)劃。Jamal Abdul Nasir等[3]綜合考慮家庭服務的時間窗約束以及距離約束提出混合遺傳算法求出最優(yōu)路徑。Jonathan F Bard等[4]提出一種貪婪隨機自適應搜索方法解決了多類型醫(yī)護人員服務成本最小化的問題。Toufik Boudouh等[5]考慮了不確定的服務時間等因素對于總成本的影響,構建成本最小化模型。María I Restrepo等[6]考慮了患者需求的不確定性,利用兩階段隨機規(guī)劃模型來整合醫(yī)護人員配置與調度。Zhang Zizhen等[7]研究了醫(yī)護人員的服務分配順序以及救援車輛路徑問題,構建了總成本最小化的調度模型。

上述文獻僅研究了以成本最小化為目標的調度模型,然而在服務過程中會出現(xiàn)一些不確定因素造成患者情緒的波動,例如:時間的偏差、緊急需求等。Gang Du等[8]針對服務的取消、緊急護理的需求和醫(yī)療設備故障這些不確定的因素會降低患者的滿意度進行建模。Ahmet Kandakoglu等[9]認為醫(yī)護人員的服務時間表和服務順序均會影響總成本以及患者滿意度。Mascolo等[10]綜合考慮家庭醫(yī)護人員的服務時間窗和性別對患者滿意度的影響。胡曉偉等人通過構建成本以及滿意度模型為疫情下因醫(yī)療物資的短缺而造成分配不均提供解決方案[11]。家庭醫(yī)療人員調度問題屬于NP-hard問題,隨著問題規(guī)模的擴大,精確解算法已不能完全勝任。在此情況下,多數學者利用元啟發(fā)式算法求解問題。Yong Shi等[12]將患者的不確定性需求設置為一個模糊變量,通過提出一種混合遺傳算法與隨機模擬相結合的方法來求解模型。陸雨薇等[13]提出一種禁忌搜索和整數規(guī)劃的混合算法來求解醫(yī)護人員的路徑問題。康麗等[14]針對家庭醫(yī)療護理人員分配問題,利用遺傳算法求解大規(guī)模資源分配問題。Chananes Akjiratikar等[15]在PSO(Particle swarm optimization)算法中嵌入了局部改進程序(LIP),求得醫(yī)護人員服務調度最佳方案。李艷等[16]設計了一種改進的多目標鯨魚群算法來求解居家養(yǎng)老醫(yī)護人員調度的多目標模型。

就求解算法而言,利用等元啟發(fā)式算法均能在一定程度上解決家庭醫(yī)療人員調度問題,但也存在編程實現(xiàn)復雜、收斂速度慢等不足之處。隨著智能算法的發(fā)展,越來越多的算法被相繼提出,天牛須算法位列其中。許多學者將該算法用于求解應急資源調度、電力調度等組合優(yōu)化問題,并取得了一定的成果。王付宇等[17]利用天牛須算法求解應急資源調度問題,最終求得最佳分配方案。Li等[18]構建了以互補系統(tǒng)和等效負荷中波動性最小化為目標的調度模型,利用天牛須算法求解模型。家庭醫(yī)療人員調度問題也屬于組合優(yōu)化問題,在文獻檢索過程中,尚未發(fā)現(xiàn)利用天牛須算法求解此類問題。

因此,針對國內某醫(yī)護中心的實際運營情況,構建調度模型,設計改進的BAS算法求解模型。將改進算法分別與遺傳算法(GA,Genetic Algorithm)和粒子群算法進行對比分析,驗證改進算法的有效性,為醫(yī)護機構尋找最優(yōu)調度方案提供決策依據。

1 問題描述與建模

1.1 問題描述

本文研究的是家庭醫(yī)療護理過程中,醫(yī)護人員的分配以及服務路徑問題,服務路徑如圖1所示。具體問題描述為假設有一個醫(yī)護中心,多名醫(yī)護人員和多個患者,醫(yī)護人員從醫(yī)護中心出發(fā)去往不同患者的家里,每天一個患者均只能被訪問一次,而一個醫(yī)護人員可以訪問多個患者,每位患者將會提前告知醫(yī)護中心希望被服務的時間范圍以及服務時長。

圖1 家庭醫(yī)療護理調度圖

醫(yī)護人員等待或遲到均會產生成本,與此同時會影響患者滿意度。根據以上信息,如何調度醫(yī)護人員可以使得醫(yī)護中心總運營成本最小,患者滿意度最大以及醫(yī)護人員工作時間最均衡。

1.2 模型建立

W={0,1,2…n},0代表服務中心;N={1,2,3…n},表示患者需求集合點,i,j∈N;K={1,2,3…k},表示醫(yī)護人員;Dist:醫(yī)護人員的旅行負載差;P:醫(yī)護人員早于或晚于患者可接受服務時間窗的時長;Ck:醫(yī)護人員固定工資;PCk:超過規(guī)定時間的單位懲罰成本;Lk:醫(yī)護人員最大工作時間;D:醫(yī)護人員基本工作時間;Tik:醫(yī)護人員為患者開始服務時間;tik:醫(yī)護人員為患者提供服務時間;tij:從患者i到患者j的時間;ETi:患者可接受的最早開始服務時間;LTi:患者可接受的最晚開始服務時間;Xijk:醫(yī)護人員k在對患者i進行服務之后再對患者j進行服務;X0jk:醫(yī)護人員k從服務中心出發(fā)直接去往患者j;Xi0k:醫(yī)護人員k為患者i服務結束之后回到服務中心;M:足夠大的正整數;b:實際開始工作時間早于患者可接受的最早開始時間或者超出患者可接受的最晚開始服務的時間時,患者給出的單位懲罰成本;distk:醫(yī)護人員k實際旅行距離;Length:醫(yī)護人員最大旅行距離;v:車輛行駛速度。

目標函數為

(1)

(2)

MinZ3=Dist

(3)

(4)

(5)

∑j∈NX0jk=1,?k∈K

(6)

∑j∈NXj0k=1,?k∈K

(7)

Tik+tik+tij-M(1-Xijk)≤Tjk,?k∈K

(8)

(9)

Dist=max|distk-distr|,?k,r∈K

(10)

distk=∑i∈N∑j∈N,i≠jtij*v*Xijk,?k∈K

(11)

∑i∈N∑j∈N,i≠jtij*v*Xijk≤Length,?k∈K

(12)

其中式(4)是確保每位患者只訪問一次,式(5)至(7)表示醫(yī)護人員從醫(yī)護中心出發(fā)最終返還到醫(yī)護中心,式(8)表示醫(yī)護人員在為患者i結束服務到達下一位患者的時間不得超過為下一個患者的實際開始服務時間,式(9)表示實際開始工作時間與期望的最早服務時間和最遲服務時間的偏差,式(10)表示醫(yī)護人員之間的最大旅行距離差,式(11)表示醫(yī)護人員的實際旅行距離,式(12)表示醫(yī)護人員單條線路旅行不能超過最大旅行距離。

本文采用線性加權法將多目標問題轉化為單目標問題,目標函數為

MinZ4=β1Z1+αβ2Z3-γβ3Z2

(13)

其中Z1表示成本,Z2表示滿意度,Z3表示工作時間差,三者有著不同的量綱,則通過引入系數α、γ使得三者可以統(tǒng)一量綱,β1、β2、β3表示權重。

2 改進BAS算法

天牛須搜索算法(BAS)是一種生物啟發(fā)的智能優(yōu)化算法,是受到天牛覓食原理啟發(fā)而開發(fā)的算法[19]。在天牛覓食的過程中,根據食物氣味的強弱來分辨食物的具體位置,天牛有兩只長觸角,如果左邊觸角收到的氣味強度比右邊大,那下一步天牛就往左飛,否則就往右飛,依據這一原理天?？梢哉业绞澄铩Ｌ炫ｍ毸阉魉惴ㄖ恍枰粋€個體就可以完成任務,運算量較小,但算法穩(wěn)定性較差,全局搜索能力弱容易陷入局部最優(yōu)。因此,本文在原始BAS算法的基礎上對其步長、初始種群等方面進行改進。

2.1 編碼與解碼

由于家庭醫(yī)療人員調度問題涉及老年患者服務順序部分和醫(yī)護人員分配部分,所以本文采用兩段式編碼。用X={X1、X2…XN}表示老年患者服務順序編碼,其中N表示患者數目,X1,…,XN取(1,N)中的任意整數不得重復,0表示醫(yī)護中心;用Y={Y1、Y2…YM}表示醫(yī)護人員分配編碼,其中M表示醫(yī)護人員數目,Y1,…,YM取(1,M)中的任意整數可重復,兩段編碼長度相等。以3位醫(yī)護人員為8位老年患者提供居家醫(yī)療服務為例介紹算法的編碼與解碼。隨機生成的X=[6,3,7,5,1,4,2,8]表示8位老年患者依次的服務順序,Y=[1,3,1,2,2,1,2,3]表示相應的醫(yī)護人員分配,解碼過程如圖2所示。在解碼過程中,醫(yī)護人員根據老年患者服務順序進行服務安排,且醫(yī)護人員均有固定工作時間,若即將超過最大工作時間,則返還醫(yī)護中心結束工作。同時利用罰函數將不符合約束條件與符合約束條件的服務路徑區(qū)分開來,從而得到有效的服務路徑。由此可知1號醫(yī)護人員的服務路徑為0→6→7→4→0,2號醫(yī)護人員的服務路徑為0→5→1→2→0,3號醫(yī)護人員的服務路徑為0→3→8→0。

圖2 解碼

2.2 改進步長

由于原始BAS算法步長為定值,尋優(yōu)能力有限,容易陷入局部最優(yōu),則通過變步長設計來控制算法的搜索能力。前期采用較大初始步長,隨著迭代系數的增加,步長逐漸減小。從最初在全局范圍內搜索,到最終進行局部尋優(yōu)從而求得全局最優(yōu)解,提高算法的精度。設置步長更改系數為r1∈(0,1)。

step=c*d0

(14)

step=r1*step

(15)

其中c是個常數,表示步長與兩觸須之間距離的比值,step則表示步長,d0表示兩觸須之間的初始距離。

2.3 利用混沌理論初始化種群

隨機生成的初始種群容易降低最優(yōu)解的質量,通過利用混沌的遍歷性、隨機性和規(guī)律性的特點對天牛須搜索算法進行初始化,可以使得初始種群遍歷整個空間,增加算法找到最優(yōu)解的概率,加快算法的收斂速度。本文采用Logistic映射模型[20]對天牛的位置進行初始化,回歸方程為

Xi+1=4Xi(1-Xi),Xi∈(0,1)

(16)

在種群初始化時,可以提高初始解的質量使得初始種群中的初始解更接近最優(yōu)解,優(yōu)于隨機產生的初始種群。

2.4 改進BAS算法的步驟

(1)初始化改進BAS算法的參數,更改步長因子參數r1∈(0,1),兩觸須之間的初始距離d0,最大迭代次數N。

(2)建立天牛觸須的隨機向量,并做歸一化處理。

(17)

其中,rands()為隨機向量,n為醫(yī)護人員和患者的數量。

(3)利用上述混沌初始化方法初始天牛的位置X0,并令最優(yōu)位置Xbest=X0,根據式(19)和(20)計算天牛左右觸須的位置坐標,然后根據式(13)計算左右適應度值Z(x0),最優(yōu)位置Zbest=Z(Xbest)。

(18)

(19)

其中,Xl、Xr表示左右觸須的坐標。

更新迭代次數,p=p+1,根據式(15)更新步長,生成新的方向。確定左右觸須的位置Xl,Xr,根據式(13)計算左右觸須的適應度值Zl,Zr。根據式(20)計算新一代的天牛的位置,計算新的適應度值Z(Xp)。

(20)

其中sign()表示符號函數,Xp表示第p次迭代更新后天牛的位置。

(4)采用3-opt局部搜索方法,隨機選擇3個位置調換順序,若比原來的解好,則接受當前解,否則按照原來的解繼續(xù)進行下去,進而將天牛的位置進行運算更新。

(5)計算最優(yōu)適應度值。

(6)判斷是否達到最大次數,滿足條件則輸出最優(yōu)解,否則跳轉至步驟(2)繼續(xù)進行。

改進的天牛須搜索算法流程圖如圖3所示。

圖3 改進BAS算法流程圖

3 算例分析

3.1 算例構造

由于缺乏標準算例,本文仿真算例是在文獻[21]的算例基礎上進行修改所得。利用3種患者規(guī)模的算例來驗證改進算法的性能,規(guī)模信息如表1所示,基本參數設置如下:為簡化算法,考慮到目標函數的重要性程度設β1=0.5、β2=0.3、β3=0.2,參數v=20 km/h,Length=200,系數α=102,γ=-102。

表1 規(guī)模信息

為了進一步驗證改進BAS算法的有效性,本文將改進BAS算法、GA算法以及PSO算法進行對比分析。其中,改進BAS算法中更改步長因子r1=0.95,系數c=2,初始兩觸須之間的距離d0=2;GA算法中交叉概率為pc=0.8,變異概率pm=0.1;PSO算法中學習因子c1=c2=1.457,最大最小慣性權重Vmax=-0.5,Vmin=0.5。

3.2 實驗結果分析

所有算法均通過MATLAB R2019a編程實現(xiàn),為保證實驗的公平性,在同等種群規(guī)模和迭代次數下,取各算法在不同算例規(guī)模下分別運算10次的最優(yōu)值作為最終結果。圖4至圖6分別為3種規(guī)模算例下算法的迭代圖,不同規(guī)模的仿真結果對比數值如表2所示(其中Z1代表總成本,Z2代表滿意度,Z3代表工作時間差)。

表2 不同規(guī)模仿真結果對比

圖4 改進BAS、GA、PSO迭代尋優(yōu)曲線(規(guī)模20)

圖5 改進BAS、GA、PSO迭代尋優(yōu)曲線(規(guī)模40)

圖6 改進BAS、GA、PSO迭代尋優(yōu)曲線(規(guī)模60)

在3種規(guī)模算例下,改進BAS算法的迭代尋優(yōu)曲線均優(yōu)于對比算法(見表2),無論在大、中、小規(guī)模中,改進BAS算法獲得的方案總成本、滿意度水平以及醫(yī)護人員之間工作均衡性均優(yōu)于其他算法。

本文選擇小規(guī)模算例進行具體分析,如表3、表4、圖4、圖7所示。(其中C1代表醫(yī)護人員固定成本,C2代表醫(yī)護人員的懲罰成本,C3/C4代表患者的等待成本或懲罰成本)。

表3 不同算法下醫(yī)護人員的服務順序

表4 改進BAS算法、GA算法、PSO算法的仿真結果對比

圖7 3種算法運行結果

表3是運用改進BAS算法、GA算法、PSO算法求解醫(yī)護人員調度方案的結果對比,其中改進BAS算法最滿意的調度方案為:編號為3的醫(yī)護人員的服務順序為:0-18-7-11-5-6-0,編號為4的醫(yī)護人員的服務順序為:0-12-4-17-16-13-0,編號為5的醫(yī)護人員的服務順序為:0-20-10-8-14-3-0,編號為6的醫(yī)護人員的服務順序為:0-1-15-19-2-9-0。由表4可得在改進BAS算法下的總成本為646.85,滿意度為8.54,旅行距離差為4。相較于其他算法,利用本文算法求解案例所得的服務路徑明顯優(yōu)于其他算法。該算法生成的調度方案所花費的成本和產生的工作均衡性均優(yōu)于GA算法和PSO算法,且滿意度也較高。

由圖4及圖7的對比結果可以看出,改進BAS算法通過引入混沌理論進行種群初始化,提高了初始解的質量,使得算法可以在較少的迭代次數內快速收斂。設計3-opt局部搜索方法,提高了算法在求解過程中的尋優(yōu)性能,當算法陷入局部最優(yōu)時, 可快速跳出。當迭代至后期時,目標函數趨于平穩(wěn)。改進BAS算法有效地提高了搜索到最優(yōu)解的概率,增加了解的多樣性與穩(wěn)定性,而PSO算法和GA算法均存在一定的早熟收斂現(xiàn)象,在種群規(guī)模相同迭代次數相同的情況下,本文所提出的改進BAS算法的尋優(yōu)性能優(yōu)于GA算法和PSO算法,說明本文所提出的算法可行性較高適合解決居家醫(yī)療人員服務路徑優(yōu)化問題。

3.3 敏感度分析

由于BAS算法提出時間相對較短,理論研究較少,參數設置較為敏感,因此,分析不同參數如天牛兩須間距、步長等對算法性能的影響具有重大研究意義。

考慮在同等種群規(guī)模下,分析天牛兩須間距不同對算法性能的影響,分為3種情況:d0=1,d0=2,d0=3。由圖8可得,隨著天牛兩須間距的減小,目標函數值也在逐漸降低,綜合效益得到提升。但當間距減小到一定程度時,所得解的多樣性與有效性卻在降低。因此在一定范圍內,間距大小對算法性能影響較為敏感,本文在保持算法求解性能最優(yōu)的基礎上設置d0=2。

圖8 不同間距下BAS算法的迭代圖

在實際工作過程中,醫(yī)護人員的工作時間對總成本、滿意度以及工作均衡性有著一定的影響。在本研究中,通過設定3種情景:基本工作時間和最大工作時間分別為(6,8)(8,10)(10,12),在不同情景下分別測得結果如表5所示(其中醫(yī)護人員的單位固定成本為160)。

表5 不同工作時間下的仿真結果

由表5可知,在情景一中醫(yī)護中心需要派出5名醫(yī)護人員為20名患者提供服務,此時產生的總成本、工作時間差以及滿意度均最大。在情景二中醫(yī)護中心只需派出4位醫(yī)護人員就可以完成對20位患者的服務,此時情景二產生的總成本雖然略高于情景三,但是就滿意度、工作時間差來說,情景二均優(yōu)于情景三和情景一。因此,通過采用不同時間窗進行總成本、滿意度和工作均衡性對比,可以看出當基本工作時間為8 h,最大工作時間為10 h時產生的總效益最大,此時家庭醫(yī)療人員的調度方案最為合理。

4 結論

本文對家庭醫(yī)療人員調度問題展開研究,綜合考慮患者接受服務的強時效性以及醫(yī)護人員工作時間的差異性等特點構建調度模型,針對模型設計了帶有混沌初始化和3-opt局部搜索方法的改進BAS算法,利用算例以及對比算法驗證了改進算法的有效性。仿真結果表明,改進BAS算法可得到實例的最優(yōu)解,且相較于GA、PSO算法,其搜索能力更強,所得可行解的質量更高,在實際服務系統(tǒng)中,能快速有效地為最優(yōu)調配決策提供科學依據。

本文研究還存在一些有待改進的地方,如未考慮醫(yī)護人員和患者之間的技能匹配問題、醫(yī)護人員工作時間利用率問題,這些問題將是進一步的研究方向。