基于MDP和動態規劃的醫療檢查預約調度優化方法研究

梁 峰, 徐 蘋

( 南開大學 商學院,天津 300071)

0 引言

醫療檢查是醫院服務過程的中間環節，既面向各大科室，又面向多類患者，其圖像結果是醫生診斷病情的重要依據。由于購置成本高昂，操作維護復雜，醫院的大型診療設備數量有限，每天的最大服務能力受到約束。隨著就醫病人持續增加，各大檢查科室壓力增大，在可允許的等待時間內，醫院的檢查資源難以滿足所有病人的需求。如何通過合理有效的方式，將可用的醫療設備資源在不同類型的病人間進行分配，以提高醫院的收益并減少病人的等待，是醫院管理面臨的重要問題。

檢查資源的需求來自多種病人，這些病人一般可分為三類：門診病人、住院病人、急診病人。不同類型的病人具有各自的需求特征。門診病人和住院病人大多會選擇提前預約，而急診病人會在服務日當天隨機到達。急診病人病情緊急，可允許的等待時間短，一般在急診病人到達時，醫院需立即安排檢查，否則會造成較高的拒絕成本。門診病人和住院病人病情相對緩和，可允許適當等待。另外，在實際中，不同類型的病人所需要的檢查時間也會有所不同。

醫療檢查資源的有效管理主要包含兩大任務：一是建立起面向病人的檢查預約系統，病人可以通過提前預約以減少服務日當天的無效等待。二是確定預約系統的決策規則，在病人的預約請求到達時，系統要能夠根據規則做出接受或者拒絕的決定。目前，大部分醫院設有預約中心來處理各類病人的預約請求，預約系統一般會根據先到先得(First Come First Served，FCFS)的決策方式，將病人的請求安排到設備最近的空閑時間段。這種預約排程方式不考慮不同類型病人的需求特征，同時，由于檢查資源的稀缺性，醫院將有可能拒絕后到達但收益更高的病人類型。為解決此類問題，本文根據有限時域馬爾可夫決策(Markov decision process，MDP)模型，研究有限檢查資源在不同類型病人間的最優預約調度：以醫院在檢查設備方面收益最大化為目標，建立有限時域馬爾可夫決策(MDP)模型，并結合動態規劃理論，得出系統最優的預約排程策略。

1 文獻綜述

關于醫療檢查資源的預約調度，國外已有廣泛的研究。文獻[1]考慮多優先級病人不同的到達率和爽約率，利用馬爾可夫決策(MDP)模型進行預約調度優化，決定有限的檢查資源在不同類型的病人間如何分配，突出之處在于提出了利用兩種算法和一種數學規劃來解決復雜維度的MDP模型。文獻[2]也是針對不同病人類型間的檢查資源分配問題，建立了連續時間馬爾可夫決策模型，考慮設備服務時間的隨機性和部分病人的不守時因素，優化目標為醫院獲得最大收益，并通過近似動態規劃的方法進行求解。文獻[3]運用MDP模型，研究在服務日當天，醫院如何將多臺檢查設備在三類病人間進行合理分配以獲得最大收益。文獻[4]研究放射科的預約排程問題，建立了連續時間馬爾可夫決策模型，考慮折扣因子，通過合理轉化，用線性規劃代替近似動態規劃來求解MDP模型。文獻[5,6]也是運用線性規劃的方式求解MDP模型。文獻[7～9]研究病情緊急的中風病人的檢查排程問題，提出簽約時間段CTS(Contracted Time Slots)的方式，即檢查系統會為中風病人預留CTS，三篇論文均是結合MDP模型與動態規劃理論，分別研究CTS分配，中風病人的合理排程和部分病人提前取消CTS的解決方案。

文獻[10]針對化療科室病人的預約排程問題，建立包含多目標的整數規劃模型，利用Cplex程序來進行求解，分析不同時間長度下的預約調度策略。文獻[11]在考慮病人爽約和病人偏好(即病人自身希望哪天進行檢查)的基礎上，建立起根據預約狀態變化的動態模型，并利用啟發式算法來求解出最優策略，通過比較證明該預約策略的優越性。文獻[12]將隨機因素考慮在內，運用近似動態規劃模型研究多種資源的分配問題和多類病人的排程問題，通過算例比較，證明近似動態規劃方法在處理病人排程問題方面的優越性。

