隨機服務時間下異質患者門診預約調度優化

張文思, 李金林, 冉 倫, 王 偉

(1.中國海洋大學 經濟學院，山東 青島 266100; 2.中國海洋大學 海洋發展研究院，山東 青島 266100; 3.北京理工大學 管理與經濟學院，北京 100081)

0 引言

門診是患者在就診過程中最早、也是最頻繁接觸的場所，其服務效率和服務質量會直接影響后續部門、甚至整個醫院的工作效率，因此門診資源的調度與優化一直是醫療服務運作管理研究的重點和熱點[1]。在新醫改的不斷推進下，門診預約掛號服務得到高度重視和推廣。以北京市為例，自統一預約掛號平臺開通以來，市屬醫院整體預約掛號率已從2012年的52.2%提高到2018年的88%。

實際操作中，由于患者服務時間的隨機性，會導致預先為患者分配的服務時間與患者實際接受服務時間的不一致。若為患者設定較早的服務開始時間，可在一定程度上提高醫療資源的使用效率，但會發生新患者到達時前序患者仍未結束服務的情況，增加患者等待時間，使患者滿意度降低；設定較晚的預約時間可減少患者等待時間，但若當前患者結束服務時后序患者仍未到達，就會造成醫療資源的閑置與浪費。因此在隨機服務時間的假設下，如何權衡患者等待時間和醫生空閑以及加班工作時間，設計合理的預約調度機制，實現醫療服務系統成本的最小化，是醫療服務提供者需要考慮的關鍵問題之一。

自Bailey[2]和Lindley[3]的開創性工作以來，門診預約調度問題受到了越來越多的關注[4～7]。Wang[8]在患者服務時間為獨立同分布的指數變量時，指出最優預約時間間隔服從先增加并維持在一個較高水平然后逐漸遞減的“dome”形模式，Robinson和Chen[9]將這一結果擴展到了服務時間服從一般分布的情形，Denton和Gupta[10]基于兩階段動態線性規劃模型求解門診預約中患者的最優時間間隔，并證明了dome型預約規則會大幅提高門診服務效率；Kupier和Mandjes[11]將該研究擴展至兩階段串行排隊的治療過程。

在現實的門診預約問題中，提前預約的患者可能因為各種原因在就診當天沒有前往醫院接受服務，即發生患者爽約(no-show)[12]；此外，不同患者的爽約率、治療時間也不同，即患者為異質的(heterogeneous)[13]。Ho和Lau[14]研究了患者爽約率、服務時間變動系數和單位服務時間患者數量三個變量對預約調度規則的影響；Liu等[15]基于經典排隊論模型，考慮患者爽約率與預約-服務時間間隔的相關關系，設計了相應的超訂機制。同時考慮患者異質性和爽約行為的研究相對較少，其中Zacharias和Pinedo[16]研究了患者爽約率和等待時間成本不同的異質患者的預約調度準則，Lee等[17]基于兩類患者期望服務時間和爽約率的不同，設計了固定到達時間間隔的門診預約調度問題。

給定一組患者，決策者對患者預約時間的決策等價于：(1)決定患者的服務順序，即患者排程，(2)給定患者排序的前提下，決定分配給各個患者的服務時長，即患者調度?；诖?，本文將在上述研究內容的基礎上，在患者服務時間隨機的假設下，考慮患者服務時間分布和爽約行為的不同，對異質患者的預約方案進行優化，以最小化患者等待時間、醫生空閑和加班時間成本，提高醫療資源使用率。

本文其余部分組織如下：第1部分對隨機服務時間的預約調度問題進行描述并給出相應的符號說明和模型假設；第2部分首先建立不考慮患者排序的預約調度模型，求解患者調度方案，并在此基礎上設計啟發式排序準則，同時優化患者的服務順序和服務時間；第3部分通過數值算例對啟發式預約調度方案的效率進行說明，并與樣本平均近似方法獲得的結果進行對比分析，最后給出結論和管理啟示。

