面向時變回診患者需求的急診周排班研究

王子翔， 吳澤銳， 劉 冉

(上海交通大學(xué) 工業(yè)工程與管理系，上海 200240)

急診服務(wù)主要是對突發(fā)疾病、意外損傷等急診患者提供醫(yī)療服務(wù)[1]，一般由醫(yī)院急診科承擔(dān)，為急診患者提供7×24 h持續(xù)服務(wù).近年來急診醫(yī)療需求的大量增加，急診科室的嚴重擁堵引起的急診服務(wù)質(zhì)量下降是普遍面臨的問題.

急診科室擁堵的原因是多方面的，一個重要原因是患者無法預(yù)約且到達率高度時變.以武漢市某醫(yī)院為例，一天中急診患者到達率在夜間較低，在上午5點左右劇增，7點到達第1個高峰，隨后患者到達率下降并于11點再次劇增，并在約下午2點到達第2個高峰.面對需求的時變、隨機特性，急診科常規(guī)采用的僅區(qū)分日間、夜間的排班往往難以在高峰時段提供充足的人員，繼而造成擁堵.同時，患者回診是導(dǎo)致?lián)矶碌闹匾?由于醫(yī)生一般需要檢查結(jié)果(如血檢、B超、X光等)作為醫(yī)療決策的依據(jù)，所以大量患者必須經(jīng)過一項或幾項檢查后回到醫(yī)生處再次問診，才能完成診療.患者甚至需要經(jīng)歷多次檢查、問診.時變、隨機到達的回診患者與初次到達患者相疊加，成為加劇急診科室擁堵的重要因素.

為了緩解急診科室擁擠，靈活的柔性排班方案被提出并已被部分醫(yī)院采納.不同于傳統(tǒng)的排班方案(如8:00—16:00、16:00—24:00、24:00—8:00固定三班制)，柔性排班的可用班次更多，相比于傳統(tǒng)的排班方案，每個醫(yī)生可被安置的上班班次更加多樣靈活，通過在高峰時段安排更多的醫(yī)生，能夠緩解擁堵問題.雖然柔性排班具有顯著優(yōu)點，但是如何針對患者的到達規(guī)律、考慮大量回診現(xiàn)象而設(shè)計出科學(xué)合理的醫(yī)生柔性排班方案卻較為困難.首先，其備選班次多，比傳統(tǒng)方式更加復(fù)雜.同時，急診非常關(guān)注患者是否能夠及時得到治療，即患者的候診時間等指標，如何采用柔性排班準確有效地減少患者的等待時間需要深入探討.

本研究與多個研究領(lǐng)域相關(guān).首先是醫(yī)護人員的排班問題，對該問題建立數(shù)學(xué)規(guī)劃模型是常用方法[2-4]，求解方法包括精確和啟發(fā)式算法.精確算法包括使用求解器如CPLEX[5]、Branch-and-Cut[6]和Branch-and-Price[7]等.啟發(fā)式算法包括模擬退火算法[8]、遺傳算法[9]、禁忌搜索算法[10]、基于列生成的啟發(fā)式算法[11]等.精確求解算法的優(yōu)點在于能夠求解問題的最優(yōu)解，缺點在于其求解規(guī)模受限，而啟發(fā)式算法則可以在較短時間獲得大規(guī)模問題的可行解.

醫(yī)護人員的排班問題中患者等待隊長、等待時間等常作為目標函數(shù)或模型約束，因此需要對其進行解析計算評估.由于對此類時變排隊系統(tǒng)建模具有挑戰(zhàn)，常用的方法是基于穩(wěn)態(tài)排隊論的近似建模方法.文獻[12]使用SIPP(Stationary Independent Period-by-Period)方法研究了時變服務(wù)系統(tǒng)的建模問題，通過將長時間段劃分為若干時段，將每個時段的系統(tǒng)近似為穩(wěn)態(tài)系統(tǒng)，完成長時段服務(wù)系統(tǒng)建模.文獻[13]同樣將長時間段分割，將每個分割時段的系統(tǒng)近似為穩(wěn)態(tài)系統(tǒng)，給出了時變排隊系統(tǒng)中顧客等待時間的評估方法，并在此基礎(chǔ)上研究了以最小化患者總等待時間為目標的醫(yī)生排班問題.文獻[14]使用逐點穩(wěn)態(tài)(PSA)法研究了時變服務(wù)系統(tǒng)的建模問題，該方法假設(shè)在任何時間點排隊系統(tǒng)幾乎都能立即到達穩(wěn)態(tài)，對每個時間點的系統(tǒng)使用穩(wěn)態(tài)排隊系統(tǒng)加以近似以完成長時間服務(wù)系統(tǒng)建模.其他常使用的時變排隊系統(tǒng)建模方法是仿真方法[15-16]和樣本均值近似方法.文獻[17]考慮了時變、存在回流客流的急診患者需求，使用樣本均值對急診患者的等待時間進行近似評估，進而建立了混合整數(shù)規(guī)劃模型求解醫(yī)護人員的排班方案.文獻[18]同樣使用樣本均值近似方法對考慮時變、帶回流客流的門診預(yù)約和非預(yù)約患者的等待時間進行解析建模.其他方法如數(shù)值方法[19]、無限服務(wù)臺近似[20]、流模型近似[21]等方法也都曾被用于時變排隊系統(tǒng)的建模研究.

