考慮患者分類的應急手術調度研究

余夢圓，葉春明，趙靈瑋，郭 靜，馬 琨

上海理工大學 管理學院，上海 200093

調度理論在生產車間、車輛等領域已經得到廣泛應用，但在應急救援管理中還需要不斷完善與創新。城市突發公共衛生事件，指的是在城市中由于無法進行提前預測或者未能準確檢測而突然發生的，涉及廣大人民群眾的生命生活全方面，并可能會帶來實際損失的事件。它的主要特點是突發性、范圍廣、傳播快、信息局限、復雜性、難以預測、破壞性等。城市突發事件一旦發生，對國家的政治和經濟都會造成不可估量的影響，甚至還會威脅到社會的穩定。距離最近的就是2019新型冠狀病毒，這種病毒傳染極快，特別是在人群聚集的地區。手術調度問題是各種調度問題中的熱點問題，并在患者救治方面有著直觀作用，多年來國內外很多學者都對其進行研究。

傳統的手術調度問題假設患者的手術持續時間是固定的，即在調度開始之前就預先知道了所有患者的手術持續時間并基于此進行排序與優化[1]。但是，在實際應急手術情形下，患者手術時間會隨著手術開始時間的延長出現手術效率下降的情況，具體表現為針對同一患者，越晚開始手術，其所需要的手術時間就越長。相對應的，對于疫情手術的相似性，醫護人員能夠在手術進行中對手術過程更加熟練，從而對于后進行手術的患者，會縮短部分手術時間。

目前，手術調度管理針對以下問題：人力、社會、資源、信息等資源的冗余或匱乏；醫生連續工作產生疲勞；手術室開放時間不足或過剩；完成時間太遲；醫生長時間加班、醫療設備空閑、病患等待成本過高等。學者們以手術時間、院方及患者期望收益、取消風險、患者滿意度、綜合成本和可信度等為目標，建立符合醫院實際情況的模型，并尋求模型的最優解。Anne等[2]提出每個病人同等重要，通過調度手術組患者，來減小手術后住院床位占用率的可變性，并采用禁忌搜索算法求解，發現該模型適合短期住院病人。提出可使用計量經濟學模型預測病人狀況，病人的年齡、性別、外科醫生和疾病是可以區分病人手術時間的一些變量。王騰飛等[3]以等待成本、加班成本和空閑成本為目標，通過蒙特卡洛方法轉化為混合整數規劃模型，對日間手術預約調度問題進行研究并進行敏感度分析。Paola等[4]在主手術調度背景下，根據三個性能標準采用不同調度策略，探尋效率、平衡和穩健性的價值。Lisa等[5]通過混合研究方法，找出了影響實時手術安排的不確定性因素，提出彈性手術安排的框架。安佰玲等[6]給出了病床合理安排的三個評價指標，建立非線性優化模型，結合蒙特卡洛方法進行模擬求解。潘興薇等[7]考慮兩種類型的檢查的不同需求，并考慮患者兩類緊急程度和患者的失約，進行門診患者調度研究。

近年來，許多學者對布谷鳥算法進行了研究，并應用于多種情境。Dipak等[8]將布谷鳥搜索算法中的連續位置轉換為離散的調度問題，以最長加工時間為目標驗證了并行機調度的有效性。Hamidreza等[9]提出了多目標入侵雜草優化算法對布谷鳥算法改進，并評價多技能資源約束項目調度問題，最后采用基于優先級的方法對所提出的算法進行了不同指標的比較。Preetam等[10]提出了一種離散種間的布谷鳥搜索算法，采用最小位置值法，并進一步說明了其在解決混合流水作業調度問題和置換流水作業排序問題中的優越性。

手術調度是應急救援管理的重要問題，是優化醫院醫療資源與服務的關鍵環節之一。在醫院日常運行中，或許并沒有大批患者短期內到達，但在應急救援中，通常會有大量患者等待救治。上述文獻在多角度對手術調度做了有效研究，為后續的研究奠定了良好的基礎，但是這些研究都沒有考慮患者的分類對手術調度的影響。因此本文考慮不同的患者類型，并同時考慮手術團隊的學習效應和患者傷情的惡化效應，在新冠疫情的背景下，對應急手術調度問題展開研究。