1 問題描述與符號規定

考慮單服務臺的預約調度系統，患者為服務時間分布各不相同且相互獨立的異質患者；已預約患者在就診當天可能會發生爽約行為。假設醫生正常服務時間和患者數量固定，正常工作時間內未能接受服務的患者需醫生加班完成服務。本文將以最小化患者等待時間成本、醫生空閑與加班成本為目標，決策各個患者的服務開始時間。

本文所用到的符號說明如下：

(1)參數

(2)決策變量

a=(aij)N×N:分配矩陣，aij=1表示將患者i指派至第j個位置，否則aij=0；

s=(s1,s2,…,sN):決策向量，其中sj表示分配處于位置j的患者的服務時間；

dj(a,x):給定分配矩陣a后處于位置j的患者隨機服務時間；

bj(a):給定a，bj(a)=1表示處于位置j的患者在就診當天出現，否則bj(a)=0；

wj(a,s,x):給定分配矩陣a后處于位置j的患者的等待時間；

lj(a,s,x):給定分配矩陣a后處于位置j和位置j+1的患者之間的醫生空閑時間；

o(a,s,x):醫生加班時間。

根據本文研究問題的特點，現做如下模型假設：

(1)患者服務數量固定，患者服務時間分布信息和行為特征信息可根據歷史數據獲得；

(2)不同患者的隨機服務時間以及就診當天發生爽約的行為相互獨立；

(3)患者隨機服務時間為單峰(unimodal)分布；

(4)患者準時到達系統，不考慮患者遲到、提前到達的情況。

若令第一個患者在0時刻到達，根據上述符號參數及模型假設，第二個患者的預計服務開始時間為s1，第三個患者預計服務開始時間為s1+s2,…,依此類推。

2 模型分析與求解

引入一個服務時間為零且在就診當天出現概率為1的虛擬患者N+1，該患者在醫生正常工作時間結束時(時刻T)到達，則其等待時間即為醫生加班時間。根據模型假設，上述問題可采用如下隨機混合整數規劃模型進行描述:

(1)

s.t.wj+1(a,s,x)=(wj(a,s,x)+

bj(a)dj(a,x)-sj)+,j=1,2,…,N

(2)

lj(a,s,x)=(sj-wj(a,s,x)-bj(a)dj(a,x))+,

j=1,2,…,N

(3)

(4)

(5)

(6)

w1=0

(7)

(8)

(9)

aij∈{0,1}

(10)

s≥0

(11)

約束條件(2)和(3)分別定義了患者等待時間和醫生空閑時間，并保證了若患者在就診當天爽約，則不產生患者等待時間成本，且該患者服務時間為零。約束條件(4)和(5)說明當且僅當患者i在第j個服務時，才會在該位置產生服務時間和等待時間成本。約束條件(6)表示所有患者分配時間總和為醫生正常服務時間T，即將醫生正常服務時間分配給N個患者，約束條件限制了第一個患者在t=0時到達。(8)～(10)保證了每個位置必須且僅能安排一個患者，每個患者只能被安排一次。注意到醫生加班時間等于虛擬患者N+1的等待時間，即o(a,s,x)=wN+1(a,s,x)，則原問題可改寫為：

(12)

滿足約束條件(2)～(11)。

根據式(12)，若第j個患者在就診當天爽約，則相當于該患者的服務時間和等待時間均為零；若該患者在就診當天出現，則服務時間為滿足已知分布函數的隨機變量，等待時間取決于其前序患者的等待時間和服務時間。由符號假設可知當給定指派矩陣a時，第j個患者在就診當天到達系統的概率為

(13)

根據Begen和Queyranne[18]，可利用患者出現的概率αi計算第j個患者的期望服務時間xj，以此代替患者服務時間；由于調整后的服務時間已經考慮了患者的行為特征，簡便起見，在隨后的分析中可忽略患者爽約行為，將模型簡化為：

(14)

