面向時(shí)變復(fù)雜環(huán)境的救護(hù)車布置和重定位

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

(1.上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，上海 200240；2.上海交通大學(xué)醫(yī)學(xué)院附屬瑞金醫(yī)院 急診科，上海 200025)

院前急救是現(xiàn)代急救醫(yī)療服務(wù)體系的重要組成部分，緊急病人的存活率在很大程度上取決于緊急呼叫發(fā)出至救護(hù)車到達(dá)需求現(xiàn)場(chǎng)的時(shí)間.因此，救護(hù)車車站的選址以及救護(hù)車的部署對(duì)于院前急救非常重要.

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

早期救護(hù)車車站選址和車輛部署方法主要有3類：① 根據(jù)救護(hù)車數(shù)量構(gòu)建模型.如：Toregas等[1]提出的救護(hù)車選址模型，期望最小化覆蓋所有需求點(diǎn)的救護(hù)車的數(shù)量.② 根據(jù)救護(hù)車的覆蓋率構(gòu)建模型.如：?jiǎn)搪?lián)寶等[2]提出了基于排隊(duì)模型的最大覆蓋選址問(wèn)題；Zarandi等[3]使用啟發(fā)式方法求解動(dòng)態(tài)最大覆蓋選址模型.③ 根據(jù)實(shí)際情況確定救護(hù)車車站位置構(gòu)建模型.如：Mccormack等[4]使用具有集成仿真模型的遺傳算法選擇救護(hù)車的車站位置；Leknes等[5]提出了一種新的適用于多樣化需求的混合整數(shù)規(guī)劃模型.

然而，隨著城市規(guī)模的發(fā)展，靜態(tài)模型已無(wú)法滿足人口及緊急醫(yī)療動(dòng)態(tài)變化的實(shí)際需求.因此，一些救護(hù)車在不同車站之間重定位的動(dòng)態(tài)模型應(yīng)運(yùn)而生：① 混合整數(shù)規(guī)劃模型.Gendreau等[6]將雙標(biāo)準(zhǔn)模型(DSM)進(jìn)行擴(kuò)展，提出了基于救護(hù)車重定位的動(dòng)態(tài)雙標(biāo)準(zhǔn)模型(DDSM).② 隨機(jī)優(yōu)化模型.Lam等[7]提出對(duì)救護(hù)車進(jìn)行實(shí)時(shí)重定位的隨機(jī)優(yōu)化模型，Naoum-Sawaya等[8]構(gòu)建了救護(hù)車重新部署的隨機(jī)優(yōu)化模型.③ 馬爾可夫模型.Ramon等[9]構(gòu)建了緊急醫(yī)療服務(wù)系統(tǒng)的馬爾可夫模型，并使用合規(guī)表策略重定位救護(hù)車.④ 仿真模型.Zhen等[10]提出了針對(duì)復(fù)雜環(huán)境的救護(hù)車部署仿真模型，在此基礎(chǔ)上提出了救護(hù)車重定位的數(shù)學(xué)模型，并通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證了所提方法的有效性.

本文針對(duì)特大城市院前醫(yī)療急救系統(tǒng)，考慮時(shí)變的人口分布、車輛行駛速度以及救護(hù)車在不同車站之間的調(diào)度成本和救護(hù)車的維護(hù)成本，構(gòu)建救護(hù)車車站選址和部署模型.設(shè)計(jì)遺傳算法和貪婪算法，采用標(biāo)準(zhǔn)計(jì)算工具CPLEX對(duì)所構(gòu)建模型進(jìn)行求解.通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證了救護(hù)車動(dòng)態(tài)分配對(duì)院前急救管理的有效性以及所設(shè)計(jì)的遺傳算法對(duì)于模型求解的準(zhǔn)確性和時(shí)效性.

1 問(wèn)題描述與數(shù)學(xué)建模

首先對(duì)時(shí)變系統(tǒng)中救護(hù)車的布置和重定位問(wèn)題進(jìn)行描述.

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

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

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

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

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

rjj′t—在時(shí)間段t至?xí)r間段(t+1)內(nèi)，從車站j調(diào)度到備選車站j′的救護(hù)車數(shù)量；

rijT—時(shí)間段t=T(最后1個(gè)時(shí)段)至?xí)r間段t=1內(nèi)，從車站i調(diào)度到車站j的救護(hù)車數(shù)量；

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

bijt—時(shí)間段t內(nèi)，車站j實(shí)際能夠覆蓋的需求點(diǎn)i的需求量；

yjt—時(shí)間段t內(nèi)，車站j停放的救護(hù)車的數(shù)量.

數(shù)學(xué)模型為

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

由于現(xiàn)實(shí)系統(tǒng)中車站和車輛數(shù)目較大且交通情況多變，通過(guò)CPLEX等軟件求解上述模型發(fā)現(xiàn)，很多算例不僅難以得到最優(yōu)解，甚至無(wú)法保證能夠得到1個(gè)可行解.為了更好地解決實(shí)際問(wèn)題，本研究將約束條件式(2)，(3)和(13)進(jìn)行松弛，得到如下的擴(kuò)展問(wèn)題模型：

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

(17)

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

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

t=1，2，…，T

x+={0,x}

2 求解算法

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

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

2.1.1編碼 編碼是問(wèn)題的一個(gè)解在遺傳算法中的表現(xiàn)形式.本文遺傳算法的每一條染色體有|W|×T個(gè)基因位置.每個(gè)基因位置表示時(shí)間段t內(nèi)備選車站j處的救護(hù)車輛的數(shù)量.圖2顯示了T=2,|W|=5時(shí)一個(gè)染色體的編碼結(jié)構(gòu)以及每個(gè)位置的編碼所對(duì)應(yīng)的實(shí)際意義.例如t=1時(shí)段車站1布置了3輛救護(hù)車，對(duì)應(yīng)圖中染色體的第1個(gè)位置的數(shù)值為3.

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

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

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

