文/姜嘉艷

?

基于政府管制的危險品運輸的雙層規(guī)劃設計

文/姜嘉艷

摘 要：本文基于危險品運輸和雙層規(guī)劃的特點，對特定的危險品在特定路段采取禁止通行的方式來實現(xiàn)道路危險品運輸網絡設計。上層政府監(jiān)管部門以危險品在運輸過程中總期望風險最小化為目標，下層運輸企業(yè)以期望運輸成本最小化為目標，構建基于政府管制的危險品運輸的雙層規(guī)劃模型。如果上層與下層的結果不一致，則通過反復修改網絡圖的方法，權衡風險值和成本，直到使雙方都滿意。最后通過數據模擬（c-free 3．5）驗證了算法的而有效性。

關鍵詞：危險品運輸；網絡設計；雙層規(guī)劃；數值模擬

1.研究背景

近年來，伴隨著國民經濟的發(fā)展，公路運輸事業(yè)和化學工業(yè)均取得了長足的發(fā)展和進步，從而對社會大多數成員來說，生活已越來越離不開危險品。不可回避的是，大多數危險品不是在生產地被使用，而是需要經過相當長距離的運輸到達使用地。據統(tǒng)計，我國95%以上的危險品涉及異地運輸問題，其中80%左右是通過道路運輸的，每天危險品的運輸量超過100萬噸[1]。由于危險品道路運輸量大、運行車輛事故率高和運輸企業(yè)安全管理水平落后，近年來災難性事故頻發(fā)，后果極其嚴重，受到了各國政府和公眾的極大關注。因此，不管在國內還是在國際上，危險品在運輸中的事故、風險、路徑選擇等問題，引發(fā)著許多學者的研究。

2.危險品運輸的特點

由于運輸貨物本身的特殊性，危險品具有易燃、易爆、毒性、腐蝕性和放射性等對人類生活生產具有危害的屬性。危險品在運輸過程中，其危險性本就高于其他運輸貨物[2]。其主要特點表現(xiàn)在：①品類繁多，性質各異——現(xiàn)今，在《危險貨物品名表》中的危險品已達2700多個品名；②危險性大——運輸中如防護不當，極易發(fā)生事故，造成人員傷亡和財產損失；③運輸管理的規(guī)章制度多——作為整個道路貨物運輸的重要組成部分，危險品道路運輸不僅要遵守道路貨物運輸共同的規(guī)章，而且要遵守很多特殊規(guī)定；④專業(yè)性強——危險品運輸要滿足一般貨物的運輸條件，還要根據貨物的物理和化學性質，滿足其特殊的運輸條件；⑤安全至上——這里安全運輸是區(qū)別于其他普通運輸的標志，它是危險品運輸的基點所在，要把安全工作放在首位[3]。

3.危險品運輸問題描述及模型設計

（1）問題描述

在本文對危險品運輸網絡設計中，涉及兩個角色：當地政府和運營商。當地政府指派網絡，運營商選擇路線。政府代表第一層，限制路段的通行以控制路網上的風險；運營商代表第二層，在可行的路網上選擇成本最小化的路徑。一旦政府決定了路網，運營商將在此路網上，選擇在始發(fā)地和目的地之間成本最小的路線，政府通常不對運營商規(guī)定路線，因此政府在設計中加入運營商選擇成本最低路線的自由。這種情況引起了雙層規(guī)劃問題[4]。

（2）假設條件及相關參數

危險品網絡設計問題是一個定義在圖形理論問題G=（V，A），其中V是定點集合，A是路段集合。一個頂點對應一個交叉口，一個路段對應網絡上的一個路段。網絡設計問題找到一個網絡服務危險品運輸從起點到終點的路線。每個商品對應一對OD。記（s，t）為運輸車輛的一對OD。參數rijk和cijk分別表示第k種危險品在路段（i，j）上相關的風險和成本，pijk表示第k種商品在路段（i，j）上發(fā)生運輸事故的概率。如果（i，j）是危險品k在網絡中的最佳路段，記xijk=1。如果（i，j）或（j，i）是政府決策的網絡中的解，記yij=1，同時本文僅考慮一類危險品，即k=1。