s.t.wj+1(a,s,x)=(wj(a,s,x)+

dj(a,x)-sj)+,j=1,2,…,N

(15)

lj(a,s,x)=(sj-wj(a,s,x)-dj(a,x))+,

j=1,2,…,N

(16)

約束條件(4)～(11)。

2.1 不考慮患者排序的調度方案

在預約調度優化中，可將問題分為調度和患者排程兩階段進行求解。對于目標函數(14)，將其等價為

(17)

給定患者排程方案a，則原問題轉化為尋找最優分配方案s，使系統總成本最小。

若系統中只有兩名患者且患者到達順序固定，令第一個患者的到達時間t=0，則此時唯一的決策變量為第二個患者的到達時間，即分配給第一個患者的服務時間s1。不考慮醫生加班成本，可將上述患者預約調度優化與隨機需求下的庫存問題等價(Weiss)[19]，當存在醫生加班成本時，根據前述符號假設，目標函數可寫為：

(18)

d1(s,x)=(s1-x1)+,w2(s,x)=(x1-s1)+

d2(s,x)=(s2-x2-w2)+

w3(s,x)=o(s,x)=(x1+x2+d1-T)+

(19)

求解式(18)關于s1的一階條件，有：

-(co+cl)F1(s1)F2(T-s1)=0

(20)

(20)式提供了當系統中存在兩個患者時分配給第一個患者最優服務時長的隱式解，當不考慮醫生加班時間成本和醫生提前完成服務的空閑時間(即d2)時可得最優解如下[19]：

(21)

下面考慮如何將兩個患者的情形擴展至系統中存在多個患者的情況。注意到，當患者數量N=2時，通過式(21)雖不能獲得最優服務時長的閉式解，但可通過數值計算得到分配給第一個患者的最優服務時長。因此可以考慮將患者分為兩個部分，并將兩部分患者分別看作單一患者進行求解。由此可提出如下算法：

算法1

Step1初始化患者集合P={1,2,…,N}和醫生正常服務時間T，j=N；

Step2將患者集合分為兩個子集，其中P1={j}，P2=P/P1；

(22)

算法2(修正后的算法1)

Step1初始化患者集合P={1,2,…,N}和醫生正常服務時間T，j=N；

Step3利用算法1，求解患者最優調度方案。

2.2 考慮患者排序的調度方案

2.2.1 樣本平均近似

當同時考慮患者服務時間和服務順序時，由于服務時間的不確定性，直接求解隨機混合整數規劃模型比較復雜，為降低求解難度，現有研究常采用樣本平均近似(sample average approximate approach，SAA)方法對模型進行近似。SAA方法利用患者服務時間的樣本值將隨機問題轉化為確定性問題求解，不需要考慮患者服務時間的分布信息，從而降低了計算的復雜性。為更好地說明并建立SAA模型，需引入如下參數和變量：

gk:提前時間，即服務完最后一個患者比醫生正常工作時間T提前的時間；M1,M2充分大的正數。

其他參數和變量的定義與隨機模型相同，基于SAA方法，可將模型(14)改寫為：

(23)

(24)

(25)

(26)

(27)

aij∈{0,1}

(28)

(29)

(30)

(31)

(32)

ok≥0,k=1,2,…,K

(33)

約束條件(24)和(25)定義了各樣本下的患者等待時間和醫生空閑時間，(26)～(28)保證了每個患者都被安排到隊列中的某個位置上，且每個位置只安排一名患者。約束條件(29)～(33)表示患者等待時間、醫生空閑和加班時間非負，當且僅當患者i被安排至第j個位置服務時，患者i會在j位置產生等待成本或帶來醫生空閑成本。

上述混合整數線性規劃問題可通過優化軟件CPLEX求解，Mancilla和Storer[20]證明了當同時考慮患者服務時間和服務順序時，上述問題為NP-hard問題，并通過數值實驗指出當僅考慮10個患者、100個樣本時，采用CPLEX求解該類問題最優解的時間長達數十小時甚至幾天。而若給定患者排序，該方法可較快獲得一個近似最優解，因此在數值算例中將以確定服務順序的SAA模型求解結果作為基準解進行比較分析。

