劉寶新，謝 偉，張婷婷

(1.軍事交通學(xué)院 聯(lián)合投送系,天津 300161； 2.軍事交通學(xué)院 研究生管理大隊，天津 300161; 3.94994部隊，南京 210019； 4．軍事交通學(xué)院 訓(xùn)練部，天津 300161)

● 基礎(chǔ)科學(xué)與技術(shù) Basic Science & Technology

時變條件下軍用爆炸品公路運輸人口風(fēng)險路徑優(yōu)化模型研究

劉寶新1，謝 偉2,3，張婷婷4

(1.軍事交通學(xué)院 聯(lián)合投送系,天津 300161； 2.軍事交通學(xué)院 研究生管理大隊，天津 300161; 3.94994部隊，南京 210019； 4．軍事交通學(xué)院 訓(xùn)練部，天津 300161)

為降低軍用爆炸品的運輸風(fēng)險，通過對運輸過程中人口風(fēng)險以及實際運輸網(wǎng)絡(luò)動態(tài)性分析，建立時變條件下軍用爆炸品運輸?shù)娜丝陲L(fēng)險模型，利用改進(jìn)的模擬退火算法思想進(jìn)行Matlab編程，對時變條件下軍用爆炸品運輸?shù)娘L(fēng)險最小路徑進(jìn)行求解。算例驗證表明，只需獲得運輸網(wǎng)絡(luò)中各個時段對應(yīng)的事故概率、人口密度和交通流量等數(shù)據(jù)，就能利用改進(jìn)的模擬退火算法較好地解決時變條件下的風(fēng)險最小路徑問題。

時變；軍用爆炸品；公路運輸；人口風(fēng)險；路徑優(yōu)化；模擬退火算法

軍用爆炸品是部隊執(zhí)行作戰(zhàn)任務(wù)、進(jìn)行爆破作業(yè)等國防工程不可缺少的組成部分，爆炸品從生產(chǎn)加工到配發(fā)部隊，公路運輸是其中的必經(jīng)環(huán)節(jié)。在運輸過程中，一旦發(fā)生爆炸事故，將會對周邊人口和環(huán)境產(chǎn)生嚴(yán)重?fù)p害。根據(jù)公路交通狀況、周邊人口數(shù)量等因素及其隨時間變化的規(guī)律，科學(xué)地選擇合適的路徑和車輛運行時間，對于降低運輸事故發(fā)生的概率、減少事故的危害后果都有著積極作用。因此，開展基于時變條件下人口風(fēng)險的軍用爆炸品公路運輸路徑優(yōu)化研究，具有十分重要的意義。

1 人口風(fēng)險模型構(gòu)建

風(fēng)險是對事故發(fā)生概率和影響后果的度量，在人口風(fēng)險模型中，一般用事故發(fā)生概率和暴露人口數(shù)量的乘積表示。其中，事故發(fā)生的概率具有時變性，各個時段的事故發(fā)生概率可通過對歷史數(shù)據(jù)的統(tǒng)計分析獲得。Frank等對不同時段發(fā)生的交通事故概率pij(t)統(tǒng)計數(shù)據(jù)見文獻(xiàn)[1]。

對于暴露人口，由于路上人口、路下人口受到的影響程度不同，一般需要對不同區(qū)域類型的人口進(jìn)行區(qū)分。由于路上人口相對集中且都沿著道路通行，可將路上人口視為按線性分布。路上人口的線密度可表示為

(1)

式中：AADTij為路段ij上的年平均日交通流量，一般可通過歷史統(tǒng)計數(shù)據(jù)獲得；θ為平均每輛車載有的人員數(shù)量；vij為路段ij上的平均運行速度；uij為路段ij上的車外人員密度，需要根據(jù)道路等級以及當(dāng)?shù)厝丝诔鲂刑攸c進(jìn)行確定。此外，考慮到一級公路、高速公路會對進(jìn)出口進(jìn)行限制，可將此類道路的車外人口密度定為0人/km。相對路上人口，路下人口分布相對分散，因此常利用矩形模型或圓形模型對路下人口數(shù)量進(jìn)行評估。由于矩形影響區(qū)域模型的誤差比半圓形模型更小，故采用矩形模型計算[2]。路下人口密度可根據(jù)該地區(qū)人口數(shù)量以及區(qū)域面積求得，并通過各時段人口出行比例系數(shù)進(jìn)行調(diào)整得到各個時段的人口密度。其中人口出行比例系數(shù)見文獻(xiàn)[3]。