(2)判斷本時(shí)段已經(jīng)布置的車輛總數(shù)是否小于本時(shí)段可用的救護(hù)車數(shù)ct，如果條件不滿足，本時(shí)段內(nèi)后續(xù)車站布置的車輛數(shù)為0；否則轉(zhuǎn)步驟(3).

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

圖3 初始解的產(chǎn)生過(guò)程Fig.3 Process of the initial solution generation

2.1.3個(gè)體適應(yīng)度評(píng)估 遺傳算法需要對(duì)每條染色體進(jìn)行適應(yīng)度評(píng)估.本算法將對(duì)應(yīng)每個(gè)染色體目標(biāo)函數(shù)的數(shù)值結(jié)果設(shè)定為染色體的適應(yīng)度，該數(shù)值越大，對(duì)應(yīng)的個(gè)體越優(yōu)秀.

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

貪婪算法過(guò)程描述如下：

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

(2)t=1.

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

(4)j=j+1,轉(zhuǎn)(3).

(5)i=1.

(6)判斷l(xiāng)it>0是否成立，若成立則轉(zhuǎn)(8).

(7)i=i+1,轉(zhuǎn)(6).

(8)判斷tij

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

ejt=ejt-lit,lit=0

轉(zhuǎn)(7);否則

lit=lit-ejt,ejt=0

轉(zhuǎn)(4).

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

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

圖4 貪婪算法過(guò)程Fig.4 Process of the greedy algorithm

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

2.2 交叉

交叉是遺傳算法中的重要組成部分.時(shí)段t中，兩個(gè)個(gè)體交叉的次數(shù)為|W|/2，交叉規(guī)則如下：

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

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

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

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

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

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

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

(8)重復(fù)進(jìn)行交叉，直到此時(shí)段的交叉次數(shù)達(dá)到|W|/2.

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

2.3 變異

在算法中，個(gè)體i在時(shí)間段t內(nèi)的變異概率為Pm.變異規(guī)則如下：隨機(jī)產(chǎn)生兩個(gè)變異點(diǎn)a和b

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

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

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

2.4 局域搜索和種群更新

遺傳算法產(chǎn)生新個(gè)體后，對(duì)每個(gè)新個(gè)體依次在時(shí)間段t內(nèi)執(zhí)行如下操作，完成個(gè)體的局域搜索：抽取兩個(gè)不同車站i和j并保證車站i非空；將車站i的救護(hù)車轉(zhuǎn)移至車站j直至車站j的容量達(dá)到其布置救護(hù)車的容量上限；完成車站i與j之間的車輛轉(zhuǎn)移，對(duì)此局域搜索得到的個(gè)體進(jìn)行適應(yīng)度評(píng)估，如果適應(yīng)度增大，則此次局域搜索結(jié)果被接受，產(chǎn)生新個(gè)體，否則終止局域搜索.

圖7為T=2,|W|=5時(shí)2個(gè)車站的1次局域搜索過(guò)程，設(shè)定車站的最大容量為3.嘗試將第1個(gè)車站的車輛調(diào)往第2個(gè)車站，得到新個(gè)體.對(duì)新個(gè)體進(jìn)行適應(yīng)度評(píng)估，如果適應(yīng)度大于原個(gè)體，則替代原個(gè)體，否則保留原個(gè)體，繼續(xù)進(jìn)行局域搜索，直到得到車輛在車站之間的最優(yōu)布置，停止搜索.

產(chǎn)生的新個(gè)體代替原種群個(gè)體的方法描述如下：在[0，λ]中隨機(jī)產(chǎn)生兩個(gè)數(shù)h和o，其中λ為種群中的個(gè)體總量，經(jīng)過(guò)局域搜索后的新個(gè)體代替h和o所對(duì)應(yīng)的個(gè)體.

圖7 個(gè)體局域搜索Fig.7 The process of local search

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

通過(guò)數(shù)值實(shí)驗(yàn)對(duì)面向時(shí)變需求的救護(hù)車車站選址與重定位問(wèn)題的遺傳算法進(jìn)行性能評(píng)估.本文所有計(jì)算程序均使用 C++語(yǔ)言編寫，數(shù)值實(shí)驗(yàn)全部在配有Intel E5-2670 2.6 GHz處理器和2 GB內(nèi)存的計(jì)算機(jī)上進(jìn)行，操作系統(tǒng)為L(zhǎng)inux.

3.1 數(shù)據(jù)生成

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

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

3.2 結(jié)果及分析

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

表1 小規(guī)模算例結(jié)果Tab.1 Computational results of small scale instance

表2 大規(guī)模算例結(jié)果Tab.2 Computational results of small large instance

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

4 結(jié)語(yǔ)

針對(duì)時(shí)變系統(tǒng)中的救護(hù)車布置與重定位問(wèn)題進(jìn)行了研究，建立了混合整數(shù)規(guī)劃模型.由于使用標(biāo)準(zhǔn)計(jì)算軟件進(jìn)行計(jì)算的時(shí)間過(guò)長(zhǎng)，精度過(guò)低，本文設(shè)計(jì)了一種遺傳算法并生成相關(guān)的算例，進(jìn)而對(duì)算法的合理性和科學(xué)性進(jìn)行評(píng)估.結(jié)果表明，遺傳算法的求解時(shí)間可控制在合理范圍內(nèi)，求解精度較高，為時(shí)變系統(tǒng)內(nèi)的救護(hù)車布置和重定位提供了新的思路和方法.