盡管已有許多醫(yī)生排班和醫(yī)院排隊系統(tǒng)建模的相關(guān)研究，由于時變的回流患者與初次到達患者的疊加效應(yīng)和不同醫(yī)療服務(wù)流程的相互影響，考慮醫(yī)院時變、帶回流客流的排隊服務(wù)系統(tǒng)的醫(yī)生排班優(yōu)化非常具有挑戰(zhàn)性.僅有文獻[22]研究了類似的時變、帶回流系統(tǒng)，并結(jié)合簡單的平方根規(guī)則給出了醫(yī)生配置方法.

針對時變、帶回流患者需求的急診醫(yī)療服務(wù)系統(tǒng)，提出新的準確患者隊長的解析計算方法，在給定醫(yī)生排班的情況下，迅速且準確地評估每個時段患者等待隊長.在此基礎(chǔ)上，建立醫(yī)生排班的混合整數(shù)數(shù)學(xué)規(guī)劃模型，提出模型的線性化方法，并設(shè)計禁忌搜索算法對模型進行求解.所得模型方法不僅可以應(yīng)用于急診醫(yī)療服務(wù)系統(tǒng)，也可以應(yīng)用于其他類似的存在回流客流的時變排隊系統(tǒng).

1 時變、帶回流客流的排隊服務(wù)系統(tǒng)隊長計算

急診服務(wù)系統(tǒng)是一個涉及到多個科室、人員、設(shè)備、床位的復(fù)雜排隊網(wǎng)絡(luò)，其基本服務(wù)流程如下.首先，患者到達時按照危重級別分診，危急患者需立即送至搶救室搶救治療；普通急癥患者需至急診科各科室等待區(qū)域候診.由于實際運營中，普通急癥患者占絕對多數(shù)，針對該部分患者，其就診流程如圖1所示.患者按照先到先服務(wù)的等待規(guī)則，等待醫(yī)生的第1次問診.經(jīng)第1次問診后，少數(shù)患者無需檢查直接離開急診科或被安排住院，多數(shù)患者需至檢查科排隊檢查，檢查后返回急診科，與初次到達急診患者形成混合隊列等待.醫(yī)生再次診斷后，患者經(jīng)過治療離開急診科或被安排住院.急診科的醫(yī)生排班將直接影響患者等待隊長等服務(wù)質(zhì)量的關(guān)鍵性能指標，因此首先研究在給定醫(yī)生排班的情況下，如何近似計算每個時段結(jié)束時醫(yī)生處和檢查臺處的患者隊長.其中，醫(yī)生處的患者隊長為初次到達患者與回診患者數(shù)量之和.

圖1 急診科室患者排隊系統(tǒng)示意圖Fig.1 Schematic diagram of queuing system of emergency patients

根據(jù)醫(yī)院實際調(diào)研，做出以下設(shè)定：

(1) 研究聚焦一周的服務(wù)時間，其劃分為若干等長時段，每個時段時長為δ，假設(shè)患者的平均到達率、醫(yī)生數(shù)目在每個時段內(nèi)均保持不變；

(2) 患者泊松到達，且不考慮未接受服務(wù)即離開的患者，第t個時段內(nèi)患者到達率為λt；

(3) 醫(yī)生及檢查臺服務(wù)對患者服務(wù)時間隨機，均服從指數(shù)分布，設(shè)醫(yī)生及檢查臺的服務(wù)速率不隨時段變化，分別為μ1和μ2；

(4) 回診患者排隊時是否具有更高優(yōu)先級并不影響醫(yī)生處的隊長結(jié)果，因此不妨設(shè)回診患者在排隊中無優(yōu)先級.

1.1 不帶回流的時變非穩(wěn)態(tài)排隊系統(tǒng)隊長計算

