災后應急救援運輸路徑優化模型研究

任其亮，喬 丹

(重慶交通大學交通運輸學院，重慶400074)

REN Qi-liang，QIAO Dan

(School of Traffic＆ Transportation，Chongqing Jiaotong University，Chongqing 400074，China)

特大自然災害以其突發性和毀滅性而受到高度重視，因災后救援物資的運輸情況十分復雜，在很多方面具有不確定性，使救援物資的運輸調度在災后應急救援中占有非常重要的位置。目前的應急救援運輸研究大都是基于確定的路徑，主要依靠經驗，從時間、費用、危險性等方面做定性或半定量分析［1－3］。筆者從災后救援運輸的實際出發，其各種不確定性，建立運輸路徑的不確定優化模型，并探討模型的求解算法。

1 災后救援運輸的不確定性因素

災后救援物資運輸的特殊性在于時間的緊迫性和多因素不確定性［4］。救援運輸網絡優化模型的不確定性包括變量的不確定性、約束條件的不確定性、決策目標的不確定性等，具體表現為:

1)網絡可靠度不確定性。網絡可靠度是指網絡在規定的時間和條件下完成預定功能的概率，是衡量交通網絡在緊急災害情況下，系統功效能否正常發揮、運行狀態是否達到預期要求的重要指標［2］。由于對災區的具體環境不了解，救援運輸網絡的節點及其各路段受災情況的不同，對整個救援的網絡不清楚。運輸網絡的節點和路段可能在某一時刻遭到毀壞，毀壞后又可能在某一時刻得到修復;另一方面發生災害后，救援車輛異常增加，加之人員的盲目流動，會造成某些路段交通量驟增，運輸網絡可靠度是不確定的。

2)容量可靠度不確定性。路網容量可靠性［5］是指在一定的服務水平下，路網容量能滿足一定交通需求水平的概率。受災后，由于各類路段毀壞的程度是不確定的，因此，救援物資運輸網絡的容量可靠性是不確定的。

3)運輸時間不確定性。由于運輸網絡各路段遭受災害的破壞程度是不確定的，而運輸梯隊通過遭受不同程度的破壞路段的時間是不確定的，救援運輸梯隊通過不同路徑的時間常常是不確定的。

4)運輸物資需求量不確定性。在救援物資運輸的時間段，次生災害隨時可能發生，造成更多的人員傷亡和財產損失，并且往往會破壞通信和電力設施，給指揮協調和信息反饋造成不利，無法確切得到救援物資需求量。因此，運輸物質的需求量也具有不確定性。

5)運輸損耗不確定性。災害對交通設施的破壞，使得運輸梯隊通過路段時會產生損耗。由于各路段遭受的破壞程度是不確定的，其造成的運輸損耗也是不確定的。因此，運輸梯隊通過網絡路段時的運輸損耗也是不確定的。

6)多重目標下選擇不確定性。災后救援運輸路徑選擇中，當多個目標發生沖突時該如何選擇，如當選擇一條運輸路徑時，運輸時間最少，而運輸損耗又比較多，而這時要達到運輸時間和運輸損耗的最優化，該如何選擇?由于救援任務的需要，2個指標往往都是路徑決策的重要因素，不能只考慮某一方面，且在很多時候這些因素是不確定的，即路徑優化問題是一個在不確定性環境下的多目標優化問題。

2 救援運輸路徑優化模型

2.1 網絡圖

根據災后救援運輸任務的特點，將交通網絡抽象為一個有向賦權圖G=(V，E，C)。式中:V={1，2，…，n}是節點的集合(n為節點個數)，若i，j∈V，則xij表示從i到j的一條弧;E為弧集，可以表示成以下網絡結構:x={xij:1≤i≤n－1，i+1≤j≤n}，其中，xij∈{0，1}，xij=1 表示路段xij在選擇的可行路徑上，否則xij=0;C為弧xij的權集，可以是弧的運輸時間、運輸損耗和可靠度的集合。

假設節點完全可靠，而節點之間的連接失效與否是彼此統計獨立的，且失效的概率已知，那么在V的子集K中的所有節點是否連接成功是一個隨機事件，把這個時間的概率稱為K，即節點可靠性，記做R(K，x)，其中x為網絡結構。如果K中的所有節點在G中都是連通的，那么稱這個網絡G是K連通的。因此，K節點可靠性R(K，x)=Pr{G相對網絡結構x是K連通}，當K=G時，K節點可靠性R(K，x)就是網絡可靠性［6］。

