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

劉寶新，謝 偉，張婷婷

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

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

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

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

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

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

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

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

1 人口風險模型構建

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

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

(1)

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

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

(2)

(3)

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

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

(4)

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

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

(5)

(6)

(7)

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

2 算法及編程實現

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

2.1 染色體編碼

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

圖1 0-1編碼和解碼

2.2 初始化種群及參數

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

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

v(:,1)=1;

v(:,end)=1;

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

2.3 恒溫操作

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

圖2 產生新解

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

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

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

for i=1:m

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

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

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函數為目標函數，對于本問題為路徑的風險值函數。

df=f(S2)-f(S1)

(6)

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

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

% v： 路徑代碼

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

% time： 各節點之間運輸所需要的時間

% t： 出發時刻

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

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

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

for i=1:vm

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

[Im,In]=size(I);%得到I的列數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

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

2.4 降溫操作

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

3 算例分析

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

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

圖3 運輸網絡

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

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

表2 計算結果

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

4 結 語

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

[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] 趙天一．基于風險分析的危險品車輛路徑優化問題研究[D]．天津：天津大學，2013．

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

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

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

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

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

[8] 梁旭，黃明，寧濤，等．現代智能優化混合算法及其應用[M]．北京：電子工業出版社，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