帶時間窗的危險品運輸?shù)缆肪W絡設計

劉苗苗，韓曉龍

(上海海事大學 物流研究中心，上海 201306)

危險品是易燃易爆有劇烈腐蝕性物品的統(tǒng)稱，危險品運輸通常由專門組織或者技術人員對非常規(guī)物品采用特殊車輛進行運輸并經過國家相關職能部門嚴格審核，因此在危險品運輸?shù)难芯繂栴}中政府監(jiān)管部門是上層決策者。由于危險品特殊的屬性，危險品運輸過程中一旦發(fā)生事故且得不到及時的控制，會嚴重威脅周邊人群的財產、生命安全，破壞生態(tài)環(huán)境。隨著我國化工產業(yè)的發(fā)展，危險品道路運輸顯著增多，如何降低危險品運輸過程中的事故風險越來越為公眾所關注，而危險品運輸網絡設計是一種有效的途徑。

現(xiàn)有國內外的文獻對危險品運輸?shù)缆返难芯看蟛糠旨性诼窂絻?yōu)化、風險評估及應急等方面，而關于危險品運輸網絡設計的文獻比較少。LIST等[1]對有害物質(危險品)道路運輸風險評價和運輸路線選擇進行了系統(tǒng)的分析。REN等[2]提出并分析了易燃易爆危險品道路運輸?shù)膽表憫燃壞Ｊ?。MAHMOUDABADI等[3-4]主要運用混沌迭代過程理論，基于不同風險屬性的優(yōu)先級確定目標函數(shù)，建立危險品路徑選擇模型。于建平等[5]在一般雙層規(guī)劃求解的基礎上運用了雙層遺傳算法求解雙層問題。李昌兵等[6]針對非線性雙層問題，提出了基于層次粒子群算法的求解策略。KARA等[7]最早提出了雙目標-雙層模型，并使用庫恩-塔克條件和線性化補充松馳條件代替下層規(guī)劃，將雙層整數(shù)規(guī)劃模型轉化為單層的混合整數(shù)規(guī)劃模型進行求解。ERHAN[8]將危險品運輸網絡設計問題描述成Steiner樹問題，并使用加權求和的方式來最小化網絡總運輸風險和成本。儲慶中等[9]初次將遺傳算法用于危險品道路運輸路徑網絡設計中。蔣洋[10]采用粒子群算法對危險品運輸網絡設計問題進行求解。張麗娜[11]在一般危險品運輸網絡雙層規(guī)劃模型的基礎上建立雙層多目標模型，提出了特定的危險品在特定路段采取征收費用的危險品運輸路徑網絡設計，并借鑒啟發(fā)式算法進行求解，但是在模型中上層決策者沒有兼顧運輸企業(yè)運輸成本最小化的目標且僅針對一類危險品。

筆者在兼顧政府監(jiān)管部門和運輸企業(yè)的基礎上，建立了基于不同危險品特定路段征收特定費用的模型，且在一般網絡設計模型的基礎上考慮時間成本，并用Lingo進行求解。

1　危險品運輸網絡設計分析

在危險品運輸?shù)缆肪W絡設計中,通常是考慮一個擁有一定數(shù)量的起點和終點(目的地)的城市道路網絡。當然,對于多個城市之間的運輸網絡的設計也同樣適用。危險品運輸網絡有兩個決策體：政府監(jiān)管部門和運輸企業(yè)，當?shù)卣O(jiān)管部門指定運輸網絡，運輸企業(yè)在指定的網絡中選擇運輸路線。因此科學的危險品運輸?shù)缆肪W絡設計應是上層決策者(政府監(jiān)管部門)實現(xiàn)決策中主要目的即風險最小化,同時也應考慮運輸企業(yè)成本最小化的路徑選擇行為；而運輸企業(yè)在上層決策的基礎上選擇運輸路線，是實現(xiàn)主要目的成本最小化。這種情況構成了雙層設計問題,政府監(jiān)管部門代表第一層，運輸企業(yè)代表第二層?；诖?筆者針對不同種類危險品，提出了帶時間窗的危險品運輸?shù)缆肪W絡設計問題。