2.2 約束條件

2.2.1 目標約束

災后救援運輸的路線選擇中，一般行駛時間這個參數最為重要，行駛時間越短的道路越適合作為災害后的緊急救援道路［2］。災后應急救援運輸的目標是在運輸時間、運輸路徑可靠度和運輸損耗以一定的置信水平不超過目標值，從而使救援運輸效率達到最高，使災區能在第一時間內得到物資供應［7］。因此，假設有如下目標優先級結構:第1優先級:時間目標，在給定的置信水平α1下，運輸時間應盡可能的不超過目標值b1;第2優先級:可靠性目標，網絡可靠性盡可能以置信水平α2不低于目標值b2;第3優先級:損耗目標，運輸損耗盡可能以置信水平α3不超過目標值b3。

2.2.2 路徑約束

災后救援運輸路徑優化問題的約束，假設:1)運輸路徑起終點均只有一個且是確定的;2)單梯隊從起點出發，只能選擇一條路段作為運輸道路，最后到達終點;

3)網絡中任意中間節點vi，梯隊進入該節點，必須還要從該節點出發，不得停留或消失;

4)梯隊通過各路段的時間和損耗是隨機的;

5)運輸網絡可靠性是隨機的。

可得路徑約束方程如下:

2.3 目標規劃模型

令tij表示弧vij的通行時間，且記t={tij│(i，j) ∈V}，那么路徑x的通行時間就可以寫成f(x，t)=令sij表示弧vij的通行損耗，且記是s={sij│(i，j)∈V}，那么路徑x的通行損耗就可以寫成

根據不確定機會約束理論［6］，得機會約束目標規劃模型約束為:

式中:lexmin{*}為按字典序極小化目標向量;Pr{*}為事件的概率;αi(i=1，2，3)為給定的置信;bi(i=1，2，3)為給定的目標值;為目標i偏離目標值bi(i=1，2，3)的樂觀正偏差;x為路徑決策變量，且x={xij:1≤i≤n－1，i+1≤j≤n}(n為網絡節點的個數，xij∈{0，1}，xij=1表示路段xij在選擇的可行路徑上，否則xij=0)。

3 模型求解

3.1 算法

為求解不確定規劃模型，筆者設計了基于遺傳算法的混合智能算法:首先利用隨機模擬［6］產生不確定函數的訓練樣本;然后利用這些數據訓練神經元網絡［8］以逼近不確定函數;最后把訓練好的神經元網絡嵌入到遺傳算法中。根據災后救援運輸的特殊情況，對遺傳算法中的因素做以下說明:

1)編碼。采用十進制編碼構造染色體，染色體的基因對應網絡節點序號，而序號的排列順序代表救援運輸梯隊從起點到終點的路徑。設路網的節點集合V中節點總數為n，則染色體的基因總數也為n。染色體基因的組成方式:第1個為起點序號“1”;接下來是中間節點，設中間節點總數為n，則有0≤l≤n－2;然后是終點“n”。如果 0≤l＜n－2，則在“n”點后補“0”，使基因總數保持為n。設染色體中從“1”到“n”的非0基因個數為m，定義其為有效基因數。以圖1為例，建立路徑1－2－3－6－7的連接矩陣(表1)，則該路徑對應的染色體的編碼為1 2 3 6 7 0 0。

圖1 網絡圖Fig.1 Network diagram

表1 連接矩陣Tab.1 Connection matrix

基于這樣的編碼方式，可得出染色體中的第1個基因是“1”，最后一個不為“0”的基因是終點的序號“n”，當基因中包含“0”基因時，說明有部分節點沒有在這個染色體所代表的路徑上。

2)評價函數。比較常用的評價函數是基于序的評價函數［6］，設目前該代中的染色體為T1，T2，…，Tpop_size，對于目標規劃模型，種群中的染色體有以下序關系:對于2個染色體，如果它們在高一級的目標值相同，則在當前一級中染色體所對應的目標值越小越好。如在每一級中2個染色體都對應相同的目標值，就認為這2個染色體無差別，從而可以對它們進行隨機的排序。設參數α∈(0，1)給定，定義基于序的評價函數為:eval(Ti)=a(1－a)i－1，i=1，2，…，pop_size 。