若考慮車輛以及建筑物的緩沖作用，還可將人口分為室內(nèi)人口和室外人口。由此，可將路上人口和路下人口分別表示為

(2)

(3)

式中：xL為車(室)外人口數(shù)量的比例，已有學(xué)者根據(jù)典型路段的人流量和車流量進(jìn)行統(tǒng)計，可按城市主干道50%，次干道、農(nóng)村道路30%，高速公路0進(jìn)行賦值[4]；SFL為車(室)內(nèi)人員的風(fēng)險減緩系數(shù)，可取為20%[5]；lij為路段長度，km；d為爆炸品的影響半徑，km。

由式(1)—式(3)，得各時段暴露人口數(shù)量為

(4)

式中：δon和δoff分別為路上人口與路下人口的權(quán)重調(diào)節(jié)系數(shù)，由于一旦發(fā)生運輸事故引發(fā)爆炸，路上人口受到的影響要比路下人口大，因此應(yīng)適當(dāng)增加路上人口的權(quán)重系數(shù)比例，參考以往的研究數(shù)據(jù)，一般可將路上、路下人口的權(quán)重系數(shù)分別取為0.6和0.4[4]。

根據(jù)不同時段人口出行特點以及交通流量的變化，將各路段的事故概率pij(t)、人口數(shù)量等按時間段進(jìn)行劃分，可建立基于時變條件下的風(fēng)險最小路徑運輸優(yōu)化模型：

(5)

(6)

(7)

式(5)為針對路徑的人口風(fēng)險最小的目標(biāo)約束；式(6)為路徑是否包括節(jié)點i與節(jié)點j之間的路段；式(7)為流向約束，表示路徑從起點至終點。

2 算法及編程實現(xiàn)

對基于靜態(tài)網(wǎng)絡(luò)的路徑優(yōu)化問題已有Dijkstra、Floyd、A*等較為成熟的算法，但對于時變下的路徑優(yōu)化問題，靜態(tài)網(wǎng)絡(luò)的算法已不再適用。隨著各種智能算法越來越廣泛地應(yīng)用于求解各類問題，遺傳算法、蟻群算法、模擬退火算法等智能算法也被用于求解路徑優(yōu)化問題。其中模擬退火算法在全局搜索中有較明顯的優(yōu)勢[6]，通過控制降溫的速度模擬退火過程搜索最優(yōu)解。利用Metropolis抽樣方法，可使算法以一定的突跳概率產(chǎn)生、接受新解。目前針對模擬退火算法有較多改進(jìn)，如在產(chǎn)生新解時利用遺傳算法的思想對解空間內(nèi)的個體進(jìn)行交叉、選擇等操作，在產(chǎn)生新解的過程中同時淘汰劣解等。一般模擬退火算法包括初始溫度設(shè)定、恒溫、降溫等過程，具體實現(xiàn)步驟如下。

2.1 染色體編碼

為使算法能夠識別，借鑒遺傳算法的思想將解空間的數(shù)據(jù)用染色體基因的形式表示出來，即染色體編碼。目前常用的編碼方式有0-1編碼、實數(shù)編碼、格雷碼編碼[7]等，其中0-1編碼具有編碼規(guī)則簡單、易于解碼以及便于算法的實現(xiàn)等優(yōu)點，一般在路網(wǎng)結(jié)構(gòu)不太復(fù)雜的情況下使用。0-1編碼的規(guī)則為：按節(jié)點號的順序依次排列，對應(yīng)位置的數(shù)值為1表示該節(jié)點被選中，否則為未被選中。如圖1所示的編碼，代表路徑1—3—5—6—9。

