基于帶記憶模擬退火算法的門診預(yù)約問題求解

郜振華，王紅俊，周春柳，胡玉煥

(安徽工業(yè)大學(xué)管理科學(xué)與工程學(xué)院，安徽 馬鞍山 243032)

門診預(yù)約決策是指醫(yī)療機(jī)構(gòu)根據(jù)前來預(yù)約患者提供的就診偏好以及門診的預(yù)約情況，為預(yù)約患者安排合適醫(yī)生及時間段的過程[1]。對于門診預(yù)約的研究，最先開始于1952年，Bailey[2]基于排隊論對醫(yī)院門診預(yù)約系統(tǒng)進(jìn)行了初步研究，后來Gupta等[3]和梁峰等[4]綜合描述了影響預(yù)約系統(tǒng)的因素，為門診預(yù)約系統(tǒng)研究提供方向。隨著計算機(jī)技術(shù)的成熟，An等[5]研究并設(shè)計了門診預(yù)約系統(tǒng)，有利于規(guī)范醫(yī)院管理。由于醫(yī)療資源的有限性，需對有限資源進(jìn)行合理配置，實現(xiàn)資源利用的最大化[6-7]。

近年，門診預(yù)約的研究更加關(guān)注患者：以患者的等待時間最小為目標(biāo)，根據(jù)服務(wù)時間確定患者服務(wù)次序[8]，考慮患者就診時可能出現(xiàn)的行為特征[9-11]，給出門診預(yù)約的最優(yōu)策略。隨著研究的深入，患者滿意度成為研究熱點(diǎn)，醫(yī)療機(jī)構(gòu)考慮其偏好并以滿意度[12]進(jìn)行度量。但作為非理性人，其偏好情況不能簡單描述，曹萍萍等[13]首先利用前景理論描述患者的滿意度，構(gòu)建門診預(yù)約決策模型；梁峰等[14]利用累積前景理論刻畫滿意度，對門診預(yù)約進(jìn)行調(diào)度并與傳統(tǒng)先到先服務(wù)（first come first service,FCFS）方式進(jìn)行對比；Li等[15]考慮患者實時滿意度，對患者的總體滿意度進(jìn)行優(yōu)化，但上述研究都沒有具體說明解決該問題的方法與過程。門診預(yù)約問題規(guī)模不大，模擬退火算法求解時間短，同時其在前中期局部收斂并且在后期可實現(xiàn)全局收斂[16]，理論上解為全局最優(yōu)解，而其他啟發(fā)式算法的解一般為較優(yōu)解。但傳統(tǒng)模擬退火算法在尋優(yōu)過程中易丟失找到的較優(yōu)解，為避免此類情況的發(fā)生，增加記憶功能[17]。

因此，本文利用前景理論描述患者對醫(yī)生以及時間段的偏好，建立門診預(yù)約決策模型；利用帶記憶模擬退火算法設(shè)計編碼以及鄰域解生成方式，同時設(shè)置不同預(yù)約患者數(shù)量求解模型，以期實現(xiàn)患者的總價值最大，從而提高患者的滿意度。

1 問題描述與模型建立

1.1 問題描述及假設(shè)

在門診預(yù)約的大環(huán)境下，門診擁有多名醫(yī)生，每位醫(yī)生在單位工作日內(nèi)可預(yù)約的患者數(shù)相同；患者可在就診前向醫(yī)療機(jī)構(gòu)提出預(yù)約，同時完成對醫(yī)生以及時間段的偏好選擇，醫(yī)療機(jī)構(gòu)每隔一段時間會對預(yù)約的患者進(jìn)行預(yù)約處理，為其選擇合適的醫(yī)生及時間段。根據(jù)醫(yī)療機(jī)構(gòu)已預(yù)約醫(yī)生的時間段以及患者對醫(yī)生以及時間段的偏好程度為患者選擇合適的醫(yī)生和就診時間以達(dá)到整體價值最大化，用價值刻畫滿意度，進(jìn)而提高滿意度。根據(jù)上述關(guān)于門診預(yù)約問題的描述，給出下列假設(shè)：

1)門診就診患者全部需要預(yù)約，不存在現(xiàn)場掛號；

2)患者預(yù)約之后不存在爽約、遲到現(xiàn)象，且患者預(yù)約時間不分先后；

3)患者對不同醫(yī)生以及時間段之間的損失間隔相同，即在患者主觀意識中，只存在排名差異，不存在具體差異大小；

4)醫(yī)生一個時間段只為一位患者服務(wù)；

5)不接受超出可接受數(shù)量的患者。

1.2 模型建立

根據(jù)問題描述以及患者提供的偏好信息，依據(jù)前景理論[18-19]構(gòu)建基于醫(yī)生的價值矩陣以及基于時間段的價值矩陣，將兩者進(jìn)行加權(quán)可得到預(yù)約的患者對不同醫(yī)生以及時間段的價值關(guān)系，從而構(gòu)建門診預(yù)約決策模型。其中模型涉及的參數(shù)及含義如表1。