1 應急手術調度模型

1.1 問題描述

本文研究的是城市公共衛生事件發生后，傷員到達救助醫院后應急手術救治過程。手術調度的過程可以看作是三級混合流水車間問題[11]，分為術前準備階段（預麻醉）、手術階段和手術恢復階段（麻醉恢復）。國內大型醫院的恢復室數量與手術室數量相近[12]，因此只有恢復階段有空余時，患者才可以被轉送去術后恢復室，否則要在當前的手術室滯留，直至有空余的恢復室。若手術調度不合理，將會直接導致手術室和恢復室的利用率低下，最終導致患者得不到妥善及時的救治與安排。手術具體流程如圖1所示。

將在醫院或者應急救援點的患者，按照術前麻醉—手術—術后恢復的流程，建立多目標整數規劃模型。在此情景下，將患者按照手術服務時間長短和傷情緊急程度相結合的方式進行手術調度，基本變量表述如下：

n位患者pi(i=1,2,…,n)將在m(m=3)道手術工序上依次進行手術治療，所有患者的手術流程相同；Oij表示第i位患者的第j道手術工序；mj(j=1,2,…,m)表示第j道手術工序包含的手術室數量，每位患者都可以在某一手術階段的任意手術室，且每位患者的手術治療路徑彼此獨立；tijk表示患者i在第j道手術工序的第k間手術室進行手術的時間；Sij表示手術工序Oij的開始時間；Cij表示手術工序Oij的完成時間；Ci表示患者i的整個手術完成時間；Njk表示第j道手術工序的k間手術室治療的患者數量；xijk為0、1變量，若Oij選擇在第k間手術室進行手術則為1，否則為0。

1.2 患者分類手術室選擇

在大規模城市突發公共衛生事件的背景下，患者的傷情具有高度的相似性，為提高手術治愈率，針對患者的不同傷情，將病患的種類分為三級。在術前對患者進行有效分類可以極大程度減少傷亡，并提高醫生的手術效率。用pu表示分類患者的集合，分為輕度患者p1、重度患者p2、危重患者p3,易知p1+p2+p3=n；表示在第j道手術工序的手術室k上救治的第R個u類患者。在手術的準備階段和恢復階段，三類患者在任意一間都可以得到合理的救治，而在手術階段卻不一樣。醫院一般采用r1（30 m2）和r2（50 m2）兩種規格的手術室對患者進行救治，其中危重患者由于手術過程的復雜性及人員和設備的多樣性，只能選擇在50 m2的手術室進行手術，而輕度患者和重度患者在兩種手術室都能完成手術。

表1 分類患者手術室選擇Table 1 Selection of operating room for classified patients

因此，重癥患者p3在手術階段在特定手術室進行可以表示為：

式中，gij是決策變量，表示第i位患者的第j道手術工序是否必須在某類指定的手術室進行手術，若是，其值為1，否則，其值為0。

1.3 手術團隊學習效應與患者惡化效應

在城市公共衛生突發事件中，患者常因得不到及時治療而使病情惡化，因此應急救援尤為重要，更何況大部分患者往往擁有相似的病情，處理手段也具有一定的相似性。手術時間不是固定的，這取決于正常手術時間、手術順序、手術團隊積累的經驗、控制參數及其開始時間。在實際的時間表中，手術時間會隨著手術團隊經驗的積累而呈現一定程度的減少，這就是學習效應[13]。隨著處理手術的數量增多以及手術時間的累積，負責固定手術階段醫生的經驗越來越豐富，技術越來越成熟，因此手術救治過程擁有一定的學習效應[14]。手術團隊的學習效應指的是由于手術過程的重復性，醫療團隊進行重復操作而獲得手術救治經驗的積累，使得繼續救治同一類患者時，手術時間不斷下降，患者的手術救治效果更好的過程。與此同時，患者不同的等待手術時間也會帶來惡化效應，因此實際手術所用的時間表示為：