2.2.2 啟發式排序方法

考慮到直接求解隨機混合整數規劃和SAA方法的計算復雜性，根據算法1和算法2的思想，可設計如下算法求解分配給各患者的服務時間和服務順序。

算法3

Step1初始化患者集合P={1,2,…,N}，j=N；

Step2對任意i∈P，將患者集合分為兩個子集，其中P1={i},P2=P/P1；

Step3將集合P2中的患者看作一個整體，并令服務順序為P2P1，將原問題轉化為兩個患者的預約調度問題，利用式(22)修正患者等待時間成本，根據式(20)求得最優解和最優期望利潤C*(i)；

與算法2相同，考慮到集合P2內患者之間的等待時間，也需要對患者單位等待時間成本進行調整。但與算法2的不同之處在于，算法2在對患者等待成本進行修正時，所有患者的服務順序已知，而在算法3中患者服務順序是不確定的，當患者服務時間方差不同時，根據式(22)，P2中各個患者對P1患者等待時間的影響也會隨著服務順序的改變而不同。因此需要進一步考慮如何確定集合P2內患者的服務順序。

Denton等[21]在患者的等待時間成本相同的假設下，利用凸序理論給出了考慮醫生加班時間下兩個患者的最優服務順序。當患者等待時間成本不同時，有：

證明當系統中只有兩個患者時，由式(20)，根據最優服務時間的一階條件，假設服務時間為服從獨立同分布的隨機變量，對第二個患者等待時間成本cw求導，得：

(34)

根據式不難發現?s1/?cw>0，即當第二個患者的等待時間成本較高時，決策者往往會給第一個患者分配較長的服務時間以減少第二個患者的等待時間。此外，由式(12)和(19)，可得系統總期望成本為:

C=E[cw(x1-s1)++co(x1+x2+(s1-x1)+-T)++cI(s1-x1)+]

(35)

對式(35)關于cw求導，

[cw+(cw+cl+co)F1(s1)+

(36)

由式(20)，顯然?C/?cw>0。

其中第二個不等式由凸序(convex ordering)的定義和期望等待時間、醫生空閑時間和加班時間的凸性可得。

當患者數量N≥3時，定理1和定理2的結論不再適用，但仍可為后續設計啟發式排序算法提供思路。根據Mak等[22]，給出如下幾種常見的啟發式排序方法：

(1)方差序(Order of variance，OV)。當患者等待成本相同時，Weiss[19]、Denton等[21]指出可采用方差增序對患者進行排序。由于患者服務時間的方差體現了服務時間的波動性，因此排序時將服務時間方差較小的患者放在前面，可減小方差波動對后序患者的影響。

(2)方差-等待成本比率(Order of variance-to-waiting cost ratio，OVC)。根據定理1，若患者方差相同，則最優服務順序為按照等待時間成本降序排列，這是因為在整個服務隊列中順序相對較前的患者等待時間往往較短，而位置相對靠后的患者由于前序患者服務時間的波動，往往需要等待較長的時間，因此可以將等待時間成本高的患者安排在隊列前面。同時由于服務時間方差會帶來服務時間的波動性，由Gupta[23]，可按照服務時間方差與患者等待成本之比σ2/cw的增序進行排列。

(3)標準差-等待成本比率(Order of standard deviation-to-waiting cost ratio，OSC)。與(2)類似，根據Mak等[22]，可利用服務時間標準差與等待成本比率的增序對患者進行排列。

下面給出基于啟發式排序方法的求解算法：

算法4

Step1初始化患者集合P={1,2,…,N}；j=N;

Step2對任意i∈P，將患者集合分為兩個子集，其中P1={i}，P2=P/P1；

2.3 患者服務時間分布卷積的簡化計算

注意到上述算法均需要計算集合P2內患者隨機服務時間之和的分布函數，即需要計算各個患者服務時間分布的卷積。首先考慮兩個連續隨機變量和的分布，若X1，X2是兩個相互獨立的隨機變量，則X=X1+X2的概率分布可由卷積公式得到：

Y=X1+X2+X3的概率分布可通過計算X(=X1+X2)與X3的卷積得到，以此類推。根據卷積計算公式可發現，當隨機變量的概率密度函數形式復雜時，卷積的計算難度也會加大。

下面通過將連續分布離散近似以對卷積計算進行簡化。對于兩個離散序列x1(n)和x2(n)，其卷積x(n)可通過如下表達式給出：

記患者i的服務時間xi概率密度函數為fi(·),i=1,2,…,N,fi(·)為單峰函數?？紤]區間[0,Tmax]，其中Tmax表示P2中患者服務時間之和的最大值。將區間[0,Tmax]以為Δt間隔等分為M份，即Δt=Tmax/M，當Δt足夠小時，可將離散化的概率密度函數近似作為連續分布的概率密度函數。根據離散序列的卷積公式，有：