（3）模型設計

目標（1）是政府最小化網絡上的總風險，而（3）為運營商最小化成本。約束（2）表示如果（i，j）或（j，i）中有任何一個路段用于貨物運輸，則兩個路段均開放使用。約束（4）確保危險品k從起點運達終點。約束（5）確保運營商選擇的路徑是由政府選定的。約束（6）是二進制要求的變量。

4.求解雙層規(guī)劃的算法設計

（1）求解雙層規(guī)劃的基本思想

雙層模型是一個NP～Hard問題[5]，它集政府決策和運營商決策于一體，當單獨考慮政府決策或運營商決策時，問題可以很容易得到解決。本文鑒于Erkut和Gzarais[6]采用一個啟發(fā)式算法進行求解。政府部門對每個運輸任務求最小風險路徑，形成網絡記作N，相應風險為R。運營商在網絡上按成本最小化選擇路徑，實際風險記為Act_R。如果R=Act_R，則認為已經找到最優(yōu)結果。否則，至少有一個運輸任務沒有按照政府部門設想的路線運輸。為了兼顧政府部門和運營商路徑選擇的目標，不斷迭代刪除某些風險較大的路段。通過刪除路段，政府指定網絡的總風險R不斷增加，而運營商選擇的網絡所對應的Act_R不斷的減小，最終達到平衡。

（2）算法設計

初始化：t=0，At=A，best_R=∞。迭代t。

第一步在At上找到運輸車輛的最小風險的路徑。

記xt和Rt分別為危險品k對應的最優(yōu)解和風險值。如果x=1 或x=1，則設置y=1。

第二步在At上找到運輸車輛的第二條最小風險路徑。

在找到的最小風險路徑中，刪除最大風險的路段，然后在新的路網中，找出最小風險路徑，這條路徑即為原路網的次風險路徑。

第三步在At上找到運輸車輛的第三條最小風險路徑。

在找到的第二條最小風險路徑中，刪除最大風險路段，然后在新的路網中，找到最小風險路徑，這條路徑即為原路網的第三條最小風險路徑。

第四步在At上找到運輸車輛的第四條最小風險路徑。

在前三步找到的兩條路徑中，分別刪除其最大風險的路段，在新路網中再次找出最小風險路徑。記以上四步找到的路徑組成的路網為A（yt）。第二步到第四步的路段的刪除是暫時的，僅限于本次循環(huán)的找尋路徑，不影響其他步驟風險值的比較和計算。在本文中，選取以上四條最小風險路徑作為政府選擇的有效路網。

第五步在A（yt）上解決最小成本問題：

記zt和ct分別為對應的最優(yōu)解和成本值，Act_Rt是與zt相關聯(lián)的風險。更新找到的最佳解決方案：如果Act_Rt＜Best_R那么Best_R=Act_Rt。

第六步如果Act_Rt=Rt，那么一個風險水平為Act_Rt的候選路徑zt確定，進入第七步。否則，進入第六步。

圖5　-1 模擬網絡

圖5　-2 最優(yōu)解

第七步記（i，j）是刪除規(guī)則找到的一條路段，從路網中刪除（i，j）和（j，i），t=t+1，At+1=At-{（i，j）（j，i）}，進入第一步。

第八步穩(wěn)定性檢查

表5　-1 結果分析表

如果不只一條，那么進入第七步。

在第三步中，條件Act_Rt=Rt，意味著實際風險不能通過刪除路徑來改善。當這個條件成立，有著最小成本ct和最優(yōu)解zt是一個候選解決方案。當路網中存在閉合的回路，可能有多個有著不同風險值的最小成本方案。要檢查解是否穩(wěn)定，只需檢查路網上最小成本路徑是否存在多種不同風險值的方案。為了驗證這種情況（步驟七），本文通過比較風險值來解決問題。若找到的解不穩(wěn)定，意味著路網上存在至少一條路徑使成本相同，但風險更高。因此，某條路段的風險是否過高，取決于運營商的選擇。在這種情況下，為了不使路徑的風險過高，本文持續(xù)刪除高風險路段，直到獲得一個穩(wěn)定的解。

