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

劉寶新，謝 偉，張婷婷

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

● 基礎科學與技術 Basic Science & Technology

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

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

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

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

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

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

1 人口風險模型構建

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

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

(1)

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

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

(2)

(3)

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

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

(4)

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

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

(5)

(6)

(7)

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

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

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

2.1 染色體編碼

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

圖1 0-1編碼和解碼

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

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

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

v(:,1)=1;

v(:,end)=1;

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

2.3 恒溫操作

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

圖2 產生新解

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

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

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

for i=1:m

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

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

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

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

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

end

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

df=f(S2)-f(S1)

(6)

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

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

% v： 路徑代碼

% D： 各路段在不同時間段的風險值

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

% t： 出發(fā)時刻

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

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

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

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準則并結合增量df的結果來決定是否接受新解，對于求解最小值問題，當df<0時，表示新解S2優(yōu)于初始解S1，則用新解S2替代初始解S1；當df>0時，則以接受概率e-df/T接受新解S2。

2.4 降溫操作

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

3 算例分析

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

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

圖3 運輸網絡

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

表1 各運輸時段的人口風險

表2 計算結果

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

4 結 語

由于運輸網絡隨時間動態(tài)變化，單一的靜態(tài)網絡并不能客觀地反映運輸風險的變化情況。為更加準確、客觀地評估運輸風險從而得出風險較小的路徑，使部隊遂行軍用爆炸品運輸任務更加安全、可靠，應當從時變角度對路網的風險進行評估。通過算例驗證說明，只需獲得運輸網絡中各個時段對應的事故概率、人口密度和交通流量等數(shù)據(jù)，就能利用改進的模擬退火算法較好地解決時變條件下的風險最小路路徑問題，與基于靜態(tài)網絡的評估方法相比更加貼近運輸?shù)膶嶋H情況。同時，算法在設計時采用細胞數(shù)組儲存路段參數(shù)，對新樣本數(shù)據(jù)的適應能力較強，可根據(jù)任務性質和側重點的不同，通過運輸時間、費用等指標評估相應的最短時路徑、運費最小路徑等，可為部隊執(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] 趙天一．基于風險分析的危險品車輛路徑優(yōu)化問題研究[D]．天津：天津大學，2013．

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

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

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

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

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

[8] 梁旭，黃明，寧濤，等．現(xiàn)代智能優(yōu)化混合算法及其應用[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—)，男，博士，教授，碩士研究生導師．

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

U116．2

A

1674-2192(2017)07- 0081- 05