面向時變復雜環境的救護車布置和重定位

虎慧澤,楊之濤,陳爾真,劉 冉

(1.上海交通大學 機械與動力工程學院，上海 200240；2.上海交通大學醫學院附屬瑞金醫院 急診科，上海 200025)

院前急救是現代急救醫療服務體系的重要組成部分，緊急病人的存活率在很大程度上取決于緊急呼叫發出至救護車到達需求現場的時間.因此，救護車車站的選址以及救護車的部署對于院前急救非常重要.

傳統的救護車車站選址和車輛部署通常針對靜態的人口分布，選擇若干位置點作為救護車車站并確定布置于每個車站的救護車數量.但是，我國的大型城市(如上海、北京)具有較大的人口數量且一天內人口的空間分布隨時間變化而變化，因而一個區域內潛在的緊急醫療需求量亦呈動態變化.此外，由于救護車在不同區域內的行駛速度并非為固定值，救護車的部署應具備動態變化的特征.因此，需要合理地布置和分配救護車，并對救護車加以動態時變定位，以適應于因城市人口時變分布而導致的復雜的院前急救狀況.

早期救護車車站選址和車輛部署方法主要有3類：① 根據救護車數量構建模型.如：Toregas等[1]提出的救護車選址模型，期望最小化覆蓋所有需求點的救護車的數量.② 根據救護車的覆蓋率構建模型.如：喬聯寶等[2]提出了基于排隊模型的最大覆蓋選址問題；Zarandi等[3]使用啟發式方法求解動態最大覆蓋選址模型.③ 根據實際情況確定救護車車站位置構建模型.如：Mccormack等[4]使用具有集成仿真模型的遺傳算法選擇救護車的車站位置；Leknes等[5]提出了一種新的適用于多樣化需求的混合整數規劃模型.

然而，隨著城市規模的發展，靜態模型已無法滿足人口及緊急醫療動態變化的實際需求.因此，一些救護車在不同車站之間重定位的動態模型應運而生：① 混合整數規劃模型.Gendreau等[6]將雙標準模型(DSM)進行擴展，提出了基于救護車重定位的動態雙標準模型(DDSM).② 隨機優化模型.Lam等[7]提出對救護車進行實時重定位的隨機優化模型，Naoum-Sawaya等[8]構建了救護車重新部署的隨機優化模型.③ 馬爾可夫模型.Ramon等[9]構建了緊急醫療服務系統的馬爾可夫模型，并使用合規表策略重定位救護車.④ 仿真模型.Zhen等[10]提出了針對復雜環境的救護車部署仿真模型，在此基礎上提出了救護車重定位的數學模型，并通過數值實驗驗證了所提方法的有效性.

本文針對特大城市院前醫療急救系統，考慮時變的人口分布、車輛行駛速度以及救護車在不同車站之間的調度成本和救護車的維護成本，構建救護車車站選址和部署模型.設計遺傳算法和貪婪算法，采用標準計算工具CPLEX對所構建模型進行求解.通過數值實驗驗證了救護車動態分配對院前急救管理的有效性以及所設計的遺傳算法對于模型求解的準確性和時效性.

1 問題描述與數學建模

首先對時變系統中救護車的布置和重定位問題進行描述.

設定歐式有向圖G=(W∪V，A)，其中：W為所有備選車站點的集合；V為所有需求點的集合，V中各元素(需求點)表示地理上靠近的一定數量的人口；A={(j,i)}(j∈W，i∈V)為歐式圖的弧集.

定義1個計劃時間周期為T，其中包含T個時間段，若每個時間段的時長為t0，則 T=T/t0.120調度中心在接到緊急呼叫后，如果至少有1輛救護車可以在時間閾值r1(r2)內到達緊急呼叫發生的需求點i，則認為此需求點可以在時間r1(r2)內被救護車覆蓋.定義時間段t(t=1,2,…,T)內：需求點i的需求量為dit，對應該時段發生的緊急醫療呼叫數目；車站j發出的救護車到達需求點i的行駛時間為tij；在時間閾值r1(r2)內能夠覆蓋需求點i的所有備選車站的集合為W1it或W2it；在時間閾值r2內被備選車站j覆蓋的所有需求點的集合為V2jt.

定義每輛救護車的最大服務能力為覆蓋ω個需求點的需求量.時段t內，所有車站允許停放的救護車總數為ct并且車站j停放的救護車數量不超過pjt.為了限制總成本，允許開啟的車站數量不能超過s.為了提高緊急醫療服務的服務質量，所有需求量在時間r2內可以被救護車覆蓋，同時占總需求量比例為α(0<α<1)的需求量在時間r1內被救護車覆蓋.為了實現此覆蓋需求，首先需要確定每個備選車站是否開啟、對應布置的車輛數以及在不同時間段和不同車站之間轉移的車輛數(救護車在車站之間重定位).模型中設定M為任意大的整數，k為只取1和2的常數.