2　危險品運輸網絡雙層規(guī)劃模型

用有向圖G=(V,A)代表現(xiàn)有的道路運輸網絡，節(jié)點集合用V表示，節(jié)點代表道路交叉口;路段集合用A表示，一條邊代表一個路段。有m種危險品通過網絡G=(V,A)自起點o∈N到終點d∈N進行運輸，該網絡設計問題是在G上尋找一個包含k個運輸任務的網絡，運輸企業(yè)以成本最小為原則選擇線路，政府監(jiān)管部門以期望的總風險最小為原則選擇線路。每個運輸任務對應一對起訖點。用(i,j)表示路段，點i、j∈V,(i,j)∈A。o(k)、d(k)表示第k個任務的OD，k∈{1,2，…,K}，點o,d∈V。

在此基礎上建立了改進后的帶時間窗的危險品運輸?shù)缆肪W絡0-1模型，式(1)為上層規(guī)劃目標函數(shù),表示政府期望網絡總風險最??；式(2)表示任何一種危險品經過任何一條路段所征收的費用為正數(shù)；式(3)表示政府監(jiān)管部門在每條路段上的風險期望限制,防止路段風險超過允許風險上限；式(4)表示上層決策變量的0,1約束。

(1)

(2)

(3)

(4)

下層數(shù)學模型中，式(5)為下層目標函數(shù), 表示運輸者期望的總運輸成本最小，通過對不同的危險品及路段設置不同的通行費用使危險暴露人口與運輸成本達到綜合最小化,實現(xiàn)期望運輸成本和風險損失最小；式(6)表示運輸網絡實現(xiàn)流量均衡, 保證貨物運出和到達目的地；式(7)表示運輸企業(yè)只能在政府監(jiān)管部門開放的路段中選擇路線；式(8)表示下層決策變量的0,1約束。

(5)

?j∈V,k∈{1,2,…，K}

(6)

(7)

(8)

雙層規(guī)劃問題通常是一個NP-hard問題。筆者建立的模型是一個混合整數(shù)線性規(guī)劃(MILP)，可直接利用Lingo軟件進行求解，確定科學的危險品運輸?shù)缆肪W絡。

3　算例分析

假設某一地區(qū)有一既定的網絡圖，如圖1所示。為簡化計算，假設所有運輸任務的期望事故影響后果和期望經濟承擔相同，每個運輸任務的時間窗已知，各運輸任務運輸車輛均為1輛。每條路段的影響后果C用影響范圍內的暴露人口數(shù)量表示，每條路段的單位運輸成本如表1所示。為了阻止運輸企業(yè)選擇風險較大的路段(3，4)和(6，5)，政府在路段(3，4)征收1個單位的通行費，在路段(6，5)征收2個單位的通行費。

圖1　運輸網絡

路段(1,2)(2,3)(2,6)(3,4)(3,5)(7,6)(6,5)(6,8)(5,4)(5,9)事故影響后果/萬人1114115111運輸成本/萬元1113311111

假設該運輸網絡中有3個運輸任務(K1:2→4,K2:7→9,K3:1→8)，并且規(guī)定了每個任務的時間窗及相應的懲罰成本，具體數(shù)據(jù)信息如表2所示。通過Lingo求解得到: 總的期望損失R=3, 總的運輸成本C=100。政府及運輸企業(yè)的決策如表3所示。

由表3可以看出，對于任務2→4，在政府對路段(3,4)征收1個單位通行費，對路段(6,5)征收2個單位通行費的限制條件下，運輸企業(yè)選擇的最優(yōu)路徑為2→3→5→4，求解的總風險R=3，總成本C=100;任務1→8和7→9都只有一條可通行的路徑，分別為7→6→5→9和1→2→6→8。