由于帶回流的時變非穩(wěn)態(tài)排隊系統(tǒng)的復(fù)雜性，首先探討不帶回流的時變排隊系統(tǒng)隊長計算方法，記該方法為“APP1”.基于以上設(shè)定，該系統(tǒng)為Mt/M/ct(時變泊松到達、指數(shù)分布服務(wù)時間、時變服務(wù)臺數(shù))的排隊系統(tǒng).對于第t個時段，排隊系統(tǒng)時段初，系統(tǒng)中的顧客數(shù)加上時段內(nèi)到達的顧客數(shù)應(yīng)等于時段末系統(tǒng)中的顧客數(shù)加上時段內(nèi)離開的顧客數(shù).假設(shè)第t個時段內(nèi)完成服務(wù)離開的顧客數(shù)為ut，時段初和時段末的系統(tǒng)隊長分別為lt-1和lt，有如下流平衡方程成立：

lt+ut=lt-1+λtδ

(1)

Mt/M/ct排隊系統(tǒng)流平衡模型如圖2所示.

圖2 Mt/M/ct排隊系統(tǒng)流平衡模型Fig.2 Fluid balance model of Mt/M/ct queuing system

假設(shè)第t個時段的平均服務(wù)強度為ρt，單位服務(wù)臺的服務(wù)速率為μ，則式(1)可改寫為

lt+ctμρtδ=lt-1+λtδ

(2)

根據(jù)排隊論，當系統(tǒng)中服務(wù)臺數(shù)c>1，且服務(wù)強度ρ<1時，穩(wěn)態(tài)M/M/c(泊松到達、指數(shù)分布服務(wù)時間、服務(wù)臺數(shù)恒為c)排隊系統(tǒng)中，顧客期望隊長l的計算方法為[23]

(3)

(4)

需要指出的是，嚴格來說式(3)和(4)僅適用于穩(wěn)態(tài)的排隊系統(tǒng)，其中服務(wù)強度ρ是穩(wěn)態(tài)M/M/c排隊系統(tǒng)的服務(wù)強度.但是考慮到排隊系統(tǒng)由于時變到達率無法達到穩(wěn)態(tài)，所以采用一個時段內(nèi)的短期平均服務(wù)強度ρt加以替代，即假設(shè)該時段排隊系統(tǒng)處于穩(wěn)態(tài)，且該短期平均服務(wù)強度的值為(ut/δ)/(ctμ).在該假設(shè)下，時段末系統(tǒng)隊長lt可通過l(ρt,ct)近似計算.

由以上假設(shè)，lt為關(guān)于ρt和ct的函數(shù)，且當ct固定時，lt隨ρt單調(diào)遞增.將l(ρt,ct)作為lt代入式(2)，則式(2)僅有一個未知數(shù)ρt，且式(2)左側(cè)關(guān)于ρt單調(diào)遞增，右側(cè)為固定值，顯然滿足式(2)的ρt存在且唯一，因此可以使用二分法快速迭代出ρt的近似值[24].經(jīng)實驗，一般經(jīng)過20次迭代后即可使式(2)左右側(cè)的絕對誤差小于0.001.在獲得ρt的近似值后，代入式(3)即可計算該時段結(jié)束時的系統(tǒng)隊長lt.由于一個時段結(jié)束時的系統(tǒng)隊長即是下一個時段開始時的系統(tǒng)隊長，根據(jù)式(2)可求得每個時段結(jié)束時的系統(tǒng)隊長.

本文考慮的排隊系統(tǒng)在部分時段可能面臨超負荷情況，即系統(tǒng)的服務(wù)能力小于顧客需求，盡管排隊論中的服務(wù)強度λt/(ctμ)>1，但時段內(nèi)的短期平均服務(wù)強度ρt的取值范圍仍然在0～1，因此該方法仍然可用.當系統(tǒng)過負荷，即系統(tǒng)的服務(wù)能力遠小于顧客需求(λt/(ctμ)>2)時，可以近似認為服務(wù)系統(tǒng)一直在以cμ的速率服務(wù)顧客，此時可將短期平均服務(wù)強度ρt近似取1，代入式(2)進行計算，即lt可通過下式計算(第t個時段的結(jié)束時隊長不小于0)：

lt=max{lt-1+λtδ-ctμδ,0}

(5)

記式(5)所示的隊長計算方法為“平穩(wěn)流”方法.

1.2 帶回流的時變非穩(wěn)態(tài)排隊系統(tǒng)隊長計算

本節(jié)隊長計算方法記為“APP2”.記醫(yī)生和檢查臺分別為系統(tǒng)1和系統(tǒng)2，l1,t和l2,t分別為醫(yī)生和檢查臺處在第t個時段結(jié)束時的隊長.該時段的醫(yī)生數(shù)和檢查臺數(shù)分別用c1和c2表示，醫(yī)生處和檢查臺處的平均服務(wù)強度分別用ρ1和ρ2表示，假設(shè)顧客去往檢查的概率為P.類似于Mt/M/ct排隊系統(tǒng)，帶回流客流的排隊系統(tǒng)有流平衡等式如下：