圖1 0-1編碼和解碼

2.2 初始化種群及參數(shù)

根據(jù)問題的規(guī)模，設(shè)定初始溫度T0、鏈長L和冷卻溫度Tend，并利用rand函數(shù)隨機(jī)生成一定規(guī)模的初始種群作為路徑優(yōu)化問題的初始解。

v=round(rand(n1,s1));%n1為種群數(shù)量，s1為節(jié)點數(shù)量

v(:,1)=1;

v(:,end)=1;

由于節(jié)點1和最后一個節(jié)點為必經(jīng)節(jié)點，設(shè)定首尾節(jié)點被選中。此外，可根據(jù)路網(wǎng)結(jié)構(gòu)，排除初始解中不存在的路線。

2.3 恒溫操作

在溫度T下，利用初始解S1產(chǎn)生新解S2。產(chǎn)生新解的方法為：隨機(jī)產(chǎn)生兩個位置，對相應(yīng)位置的編碼進(jìn)行交換。如圖2所示，隨機(jī)產(chǎn)生的兩個位置為第2位和第6位，將初始解S1的第2位和第6位上的編碼進(jìn)行互換得到新解S2。

圖2 產(chǎn)生新解

根據(jù)以上算法思想，可利用round函數(shù)和rand函數(shù)產(chǎn)生兩個隨機(jī)位置，同時為降低產(chǎn)生非法路徑(不存在的路徑)的概率，可將隨機(jī)位置限定為首尾節(jié)點之間的點，即首尾節(jié)點不參與編碼交換。實現(xiàn)代碼為

function S2=NewAnswer(S1)%產(chǎn)生新解

[m,n]=size(S1);%計算初始解的個數(shù)及節(jié)點數(shù)量

for i=1:m

S2(i,:)=S1(i,:);

a=round(rand(1,2)*(n-3)+2);%產(chǎn)生兩個首尾節(jié)點之外的隨機(jī)位置

temp=S2(i,a(1));

S2(i,a(1))=S2(i,a(2));%產(chǎn)生新解

S2(i,a(2))=temp;

end

產(chǎn)生新解S2之后，可利用式(6)計算S2相對于S1的增量df。其中f函數(shù)為目標(biāo)函數(shù)，對于本問題為路徑的風(fēng)險值函數(shù)。

df=f(S2)-f(S1)

(6)

由于時變特性化，因此f函數(shù)應(yīng)按各時間段的不同風(fēng)險值來計算路徑的總風(fēng)險。若把時間分為8個時間段，結(jié)合式(1)的目標(biāo)函數(shù)，可將f函數(shù)用以下代碼實現(xiàn)：

function[risk,T]=path_risk (v,D,time,t)%求解路徑v的風(fēng)險函數(shù)

% v： 路徑代碼

% D： 各路段在不同時間段的風(fēng)險值

% time： 各節(jié)點之間運輸所需要的時間

% t： 出發(fā)時刻

[vm vn]=size(v);%得到v的行數(shù)vm，列數(shù)vn

T=ones(vm,1)*t; %到達(dá)的時刻

risk=zeros(vm,1);%初始化路徑的風(fēng)險值

for i=1:vm

I=find(v(i,:)= =1);%解碼

[Im,In]=size(I);%得到I的列數(shù)In

for j=1:In-1

t_time=rem(T(i),24);

if t_time= =0

risk(i)=risk(i)+D{I(j),I(j+1)}(1,1);

T(i)=T(i)+time(I(j),I(j+1));

else

k=ceil(t_time/3);

if k= =T(i)/3

k=k+1;

end

risk(i)=risk(i)+D{I(j),I(j+1)}(1,k);

T(i)=T(i)+time(I(j),I(j+1));%加上本段路耗費的時間

end

end

end