系統的總成本包括開啟車站的固定成本和救護車在不同車站之間重定位的成本兩部分.開啟1個車站的成本(β1)與車站的維護、車輛的保養等費用相關.1輛救護車在不同車站之間的重定位成本與重定位路途行駛的時間、重定位的兩個車站之間的距離、車輛類型、重定位所處的時間段等諸多現實因素有關.為了簡化計算，設定1輛救護車在不同車站之間重定位的成本為β2.本文研究目標：①最大化時間r1內被救護車覆蓋兩次的需求點；②最小化β1和β2.引入以下決策變量：

x2it(x1it)—時間段t內，需求點i在時間閾值r1內被救護車覆蓋2次(1次)為1，否則為0；

rjj′t—在時間段t至時間段(t+1)內，從車站j調度到備選車站j′的救護車數量；

rijT—時間段t=T(最后1個時段)至時間段t=1內，從車站i調度到車站j的救護車數量；

zj—如果車站j有車輛停放為1，否則為0；

bijt—時間段t內，車站j實際能夠覆蓋的需求點i的需求量；

yjt—時間段t內，車站j停放的救護車的數量.

數學模型為

式(1)為目標函數；式(2)表示在時段t中，需求點i在時間閾值r2內至少要被救護車覆蓋1次；式(3)表示在時段t中，至少有占總需求量的比例為α的需求量在時間r1內被救護車覆蓋1次；如果有足夠的救護車位于需求點i周圍，式(4)和(5)確保需求點i只能被覆蓋1次或者2次；式(6)和(7)對救護車的停放數量進行約束；式(8)和(9)表示經歷救護車的重定位后車站j在時間段t與(t+1)內的救護車數量保持平衡；式(10)和(11)是對開啟車站數量的約束；式(12)表示時段t中，時間r2內車站j實際覆蓋的所有需求點的需求量之和不多于車站j的覆蓋容量；式(13)表示時段t中，所有在時間r2內覆蓋需求點i的車站實際覆蓋的需求量之和嚴格等于dit；約束條件式(12)和(13)保證了高緊急呼叫區域被足夠多的救護車所覆蓋.

由于現實系統中車站和車輛數目較大且交通情況多變，通過CPLEX等軟件求解上述模型發現，很多算例不僅難以得到最優解，甚至無法保證能夠得到1個可行解.為了更好地解決實際問題，本研究將約束條件式(2)，(3)和(13)進行松弛，得到如下的擴展問題模型：

β4f2t(x)+β5f3t(x)]

(17)

s.t.式(4)～(12)以及式(14)～(16)

式中：β3、β4和β5是松弛約束的懲罰系數；

t=1，2，…，T

x+={0,x}

2 求解算法

上述模型較為復雜，筆者嘗試采用混合整數規劃求解軟件(例如CPLEX 12.7)對模型進行求解，但運算24 h后無法得到高質量的計算結果.然而，急救系統需要在短時間內得到救護車重定位的方案，因此本文設計了一種高效遺傳算法來求解上述問題.算法首先產生一個初始種群，對種群中的個體按照適應度從大到小排序，通過輪盤賭法選擇2個個體進行交叉、變異和局域搜索操作；新產生的個體代替部分原有種群的個體并繼續上述操作；迭代一定次數后算法結束并輸出種群中的最優個體作為最后求解結果.圖1所示為遺傳算法的流程圖.

2.1 染色體編碼與初始種群生成

2.1.1編碼 編碼是問題的一個解在遺傳算法中的表現形式.本文遺傳算法的每一條染色體有|W|×T個基因位置.每個基因位置表示時間段t內備選車站j處的救護車輛的數量.圖2顯示了T=2,|W|=5時一個染色體的編碼結構以及每個位置的編碼所對應的實際意義.例如t=1時段車站1布置了3輛救護車，對應圖中染色體的第1個位置的數值為3.

2.1.2初始種群生成 首先生成全部車站的隨機序列并執行以下操作步驟，完成1個遺傳算法染色體的構造：

圖1 遺傳算法流程圖Fig.1 Genetic algorithm flow chart

圖2 染色體編碼方式Fig.2 Chromosome coding

(2)判斷本時段已經布置的車輛總數是否小于本時段可用的救護車數ct，如果條件不滿足，本時段內后續車站布置的車輛數為0；否則轉步驟(3).