……

h1(·)、h2(·)分別為x1+x2、x1+x2+x3的概率密度函數，同理可得到x1+x2+x3+x4，x1+x2+x3+x4+x5等的概率密度函數。

3 數值算例

本節通過數值算例對算法的有效性加以驗證。首先假設患者服務時間為獨立同分布的隨機變量，且患者等待時間成本相等，此時無需考慮患者排序。Denton和Gupta[10]利用L-shape算法求解了基于兩階段隨機規劃的調度問題，并以較高的精度給出了最優解的上下界，因此可將L-shape算法獲得的結果作為最優解，將啟發式算法的結果與L-shape算法進行比較，驗證算法的有效性。

表1 不考慮醫生加班時間的調度方案期望成本比較

*Gap1=(C1—CL-shape)/CL-shape，**Gap2=(C2—CL-shape)/CL-shape;C1、C2分別表示利用算法1和算法2求解患者調度方案獲得的系統期望成本。

當醫生加班成本不為零時，假設患者服務時間服從均勻分布U(0,2)，不同患者的等待時間成本相等。與Denton和Gupta[10]一致，令N=7，表2比較了不同成本參數下算法1、算法2和L-shape算法得到的系統期望成本，圖1給出了不同成本參數下三種算法分別為患者分配的服務時間。根據表2可發現，對等待時間成本進行修正的算法2明顯改善了算法1，且算法2獲得的系統期望成本與L-shape算法結果差距較小，從而驗證了算法2的有效性。

表2 不同參數下的期望成本比較

*Gap1=(C1—CL-shape)/CL-shape，**Gap2=(C2—CL-shape)/CL-shape；C1、C2分別表示利用算法1和算法2求解患者調度方案獲得的系統期望成本。

圖1 不同參數下算法結果比較

再來看同時考慮患者服務時間與服務順序的問題。為與SAA方法的患者排序方式保持一致，均采用方差-等待成本比率(OVC)的啟發式排序方法給定患者服務順序，通過算法4獲得患者服務時間，并將結果與通過CPLEX軟件求解模型(23)得到的結果進行對比。

假設系統中共有7位患者，服務時間分別服從均勻分布U(0,4),U(0.2,3.8),U(0.5,3.5),U(1,3),U(1.2,2.8),U(1.5,2.5),U(1.8,2.2),患者單位時間等待成本向量為cw=[9,8,3,4,5,6,7]，表3對比了當成本系數不同時，樣本均值近似方法與算法4在不同樣本數量下獲得的結果。

根據表3可發現，在不同的參數組合下，當樣本規模K≤10000時，基于算法4的預約調度方案得到的系統期望成本低于給定患者服務順序時利用SAA方法獲得的結果，且隨著樣本數量的增加，SAA方法獲得的結果會得到改善并收斂于最優，但所需求解時間較長，算法4在一定程度上保證求解質量的同時減少了計算時間，由此體現了算法4在計算時間和效率上的優越性。