根據(jù)Metropolis準(zhǔn)則并結(jié)合增量df的結(jié)果來決定是否接受新解，對于求解最小值問題，當(dāng)df<0時，表示新解S2優(yōu)于初始解S1，則用新解S2替代初始解S1；當(dāng)df>0時，則以接受概率e-df/T接受新解S2。

2.4 降溫操作

以速率q進(jìn)行降溫，即T′=q×T。在新的溫度T′下，重復(fù)恒溫操作。當(dāng)溫度達(dá)到冷卻溫度Tend時，算法結(jié)束，輸出最優(yōu)解。需要注意的是，速率q的取值對算法有較大影響。若取值過小，需要耗費較長時間進(jìn)行計算，使算法效率降低；若取值過大，則溫度下降過快，易錯過最優(yōu)解，使算法陷入局部最優(yōu)。因此，q的取值需要根據(jù)問題的實際情況進(jìn)行調(diào)試選擇，其取值范圍一般在0.5～0.99之間[8]。

3 算例分析

某部隊有一批軍用爆炸品需從節(jié)點1處運往節(jié)點8，假設(shè)根據(jù)式(1)至(5)及人口密度、人口出

行系數(shù)等參數(shù)計算出8個時間段的人口風(fēng)險見表1。為簡化問題，各路段的運輸時間設(shè)為固定值，運輸網(wǎng)絡(luò)如圖3所示，圖中標(biāo)注的路權(quán)值為各路段所耗費的運輸小時數(shù)。據(jù)此求解運輸風(fēng)險的最小路徑以及相應(yīng)的出發(fā)時刻，確定該部隊運輸軍用爆炸品的合理路線以及相應(yīng)出發(fā)時間。

圖3 運輸網(wǎng)絡(luò)

根據(jù)上文所述思想和方法利用Matlab進(jìn)行編程，由于目前針對算法參數(shù)賦值的理論都只能給出取值范圍，因此參數(shù)的具體設(shè)定還需要通過不斷的調(diào)試來確定。通過調(diào)試，將初始溫度設(shè)為1 000，冷卻溫度設(shè)定為0.001，降溫速率設(shè)定為0.9，鏈長設(shè)定為50。以6:00—18:00作為出發(fā)時刻的選擇區(qū)間，每隔10 min計算一次風(fēng)險最小的路徑，計算結(jié)果見表2，其中出發(fā)時刻“6:10—6:50”表示當(dāng)出發(fā)時刻為6:10、6:20、6:30、6:40、6:50時其風(fēng)險最小路徑相同。

表1 各運輸時段的人口風(fēng)險

表2 計算結(jié)果

根據(jù)表2的計算結(jié)果可知，該部隊運輸軍用爆炸品風(fēng)險最小的路徑為1—3—5—6—8，運輸總風(fēng)險為4.46，對應(yīng)于15:00從節(jié)點1出發(fā)。不同的出發(fā)時刻會導(dǎo)致運輸?shù)娘L(fēng)險不同，最小風(fēng)險路徑也會發(fā)生相應(yīng)的變化。如6:00和6:10出發(fā)時運輸風(fēng)險最小的路徑在第3個節(jié)點發(fā)生了變化，風(fēng)險值相差0.1。在15:00出發(fā)時，路徑1—3—5—6—8的運輸風(fēng)險最小，需耗時24 h，而根據(jù)圖3可求得時間最短路徑1—3—5—6—7—8，需耗時23 h。可見，風(fēng)險最小的路徑與時間最短路徑并不一定是同一條路徑，同樣即使對于同一條路徑，其風(fēng)險值也有可能會隨出發(fā)時間的不同而發(fā)生變化，如對于路徑1—2—4—6—8，6:00出發(fā)和7:00出發(fā)的風(fēng)險值相差0.3。

4 結(jié) 語

