基于政府管制的危險(xiǎn)品運(yùn)輸?shù)碾p層規(guī)劃設(shè)計(jì)

文/姜嘉艷

?

基于政府管制的危險(xiǎn)品運(yùn)輸?shù)碾p層規(guī)劃設(shè)計(jì)

文/姜嘉艷

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

關(guān)鍵詞：危險(xiǎn)品運(yùn)輸；網(wǎng)絡(luò)設(shè)計(jì)；雙層規(guī)劃；數(shù)值模擬

1.研究背景

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

2.危險(xiǎn)品運(yùn)輸?shù)奶攸c(diǎn)

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

3.危險(xiǎn)品運(yùn)輸問題描述及模型設(shè)計(jì)

（1）問題描述

在本文對危險(xiǎn)品運(yùn)輸網(wǎng)絡(luò)設(shè)計(jì)中，涉及兩個(gè)角色：當(dāng)?shù)卣瓦\(yùn)營商。當(dāng)?shù)卣概删W(wǎng)絡(luò)，運(yùn)營商選擇路線。政府代表第一層，限制路段的通行以控制路網(wǎng)上的風(fēng)險(xiǎn)；運(yùn)營商代表第二層，在可行的路網(wǎng)上選擇成本最小化的路徑。一旦政府決定了路網(wǎng)，運(yùn)營商將在此路網(wǎng)上，選擇在始發(fā)地和目的地之間成本最小的路線，政府通常不對運(yùn)營商規(guī)定路線，因此政府在設(shè)計(jì)中加入運(yùn)營商選擇成本最低路線的自由。這種情況引起了雙層規(guī)劃問題[4]。

（2）假設(shè)條件及相關(guān)參數(shù)

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

（3）模型設(shè)計(jì)

目標(biāo)（1）是政府最小化網(wǎng)絡(luò)上的總風(fēng)險(xiǎn)，而（3）為運(yùn)營商最小化成本。約束（2）表示如果（i，j）或（j，i）中有任何一個(gè)路段用于貨物運(yùn)輸，則兩個(gè)路段均開放使用。約束（4）確保危險(xiǎn)品k從起點(diǎn)運(yùn)達(dá)終點(diǎn)。約束（5）確保運(yùn)營商選擇的路徑是由政府選定的。約束（6）是二進(jìn)制要求的變量。

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

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

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

（2）算法設(shè)計(jì)

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

第一步在At上找到運(yùn)輸車輛的最小風(fēng)險(xiǎn)的路徑。

記xt和Rt分別為危險(xiǎn)品k對應(yīng)的最優(yōu)解和風(fēng)險(xiǎn)值。如果x=1 或x=1，則設(shè)置y=1。

第二步在At上找到運(yùn)輸車輛的第二條最小風(fēng)險(xiǎn)路徑。

在找到的最小風(fēng)險(xiǎn)路徑中，刪除最大風(fēng)險(xiǎn)的路段，然后在新的路網(wǎng)中，找出最小風(fēng)險(xiǎn)路徑，這條路徑即為原路網(wǎng)的次風(fēng)險(xiǎn)路徑。

第三步在At上找到運(yùn)輸車輛的第三條最小風(fēng)險(xiǎn)路徑。

在找到的第二條最小風(fēng)險(xiǎn)路徑中，刪除最大風(fēng)險(xiǎn)路段，然后在新的路網(wǎng)中，找到最小風(fēng)險(xiǎn)路徑，這條路徑即為原路網(wǎng)的第三條最小風(fēng)險(xiǎn)路徑。

第四步在At上找到運(yùn)輸車輛的第四條最小風(fēng)險(xiǎn)路徑。

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

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

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

第六步如果Act_Rt=Rt，那么一個(gè)風(fēng)險(xiǎn)水平為Act_Rt的候選路徑zt確定，進(jìn)入第七步。否則，進(jìn)入第六步。

圖5　-1 模擬網(wǎng)絡(luò)

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

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

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

表5　-1 結(jié)果分析表

如果不只一條，那么進(jìn)入第七步。

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

5.數(shù)值模擬及結(jié)果分析

（1）數(shù)值模擬

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

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

Route1=（1，5）（5，14）（14，18）（18，19）（19，20），風(fēng)險(xiǎn)值R1=8，成本值C1=21；

Route2=（1，5）（5，9）（9，14）（14，18）（18，19）（19，20），風(fēng)險(xiǎn)值R2=10，成本值C2=21；

Route3=（1，3）（3，6）（6，12）（12，17）（17，20），風(fēng)險(xiǎn)值為R3=11，成本值C3=20；

Route4=（1.9）（9，14）（14，18）（18，19）（19，20），風(fēng)險(xiǎn)值R4=13，成本值C4=19；

Rt=8，運(yùn)行結(jié)果顯示其中（1，9）路段為第一次循環(huán)形成的路網(wǎng)中的最高風(fēng)險(xiǎn)路段。

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

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

（2）結(jié)果分析

本文共通過四次循環(huán)，找到了最優(yōu)路徑，即找到最小成本路徑的實(shí)際風(fēng)險(xiǎn)值A(chǔ)ct_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；其實(shí)際風(fēng)險(xiǎn)值分別為8，10，15，而目標(biāo)風(fēng)險(xiǎn)值R=8，所以Act_Rt=Rt的路徑為1～5～14～18～19～20。找到了最優(yōu)路徑。

（作者單位：中國民航大學(xué)）

參考文獻(xiàn)：

[1]儲慶中，張家應(yīng)，謝之權(quán)．基于雙層規(guī)劃的危險(xiǎn)品道路運(yùn)輸網(wǎng)絡(luò)設(shè)計(jì)[J]．重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版)，2010，04：597～603．

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

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

[4]宋杰珍，丁以中，孟林麗．基于雙層規(guī)劃的危險(xiǎn)品運(yùn)輸網(wǎng)絡(luò)設(shè)計(jì)[J]．上海海事大學(xué)學(xué)報(bào)，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．