王子翔， 吳澤銳， 劉 冉

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

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

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

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

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

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

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

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

1 時(shí)變、帶回流客流的排隊(duì)服務(wù)系統(tǒng)隊(duì)長(zhǎng)計(jì)算

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

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

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

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

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

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

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

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

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

lt+ut=lt-1+λtδ

(1)

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

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

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

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

(2)

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

(3)

(4)

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

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

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

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

(5)

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

1.2 帶回流的時(shí)變非穩(wěn)態(tài)排隊(duì)系統(tǒng)隊(duì)長(zhǎng)計(jì)算

本節(jié)隊(duì)長(zhǎng)計(jì)算方法記為“APP2”.記醫(yī)生和檢查臺(tái)分別為系統(tǒng)1和系統(tǒng)2，l1,t和l2,t分別為醫(yī)生和檢查臺(tái)處在第t個(gè)時(shí)段結(jié)束時(shí)的隊(duì)長(zhǎng).該時(shí)段的醫(yī)生數(shù)和檢查臺(tái)數(shù)分別用c1和c2表示，醫(yī)生處和檢查臺(tái)處的平均服務(wù)強(qiáng)度分別用ρ1和ρ2表示，假設(shè)顧客去往檢查的概率為P.類似于Mt/M/ct排隊(duì)系統(tǒng)，帶回流客流的排隊(duì)系統(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ī)生及檢查臺(tái)處流平衡模型如圖3所示.對(duì)于l1,t和l2,t的計(jì)算同理，在c1和c2已知的情況下，式(6)和(7)僅有兩個(gè)未知數(shù)ρ1和ρ2.對(duì)于一個(gè)給定的ρ2，代入式(6)使用二分法迭代可計(jì)算ρ1，再將迭代得出的ρ1作為給定值代入式(7)使用二分法迭代計(jì)算ρ2，重復(fù)以上求解過(guò)程直至式(6)和(7)左右側(cè)絕對(duì)誤差均足夠小，再將ρ1和ρ2代入式(3)即可得到醫(yī)生和檢查臺(tái)處的隊(duì)長(zhǎng).

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

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

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

(8)

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

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

MIP1：

(9)

s.t.

(30)

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

3 算法設(shè)計(jì)

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

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

3.1 產(chǎn)生初始解

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

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

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

3.3 解評(píng)估

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

3.4 赦免規(guī)則

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

3.5 停止條件

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

4 數(shù)值實(shí)驗(yàn)

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

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

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

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

4.1 隊(duì)長(zhǎng)計(jì)算方法精度實(shí)驗(yàn)

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

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

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

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

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

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

表4 TS算法解與實(shí)際排班對(duì)比Tab.4 Comparison of TS scheduling solutions and real scheduling plan

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表6 不同場(chǎng)景下TS算法解與實(shí)際排班的目標(biāo)函數(shù)值對(duì)比

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

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

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

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

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

5 結(jié)語(yǔ)

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

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