近幾年，國內一些學者也都開始研究醫療檢查資源的調度優化問題。文獻[13]利用MDP模型和動態規劃理論，研究一臺設備、三類病人條件下檢查設備的預約調度。文獻[14]研究的情況為三類病人、兩項檢查、且各類病人可允許的等待時間都為一天，建立包含有限時域的MDP模型，通過值迭代算法得出各類病人的最優預約排程策略。文獻[15]考慮病人的不守時因素，根據CT檢查室現有排程規則，利用Simio軟件建立仿真模型，證明該模型的合理性與有效性，并在此基礎上尋求優化的排程方案。文獻[16]也是利用仿真方法，實地調查所研究醫院的放射科現狀，建立起針對核磁共振檢查(MRI)的分時段預約模型，設計出三種新的排程規則，并通過遺傳算法進行優化，后與傳統預約策略比較，證明新規則的優越性。

目前，對于病人的預約排程問題，各學者考慮的內容有所不同，采取的求解方法也都各異，為進一步的研究確立了基礎。在關于醫療檢查資源優化調度的現有文獻中，由于模型的建立和求解會隨著考慮因素的增加而變得復雜，大部分研究對不同病人的需求特征考慮的不夠完整，研究多臺檢查設備的文獻仍為少數，更很少有學者考慮不同類型病人所需的檢查時間不同，而病人檢查時間的不同將會影響系統產能的最優調度。本文考慮的情況為兩臺設備、三類病人且各類病人所需要的檢查時間不同，根據合理假設，建立有限時域馬爾可夫決策模型，利用matlab軟件求解得出最優預約調度策略，并通過敏感性分析研究了預約策略的適用性。

2 模型描述

本文針對兩臺設備、三類病人的情況進行最優預約排程策略的研究。每類病人需要的檢查時間有所不同，收益情況也存在差別。預約排程的目標是醫院在檢查設備方面獲得最大收益。當某類病人的預約請求到達時，系統會根據決策規則立刻做出接受或者拒絕該請求的決定，并根據設定的排程規則做出合理的預約排程。

2.1 模型假設

假設1醫院安排設備A和設備B同時為病人服務，這兩臺設備的新舊程度、服務能力等完全相同。

假設2檢查設備的服務能力通過時間槽(Time Slot)來衡量，根據實際情況，時間槽可設定為時間的基數，設備A與設備B每天可用的最大時間槽個數相同。

假設3不同類型的病人所需要的檢查時間不同，并且各類病人的檢查時間可以通過時間槽的個數來表示，住院病人所需檢查時間比門診病人所需檢查時間長。

假設4整個預約周期可劃分為有限個相等的時刻。在任意的預約時刻，門診病人與住院病人的預約請求根據不同的概率到達系統，且到達情況相互獨立。急診病人會在檢查當天隨機到達。

假設5在任一預約時刻，每臺設備最多只有一位病人的預約請求到達，即系統在任一預約時刻最多有兩位病人的預約請求到達。

假設6設備A和設備B的到達情況相互獨立。在任一預約時刻，每臺設備都有三種可能，即到達一位門診病人的預約請求、到達一位住院病人的請求和沒有預約請求到達。

假設7在任一預約時刻，預約系統的排程規則設置如下：如果系統只接受一位病人(門診病人或住院病人)的預約請求，優先選擇剩余產能多的設備為該病人服務，若兩臺設備剩余產能相同，則選擇設備A為病人服務；如果系統接受一位門診病人、一位住院病人的預約請求，優先選擇剩余產能多的設備為住院病人服務，若兩臺設備剩余產能相同，則選擇設備A為住院病人服務；如果系統接受兩位同類型病人(兩位門診病人或兩位住院病人)的預約請求，則兩臺設備各服務一位病人。

基于以上假設，醫療檢查預約調度問題可以通過有限時域馬爾可夫決策過程(MDP)來進行描述，醫院收益最大化的目標也可以轉化為動態規劃的最優解。MDP模型可以在任一預約時刻，根據系統的狀態和病人的到達情況做出滿足條件的最優決策。

2.2 模型參數設置

現假設設備A和設備B每天的最大可用時間槽數分別為個，則檢查系統每天總可用時間槽數為個。將整個預約周期劃分為個相等的預約時刻，即預約周期的所有預約時刻可表示為t=H,H-1,…,2,1，病人的預約請求在這些時刻按一定概率到達，假設t=H為預約周期的開始，t=0為預約周期的結束，即服務日當天的開始。模型中的其他參數設置如表1所示。