如果采用一般的網絡設計方法(政府監(jiān)管部門對于風險較大路段禁止通行)和政府對運輸企業(yè)不進行管制(即運輸企業(yè)以成本最小化為目標可在既定道路網絡上自由選擇),求解得到運輸企業(yè)在3種策略下的最優(yōu)路徑結果，如表4所示。

表2　運輸任務及相關數(shù)據(jù)

表3　政府及運輸企業(yè)的最終決策

表4　3種策略下的最優(yōu)路徑結果對比分析

從表4可以看出通過3種網絡方案設計比較，筆者所建立的到時間窗危險品運輸網絡雙層規(guī)劃模型，通過對特定的危險品在特定路段征服收通行費的策略可以有效協(xié)調風險和成本。

通過設置路段通行費，可以阻止一部分運輸企業(yè)使用此路段，而其他運輸同種危險品的運輸企業(yè)依然可以選擇此路段。但一般的網絡設計方法就沒有這種靈活性，所有運輸同種危險品的運輸企業(yè)的路徑都是一樣的。因此可以說特定路段設置高額通行費策略比一般的網絡設計要好。

4　結論

筆者建立了帶時間窗的危險品運輸雙層規(guī)劃模型，通過對特定路段收取通行費有效協(xié)調運輸網絡中的風險和成本。建立模型時充分考慮現(xiàn)實決策中諸多實際因素，首次在模型約束條件里加入了時間窗,考慮運輸企業(yè)運輸過程的時間成本，使模型更接近實際。結合一個具體算例進行分析，經過對危險品運輸網絡設計的一般措施進行比較，證明了雙層規(guī)劃模型用于危險品運輸?shù)缆肪W絡設計的有效性。在實際中獲取數(shù)據(jù)并進行大規(guī)模的案例求解是以后研究的方向。

參考文獻：

[1]LIST G F, MIRCHANDANI P B,TURNQUIST M A, et al. Modeling and analysis for hazardous materials transportation: Risk analysis, routing / scheduling and facility location[J] .Transportation Science, 1991,25(2):100-114.

[2]REN C, YUAN X，WANG J, et al. Study on emergency response rank mode of flammable and explosive hazardous materials road transportation[J].Procedia Engineering, 2012,45(2):830-835.

[3]MAHMOUDABADI A，SEYEDHOSSEINI S M .Developing a chaotic pattern of dynamic Hazmat routing problem[J]. Iatss Research,2014,37(2):110-118.

[4]MAHMOUDABADI A，SEYEDHOSSEINI S M. Solving hazmat routing problem in chaotic damage severitynetworkunderemergencyenvironment[J].Transport Policy,2014(36):34-45.

[5]于建平,杜綱.一類雙層規(guī)劃問題的遺傳算法求解[J].重慶理工大學學報(自然科學),2013,28(4)：93-98.

[6]李昌兵,杜茂康，付德強.基于層次粒子群算法的非線性雙層規(guī)劃問題求解策略[J].系統(tǒng)工程理論與實踐,2013,33(9)：2292-2298.

[7]KARA B Y, VERTER V. Designing a road network for hazardous materials transportation [J]. Transportation Science, 2004,38(2):188-196.

[8]ERHAN E, GZARA F. Solving the hazmat transport network design problem [J] . Computer s & Operations Research, 2008,35(7):2234-2247.

[9]儲慶中,劉玉兵,吳國君.基于遺傳算法求解的道路危險品運輸線路優(yōu)化雙層規(guī)劃模型[J].交通信息與安全,2011,29(2):95-99.

[10]蔣洋.基于結構和隨機特性的交通網絡設計問題研究[D].北京:北京交通大學,2011.

[11]張麗娜.道路危險品運輸網絡設計模型與算法研究[D].蘭州：蘭州交通大學,2013.