基于成本效益分析的救護車多時段布局優化研究

蔣清宸， 蘇 強, 祝延宏， 王秋根

(1.同濟大學 經濟與管理學院,上海 200092; 2.上海市第一人民醫院，上海 200080)

0 引言

院前急救(Emergency medical service, EMS)是指緊急事故發生時，病患撥打急救電話，急救中心派遣救護車及相應設備人員到達現場進行醫療救護的過程[1]。院前急救作為城市醫療衛生體系和公共安全應急保障體系的重要組成部分，在維護市民健康和保障城市安全方面發揮重要的作用。世界衛生組織(WHO)的統計數據顯示，對危重病人實施急救的黃金時間是5分鐘，一旦超出10分鐘，病人的生還概率將顯著降低達80%以上，因此救護車對急救需求的響應時間十分關鍵。根據Lowthian等[2]的預測，到2020年隨著全球老齡化的趨勢加劇，對急救服務的需求將會上升46%～69%。這無疑對現有有限急救資源的優化管理提出了更緊迫的要求。

救護車布局對院前急救的效果與效率有著重要影響。對于救護車布局問題，可從規劃和運營兩個層面來考慮：(1)規劃層面的救護車布局問題常利用靜態模型對站點的選址以及車輛分配進行決策，以達到預期的覆蓋范圍、響應時間、急救資源數量等目標。(2)運營層面的救護車布局問題則進一步在動態環境中，考慮在需求、行駛速度、救護車的不可獲得性等不確定因素影響下救護車的布局。

盡管研究救護車配置布局問題的文獻眾多，但大多數研究集中于規劃層面，目標是最大化急救服務覆蓋范圍。本文屬于運營層面的研究，重點研究在時變環境下的救護車布局問題。同時考慮院前急救的服務水平及其經濟性指標。引入成本-效益分析，根據隨時間變化的需求、行駛速度以及救護車可獲得性，調整車輛規模與布局方案，在保證急救服務水平的基礎上，降低急救社會總成本。

本文在理論建模基礎上，應用2014年上海市松江區的急救數據進行實證分析，利用改進的蟻群算法計算分析了各種情況下的優化方案。結果表明在保證急救服務效果的前提下，優化后的系統比原系統的社會總成本下降32.23%；相比于靜態優化模型，考慮時變因素的模型可以使EMS社會總成本降低15.8%，同時能夠顯著提升各時段救護車輛的工作負荷平衡度。

1 文獻綜述

救護車布局問題的研究已經開展40多年，從研究角度可分為兩大類：靜態環境下救護車規劃層面的研究，和動態環境下救護車運營層面的研究。

早期的最具代表性的靜態環境下的救護車布局模型是Toregas等[3]提出的LSCM(Location set covering model)，該模型的優化目標是在覆蓋所有需求點的情況下最小化救護車的數量。另一個早期代表性模型是Church和ReVelle[9]提出的Maximal Covering Location Problem (MCLP)，是在給定的救護車資源限制下最大化需求覆蓋。在這些經典靜態研究基礎上，近期靜態環境下規劃層面的研究開始考慮多種需求類型(Liu等[4])、多種救護資源類型(Soo-Haeng等[5])、多階段救護(Liu和Yang[6])等因素對救護車布局的影響效果。