表1 模型參數設置

2.3 模型建立

根據馬爾可夫決策的六大要素：決策階段、狀態集合、決策集合、轉移概率、報酬、目標函數，建立預約周期內的MDP模型如下。

2.3.1 決策階段

預約周期內的任一預約時刻t，即t=H,H-1,…,2,1。

2.3.2 狀態集合

TA表示設備A的剩余可用時間槽數，TB表示設備B的剩余可用時間槽數。S=(TA,TB)為系統的狀態集合，滿足0≤TA≤T， 0≤TB≤T。

2.3.3 決策集合

每一預約時刻t=H,H-1,…,2,1，系統根據當前剩余時間槽數和病人的到達情況做出決策，即接受或者拒絕的病人的預約請求。系統的行動集合用At(TA,TB)來表示，其中0代表拒絕病人的預約請求，1代表接受病人的預約請求。即有

2.3.4 轉移概率

每臺設備在任一預約時刻都有三種預約到達可能，即到達一位門診病人的預約請求、到達一位住院病人的預約請求和沒有預約請求到達，則預約系統在任一時刻的到達情況可能有六種，對應六種不同的轉移概率。表2列出了六種可能的到達情況及其相應的轉移概率。

表2 到達情況與轉移概率

2.3.5 報酬

醫院檢查一位門診病人、住院病人、急診病人的收益分別是y1,y2,y3，相應的，拒絕一位門診病人、住院病人、急診病人的成本分別是c1,c2,c3。一般有y1+c1

2.3.6 目標函數

Jt(TA,TB)表示從t時刻，系統的當前狀態S=(TA,TB)開始，一直到預約周期結束醫院所能獲得的最大收益。

(1)

其中，當兩個門診病人的預約請求到達，即i=1時，

(2)

當兩個住院病人的預約請求到達，即i=2時，

(3)

當一個門診病人和一個住院病人的預約請求到達，即i=3時,

(4)

當只有一個住院病人的預約請求到達，即i=4時，

(5)

當只有一個住院病人的預約請求到達，即i=5時，

(6)

當沒有預約請求到達，即i=6時，

(7)

當檢查預約周期結束，服務日當天開始，即t=0時，急診病人開始到達，隨機到達的急診病人數為Y。一個急診病人所需檢查時間為p個時間槽，系統的狀態S=(TA,TB)，當[TA/p]+[TB/p]>Y([a]表示不大于a的最大整數)，即總剩余時間槽所能服務的急診病人數大于當天實際到達的急診病人數時，系統會產生空閑成本，同樣的，當[TA/p]+[TB/p]

J0(TA,TB)=y3E(TS^Y)-c4[TA+TB-E(TS^Y)×p]-c3E(Y-TS)+

=(y3+c3+c4×p)E(TS^Y)-c3E(Y)-c4(TA+TB)

(8)

在公式(8)中，(a^b)表示min(a,b)，(a)+表示max(a,0)。

2.4 模型求解

根據MDP模型，At(TA,TB)為使得系統收益函數(公式(1))最大化的行動集合。在所有預約時刻t=H,H-1,…,1，根據邊際條件(公式(8))的限制，確保最優解的存在。在合理設置參數后，可以利用值迭代策略求解MDP模型，使得系統在每一時刻，都能根據剩余時間槽數和病人的到達情況做出最優決策，即接受或者拒絕一個病人的預約請求，并根據設置的排程規則得出具體排程策略。

任一預約時刻，設備A和設備B各自有三種到達情況，到達一個門診病人的預約請求、到達一個住院病人的預約請求和沒有預約請求到達。將兩臺設備的預約到達情況相結合，系統在任一預約時刻都有六種可能的到達情況(表2)。在任一預約時刻t=H,H-1,…,1，系統狀態S=(TA,TB)時，如果到達一個門診病人的請求，系統需比較Jt-1(TA+TB-m)+y1與Jt-1(TA+TB)-c1的大小，若y1+c1≥Jt-1(TA+TB)-Jt-1(TA+TB-m)，則接受該門診病人的請求，否則拒絕。如果到達一個住院病人的請求，則需比較Jt-1(TA+TB-n)+y2與Jt-1(TA+TB)-c2的大小，若y2+c2≥Jt-1(TA+TB)-Jt-1(TA+TB-n)，則接受該住院病人的請求，否則拒絕。根據這樣的決策規則，通過多級迭代，任一預約請求到達時，系統都可以自動做出最優決策。在做出是否接受某位病人的決策后，系統會根據當前時刻的接受情況及設定的排程規則得出排程策略。