式中，C′i1,C′i2,…,C′im分別為患者i的第j道手術工序實際結束時間；ti1k,ti2k,…,timk分別為基本手術的各個工序所需時間；α1,α2,…,αm分別為醫護工作者不同手術階段的學習系數；βi(0≤βi≤1)表示第i位患者的惡化系數。

1.4 目標函數

本文根據對手術調度實際情況的分析，確定的調度目標集表示為min(f1,f2,f3)。其中f1表示平均手術時間；f2表示患者惡化成本；f3表示手術室總能耗。

（1）最小化平均完成手術時間

在醫院的手術管理中，很多管理過程都是統一的，例如部分手術室的中央空調是集中進行管控的；手術室的普通照明燈光是統一進行控制的，等等。同時，用最小的時間對患者進行有效治療是醫院和患者同時關注的重點，手術時間在一定程度上也關乎著患者的身體及精神負擔。因此，對所有患者的手術過程平均時間的考慮是必要且有效的。

（2）最小化患者惡化成本

患者的惡化成本也是應納入考慮的重要因素，在最佳治療時間內進行手術能極大降低患者進一步惡化的風險，手術開始和進行的時間與患者的治愈效果直接相關，靠前則治療效果相對較好，反之亦然。因此，患者的惡化成本包括手術開始前等待時間成本和手術持續時間成本。

式中，參數ω、δ1、δ2、δ3為非負數。

（3）最小化手術室總能耗

Karme等[15]提出手術完成質量與執行或推遲手術、手術室加班和閑置時間以及重癥監護室（ICU）的成本不足有關。Wim等[16]提出資源過載的數量是進行評估的重要因素，并針對醫院的資源對手術數量進行研究，結果表明構建的模型在文獻和實踐中考慮的許多外科病例調度方面有較好的改進效果。

在應急救援管理中，由于突發事件的隨機性和廣泛性，醫療消耗資源例如醫用外科口罩、防護服和檢驗類試紙等是有限的，資源的調度需要一定的時間，未必能按時按量送達指定地點。同時手術所需的各類醫療設備，例如呼吸機、制氧機、麻醉機和X射線機等，它的能耗越小，則設備的損耗越小，越能救治更多的患者，同時醫療成本也越低。因此，醫院進行手術的資源在應急管理的場景下是珍貴的，對資源有效合理地利用能在一定程度上提高手術的效率、患者的治愈率以及患者的救治數量。本文將醫院的手術資源量化為手術室的總能耗進行研究。

綜上所述，手術室總能耗也是應急手術考慮的重要因素，其包括忙時能耗和空載能耗，手術過程中的能耗與調度方案直接相關。手術室處于空載狀態時會加速醫療設備的老化，以及手術室能源包括空調在內的無故消耗。同樣，手術室作業時也會加速設備的老化，同時也會消耗醫院的醫護資源和醫療用品資源等。因此，手術室總能耗的計算公式為：

式中，IEk表示手術室k上的單位時間空載的單位能耗；Tk表示手術室k處于空載的時間；PEijk表示手術工序Oij在手術室k處于忙時的單位能耗。

1.5 應急手術調度數學模型

本文以平均完成手術時間、患者惡化成本和手術室總能耗為目標，對應急手術調度進行優化研究。為了簡化并構建合理有效的模型，需要對問題做出如下假設：

（1）一間手術室同一時間只能進行一臺手術；

（2）一位患者同一手術階段只能在一間手術室進行；

（3）保證手術過程連續性，一旦開始就不能中斷；

（4）手術過程必須按照同一順序依次進行；

（5）不考慮手術過程中突發情況手術間轉移情況；

（6）不同患者之間沒有先后約束；

（7）手術過程中患者的移動時間忽略不計；

（8）手術過程中所有資源包括人員、設備和物資準備充足并且能夠準時到位；

（9）患者的類別已全部分好，不存在檢查產生的時間；

（10）沒有特殊要求的病患，并且在手術前不用特殊檢查[17]；

（11）所有手術的初始開始時刻以及手術間的開始手術時間都為0；

（12）不考慮連續不同手術之間的切換時間。

約束條件如式（6）～（15）所示：