由于運輸網(wǎng)絡(luò)隨時間動態(tài)變化，單一的靜態(tài)網(wǎng)絡(luò)并不能客觀地反映運輸風(fēng)險的變化情況。為更加準(zhǔn)確、客觀地評估運輸風(fēng)險從而得出風(fēng)險較小的路徑，使部隊遂行軍用爆炸品運輸任務(wù)更加安全、可靠，應(yīng)當(dāng)從時變角度對路網(wǎng)的風(fēng)險進(jìn)行評估。通過算例驗證說明，只需獲得運輸網(wǎng)絡(luò)中各個時段對應(yīng)的事故概率、人口密度和交通流量等數(shù)據(jù)，就能利用改進(jìn)的模擬退火算法較好地解決時變條件下的風(fēng)險最小路路徑問題，與基于靜態(tài)網(wǎng)絡(luò)的評估方法相比更加貼近運輸?shù)膶嶋H情況。同時，算法在設(shè)計時采用細(xì)胞數(shù)組儲存路段參數(shù)，對新樣本數(shù)據(jù)的適應(yīng)能力較強，可根據(jù)任務(wù)性質(zhì)和側(cè)重點的不同，通過運輸時間、費用等指標(biāo)評估相應(yīng)的最短時路徑、運費最小路徑等，可為部隊執(zhí)行軍用爆炸品運輸時，在路徑選擇方面提供一定程度的決策支持和參考。

[1] FRANK W C，THILL JC，BATTA R．Spatial decision support system for hazardous material truck routing[J]．Transportation Research Part C Emerging Technologies，2000,8(1-6)：337-359．

[2] 趙天一．基于風(fēng)險分析的危險品車輛路徑優(yōu)化問題研究[D]．天津：天津大學(xué)，2013．

[3] 西安市城鄉(xiāng)建設(shè)委員會，長安大學(xué)．西安市城市交通可持續(xù)發(fā)展研究[EB/OL](2005-12-16)[2016-05-06]．http:// www.docin.com/touch-new/preview-new.do?id=504089821．

[4] 沈小燕．道路危險貨物運輸風(fēng)險分析及路線優(yōu)化研究[D]．西安：長安大學(xué)，2009.

[5] 任常興．基于風(fēng)險分析的危險品道路運輸路徑優(yōu)化方法研究[D]．天津：南開大學(xué)，2007．

[6] 王勇為，李昱.模擬退火算法在軍事運輸路徑優(yōu)化中的應(yīng)用及求解[J].國防交通工程與技術(shù)，2009，7(4)：23.

[7] 李清，胡志華．基于多目標(biāo)遺傳算法的災(zāi)后可靠路徑選擇[J]．浙江大學(xué)學(xué)報(工學(xué)版)，2016，50(1)：33-40．

[8] 梁旭，黃明，寧濤，等．現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M]．北京：電子工業(yè)出版社，2014：117．

(編輯：史海英)

Population Risk and Route Optimization Model of Military Explosives Highway Transportation in Time-varying Condition

LIU Baoxin1, XIE Wei2,3， ZHANG Tingting4

(1.Joint Projection Department, Military Transportation University, Tianjin 300161, China;2.Postgraduate Training Brigade, Military Transportation University, Tianjin 300161, China;3.Unit 94994, Nanjing 210019, China； 4．Training Division, Military Transportation University, Tianjin 300161, China)

To reduce the risk of military explosives transportation, the paper firstly establishes population risk model of military explosives transportation in time-varying condition by analyzing population risk during the transportation and the network dynamic of actual transportation. Then, it programs with improved simulated annealing algorithm and Matlab, and solves the minimum risk path of military explosives transportation in time-varying condition. The result shows that obtaining the data of accident probability, population density, and traffic flow can solve the problem of minimum risk path with improved simulated annealing algorithm in time-varying condition.

time-varying; military explosives; highway transportation; population risk; route optimization; simulated annealing algorithm

2016-10-10；

2017-02-18． 作者簡介： 劉寶新(1966—)，男，博士，教授，碩士研究生導(dǎo)師．

10．16807/j.cnki.12-1372/e.2017.07.019

U116．2

A

1674-2192(2017)07- 0081- 05