3 數值算例

為了更好的模擬出各類病人的到達情況和系統的最優決策過程，對MDP模型中的各項參數進行設置。將預約周期平均劃分為50個相等的時刻，即H=50，此時病人的到達時刻和系統的決策時刻為任一預約時刻t，其中t=50,49,…,1。設備A和設備B每天的最大可用時間槽數T=100，檢查一位門診病人所需時間槽數m=3，檢查一位住院病人所需時間槽數n=4，檢查一位急診病人所需時間槽數p=1。三類病人各自對應的收益和拒絕成本設置如下：y1=200，y2=400，y3=600，c1=100，c2=300，c3=500。每個時間槽的空閑成本c4=100。門診病人的預約請求在任一時刻以α1=0.7的概率隨機到達，住院病人的預約到達率α2=0.2。檢查當天，隨機到達的急診病人數Y服從參數為15的泊松分布。根據各類病人的請求到達概率可計算得出系統在任一預約時刻的轉移概率pi(其中i=1,2,3,4,5,6)，相應的到達情況和六種轉移概率值如表3所示。

表3 到達情況與轉移概率值

基于以上參數設定，根據動態規劃理論，可利用matlab軟件對馬爾可夫決策(MDP)模型進行仿真求解。根據門診病人和住院病人的預約請求到達率α1,α2，可以模擬出預約周期內的一組到達情況，通利用多級迭代，得出最優排程策略。在本文的算例中，通過觀察，發現系統會產生對于接受各類病人的臨界值。以門診病人為例，在任一預約時刻，存在這樣的臨界值L，L為使得y1+c1≥Jt-1(TA+TB)-Jt-1(TA+TB-m)成立的最小值，故決策規則可簡化為比較TA+TB與L的大小，TA+TB≥L時，可保證y1+c1≥Jt-1(TA+TB)-Jt-1(TA+TB-m)一定成立，故接受病人的請求，否則拒絕。對于住院病人，同樣存在這樣的臨界值。系統做出接受或拒絕的決策后，根據接受情況進行排程，若只接受一位病人的預約請求，優先選擇剩余產能多的設備為病人服務(TA=TB時選擇設備A)；若接受一位門診病人、一位住院病人的預約請求，優先選擇剩余產能多的設備為住院病人服務(TA=TB時選擇設備A服務住院病人)；若接受兩位同類型病人，則兩臺設備各自服務一位病人。根據仿真結果，醫院的期望收益函數Jt(TA,TB)隨預約時刻和總剩余時間槽的變化情況如圖1所示。由于系統在每一預約時刻有兩位病人的預約請求到達，故在任一時刻，系統接受第一位病人(門診病人或住院病人)的臨界值變化如圖2所示，接受第二位病人的臨界值變化如圖3所示。

圖1 醫院期望總收益變化圖

圖2 系統接受第一位病人的臨界值變化圖

圖3 系統接受第二位病人的臨界值變化圖

根據MDP模型的決策規則及設定的排程規則，預約周期內的最優排程策略如表4所示。傳統預約策略的決策過程如表5所示。在病人類型中，1代表一位門診病人的預約請求到達，2代表一位住院病人的預約請求到達，0代表沒有預約請求到達。在決策中，1用來表示接受一位病人的預約請求，0用來表示拒絕一位病人的預約請求。TA表示設備A在當前時刻的剩余可用時間槽數，TB示設備B在當前時刻的剩余可用時間槽數。

表4 MDP預約策略

表5 傳統預約策略

根據MDP的決策過程，兩臺設備的剩余時間槽個數隨預約時刻的變化情況分別如圖4、圖5所示。設備剩余時間槽變化情況對應檢查當天的排程策略，由于系統總排程規則為在任一預約時刻，優先選擇剩余產能多的設備為病人服務，故兩臺設備的剩余時間槽變化情況相近，實現了產能的均衡利用，符合檢查當天兩臺設備同時服務的實際情況。

圖4 設備A剩余時間槽變化圖

圖5 設備B剩余時間槽變化圖

根據本文的預約策略，系統在預約周期內所能獲得最大總收益為19600，而傳統的先到先得(FCFS)的預約策略所能帶來的收益為17000。通過比較，可以證明本文的預約排程策略為更優的排程方式。