式（6）表示每位患者在同一手術工序上只能在唯一的手術室進行治療；式（7）和式（8）表示應急手術每個階段至少有一個病床；式（9）表示每道手術工序治療的患者總數為n；式（10）表示一間手術室在同一時間只能對一位患者進行一道手術過程；式（11）表示必須按照手術流程進行手術；式（12）表示手術過程Oij一旦開始就不可以中斷；式（13）表示手術工序的順序約束；式（14）約束了手術開始和結束時間一定是正數；式（15）表示變量的取值范圍。

2 算法設計

2.1 應急手術調度數學模型

布谷鳥算法（cuckoo search，CS）是由英國劍橋大學的Yang等在2009年提出的一種仿生群智能算法[18]，是一種求解優化問題的新型高效的基于種群的啟發式進化算法，具有實現簡單、控制參數少等優點。該算法是基于某些布谷鳥類的義務后代寄生行為，結合某些鳥類和果蠅的Lévy飛行行為而設計的。該算法的靈感來源于布谷鳥的繁殖策略，根據布谷鳥產卵時的飛行機制進行搜索，能夠快速有效地解決多維空間尋優問題。通過模擬布谷鳥的智能繁殖行為而開發出來的，基于群體的搜索過程，作為優化工具，解決復雜的、非線性的和非凸的優化問題。在初始化過程中，所有的鳥巢（解）都是在上限和下限內隨機生成的。

2.1.1 Levy飛行

布谷鳥算法的一個重要特征是使用了Levy飛行的方式進行局部和全局搜索。Levy飛行過程，以前被用于其他啟發式搜索，其特征是從概率密度函數中選擇一系列瞬時移動。這個過程代表了最佳隨機搜索模式，在自然界中經常發現[19]。Levy飛行的原理是模擬一種隨機游走過程，它由低頻率的長距離飛行和高頻率的短距離飛行所組成，其步長服從Levy分布。因此，布谷鳥算法尋找鳥巢的位置以及路徑更新公式如下：

式中，Xti為當前的解；?為點乘；Levy(λ)為Levy飛行的搜索路徑；λ為參數；α是步長參數，其大小直接取決于問題的規模，具體可表示為：

式中，α0為大于0的實數，通常取0.01；Xbest表示當前最優解。

2.1.2 布谷鳥搜索過程

傳統的布谷鳥算法需要滿足以下三種原則：（1）布谷鳥隨機選擇寄生巢，并且隨機產卵。（2）只有擁有最高質量的卵的最好的巢才會被選擇給下一代。（3）布谷鳥的卵被宿主察覺的概率為pa，并且被察覺后，布谷鳥需要尋找新的鳥巢。最后一個假設可以理解為：如果參數設置為0.2，則在每次迭代結束時，有20%的最差巢穴將被隨機生成的新巢所取代。Levy飛行表示隨機飛行的路徑，飛行的方向服從均勻分布，連續跳躍距離和時間t服從著名的Levy概率分布，故對其簡化和進行傅里葉變換后，得到符合冪次形式的分布：

式中，u是一個帶有重尾的概率分布，服從Levy分布，該分布有一個無窮方差和無窮均值，其步長本質上構成一個隨機行走過程。

2.2 改進的布谷鳥算法

布谷鳥算法具有全局搜索性能好、參數較少、簡單易實現等優點。但它只適用于局部，容易陷入局部最優解，并且最初的布谷鳥算法是為了應用于連續優化問題而開發的。因此，該算法不能直接用于解決離散的問題，通過改變算法的原始范式，將算法的思想推廣到離散域。

2.2.1 Levy飛行數學模型

本文采用Mantegna[20]提出的Levy飛行算法，公式如下：

式中，θ為分布參數，θ∈[0.3,1.99]，一般取1.5；μ和v服從正態分布，μ:N(0,σ2μ)和v:N(0,σ2v)；σμ和σv的取值如下：

綜上所述，布谷鳥算法的位置更新公式為：

2.2.2 被發現概率自適應調整

傳統的布谷鳥算法都會采用不變的被發現概率pa，并且一般取值為0.25。被發現概率的大小會直接影響尋優的搜索速度，若被發現概率過大，則會較難收斂到最優解并有可能陷入局部最優；而過小，則會使得收斂速度較慢并對搜索范圍盲目搜尋。因此，為了解決該問題，本文引入自適應調整機制，具體如下：