l1,t+μ1c1ρ1δ=l1,t-1+λtδ+μ2c2ρ2δ

(6)

l2,t+μ2c2ρ2δ=l2,t-1+Pμ1c1ρ1δ

(7)

醫(yī)生及檢查臺處流平衡模型如圖3所示.對于l1,t和l2,t的計算同理，在c1和c2已知的情況下，式(6)和(7)僅有兩個未知數(shù)ρ1和ρ2.對于一個給定的ρ2，代入式(6)使用二分法迭代可計算ρ1，再將迭代得出的ρ1作為給定值代入式(7)使用二分法迭代計算ρ2，重復(fù)以上求解過程直至式(6)和(7)左右側(cè)絕對誤差均足夠小，再將ρ1和ρ2代入式(3)即可得到醫(yī)生和檢查臺處的隊長.

圖3 醫(yī)生及檢查臺處流平衡模型Fig.3 Fluid balance model of physicians and examination servers

同樣地，當系統(tǒng)過負荷時，可將系統(tǒng)強度假設(shè)為1，代入式(6)和(7)計算醫(yī)生和檢查臺處的隊長.現(xiàn)實中一般醫(yī)生處易處于過負荷狀態(tài)(λt/(c1μ1)>2)，而檢查臺處往往不處于過負荷狀態(tài)，在此種情況下可將ρ1假設(shè)為1，式(7)中僅有的未知數(shù)ρ2仍使用二分法迭代獲得，ρ2代入式(3)獲得檢查臺處的隊長.醫(yī)生處隊長由下式計算：

l1,t=max{l1,t-1+λtδ+μ2c2ρ2δ-μ1c1ρ1δ,0}

(8)

2 醫(yī)生周排班數(shù)學(xué)模型

基于以上隊長計算方法，對急診科室醫(yī)生周排班問題建立數(shù)學(xué)模型.數(shù)學(xué)模型以最小化患者醫(yī)生處總等待隊長及醫(yī)生人力成本為目標，確定每個醫(yī)生一周的排班.在模型中，醫(yī)生用集合K={1,2,…,O}表示，醫(yī)生總數(shù)為O.排班周期為7 d，用集合A={1,2,…,7}表示，一周時間共168 h，分為168/δ個時段，用集合T={1,2，…,168/δ}表示.每天有N個相同的可用排班，假設(shè)N個排班中最后一個排班為夜班，所有排班用集合S={1,2，…, 7N}表示，第n個排班覆蓋的時間范圍用二元參數(shù)rn,t表示，該變量僅當?shù)趎個排班覆蓋第t個時間段時取1，否則取0.c1,t為第t個時間段的醫(yī)生數(shù)，檢查臺數(shù)c2設(shè)為常數(shù).xi,n為二元決策變量，該變量僅在第i個醫(yī)生被安排至第n個排班時取1，否則取0.由于系統(tǒng)隊長的計算表達式非常復(fù)雜且非線性，無法直接使用求解軟件如Gurobi直接求解，所以引入二元決策變量aj,t、bk,t、yl,t和dj,k,l,t對隊長的計算線性化.假設(shè)U和V分別為l1,t和l2,t可能的最大取值，L1和L2分別為APP2近似中l(wèi)1,t和l2,t的計算方法.醫(yī)生周排班數(shù)學(xué)模型如下：

MIP1：

(9)

s.t.

(30)

式中：α為平衡系統(tǒng)隊長和醫(yī)生人力成本的系數(shù)；F為醫(yī)生一周最大工作時長；G為醫(yī)生兩班最大時間間隔.目標函數(shù)式(9)為最小化患者的醫(yī)生處總隊長及人力成本；式(10)保證每個醫(yī)生每天最多只在1個排班工作；式(11)保證醫(yī)生上夜班后至少休息24 h；式(12)～(13)保證每個醫(yī)生一周最多上夜班Cmax次，最少Cmin次；式(14)保證醫(yī)生一周工作最多不超過Fh；式(15)給出每時段醫(yī)生數(shù)；式(16)～(17)保證每時段醫(yī)生數(shù)不超過最大醫(yī)生數(shù)且不少于1；式(18)保證每個醫(yī)生兩班間隔不少于G；式(19)～(20)使只有在l1,t=j時，aj,t才取為1；式(21)～(22)使只有在l2,t=k時，bk,t才取為1；式(23)～(24)使只有在c1,t=l時，yl,t才取為1；式(25)～(26)使只有在l1,t=j、l2,t=k且c1,t=l時，dj,k,l,t才取為1；式(27)～(28)給出每時段結(jié)束時醫(yī)生和檢查臺處隊長；式(29)～(30)為初始化條件.盡管以上模型可以被離散線性化[1]，但由于以上問題規(guī)模很大且約束復(fù)雜，使用求解軟件求解得到的解質(zhì)量不高，具體見數(shù)值實驗4.3節(jié).