4 敏感性分析

4.1 設備的最大可用時間槽數T變化

其他條件不變的情況下，改變兩臺設備每天可用的最大時間槽數T，醫院的總收益隨系統總產能的變化情況如圖6所示。可得出結論：(1)當兩臺設備的總產能不能滿足所有病人的預約請求時，無論是傳統預約策略還是MDP預約策略，醫院總收益都隨著可用時間槽數的增加而增加。(2)兩臺設備的總可用時間槽數越少，即檢查系統的產能越匱乏時，MDP預約策略相對于傳統預約策略的優勢越明顯，醫院的總收益增長率隨產能的變化圖(圖7)也更好的證明了這一結論。其中，假設MDP預約策略能給醫院帶來的總收益為r1，傳統預約策略下醫院可獲得的總收益為r2，用k來表示醫院總收益增長率，則有

(9)

圖6 醫院總收益隨產能變化圖

圖7 醫院收益增長率隨產能變化圖

4.2 住院病人的預約請求到達率α2變化

其他條件不變的情況下，調節住院病人的預約到達率α2，醫院的總收益隨α2的變化如圖8所示。在系統總產能不能滿足所有病人預約請求的情況下，可得出以下結論：(1)隨著住院病人預約到達率的增加，MDP預約策略下醫院總收益變化不大，而傳統預約策略下醫院總收益呈遞減趨勢。這是因為在產能缺乏的情況下，隨著住院病人預約到達率的增加，醫院會拒絕更多病人，帶來拒絕成本的上升，而在MDP預約策略下，醫院也將會選擇服務更多綜合收益較高的住院病人，從而實現了總收益的平衡。(2)隨著住院病人預約到達率的增加，MDP預約策略相對于傳統預約策略的收益增長率呈上升趨勢(圖9)。由于住院病人的綜合收益高于門診病人的綜合收益(y2+c2>y1+c1)，MDP預約策略會根據住院病人預約到達率的變化，調整接受某類病人的臨界值，從而為后到達的、收益更高的住院病人保留產能。另一方面，住院病人的預約請求越多，先到先得的預約方式也將有可能拒絕更多后來的住院病人，帶來更高的拒絕成本。

圖8 醫院總收益隨α2變化圖

圖9 醫院收益增長率隨α2變化圖

總的來看，保持其他變量不變，當每臺設備的最大可用時間槽數T變化時，兩種預約策略下的各項指標隨總產能的變化情況如表6所示。表6中，以T=80時的各項數值作為初始基準，各項指標變化值代表下一狀態在上一狀態基礎上的變化情況，即T=90相對于T=80的變化情況，T=100相對于T=90的變化情況，以此類推到T=130。表7為保持其他變量不變，當住院病人到達率α2變化時各項指標的變化情況。以α2=0.1時的各項數值為初始基準，類推方式與表6相同，也表示下一狀態在上一狀態基礎上的變化情況。從表6和表7可以進一步得出結論：系統產能越匱乏、住院病人預約到達率越高的情況下，MDP預約策略相對于傳統預約策略的優越性越是突出。

表6 各項指標隨產能變化情況

表7 各項指標隨α2變化情況

5 結論

本文針對醫療檢查設備的預約調度問題，提出了利用馬爾可夫決策(MDP)模型來動態處理病人的預約請求，優化目標為醫院在檢查設備方面收益最大化。在檢查設備為兩臺、病人被分為三類，且各類病人所需檢查時間不同的情況下，結合動態規劃理論，分析系統在預約周期的最優預約排程策略。通過合理設置各參數值，利用matlab軟件實現多級迭代，仿真結果證明相對于傳統的先到先得的預約策略，本文的預約排程策略具有一定的優越性，能使醫院在檢查系統方面獲得更大的收益。后對模型進行敏感性分析，分別改變兩臺設備的最大可用時間槽數T和住院病人的預約請求到達率α2，得出結論為馬爾可夫決策(MDP)模型適用于醫院的預約排程問題，并且在系統產能越匱乏、住院病人預約到達率越高的情況下，該決策模型相對于傳統預約策略的優越性越是突出。后續的研究工作可考慮從以下兩個方面展開，一是考慮不同設備服務能力與服務效率間的區別，二是研究模型在實際決策過程中可能帶來的不公平現象，可考慮在模型建立時引入公平性因素。