經典靜態模型沒有考慮救護車的不可獲得性及由此導致的某些需求點的偽覆蓋問題。為了來克服這一缺陷，Gendreau[10]提出了雙覆蓋模型(Double Standard Model, DSM)，使需求點被救護車多次覆蓋，當一輛救護車執行任務無法響應其他需求時，需求點仍有備選救護車可及時響應需求。DSM模型保證α%的需求量在高標準時間r1內被覆蓋，并且所有需求點在低標準時間r2內被救護車至少覆蓋一次(r1

一些研究已經開始在動態的環境中考慮救護車運營層面布局的問題。Repedeand J Bernardo[13]將Daskin[11]提出的Maximum Expected Covering Location Problem(MEXCLP)拓展成多時段的MEXCLP模型，以最大化各時間點的期望覆蓋范圍為目標函數，考慮了行駛時間、需求分布和救護車規模等隨時間變化因素的影響。Rajagopalan等[15]提出的在動態的需求環境中的多時段模型，進一步考慮了救護車可獲得性的不確定性。在滿足預設的救護車可獲得率的同時，最小化救護車數量。Schmid[16]提出了多時段的mDSM模型，考慮了行駛速度在時間和空間分布上的變化，最大化所有時段總的雙覆蓋范圍。該模強調行駛速度和再布局懲罰系數對各時段車輛布局和再布局的影響，但是忽略了需求在不同時段的變化。Pieter L等[7]對多時段的研究也主要關注行駛速度隨時間的變化，最大化期望覆蓋范圍的同時，最小化再布局車輛數，忽略了需求與車輛規模在不同時段的變化，可能導致在需求低的時段過度配置救護資源。

現有的動態環境中的研究，大多以最小化救護車數量或者最大化覆蓋范圍為目標優化車輛布局，難以在急救效果和救護資源的悖反中達到均衡。在考慮隨時間變化的因素上，許多研究并未同時考慮需求、行駛速度以及救護車可獲得率的影響。基于此，本文在雙覆蓋DSM模型的基礎上引入成本效益分析，在考慮需求、行駛速度以及救護車不可獲得率隨時間變化的影響下，分時段優化救護車布局。其余部分結構如下：第二節建立多時段的救護車優化布局模型，對院前急救系統進行成本效益分析；在第三節，根據多時段模型的特點設計了啟發式算法。第四節應用上海市松江區的實際數據，對提出的模型和算法進行實證分析。最后是結論與展望。

2 問題描述與建模

模型的目的是為所有的時間段t∈T(T={1,2,…,n}，在候選的救護車站點中決定站點配置的救護車數量，從而使救護車能在低標準時間r2內到達所有的需求點，并且保證α%(0<α<1)的需求量能被救護車在高標準時間r1(r1

模型中符號定義如下：

表1 符號定義

建立模型如下：

minf(x)=∑t∈T(CsttNstt+CamtNamt+

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

3 算法設計

上一部分建立的多時段救護車布局模型是一個NP-hard問題，難以在有限的時間和資源限制下得出精確解，因此本文設計了啟發式算法尋求該問題有效的近似最優解。在經典的蟻群算法的基礎上，根據多時段救護車布局模型的特點設計算法求解。

由于多時段模型的求解規模遠遠大于單一時段的求解規模，直接利用蟻群算法編碼多時段的解會使計算規模呈指數增長，可能降低解的精確性，因此本文結合貪婪算法的思想，利用蟻群算法尋求每一時段的最優解，再通過對時段循環迭代得到最優解。通過對比驗證，貪婪思想結合蟻群算法求解的結果明顯由于蟻群算法直接編碼的求解結果。算法具體設計如下。

蟻群算法應用在上述問題中時，每只螞蟻代表一個解，即一個救護車的布局方案，其搜索過程如下：在初始時刻，m只螞蟻被放置在起始救護車備選站點上，每只螞蟻隨機選擇該站點上的救護車數量。其次，螞蟻k(k=1,2,…,m)按照隨機比例選擇下一個救護車備選站點中停放的車輛數。救護車可能數量的信息矩陣的初始值是相同的，因此，初始的信息矩陣定義為μij(0)=μ0，其中i表示放置的救護車數量，j表示備選的救護車站點。螞蟻選擇站點中停放車輛的概率為：

式中，μij表示(i,j)上的信息素;ηij表示(i,j)上的啟發因子，其初始值相同；S表示備選站點的集合。

為了保證所有的救護車備選站點都被螞蟻訪問，采用禁忌表來記錄螞蟻k在每個備選站點上選擇的車輛數。每只螞蟻k代表一個車輛布局方案。當所有螞蟻完成搜索，即所有備選站點都選擇了相應的車輛數，計算每只螞蟻對應的方案所產生的社會總成本，并且保留m只螞蟻中成本最小的解。同時，更新(i,j)上的信息素。首先是信息素揮發，其次是螞蟻在它們所經過的邊(i,j)上釋放信息素。信息素更新公式如下:μij=(1-ρ)μij，式中，ρ表示信息素揮發系數(0<ρ≤1)。

式中，Ck表示螞蟻k的車輛布局方案所對應的EMS總成本。明顯地，EMS的成本越低，相應的(i,j)邊上獲得的信息素越多，則在以后的迭代中更有可能被其他的螞蟻選擇，形成一個正反饋機制。

m只螞蟻遍歷所有站點完成一次循環后，保留本次迭代中m只螞蟻中成本最小的解，清空禁忌表，重新回到初始站點，準備下一次迭代直到完成事先設定的迭代次數。算法流程如表2所示。

表2 改進蟻群算法流程

多時段的解是在每個時段不同的行駛速度、救護車可獲得率以及需求的數量及分布下的救護車的布局方案。在上述的蟻群算法的基礎上再嵌套一層時段t的循環，對于每一時段t，都重新初始化該時段對應的行駛速度，需求數量和空間分布以及救護車不可獲得率，分別求得時段t的最優布局方案，完成所有時段迭代后，計算所有時段的EMS社會總成本。

4 實證分析

4.1 數據描述

根據收集的上海市松江區2014年的急救數據，進行實證分析。松江區位于上海市西南部，總面積約605.64平方千米。首先，利用“網格法”將松江區劃分為144個需求點，每個需求點為2.5km×2.5km的單位網格。其次，對從上海市松江區120急救中心系統中導出的救護車數據進行初步篩選和清理，去除非急救出車等無效數據，得到2014年的松江區的總的急救需求數量為25941(分布如圖1所示)。再次，為了詳細刻畫一天中各時段需求量的變化、需求空間分布的變化以及行駛速度的變化，本文將一天均等劃為24個時段，每個時段時長1小時。按照劃分的時段將總需求量歸類，得到每個時段的需求量情況(如圖2所示)。最后，根據不同時段的每個具體需求位置的經緯度，將需求集合到劃分的單位網格中，得到每個時段需求的空間分布。因上海路網呈南北-東西走向，所以根據站點和需求點的經緯度，計算需求點和站點之間的直角邊距離，近似估算兩者之間的實際距離。

圖1 2014年上海市松江區急救需求與站點分布

實證中不同時段的行駛速度數據來源于上海市交通出行網，全時段的平均行駛速度為46.56km/h，其中早高峰7∶00到9∶00期間的平均行駛速度約為41.67km/h，晚高峰17∶00到19∶00的平均行駛速度為37.93km/h，具體情況如圖2所示。

圖2 各時段需求量與行駛速度

根據實地調研結果，對EMS社會總成本進行估算。平均每個急救站點的建設成本約150萬元，土地租金每年約10萬元，租期長為30年，據此折算每個急救站點的平均年運營成本Cst=150萬元/30+10萬元=15萬元。救護車的運營成本包括救護車的使用費用以及隨車人員的工資，其中車輛購置費用約為40萬元/輛(包括車載醫療設備費用)，平均使用年限為10年。每輛救護車配備5名工作人員，年薪約6元萬/人。此外救護車的維護費用以及油費每年約6萬元。因此救護車每年平均運營成本Cam=40萬元/10+6萬元×5+6萬元=40萬元。根據Su等[13]的研究，院前急救中普通病患呼叫比例為7.662%，嚴重病患呼叫比例為92.338%。通過查閱相關因急救延誤造成的司法案件，根據案件中的訴訟賠償金進行估算，嚴重病情的急救延誤損失成本為5000元/分鐘，普通病情的急救延誤損失成本為500元/分鐘。

根據2014年上海市松江區急救數據統計，松江區現有8個救護車站點，26輛救護車。設定每個站點車輛最大容量為3。由于目前中國沒有法律規定的急救覆蓋標準，因此根據《美國醫療急救服務法》中的規定，設置r1(α)為10分鐘(80%)，r2為20分鐘。

4.2 結果分析

利用第四部分設計的啟發式算法求解模型，在保證所有需求點在低標準時間r2內被覆蓋，80%的需求在高標準時間r1內被覆蓋的條件下，尋求使EMS的社會總成本最小化的車輛布局方案。求解結果如表3所示。總成本指在各個時段上EMS一年的社會總成本，包括延誤成本和運營成本兩個部分。雙覆蓋率指被高標準r1覆蓋兩次及其以上的比例，即能被救護車在10分鐘內多次響應的需求比例。單覆蓋率指被高標準r1覆蓋一次的比例，車輛數指每個時段的救護車布局方案中所有站點停放的車輛總數。繁忙率根據Soo-Haeng[5]提出的實際繁忙率計算方法，通過總需求、車輛數和平均出車時間進行估算(需求*平均出車時間/車輛數)，用以衡量救護車的閑忙程度。根據結果，可以發現EMS的社會總成本在9∶00～10∶00以及19∶00時達到峰值，這是由于在這兩個時間點，急救需求的數量較大，并且位于早晚高峰時期行駛速度較慢，所以導致難以及時響應需求，延誤成本增加。這兩個時段救護車的繁忙率大約處于0.2到0.3左右，工作負荷量并不大，因此即使再增加救護車數量只會導致運營成本的增加速度大于延誤成本的減少速度從而使總成本增加。而在0∶00～7∶00時段，急救需求較少且行駛速度較快，因此未能及時響應導致的延誤成本小，救護車布局數量相應減少使運營成本較小，從而使EMS的總成本較小。此外，根據結果可以得到急救網絡的平均雙覆蓋率達到75.71%，平均一次覆蓋率達到88.75%高于設定的80%的服務水平。各個時段的繁忙率比較平均，位于0.2～0.3之間，可見根據需求和行駛速度隨時間的變化，調整車輛規模可以平衡各時段救護車的工作負荷。

表3 模型結果

根據表4，優化后的系統總成本比原系統下降了32.23%，雖然從表面上看原系統的雙覆蓋率高于優化后的系統，但兩者的延誤成本基本持平，說明原系統過高保證了雙覆蓋率，造成救護資源的浪費和冗余，優化后的系統在保證院前急救服務水平和急救效果的情況下減少了車輛資源，提高了EMS的效率。

表4 原系統與優化系統對比

4.3 實際應用分析

上文中根據每小時需求和速度的變化得到的布局方案，再布局調整太過頻繁，在實際中難以應用。考慮到急救服務系統管理的便捷性和調度的可操作性，本節將對得到的車輛布局方案進行分析，確定合適的再布局時間點以及調度方案，從而即方便EMS網絡的管理又有效地降低EMS社會總成本，提高效率。

根據急救調度中心的實際情況，一天24小時內安排3個調度班次，每班工作時長8小時。通過計算各個時段的布局方案之間的歐式距離刻畫方案間的差異性，布局方案的差異越小則再調度調整越少，時段間的需求規模、分布和行駛速度也越相近，則更適合整合成同一調度班次。根據實際排排班要求和布局方案差異的分析，確定時段8、16以及24分別為再布局時間點，一天被均勻地劃分為8小時的三個調度班次。再根據重新劃分的時段的需求和行駛速度，得到新的調度方案(如表5所示)。新的調度方案中，第二和第三個調度班次布局相同，因此實際中只用在7點時進行重新布局調度。基于新劃分的時段的需求和速度數據，分別根據各時段優化后的調度方案和原系統的車輛布局方案計算EMS總成本，原系統和優化后的結果如表6所示。優化后的系統總成本比原系統下降了29.03%，雖然從表面上看原系統的多次覆蓋率高于優化后的系統，但兩者的延誤成本相差較小，說明原系統過高保證了多次覆蓋率，造成救護資源的浪費和冗余，優化后的系統在保證院前急救服務水平的情況下減少了車輛資源，提高了EMS的效率。

表5 車輛布局方案

表6 原系統與新的優化系統對比

4.4 多時段模型與靜態模型對比

為了說明考慮需求和行駛速度隨時間變化的重要性，下文將對多時段模型和靜態模型進行對比。利用蟻群算法求解靜態的模型，基于平均行駛速度和各時段總需求量及分布的數據，得到車輛布局方案，再將該方案帶入各時段實際環境中，計算EMS社會總成本及相關結果。靜態模型和多時段模型在各個時段的成本及覆蓋率對比如圖3所示。除了在時段8和23總成本持平外，其他時段中多時段模型的總成本明顯低于靜態模型的總成本。多時段模型的雙覆蓋率在24和時段1到7低于靜態模型的雙覆蓋率，而在其他時段均高于。從整體上來看(見表7)，靜態模型的年總成本約為1500萬元，而多時段模型的年總成本為1263萬元，考慮需求和速度隨時間的變化使EMS的成本下降了15.8%。靜態模型的雙覆蓋率為62.87%，多時段模型的雙覆蓋率為75.71%，提升了12.84%。此外，靜態模型的繁忙率的方差為0.011561，而多時段模型的0.000962，下降了91.68%，說明靜態模型中救護車的工作負荷不均衡，而多時段模型顯著平衡了車輛的工作負荷。

圖3 多時段模型與靜態模型各時段對比

4.5 算法分析

上文中的實例分析應用了第四章中設計的啟發式算法求解。為了驗證改進后算法的有效性，本節將分別利用設計的啟發式算法、改進前蟻群算法以及CPLEX對多個規模的樣本進行求解。在4、8、23個站點的情境下求解，對比結果如表8所示。

對于4個站點的情況，CPLEX給出了精確解。然而CPLEX在10小時內得出的優化結果僅比改進的算法在5分鐘得到的結果高0.23%。對于8個站點和23個站點的情況，CPLEX在10小時內未找到最優解。

本文設計的算法是將蟻群算法結合貪婪算法的思想，針對多時段模型的特點，分階段對解進行編碼(詳見第四章)，而改進前的蟻群算法指直接利用蟻群算法對多時段模型進行編碼。三種站點規模的測試中，改進前后算法參數設置一致：螞蟻數m=50，迭代次數N=100，信息揮發系數為p=0.15，α=0.1，β=2.5。結果表明雖然改進后的蟻群+貪婪算法運算時間較改進前蟻群算法的時間長，但在可接受范圍內，并且改進后算法的優化結果分別比改進前高出5.16%、9.77%和18.48%，提高了求解結果的精確度。

表8 算法分析對比

5 結論

本文提出了多時段的成本效益DSM模型，考慮了需求數量、需求空間分布、行駛速度以及救護車不可獲得率等因素隨時間的變化。在保證一定服務水平的條件下，最小化所有時段社會總成本。模型根據需求規模變化配置相應車輛規模，以平衡各時段工作負荷。根據需求空間分布、行駛速度和救護車不可獲得率變化動態調整救護車布局方案，從而保證急救服務水平，降低EMS社會總成本。

利用上海市松江區2014年的急救數據，本文進行了實證分析。優化后的系統在保證80%的高標準覆蓋水平下，社會總成本比原系統下降了32.23%。優化后的系統與原系統的延誤成本基本持平，說明兩者的急救服務效果相同，而優化后的系統減少了急救資源數量，因此降低了社會總成本。為了使布局方案在實際運營中具有可操作性，避免每小時頻繁的調動與再布局，本文分析各時段布局方案的差異性，將一天劃分為三個時段，每時段時長8小時，確定再布局時間點為7∶00，并得到相應布局方案。與原系統相比，重新制定的布局方案使系統的社會總成本下降了29.03%。

通過多時段模型與靜態模型的對比，驗證了考慮隨時間變化的不確定性因素的重要性。由于多時段中考慮了需求、行駛速度及救護車不可獲得率隨時間的變化，多時段模型的EMS的總成本比靜態模型的總成本下降了15.8%，并且雙覆蓋率提高了12.84%。此外，相比靜態模型，多時段模型顯著降低了各時段救護車繁忙率的方差，有效平衡了車輛工作負荷。

本文針對多時段模型的特點，基于蟻群算法和貪婪算法思想，提出了一種改進的啟發式算法。在不同站點規模下的測試結果表明，相比CPLEX和原始的蟻群算法該算法在運行速度和精確度上表現良好。

本文的研究雖然在動態環境中研究EMS布局問題，但由于數據收集的限制，沒有考慮行駛速度在各時段空間分布上的變化，即只考慮行駛速度在各時段上的平均速度。根據Schmid[16]的研究，考慮行駛速度在空間上的不確定性可使覆蓋范圍提高10%。此外，本文的模型是單階段的，即只考慮了救護車到急救病人的過程，而沒有考慮將病患送往醫院的過程。Soo-Haeng[5], Liu和Yang[6]的研究均表明考慮兩階段對救護車布局問題的重要性，以后的研究中，可進一步分析。