3 算法設(shè)計

由于使用求解軟件(如CPLEX、Gurobi等)對以上模型求解非常困難，本文設(shè)計了一種禁忌搜索(TS)算法，基本流程如圖4所示.其中：s為每輪迭代的當前解；s0為初始解；s′為領(lǐng)域中最好的可行解.

圖4 禁忌搜索算法流程圖Fig.4 Flowchart of TS algorithm

3.1 產(chǎn)生初始解

算法通過簡單的原則產(chǎn)生初始可行解s0.首先，安排第i個醫(yī)生(當醫(yī)生數(shù)O≥7)值第md 的夜班(i=m, 1≤m≤7)，接著通過“First-accept”策略安排醫(yī)生使每個時段都有醫(yī)生上班，即當某時段醫(yī)生數(shù)為0時，找到覆蓋該時段的排班中序號最小的，將能夠滿足所有排班約束的最小序號的醫(yī)生安排至該排班，重復(fù)這一過程直到每個時段醫(yī)生數(shù)均大于0.通過以上過程能夠得到醫(yī)生上班總時長最小的初始解，在此解的基礎(chǔ)上，將醫(yī)生按貪婪法安排排班，即選擇能最小化目標函數(shù)值的位置加入排班，直到每個醫(yī)生均無法再加入更多排班.

3.2 鄰域結(jié)構(gòu)及禁忌操作

獲得解s0后，記該解為第1個當前解s，構(gòu)造當前解的鄰域集合，鄰域解通過以下兩個操作產(chǎn)生：① 為1名醫(yī)生增加1個工作班次；② 去除1名醫(yī)生的1個已有排班.若解集合中所有解均為不可行解，則隨機選擇兩個醫(yī)生的兩個排班交換，直到產(chǎn)生新的可行解作為新的當前解(實驗中未出現(xiàn)由以上鄰域操作產(chǎn)生的鄰域集合全部為不可行解的情況).獲得鄰域集合后，選擇集合中最好的一個鄰域可行解s′，令其為新的當前解.為了防止算法在迭代過程中陷入局部最優(yōu)，反復(fù)搜索已經(jīng)搜索過的解或解空間，算法需要規(guī)定禁忌操作.算法的禁忌規(guī)則設(shè)計如下：若一輪迭代中當前解為s，產(chǎn)生新的當前解為s′，定義使解s變化至解s′操作的逆操作為該輪迭代的禁忌操作，并在此后θ輪迭代中禁止該禁忌操作.

3.3 解評估

算法需要對當前解的所有可行鄰域解進行評估，即計算該解對應(yīng)醫(yī)生排班下的目標函數(shù)值，所提算法對患者等待隊長的近似評估使用1.2節(jié)中“APP2”系統(tǒng)評估方法.

3.4 赦免規(guī)則

若當前解的一個鄰域可行解通過被禁忌的操作產(chǎn)生，但其目標函數(shù)值較當前最好解的目標函數(shù)值更好，則算法對該解實行赦免，即取消對該解的禁忌限制.

3.5 停止條件

所設(shè)定算法的迭代次數(shù)為停止條件，當算法迭代給定次數(shù)(如500次)后停止并輸出當前最好解.

4 數(shù)值實驗

設(shè)計數(shù)值實驗驗證所提出的隊長近似方法和TS算法.首先，針對醫(yī)院實際的患者到達數(shù)據(jù)和醫(yī)生排班方案，通過對比仿真結(jié)果驗證所提出的隊長近似方法的有效性，然后使用設(shè)計的TS算法對醫(yī)院的醫(yī)生排班進行優(yōu)化，并將TS算法解分別與實際排班、基于仿真模型的遺傳算法(GA)解和MIP1模型求解結(jié)果進行對比，以驗證TS算法的有效性.數(shù)值實驗所使用的硬件為3.1 GHz CPU，512 GB內(nèi)存，運行Win10操作系統(tǒng).

實驗數(shù)據(jù)來自武漢市某醫(yī)院急診科5周的實際數(shù)據(jù)，該醫(yī)院急診科目前實際采用固定的四班制排班：8:00—16:00為第1班，9:00—17:00為第2班，17:00—1:00為第3班，1:00—9:00為第4班，每班分別安排1、2、1、2個醫(yī)生.數(shù)值實驗使用的柔性排班如表1所示，其他參數(shù)如表2所示.所有數(shù)值實驗的系統(tǒng)初始隊長均假設(shè)為0，流平衡允許誤差設(shè)為10-4.

表1 柔性排班的班次時間Tab.1 Schedule time of flexible scheduling plan