表3 算法4與SAA結果對比

*Gap=(CH—CSAA)/CSAA，TH表示利用啟發式算法4求解原問題所需要的計算時間;CH表示利用啟發式算法4求解患者調度方案獲得的系統期望成本。

圖2 算法4與SAA算法獲得的患者調度方案對比

圖2給出了不同醫生空閑成本和加班時間成本下，基于不同樣本數的樣本均值近似方法獲得的患者預約調度方案以及基于算法4獲得的患者預約調度方案，從圖中可以看出，兩種算法下分配給各個患者服務時間變動的趨勢一致，且隨著樣本數量的增加，兩種算法下的預約調度方案趨近一致。根據圖2還可發現，兩種算法給第5個患者分配的服務時間最長，給第6個患者分配的服務時間最短。這是由于按照方差-等待成本比率增序對患者進行排序時，根據患者方差和等待成本參數，排在第5個和6個進行服務的患者分別為患者2和患者1；患者2的等待時間成本最小，且小于醫生空閑時間成本，決策者會減少分配給前4個患者的等待時間以減小醫生空閑時間，而患者1等待時間成本最高，因此會為前5個患者分配更多的服務時間，以減少患者1的等待時間。

表4進一步對比了不同患者數量下算法4與SAA的計算結果，當樣本數量較少時，基于算法4的預約調度方案在計算時間和計算效率上均優于SAA方法，隨著患者數量和樣本數量的增多，SAA方法所需計算時間顯著增加，由此進一步體現了算法4在計算效率上的優勢。

表4 不同患者數量下算法4與SAA結果對比

*Gap=(CH—CSAA)/CSAA，TH表示利用啟發式算法4求解原問題所需要的計算時間；CH表示利用啟發式算法4求解患者調度方案獲得的系統期望成本。

4 結論

本文研究了單服務臺的隨機預約調度模型，針對服務時間隨機的異質患者，考慮患者服務時間分布函數和爽約行為的不同，建立隨機混合整數規劃，對患者的預約調度方案和服務順序進行優化。首先給定患者服務順序，求解了兩患者預約系統最優方案滿足的一階條件。進一步的，設計啟發式算法對多個患者的預約系統調度方案進行求解，并通過對患者等待時間成本系數進行調整以修正算法。在此基礎上，對患者的排序方案進行優化，確定各個患者的服務開始時間。

數值結果表明，當患者服務時間為獨立同分布的隨機變量時，分配給患者的服務時間呈現先增加并維持在一個較高水平，后逐漸減少的“dome”形，即給較早接受服務的患者和最后接受服務的患者預留較短的服務時間，而給服務順序處于隊列中間的患者預留較長的服務時間；當患者服務時間分布互不相同時，與基于樣本均值近似方法的結果相比，啟發式算法在求解效率和計算時間上都具有一定的優越性。

當患者等待時間成本較低時，根據數值結果，系統會為隊列中間的患者安排較長的預約時間間隔，若當前患者在下一個患者到達前結束服務，則會造成醫生空閑時間。由于醫療服務過程中，醫生空閑往往伴隨著設備空轉、醫療資源閑置等，空閑時間成本往往較高，實際應用中，醫院可考慮在醫生服務能力范圍內，安排部分當天到達的患者接受服務，以減少醫療資源的閑置；同時，為提前預約患者賦予較高的優先權，防止預約患者因等待時間過長而造成的滿意度下降。在對患者的服務順序進行決策時，需要權衡患者等待時間成本和隨機服務波動性對系統的影響，將服務時間波動較小、等待時間成本較高的患者指派至等待隊列的前面接受服務，將服務時間波動性大且等待時間成本較小的患者安排在后面接受服務，以最小化由于患者服務時間的波動性對系統造成的影響，并減少預約調度系統總成本。