表1 主要參數(shù)及其含義Tab.1 General parameters and their meanings

1.2.1 基于醫(yī)生的價值矩陣

1.2.2 基于時間段的價值矩陣

1.2.3 模型構(gòu)建

整合患者對醫(yī)生和時間段的價值矩陣，可得到患者Pk的綜合價值矩陣，

2 算法設(shè)計

2.1 編碼和解碼

2.2 帶記憶模擬退火算法

2.2.1 能量函數(shù)

根據(jù)模型可知目標(biāo)函數(shù)為總價值最大，但模擬退火算法的最優(yōu)解為最低能量狀態(tài)，因此構(gòu)造能量函數(shù)。通過倒數(shù)的方法將目標(biāo)函數(shù)求最大變成求最小，對數(shù)據(jù)進(jìn)行分析可發(fā)現(xiàn)目標(biāo)函數(shù)的倒數(shù)較小，在進(jìn)行差值計算時不明顯。因此，構(gòu)造的能量函數(shù)為目標(biāo)函數(shù)的倒數(shù)形式并擴(kuò)大1 000倍，如式(15)。

2.2.2 鄰域解

2.2.3 算法步驟

傳統(tǒng)模擬退火算法在初始溫度較高時，跳出局部最優(yōu)的概率較高，這也是理論上能找到全局最優(yōu)解的原因；但算法采用概率接收較優(yōu)解的方式，局部最優(yōu)的解可能被舍去，從而導(dǎo)致算法效率下降，因此采用添加記憶功能的模擬退火算法進(jìn)行求解。算法步驟如下：

1)設(shè)置初始化數(shù)據(jù)，給定初始溫度Tmax，隨機(jī)產(chǎn)生初始狀態(tài)x，給定內(nèi)循環(huán)次數(shù)L，溫度縮減系數(shù)δ，給定最低溫度Tmin；

2)隨機(jī)產(chǎn)生可行解x，記錄當(dāng)前可行解的能量E(x)；

3)對k= 1,2,…,L，進(jìn)入內(nèi)循環(huán)，進(jìn)行步驟4)～7)迭代；

4)利用交換、逆序、變異產(chǎn)生新狀態(tài)即新解xnew；

5)計算新狀態(tài)與舊狀態(tài)能量的增量ΔE=E(xnew)-E(x)；

7)判斷算法是否達(dá)到規(guī)定的內(nèi)循環(huán)次數(shù)L，找到L次內(nèi)循環(huán)所有產(chǎn)生的能量最優(yōu)解，并記錄為當(dāng)前狀態(tài),此時一次外循環(huán)結(jié)束；

8)判斷當(dāng)前狀態(tài)能量與上一次外循環(huán)最優(yōu)狀態(tài)的能量，記錄其中較優(yōu)的能量，且為當(dāng)前狀態(tài)；

9)判斷算法是否滿足規(guī)定的終止條件T＜Tmin，若滿足則當(dāng)前的狀態(tài)為最優(yōu)解，若不滿足則繼續(xù)；

10)降低溫度T，令T=T×δ，返回步驟3)。

帶記憶模擬退火算法的流程圖如圖1。

圖1 帶記憶模擬退火算法流程圖Fig.1 Flow chart of Simulated Annealing algorithm with memory

3 算例分析

已知某醫(yī)療機(jī)構(gòu)門診部每隔一段時間進(jìn)行一次預(yù)約決策，該門診共有4名醫(yī)生，每位醫(yī)生單個工作日將時間段分為10 個工作時間段，門診會對每次決策時間間隔提交的預(yù)約申請進(jìn)行處理，使預(yù)約的患者總滿意度達(dá)到最優(yōu)。在某時間間隔中收集24名預(yù)約患者對醫(yī)生以及時段的偏好排序，如表2，且在這之前醫(yī)療機(jī)構(gòu)門診已預(yù)約的就診時間段如表3。

表2 患者偏好情況Tab.2 Patients preferences

表3 已預(yù)約時間段Tab.3 Booked service time periods

根據(jù)預(yù)約前患者提供的偏好數(shù)據(jù)，將其轉(zhuǎn)變?yōu)榫仃嚫袷綄?dǎo)入MATLAB 中，依據(jù)前景理論求解出患者基于醫(yī)生以及就診時間段的價值矩陣，并進(jìn)行規(guī)范化處理，得到患者的價值矩陣；利用帶記憶的模擬退火算法對門診預(yù)約決策模型進(jìn)行求解。設(shè)置價值函數(shù)參數(shù)α=β=0.88，λ=2.25[14]，模擬退火算法參數(shù)Tmax=1 000，Tmin=0.01，內(nèi)循環(huán)次數(shù)L=100，溫度縮減系數(shù)δ=0.98，交換、逆序概率P=0.80，變異概率Pb=0.60。在Windows10環(huán)境下，利用MATLAB 2018b將該醫(yī)療機(jī)構(gòu)在面對12，16，20，24名患者預(yù)約的情況下，分別運(yùn)行50次，得到其中某次能量變化迭代圖，如圖2。