表2 數(shù)值實驗參數(shù)表Tab.2 Parameters of numerical experiments

4.1 隊長計算方法精度實驗

表3 仿真與APP1、APP2近似方法的醫(yī)生處總隊長比較

從表3可以看出，在5個算例下APP2近似方法得到的總隊長結(jié)果與仿真結(jié)果均非常接近，而由于未考慮患者的回流現(xiàn)象，APP1近似方法得到的總隊長結(jié)果與仿真結(jié)果相差較大.APP1近似方法所得結(jié)果與仿真結(jié)果的相對誤差均高于80%;APP2近似方法所得結(jié)果與仿真結(jié)果的相對誤差均低于5%，5個算例使用APP2近似方法得到的平均總隊長為 1 586.24，而仿真結(jié)果為 1 627.96，平均誤差為2.44%.由圖5和6可以看出，APP1近似方法與仿真結(jié)果在每時段結(jié)束時的醫(yī)生處隊長上有明顯差別，而APP2近似方法與仿真方法得到的結(jié)果不僅趨勢一致，在數(shù)值上也十分接近.因此，所提隊長近似方法能夠作為TS算法中的解評估方法.

圖5 W2每時段結(jié)束時APP1、APP2醫(yī)生處隊長與仿真結(jié)果比較Fig.5 Hourly patient queue lengths by APP1, APP2, and simulation in the physicians’ queue of W2

圖6 W3每時段結(jié)束時APP1、APP2醫(yī)生處隊長與仿真結(jié)果比較Fig.6 Hourly patient queue lengths by APP1, APP2, and simulation in the physicians’ queue of W3

4.2 TS算法求解結(jié)果與實際排班方案的對比

使用所設(shè)計的TS算法對5個算例分別進行求解，設(shè)定算法迭代500次后停止并輸出結(jié)果.每個算例的TS算法解與實際排班的目標函數(shù)值和患者醫(yī)生處總等待時間如表4所示.其中：γTS為算法解；γREAL為實際排班值；tCT為算法求解時間；ω3為算法解與實際排班目標函數(shù)值的相對誤差；ω4為算法解與實際排班患者在醫(yī)生處的總等待時間的相對誤差；tWT為患者在醫(yī)生處的總等待時間，通過仿真得到.以W1為例，算法解與實際排班下的每時段結(jié)束時醫(yī)生處仿真隊長對比如圖7所示，算法解與實際排班的對比如圖8所示.

表4 TS算法解與實際排班對比Tab.4 Comparison of TS scheduling solutions and real scheduling plan

圖7 W1時的TS算法解與實際排班下醫(yī)生處仿真患者隊長對比Fig.7 Comparison of patient queue lengths of TS scheduling solutions and real scheduling plan in the physicians’ queue of W1

圖8 W1時的TS算法解與實際排班各時段醫(yī)生數(shù)對比Fig.8 Comparison of physician staffing plan of TS scheduling solutions and real scheduling plan of W1

由表4可以看出，每個算例的TS算法解對應(yīng)的目標函數(shù)值較實際排班小21.8%～42.6%.同時，患者總等待時間的仿真結(jié)果顯示，相比于實際排班，TS算法排班能夠平均減少患者醫(yī)生處的總等待時間70%以上.所有算例中，W2的算法運行時間最長，為1.38 h，5個算例的平均運行時間小于1.3 h.

由圖7可以看出，TS算法排班能有效地降低患者的等待隊長.相較于實際排班，算法排班下除了少量時段(如時段9～14、57～59、81～85)結(jié)束時的醫(yī)生處隊長較大，多數(shù)時段算法排班下的醫(yī)生處隊長更優(yōu)，同時在算法排班下，醫(yī)生處的峰值隊長由27降至12，排隊超過10人的“峰”的數(shù)量明顯減少.對比W1患者的到達率變化和圖8可以看出，使用表1所示的柔性排班方案，TS算法排班在患者到達的高峰時段(如15～18、39～40、63～64等時段)增加了醫(yī)生數(shù)量以降低患者隊長，而在患者到達率相對降低的時段(如9、34～35、57等時段)適當減少醫(yī)生數(shù)量，從而在整體上減少患者在醫(yī)生處的等待隊長及等待時間.值得注意的是，表1所示的柔性排班方案并不適用于所有醫(yī)院，醫(yī)院可根據(jù)自身實際運營情況，設(shè)計并應(yīng)用適合自身的柔性排班方案，降低患者的等待隊長，提高醫(yī)生的整體利用率.

4.3 與GA算法及大型優(yōu)化軟件結(jié)果對比