式中，pmax表示最大被發現概率；i表示當前迭代次數；Max_iter表示最大迭代次數；pmin表示最小被發現概率。

該策略使得算法在計算前期保證全局搜索能力的前提下快速收斂到非劣解，隨著迭代次數的逐步增加，種群個體的質量也隨之增高。到了計算后期，被發現概率會隨著迭代次數的增加而遞減，有利于算法進行更精確的局部搜索。相比于其他改進方式，本文提出的改進策略參數少，求解速度快，實現方式簡單，有效地改善了搜索能力和收斂速度。

2.3 編碼規則

編碼是算法實現的關鍵。由于患者手術排序編碼是離散型的，無法直接使用布谷鳥算法，本文需要對手術工序和手術室進行編碼。考慮當前手術工序手術室選擇和患者前后手術順序兩方面，為此，本文設計一種同時考慮當前患者手術選擇和患者前后手術順序的兩段式整數編碼方式，如圖2所示。

基于手術工序編碼中，數字表示患者編號，數字出現的次數表示手術工序，比如第三個數字1表示患者1的第2道手術工序?；谑中g室編碼中，上行數字表示手術室編號，比如說第三個數字5表示患者1的第2道手術工序在手術室5上進行。第一段編碼確定患者手術工序的順序，第二段編碼確定當前患者手術工序所在的手術室。兩段編碼相結合確保所求解可行。

2.4 算法步驟

綜上所述，改進的布谷鳥算法對應急手術調度問題具體實現步驟如下：

步驟1設置算法參數，被發現概率pa，編碼上下限，Pareto解的個數Z，設置搜索終止條件以及最大迭代次數Max_iter。

步驟2初始化種群，計算各個鳥巢的目標函數值，并保留最好鳥巢及其目標函數值。

步驟3計算鳥巢位置，對應三個目標函數值，構建初始Pareto最優解集。

步驟4根據位置更新公式（16）～（21），得到下一代鳥巢的位置。

步驟5計算每個鳥巢的目標函數值，并與上一代的鳥巢進行對比，如果較優，則更新當前最好鳥巢的位置和最優目標函數值。

步驟6用隨機游走的方式產生的新鳥巢代替位置較差的部分鳥巢，并計算被發現概率pa；每個新鳥巢產生一個隨機數r，服從[0,1]之間均勻分布，如果r大于被發現概率pa則返回步驟4，否則進入步驟7。

步驟7比較兩代鳥巢目標函數值，構建新Pareto最優解集，并計算每個鳥巢的目標函數值，更新最優鳥巢。

步驟8判斷當前迭代次數是否達到最大迭代次數Max_iter，若不符合則返回步驟4；否則終止算法，輸出Pareto解。

改進后的算法流程圖如圖3所示。

3 仿真實驗

3.1 算例描述

在新冠肺炎疫情的背景下以某地突發城市公共衛生事件為例，驗證本文提出的模型和設計的布谷鳥算法。假設突發事件后有12個患者需要應急手術，所有患者全部同時到達[21]，患者的傷勢人數比例為輕度患者50%、重度患者25%、危重患者25%?；颊叨夹枰来芜M行準備、手術和恢復3個手術流程，手術不同階段手術團隊的學習率分別取20%、15%和10%；患者惡化率取1.5%。其中，準備室有2個編號為m1、m2；手術室有5個，包括3個r1手術室編號為m3、m4、m5和2個r2手術室編號為m6、m7；恢復室有3個編號為m8、m9、m10。成本參數設置方面，文靜等[22]在急診檢查調度研究中考慮了患者的滯留成本，與本文的患者因長時間等候造成的惡化成本相似，因此將參數一致設置為ω=1/15,δ1=0,δ2=1,δ3=2。手術室能耗參數方面，于思文[23]在對手術排程研究中的手術室加班和空閑的懲罰系數的值是以Jebali[24]研究中的系數為標準，因此設定各手術室單位時間的空載能耗系數IE=1,手術室處于忙時單位時間的能耗系數PE=8[25]。手術時間具有不確定性的特點，同時考慮患者的不同分類，患者在每個手術流程的具體治療時間如表2所示。