5.數值模擬及結果分析

（1）數值模擬

本文模擬一輛危險品運輸車輛穿過擁有20個節(jié)點的城市進行算法測試，并用c～free3.5編程實現(xiàn)路徑的選擇。測試的路網如下：（見圖5-1）

道路網由20個節(jié)點和48條邊組成。其中路段間的成本根據行駛里程以及路段情況計算，路段間的風險值根據危險品道路運輸風險分類中的風險因素得到。本文利用雙層規(guī)劃模型方案，分兩階段進行測試。第一階段找到風險最小的四條路徑，形成一個新路網。

Route1=（1，5）（5，14）（14，18）（18，19）（19，20），風險值R1=8，成本值C1=21；

Route2=（1，5）（5，9）（9，14）（14，18）（18，19）（19，20），風險值R2=10，成本值C2=21；

Route3=（1，3）（3，6）（6，12）（12，17）（17，20），風險值為R3=11，成本值C3=20；

Route4=（1.9）（9，14）（14，18）（18，19）（19，20），風險值R4=13，成本值C4=19；

Rt=8，運行結果顯示其中（1，9）路段為第一次循環(huán)形成的路網中的最高風險路段。

第二次循環(huán)中，加入成本指標再次尋找路徑，即在新路網中找到最小成本路徑：（1，9）（9，14）（14，18）（18，19）（19，20），計算風險值Act_Rt=13。由于Act_Rt=13不等于第一個階段的解中的最小風險值Rt=8，所以要刪除路段精心權衡。找到新路網中的最大風險的路段（1，9），并將其刪除。刪除后重新執(zhí)行第一步，直到找到Act_Rt=Rt的路徑。經過多次循環(huán)找到Act_Rt=Rt的路徑：（1，5）（5，14）（14，18）（18，19）（19，20），風險值為8，成本為21。這條路徑成為最優(yōu)解的候選路徑。要想將候選路徑確定為最佳路徑，需要檢查最優(yōu)解是不是唯一。（見圖5-2）

經過搜索，發(fā)現(xiàn)本文Act_Rt=Rt的路徑只有一條，候選路徑穩(wěn)定，于是確定其為最優(yōu)解。算法得到了最優(yōu)解，驗證了它的有效性。

（2）結果分析

本文共通過四次循環(huán)，找到了最優(yōu)路徑，即找到最小成本路徑的實際風險值Act_Rt=Rt的路徑，如表5-1所示：

第四次循環(huán)后，最小成本路徑有三條，即1～5～1 4～1 8～1 9～2 0，1～5～9～1 4～1 8～1 9～2 0，1～2～3～6～12～17～20；其實際風險值分別為8，10，15，而目標風險值R=8，所以Act_Rt=Rt的路徑為1～5～14～18～19～20。找到了最優(yōu)路徑。

（作者單位：中國民航大學）

參考文獻：

[1]儲慶中，張家應，謝之權．基于雙層規(guī)劃的危險品道路運輸網絡設計[J]．重慶交通大學學報(自然科學版)，2010，04：597～603．

[2]孫敬．危險貨物道路運輸路徑優(yōu)化雙層規(guī)劃模型研究[D]．華東交通大學，2012．

[3]曾意．國內危險品物流現(xiàn)狀調查[J]．中外物流，2007，04：33～35．

[4]宋杰珍，丁以中，孟林麗．基于雙層規(guī)劃的危險品運輸網絡設計[J]．上海海事大學學報，2006，02：56～59．

[5]Jeorslone R G． The polynomial hierarchy and simple m od le for competitive analysis[ J] ． Mathematical Programming， 1985，32：146 ～ 164．

[6]Erhan Erkut， Fatma Gzara． Solving the hazmat transport network design problem[R]，Science Direct，2007．