比較TS算法解與GA算法和MIP1模型的求解結(jié)果，以評估TS算法的有效性.首先設(shè)計GA算法，采用二進制編碼方法，當?shù)趇個醫(yī)生被安排至第n個排班時，第7iN+n位編碼取1，否則取0.算法基本流程如下：首先對醫(yī)生上班總時長最小的初始解編碼，在此解的基礎(chǔ)上隨機改變1個基因位，生成50個個體組成初始種群，對編碼解碼后計算每個個體的適應(yīng)度；在每一輪迭代中基于適應(yīng)度采用輪盤賭方法對群體進行選擇，對被選擇的兩個個體進行交叉，交叉方式為隨機生成一個基因位，交換該基因位后的所有編碼，交叉完成后對個體進行變異操作；隨機選取1個基因位變異，交叉概率為0.8，變異概率為0.15；迭代500次后終止計算，將算法迭代中得到的具有最優(yōu)適應(yīng)度的個體作為算法的最好解輸出.

與TS算法不同，GA算法對于待評估的個體采用基于仿真的方法計算其適應(yīng)度(即目標函數(shù)值).首先，根據(jù)編碼與醫(yī)生排班的對應(yīng)關(guān)系解碼得到該個體對應(yīng)的醫(yī)生排班方案，再對該排班方案進行仿真，計算每時段結(jié)束時醫(yī)生處的排隊隊長，進而得到該個體的適應(yīng)度.仿真模型采用基于事件的仿真方法，使用C++實現(xiàn)仿真程序，對每周的算例運行5×104次取平均得到隊長仿真結(jié)果.為了進一步對比TS算法，同時使用軟件Gurobi 9.0.2對MIP1模型進行求解，設(shè)定求解時間為 8 h.

GA、MIP1以及TS算法的求解結(jié)果對比，如表5所示.其中：ω5為GA與TS算法解目標函數(shù)值的相對誤差；ω6為MIP1模型求解結(jié)果與TS算法解目標函數(shù)值的相對誤差.

表5 TS、GA算法解與MIP1模型求解結(jié)果Tab.5 TS solutions, GA solutions, and solutions of MIP1 models

通過表5可以發(fā)現(xiàn)，TS算法解與GA算法解和MIP1結(jié)果的差異較為明顯.TS算法解目標函數(shù)值較GA算法解平均小24.9%，較MIP1結(jié)果平均小66.9%，而TS算法的平均求解時間僅為GA算法和MIP1模型的1/5.同時，以計算時間為終止條件輸出MIP1模型求解結(jié)果得到的解質(zhì)量可能很差.通過以上對比可以發(fā)現(xiàn)，使用所提TS算法能夠在合理時間范圍內(nèi)得到更好的醫(yī)生排班方案.

4.4 算法參數(shù)分析和靈敏度分析

首先對TS算法的迭代次數(shù)進行分析，確定算法迭代次數(shù)的合理性，然后在W1數(shù)值實驗的基礎(chǔ)上，分別增加和減少醫(yī)生數(shù)、醫(yī)生最大工作時長、醫(yī)生服務(wù)效率和檢查臺數(shù)，以對TS算法的表現(xiàn)進行靈敏度分析.以W1和W2為例，TS算法每輪迭代后最好解的更新如圖9所示，其中：η為算法迭代次數(shù).

圖9 TS算法收斂速度Fig.9 Convergence rate of TS algorithm

由圖9可以看出，在TS算法迭代過程中，最好解的目標函數(shù)值在前期迅速下降，并在迭代100次左右時基本達到收斂.嘗試將迭代次數(shù)增加至 1 000，未發(fā)現(xiàn)更大的迭代次數(shù)能帶來解的改進.考慮到算法的解質(zhì)量和求解時間，500次迭代次數(shù)是一個合理的終止條件.

在實際的患者到達及醫(yī)生配置下，所提數(shù)學(xué)模型和TS算法可以給出合理的醫(yī)生排班，降低患者的等待隊長.在W1數(shù)值實驗的基礎(chǔ)上，每次只改變一個參數(shù)生成不同的場景，研究TS算法的表現(xiàn).在第1、2個場景中，可用醫(yī)生數(shù)由原先的9分別增加至10和減少至8；在第3、4個場景中，每個醫(yī)生的周最大工作時長分別增加和減少10%；在第5、6個場景中，醫(yī)生的服務(wù)速率分別增加和減少10%；在第7、8個場景中，檢查臺數(shù)由原先的10分別增加至11和減少至9.由于醫(yī)院實際排班無法更改醫(yī)生數(shù)或醫(yī)生工作時長，場景1～4使用如下方法產(chǎn)生新排班方案：在場景1、2中分別增加和減少1個醫(yī)生，假設(shè)該醫(yī)生每天在同一個班次工作；在場景3、4中分別給每個醫(yī)生增加和減少1個工作班次，對每個場景均選擇目標函數(shù)值最小的新排班方案.由仿真得到的8個新場景下TS算法排班和實際排班的目標函數(shù)值如表6所示.