(4)判定車站j是否為t時段的最后1個車站，如果是，則終止操作，重新從本時段第1個車站開始布置車輛；如果不是，則布置車輛數為0和vjt內的一個隨機數，繼續處理下一個車站，轉步驟(1).

圖3 初始解的產生過程Fig.3 Process of the initial solution generation

2.1.3個體適應度評估 遺傳算法需要對每條染色體進行適應度評估.本算法將對應每個染色體目標函數的數值結果設定為染色體的適應度，該數值越大，對應的個體越優秀.

對每個染色體必須求解得到bjit才可得到其適應度，本文使用貪婪算法求解bjit.首先，將全部車站按照其在r2內能夠覆蓋需求量的大小進行排序，并生成全部需求點的隨機序列.令：li t為在時間段t內需求點i的剩余需求量；ejt為時間段t內車站j的剩余可覆蓋容量.

貪婪算法過程描述如下：

(1)lit=dit，ejt=ωyjt(i∈V,j∈W,t=1,2,…,T).

(2)t=1.

(3)判斷ejt>0是否成立，若成立則轉(5).

(4)j=j+1,轉(3).

(5)i=1.

(6)判斷lit>0是否成立，若成立則轉(8).

(7)i=i+1,轉(6).

(8)判斷tij

(9)判斷ejt≥lit是否成立，若成立則

ejt=ejt-lit,lit=0

轉(7);否則

lit=lit-ejt,ejt=0

轉(4).

(10)t=t+1,判斷t≤T是否成立，若成立轉(3);否則結束.

圖4舉例說明貪婪算法求解變量的過程.圖中方框內、外的數字分別為備選車站編號和救護車數量.圓圈內、外的數字分別為需求點編號以及需求點的需求量.1輛救護車可覆蓋的需求量為30.圖4(b)為車站2的覆蓋過程，車站按照1、2和3的次序依次覆蓋需求點，因此需求點1和2被完全覆蓋，需求點3被部分覆蓋，實線和虛線分別表示車站對需求點的需求量為完全覆蓋以及不完全覆蓋.完成此步驟后剩余總需求量為9.圖4(c)中需求點1、2和4均被1個車站所覆蓋，而需求點3被2個車站(1和2)的救護車覆蓋.

圖4 貪婪算法過程Fig.4 Process of the greedy algorithm

圖5 染色體的交叉Fig.5 The crossover of chromosome

2.2 交叉

交叉是遺傳算法中的重要組成部分.時段t中，兩個個體交叉的次數為|W|/2，交叉規則如下：

(1)在0～|W|之間隨機產生兩個不同的交叉點m和n，分別指向個體i和j的第m和n個車站；假定兩個個體中交叉點的車輛數(即對應的基因數)為im1,in1和jm1,jn1，交叉后的車輛數分別為im2,in2和jm2,jn2.

(2)判斷個體i在交叉點m處的im1和個體j在交叉點n處的jn1是否為0.若為0，則交叉點處的數值不發生改變.

(3)若im1≠0，個體i在交叉點m處發生交叉.交叉后得到的染色體i在交叉點m處的基因值為im2=(im1+in1)im1/(im1+jm1).

(4)個體i在交叉點n處的基因值為in2=(im1+in1)-im2.

(5)若jn1≠0，個體j在交叉點n處發生交叉，jn2=(jm1+jn1)jn1/(in1+jn1).

(6)個體j在交叉點m處的基因值為jm2=(jm1+jn1)-jn2.

(7)判斷個體i和j的交叉位的基因值是否超過上限，若超過，取消交叉操作.

(8)重復進行交叉，直到此時段的交叉次數達到|W|/2.

圖5展示了T=2，|W|=5時個體在交叉前后的對比，交叉點為車站2和3.對個體i的交叉點2進行交叉操作，交叉后個體i在交叉點2的基因值為(1+0)×1/(1+3)=0(此外為取整操作)，在交叉點3的基因值為 (1+0)-0=1.

2.3 變異

在算法中，個體i在時間段t內的變異概率為Pm.變異規則如下：隨機產生兩個變異點a和b

u=rand(0,rand(a,b))

其中:rand(a,b)表示在a和b之間產生的隨機數.變異點a和b中車輛較多的點將遷移u輛車至車輛較少的變異點.如果變異后變異點的車輛數為負值或者超過停放上限，則變異失敗，取消變異操作.圖6所示為T=2，|W|=5時個體i的變異.變異點a=1，b=3，u=1.變異后車站1的基因值為3，車站3的基因值為2.

圖6 染色體的變異Fig.6 The mutation of chromosome

2.4 局域搜索和種群更新