圖2 能量變化迭代圖Fig.2 Iterative diagram of energy change

由圖2 可看出，在面對12，16，20，24 名患者預(yù)約的情況下，采用建立的預(yù)約模型并利用帶記憶模擬退火算法進(jìn)行求解都可找到較優(yōu)解，相比于隨機(jī)生成的解，能量一直呈下降趨勢，說明患者的總價值逐步趨近于最大值。因此，利用前景理論量化患者對門診預(yù)約決策結(jié)果的價值并計算出滿意解，可有效提高患者對決策結(jié)果的總價值，提高患者滿意度。

隨機(jī)挑選運(yùn)行10 次的實驗數(shù)據(jù)，記錄患者數(shù)目變化時運(yùn)行時間以及最終能量變化情況，結(jié)果如表4，并計算運(yùn)行10 次的平均運(yùn)行時間與平均能量函數(shù)值。根據(jù)能量函數(shù)與目標(biāo)函數(shù)的轉(zhuǎn)換關(guān)系計算出目標(biāo)函數(shù)值，可得到患者數(shù)為“12，16，20，24”時的平均目標(biāo)函數(shù)值分別為9.46，12.28，15.29，17.30。為了更清楚地看出每位預(yù)約患者的價值，計算人均價值(人均價值=平均目標(biāo)函數(shù)值/患者數(shù))，可得到患者數(shù)為“12，16，20，24”時的人均價值分別為0.79，0.77，0.76，0.74，均處于較高水平。根據(jù)圖2 及表4 可看出：當(dāng)預(yù)約患者人數(shù)增加時，運(yùn)行時間并沒有大幅度增加，24名患者預(yù)約時，運(yùn)行時間少于10 s，可滿足日常決策時間要求，證明了該算法求解門診預(yù)約問題的效率較高；運(yùn)行結(jié)果與較優(yōu)結(jié)果能量函數(shù)值相差不足5%，說明該算法求解問題的穩(wěn)定性。

表4 運(yùn)行時間及能量變化情況Tab.4 Changes of running time and energy

對上述運(yùn)行10 次中挑選出較最優(yōu)結(jié)果，整理解碼的預(yù)約結(jié)果如表5。利用傳統(tǒng)FCFS 方法進(jìn)行預(yù)約，當(dāng)存在24 名患者預(yù)約時，結(jié)果如表6，由于先到先服務(wù)的方式，后到患者的決策結(jié)果不影響先到的患者，當(dāng)患者數(shù)為“12，16，20”時，預(yù)約結(jié)果不變。FCFS方法與本文方法得到預(yù)約結(jié)果的價值如表7。

表5 不同數(shù)量患者預(yù)約時的預(yù)約結(jié)果Tab.5 Results of different number of patients’appointments

表6 FCFS規(guī)則下的預(yù)約結(jié)果Tab.6 Results of FCFS reservation

表7 本文方法與FCFS方法價值對比Tab.7 Value comparison betwen this method and FCFS method

結(jié)合表5～7 可看出，在不影響已預(yù)約患者情況下，文中建立的模型根據(jù)患者自身對預(yù)約時間段及醫(yī)生的偏好情況計算價值,并通過帶記憶模擬退火算法進(jìn)行求解，得到的決策結(jié)果可將患者全部安排到適合自己的醫(yī)生以及時間段，總價值比傳統(tǒng)方法的價值高，提高了患者的總體滿意度。

4 結(jié)論

綜合患者對醫(yī)生以及就診時間段的偏好情況，利用前景理論對偏好進(jìn)行量化，設(shè)計兩種偏好的合成方法，建立患者滿意度最大的門診預(yù)約決策模型。依據(jù)問題的特殊性，設(shè)計符合問題特性的編碼以及鄰域解的生成方式，利用帶記憶模擬退火算法對門診預(yù)約決策模型進(jìn)行求解。不同預(yù)約患者算例的求解結(jié)果表明，采用帶記憶模擬退火算法求解門診預(yù)約決策模型，能夠在短時間內(nèi)使整體患者滿意度達(dá)到最優(yōu)，為提高醫(yī)院門診服務(wù)滿意度提供方法支持。

對于患者的心理偏好，未考慮患者取消預(yù)約或者未在規(guī)定時間點(diǎn)到達(dá)的情況，此類情況的發(fā)生會導(dǎo)致醫(yī)生在該時間段的閑置，降低了資源的利用率。因此，后續(xù)研究會根據(jù)患者的往期行為特征預(yù)測預(yù)約之后的行為特征，為醫(yī)療機(jī)構(gòu)更好地提供柔性決策。