表6 不同場景下TS算法解與實際排班的目標函數(shù)值對比

從表6可以看出，在場景1～8下TS算法排班的目標函數(shù)值較實際排班小7.5%～58.3%.對比表4和6可以發(fā)現(xiàn)，即使可用醫(yī)生數(shù)減少1或醫(yī)生的周最大工作時長減少10%，TS算法排班的目標函數(shù)值仍優(yōu)于醫(yī)院實際排班的目標函數(shù)值(2 645.66).以上實驗表明，所提 TS算法對不同場景均能給出合理的排班方案.

4.5 非負指數(shù)分布服務(wù)時間拓展實驗

本文所提出的“APP2”隊長近似計算方法建立在患者到達時間間隔和服務(wù)時間均服從指數(shù)分布假設(shè)基礎(chǔ)上.醫(yī)院實際運營數(shù)據(jù)顯示，指數(shù)分布的患者到達時間間隔可作為實際情況的一種合理近似，而實際服務(wù)時間與指數(shù)分布則常偏離很大.因此，本文對比了TS算法排班與醫(yī)生實際排班在非指數(shù)分布服務(wù)時間下的患者醫(yī)生處總等待隊長和總等待時間.醫(yī)生和檢查臺的服務(wù)時間均服從退化分布和Erlang分布時患者醫(yī)生處總等待隊長和總等待時間分別如表7和8所示.其中：ω7為“算法解”與“實際排班”醫(yī)生處總等待隊長的相對誤差；退化分布和Erlang分布的參數(shù)均經(jīng)過調(diào)整，使醫(yī)生和檢查臺的服務(wù)時間均值與表2所示的指數(shù)分布下的服務(wù)時間均值大小一致；Erlang分布的階數(shù)取為3；患者醫(yī)生處總等待隊長和總等待時間結(jié)果均通過仿真得到.由表7和8可以看出，當服務(wù)時間不滿足指數(shù)分布的情況下，TS算法排班仍能夠有效降低患者的總等待隊長和總等待時間.當醫(yī)生和服務(wù)臺的服務(wù)時間服從退化分布時，算法解相比實際排班，患者的總等待隊長和總等待時間平均分別減少了63.7%和78.2%，當醫(yī)生和服務(wù)臺的服務(wù)時間服從3階Erlang分布時，算法解相比實際排班，患者的總等待隊長和總等待時間平均分別減少了63.0%和76.2%.

表7 退化分布服務(wù)時間下的TS算法解與實際排班對比

表8 Erlang分布服務(wù)時間下TS算法解與實際排班對比

5 結(jié)語

醫(yī)院急診科往往面臨時變、回流的患者流，由于醫(yī)院服務(wù)能力有限，急診科常常面臨擁擠，解決方法之一是將醫(yī)生排班的傳統(tǒng)排班方案改為柔性排班方案.為了得到較優(yōu)的醫(yī)生周排班方案，本文首先提出了一個時變、帶回流客流排隊服務(wù)系統(tǒng)的隊長近似方法，該方法將排班周期分割為若干等長的時段，對每個時段建立流平衡方程并近似將每個時段內(nèi)的系統(tǒng)視為穩(wěn)態(tài)，應(yīng)用穩(wěn)態(tài)下的排隊論公式和二分法，給出了每個時段結(jié)束時系統(tǒng)隊長的近似值.基于該系統(tǒng)評估方法，針對急診醫(yī)療排隊服務(wù)系統(tǒng)建立了一個混合整數(shù)規(guī)劃模型，并設(shè)計TS算法求解醫(yī)生的周排班方案.基于武漢市某醫(yī)院急診科實際數(shù)據(jù)的數(shù)值實驗顯示，本文所提出的隊長近似方法能夠很好地近似時段結(jié)束時的系統(tǒng)隊長，TS算法得到的優(yōu)化排班能夠有效地降低患者的等待隊長，進而緩解急診科的擁堵現(xiàn)象.

將所提出的模型擴展至更一般的排隊網(wǎng)絡(luò)，可以將其應(yīng)用于更實際的場景.后續(xù)的研究可以從以下幾個方面進行擴展：① 由于不同醫(yī)療檢查所需時間不同，考慮在檢查臺處根據(jù)患者的檢查類型分流，研究不同患者不同檢查的排隊網(wǎng)絡(luò)；② 由于部分患者經(jīng)醫(yī)生檢查后需要進入觀察區(qū)，接受一段時間觀察方能判斷是否需要再次返回醫(yī)生處問診，考慮引入觀察區(qū)，研究患者經(jīng)觀察后返回醫(yī)生處再次問診的排隊網(wǎng)絡(luò).