遺傳算法產生新個體后，對每個新個體依次在時間段t內執行如下操作，完成個體的局域搜索：抽取兩個不同車站i和j并保證車站i非空；將車站i的救護車轉移至車站j直至車站j的容量達到其布置救護車的容量上限；完成車站i與j之間的車輛轉移，對此局域搜索得到的個體進行適應度評估，如果適應度增大，則此次局域搜索結果被接受，產生新個體，否則終止局域搜索.

圖7為T=2,|W|=5時2個車站的1次局域搜索過程，設定車站的最大容量為3.嘗試將第1個車站的車輛調往第2個車站，得到新個體.對新個體進行適應度評估，如果適應度大于原個體，則替代原個體，否則保留原個體，繼續進行局域搜索，直到得到車輛在車站之間的最優布置，停止搜索.

產生的新個體代替原種群個體的方法描述如下：在[0，λ]中隨機產生兩個數h和o，其中λ為種群中的個體總量，經過局域搜索后的新個體代替h和o所對應的個體.

圖7 個體局域搜索Fig.7 The process of local search

3 數值實驗

通過數值實驗對面向時變需求的救護車車站選址與重定位問題的遺傳算法進行性能評估.本文所有計算程序均使用 C++語言編寫，數值實驗全部在配有Intel E5-2670 2.6 GHz處理器和2 GB內存的計算機上進行，操作系統為Linux.

3.1 數據生成

在2 km×2 km的矩形區域中隨機生成需求點和潛在車站的坐標，分別產生16、51、94和163個備選車站位置.每個備選車站分別產生1個小規模和1個大規模算例，大、小算例分別包含200和500個需求點.將1天分為6個時間段，如果前3個時間段需求點的橫坐標小于0.5，則每個時段的需求量分別在3個區間[272，1 122]，[856，1 360]和[1 020，1 234]中隨機產生，否則在[68，340]，[214，1 360]和[255，305]中隨機產生.如果后3個時段需求點的橫坐標小于0.5，則需求量分別在[251，351]，[287，312]和[117，196]中隨機產生，否則在[1 004，1 406]，[1 150，1 250]和[470，784]中隨機產生.使用歐式距離公式計算車站與需求點的距離.設置救護車的平均行駛速度為38 km/h，不同時段內救護車的行駛速度在平均行駛速度的75%～125%之間變化.

將遺傳算法命名為“GA-Local Search”，最大迭代次數設置為100，Pm設置為0.7.采用基于貪婪思想的求解算法Greedy Algorithm(GA)與遺傳算法進行對比.GA算法中，首先用 2.1.2 節方法生成30個初始解，再利用 2.1.3 節所述貪婪算法求解得到30個初始解對應的bijt，從而得到每個初始解的求解結果，抽取最好個體作為GA算法的求解結果.

3.2 結果及分析

數值實驗結果見表1和2.其中F1max、F2max和F3max分別為由 CPLEX、貪婪算法以及遺傳算法得到的解；tc、tg以及ta分別為3種算法的計算時間；rc、rg和ra分別為3種算法的重定位車輛總數；Gap定義為(F3max-F2max)/F2max.

表1 小規模算例結果Tab.1 Computational results of small scale instance

表2 大規模算例結果Tab.2 Computational results of small large instance

可以看出，在|W|、r1和α相同的情況下，r2越大，目標函數值越大；總需求量、r1、r2和α相同的情況下，|W|越大，目標函數值越大，在時間r1內被救護車覆蓋2次的需求量越大.比較遺傳算法和CPLEX發現，CPLEX的結果雖然優于算法的結果，但是個體之間的差異不大，同時，遺傳算法在求解時間上明顯優于CPLEX，如表1中的算例，CPLEX的計算時間最長達到了12 h.比較遺傳算法和貪婪算法的結果發現，遺傳算法的求解精度優于貪婪算法，但是在求解時間上，貪婪算法更有優勢，這是由貪婪算法的特性決定的.綜上所述，雖然遺傳算法求解問題的時間相對貪婪算法較長，求解精度稍遜于CPLEX，但對于求解實際問題，所需時間仍在合理計算時間范圍內，而且其精度與CPLEX相差較小，對現實問題更具有實用性.

4 結語

針對時變系統中的救護車布置與重定位問題進行了研究，建立了混合整數規劃模型.由于使用標準計算軟件進行計算的時間過長，精度過低，本文設計了一種遺傳算法并生成相關的算例，進而對算法的合理性和科學性進行評估.結果表明，遺傳算法的求解時間可控制在合理范圍內，求解精度較高，為時變系統內的救護車布置和重定位提供了新的思路和方法.