表2 患者在每個手術室的治療時間Table 2 Treatment time of patients in each operating room 單位：min

3.2 結果及分析

多目標應急手術調度問題求解的運行環境為：操作系統為Windows10，處理器為Intel?CoreTMi5-5200U，主頻為2.20 GHz，內存為4 GB，采用MatlabR2018a編程實現。

根據應急手術調度的數學模型，將改進的布谷鳥算法與傳統的布谷鳥算法的運行結果進行對比。為了驗證算法的有效性，設置算法的總迭代次數為100，分別對兩組實驗獨立運行20次后取平均值，實驗結果具體如表3所示。從表3可以看出，與傳統的布谷鳥算法相比改進的布谷鳥算法對目標函數f1有15.51%的提升；對目標函數f2有30.72%的提升；對目標函數f3有15.52%的提升。這說明經過被發現概率自適應性調整的布谷鳥算法能夠很好地找到Pareto解，并避免陷入局部最優。

表3 20組Pareto最優解Table 3 20 Pareto optimal solutions

為了更清楚地看出改進布谷鳥算法的收斂速度，本文隨機選取表3中的第17次運行過程，繪制算法的收斂曲線圖。平均完成手術時間、患者惡化成本和手術室空載及忙時總能耗三個目標函數的迭代曲線具體如圖4所示。圖中橫坐標表示迭代次數，縱坐標表示各目標函數的變化值。

從圖4可以看出，隨機選取的第17次運行結果的最優目標值收斂曲線中改進的布谷鳥算法相比傳統布谷鳥算法，具有更快的收斂速度。

由此繪制的甘特圖如圖5所示，圖中橫坐標表示時間；縱坐標表示不同手術室，圖中不同顏色代表不同患者，并且每個患者應急手術不同階段的顏色是相同的。圖5中患者手術的三個階段在時間維度上基本首尾相接，說明患者的應急手術調度安排得比較緊湊，調度結果比較合理。

根據圖6可知，Pareto可行解的分布比較分散且均勻，能夠有效地跳出局部收斂狀態，說明被發現概率自適應性能夠使布谷鳥算法跳出局部最優，擴大搜索的范圍，有效更新鳥巢并保證種群的多樣性。

3.3 不同參數對手術調度的影響

手術團隊中各成員直接配合的默契程度以及醫生的職稱和經驗之間存在差異，會有不同的學習效應，學習率以20%、15%、10%為例，按照手術階段依次遞減規律，獨立運行改進的布谷鳥算法20次求平均值，以平均手術時間為例，結果如表4所示。由表4可知，隨著不同手術階段的學習率的遞減，平均手術時間并不是直線下降而是呈現跳躍的趨勢。

表4 不同學習率下的調度結果Table 4 Scheduling results under different learning rates

由于每批患者的惡化效應存在差異，會導致患者擁有不同的惡化效應，惡化率分別取0.5%、1.0%、1.5%、2.0%、2.5%、3.0%，獨立運行改進的布谷鳥算法20次求平均值，同樣以平均手術時間為例，結果如表5所示。由表5可知由于惡化率的存在，應急手術調度問題的所有患者平均完成手術的時間會比理論值小，并且惡化率越高，對手術調度的結果影響越大。

表5 不同惡化率下的調度結果Table 5 Scheduling results under different deterioration rates

4 結束語

應急手術的調度對患者傷勢的救治情況起著至關重要的作用。本文充分考慮手術治療的三個階段與三級置換流水車間相似的特點，將流水車間的思想運用到應急手術調度中，以最小化平均完成手術時間、患者惡化成本和手術室總能耗為目標，并同時考慮了患者的三級分類。在求解算法方面，對算法中被發現概率進行自適應性調整，通過對算法和模型的結果分析，驗證了改進布谷鳥算法的有效性。未來可進一步考慮突發事件不同階段的特征，針對性地探索手術資源及醫院資源多周期配置，進行動態手術調度研究。