3)選擇。采用改進的輪盤賭選擇法。在選擇新個體時，首先在當前代中選擇最佳個體直接進入下一代(若有多個，則隨機選取一個)，然后對其它個體依累積概率大小采用輪盤賭方式進行選擇。對每個染色體Ti，計算累計概率1，2，…，pop_size 。從區間(0，qpop_size)中產生一個隨機數r，若qi－1＜r≤qi，則選擇第i個染色體Ti，重復選擇，得到pop_size個復制的染色體。

4)交叉。根據染色體編碼規則的特點及與路徑節點序號的關聯性，采用類OX法作為染色體交叉的方法，交叉步驟為:①從上一代選擇染色體T0、T1的基因中隨機選擇2個交叉點，交叉點必須同時位于2個染色體的“1”之后，“n”之前，以保證“0”基因不被交叉，交叉點之間的部分為匹配區域段;②將T0的匹配段加到T1的基因“1”之后，將T1的匹配區域加到T0的基因“1”之后;③消除染色體匹配段后面的重復節點。

5)變異。采用的染色體變異方式有3種:①在基因“1”和“n”之間隨機刪除一個非必經點所代表的基因，同時在“n”后補“0”基因，以使保持基因數為n;②當有效基因總數m＜n時，增加一個基因中沒有的節點序號作為基因，其位置可以在有效基因的中間部份隨機選取，同時在“n”后刪除一個“0”基因;③互換“1”和“n”之間的2個基因。為提高遺傳算法的性能，筆者采用類似于模擬退火算法中的Metropolis準則［1］對變異進行改進，如果變異后的值優于變異前的值，則新染色體進入下一代;否則，依概率確定是否進入下一代。公式如下代中的適應度最大值，P為變異后染色體接受概率。

3.2 算例

以圖1為救援運輸網絡圖，對建立的目標規劃模型進行試驗，以驗證模型和算法的有效性。

單梯隊通過各路段的隨機時間和通行損耗分布如表2和表3。路網各路段的可靠性服從正態分布N(1，4)。

表2 通行時間隨機分布Tab.2 Random distribution of time

表3 通行損耗隨機分布Tab.3 Random distribution of loss

根據網絡節點數，染色體的基因個數為7。在置信水平(α1，α2，α3)=(0.8，0.85，0.8)下，通行時間、路網可靠性和通行損耗的目標水平為(b1，b2，b3)=(5，0.85，5)。設遺傳算法的種群大小為 50，交叉概率 0.85，變異率 0.05。

通過運行混合智能算法(1 000次模擬循環，500次遺傳迭代)，得到最優路徑為1－3－7，它滿足前2個目標，第3個目標偏差為0.975。

4 結語

從災后救援運輸的角度出發，建立災后救援運輸路徑動態優化模型和算法。該模型能符合發生各類特大自然災害時的實際情況，解決不確定性救援運輸路徑動態優化問題，滿足各類特大自然災害時的救援運輸需求，并指導其他緊急狀態下的運輸問題，能夠為極大地減少因現有理論方法不足而產生的人員、物資的損耗問題提供借鑒，提高救援運輸的效率，具有較高的社會經濟效益。

［1］黃金虎.應急物流系統若干關鍵技術的研究與實現［D］.上海:上海交通大學，2007.

［2］巴桑次仁，鄧桂英，巴桑央金.西藏地震應急救援體系建設的探索［J］.高原地震，2009，21(2):58 －61.

［3］王洪，陸愈實，王莎莎.基于MATLAB的應急救援最優路徑選擇［J］.工業安全與環保，2009，35(5):48－50.

［4］繆成，許維勝，吳啟迪.大規模應急救援物資運輸模型的構建與求解［J］.系統工程，2006，24(11):6 －12.

［5］任其亮.灰色馬爾可夫模型在公路運量彈性系數預測中的應用研究［J］.重慶交通大學學報:自然科學版，2009，28(2):290－293.

［6］石玉峰.戰時不確定性運輸路徑優化研究［D］.成都:西南交通大學，2006.

［7］彭錦，劉寶碇.不確定規劃的研究現狀及其發展前景［J］.運籌與管理，2002，11(2):1 －10.

［8］陳燕燕，劉小明，梁穎.可靠度在交通系統規劃與管理中的應用［M］.北京:人民交通出版社，2006.