路徑-脆弱點最短距離最大化的危險品運輸網絡設計*

項 寅, 姜冠群

(上海財經大學 商學院，上海 200433)

0 引言

危險品交通運輸事故容易造成重大人員財產損失，因此如何降低危險品運輸風險，受到了學術界的大量關注和廣泛研究。相關研究以危險品運輸風險評估[1-3]為起點，逐步拓展到危險品運輸路徑優化[4-5]、網絡設計[6-8]、應急設施選址[9]，以及恐怖襲擊下的危險品運輸優化問題[10]。其中，網絡設計和風險評估與本文緊密相關。

目前，危險品運輸網絡設計思路大體包括2類。第1類思路采用關閉路段的方法來禁止危險品車輛行駛于覆蓋人口較多的路段之上，以此降低車輛路徑的風險，該方法首先由Kara和Verter提出[6]，主要針對靜態網絡展開研究并利用雙層理論構建模型；后續學者則進一步考慮了運輸風險和行駛路徑之間的折中方案選擇[8]、網絡設計中的分流站點選址規劃[11]，以及隨機和時變情形下的危險品運輸網絡設計[12-13]。第2類思路則通過征收過路費的方式來控制和約束危險品車輛的行駛路徑，Marcotte等是該方法的提出者[14]，相關拓展研究進一步考慮了承運商的路徑偏好[15]及其在鐵路網絡中的應用[16]。

現有危險品運輸風險的計算方法主要包括事故率風險模型[1]、傳統風險模型[2]、條件風險模型[3]、人口覆蓋率風險模型[17]等。這些風險模型從事故率、事故后果、人口分布這3個角度來實現風險度量，而目前的危險品運輸網絡設計研究則較多采用了人口覆蓋率風險。

通過文獻綜述發現：現有危險品運輸網絡設計仍有2方面不足，一方面是常用的人口覆蓋率風險忽略了脆弱點和距離這2類因素，此處脆弱點是指分布在道路兩旁的人口集聚且難以快速疏散的場所，例如，當某路段周圍脆弱點的人口分布較多，但是分布人群離開該路段的距離較遠時，其風險可能小于另一條周圍人口分布較少，但人群距離較近的路段；另一方面是現有研究大多以最小化運輸風險為決策目標，通過壓縮承運商經濟利潤來降低風險，而關于兼顧風險-成本的優化模型及算法則仍然有待完善。

本文將Bronfman等[18]提出的1類危險品道路風險評估方法引入危險品運輸網絡設計研究中，通過脆弱點和運輸路徑間的加權距離來度量風險，實現人口分布和距離這2類風險影響因素的聯合考慮；設計1類啟發式算法，該算法結合具體算例可在多項式時間內獲取最優解、次優解、…、第k優解，為尋求兼顧運輸風險和運輸成本的優化方案提供決策支持。

1 基本分析

本文主要考慮的危險品種類為發生泄漏事故后可產生大面積擴散的有毒氣體，如液氯等。一旦此類事故發生，道路兩旁的脆弱點(如醫院、學校、購物中心、居民區等)中往往集聚著大量人群，其不易在短時間內疏散，故很容易因有毒氣體的擴散而受到危害。在有毒氣體參數和氣象環境給定的情況下，對應濃度及危害程度往往和相離事故點的距離緊密相關。在該情景下，由于傳統風險評估方法[1-3,17]無法著重反映脆弱點和距離等實際因素，因此本文參考文獻[18]并將危險品運輸路徑和各脆弱點間的加權距離作為風險界定方法，加權距離越小，風險系數越大。

危險品運輸網絡設計所需解決的問題為：給定某交通拓撲網絡，在各路段的周圍分布著一些醫院、學校、公園景點、購物中心之類的“脆弱點”，且每個脆弱點存在1個權重，反映為該地點的人口數量。承運商選擇源匯點間的最短路徑來實現危險品的運輸，政府則需通過關閉網絡中的部分路段，來控制和約束承運商的運輸路徑，并使之最大程度地遠離各脆弱點，即最小化運輸風險。

與經典危險品運輸網絡設計問題[6]相同，上述問題同樣是1個典型的雙層規劃問題。如圖1所示，政府處于領導地位，其決策屬于上層規劃，通過關閉交通網絡中的一些路段來最大化危險品運輸路徑和各脆弱點間的最小加權距離；承運商處于從屬地位，其決策屬于下層規劃，需在政府給定的危險品運輸網絡下，決策源匯點間的最短路徑，以最小化其運輸成本。

圖1 雙層規劃模型結構示意Fig.1 Structure of the bi-level programming model

2 問題描述

3 數學模型

將上述問題構建為如下雙層規劃模型：

(1)

(2)

(3)

(4)

(5)

xij∈{0,1},?(i,j)∈A

(6)

(7)

其中，yij為下層規劃的解

(8)

(9)

yij≤xij,?(i,j)∈A

(10)

yij∈{0,1},(i,j)∈A

(11)

式(1)～(7)是關于政府的危險品運輸網絡設計問題，式(8)～(11)則是承運商在給定危險品運輸網絡下的最短路徑決策問題。

上層規劃中，目標式(1)表示最大化路徑和脆弱點間的最小加權距離δ；而約束式(2)保證了δ一定是危險品運輸路徑與所有脆弱點間的最小加權距離；約束式(3)確保分配給脆弱點p的加權距離最小的路段是唯一的；約束式(4)為最近指派約束，保證分配給脆弱點p的路段一定是離開其加權距離最小的；約束式(5)確保被分配的路段必須為承運商的通行路段。下層規劃中，目標式(8)表示最小化危險品運輸路徑的總距離；約束式(9)為流量平衡約束，保證承運商選擇的各通行路段可以合并為源匯點間的一條連通路徑；約束式(10)限制承運商只能選擇開放的路段行駛。

4 算法設計

雙層規劃是典型的NP-難題。為求解上述危險品運輸網絡設計模型，本文設計1類啟發式算法。

4.1 符號說明

4.2 算法思路

該啟發式算法包括2個階段。

1)第1階段：確定風險最小，即離開所有脆弱點的最小加權距離最大的路徑。按θij從小到大，即風險由高到低的順序，依次對各路段(i,j)關閉，每次迭代僅關閉1條路段并逐步累加。每次迭代移除關閉路段后，用dijkstra算法求解源匯點間的最短路徑，若路徑存在，進入下1次迭代，若路徑不存在或網絡不聯通時，停止迭代并將前1次迭代所得路徑作為風險最小的運輸路徑。

2)第2階段：修正第1階段的路段關閉方案。由于第1階段采用貪心法逐一關閉路段，故會產生一些“無效”方案。在所有被關閉路段中，按θij從大到小，即風險由低到高的順序依次進行開放，每次迭代僅開放1條路段并逐步累加。每次迭代開放相應路段后，用dijkstra算法求解源匯點間的最短路徑，若該路徑和第1階段得到的最小風險路徑相同，說明開放當前路段不增加風險，開放該路段并進入下1次迭代；若2條路徑不同，說明開放當前路段會增加風險，則仍然保持該路段的關閉狀態，并進入下1次迭代。直到所有在第1階段中被關閉的路段都得到1次“開放測試”后，所保留下的被關閉的路段就為政府最優的路段關閉方案。

4.3 算法步驟

啟發式算法的具體步驟如下：

4)步驟4：最優解確定。得到optC為政府最優的路段關閉方案，相應的承運商行駛路徑則為optR。

4.4 算法性質

1)性質1：算法是收斂的，且路段關閉方案optC下的危險品運輸路徑optR一定為風險最小的路徑，即離開所有脆弱點的最小加權距離最大的路徑。

證明：由步驟2看出，隨著迭代的進行，交通網絡中的路段按照其與所有脆弱點加權距離θij由小到大的順序依次被關閉。那么，在剩余的開放路段中，路徑R和所有脆弱點間最小加權距離θR的下界會不斷增加，并等于剩余開放路段中最小的θij值，又由于每次迭代都是在上1次迭代的基礎上，繼續關閉1條θij最小的路段，因此上述加權距離θR的值會不斷增加。顯然，有限數量的迭代后，隨著關閉路段數量的增加，網絡不再連通，此時算法停止，且θR收斂到最大的1個值。

2)性質2：算法的計算時間復雜性為O(2|A||N|2)。

證明：顯然，整個算法的主要計算時間復雜性存在于步驟2～3中的迭代過程。

首先，用dijkstra算法計算2點間最短路徑的計算時間復雜性為O(|N|2)。

其次，步驟中最壞的情況是依次關閉|A|-1條路段，即進行|A|-1次迭代，而每次迭代最主要的計算時間成本在于dijkstra算法的執行。

最后，步驟3中最壞的情況需依次開放|A|-1條之前被關閉的路段，即進行|A|-1次迭代，而每次迭代最主要的計算時間成本同樣為dijkstra算法。

綜上所述：算法的計算時間復雜性就為O(2·(|A|-1)·|N|2)～O(2|A||N|2)。

4.5 算法拓展

改進算法第1階段，不再要求達到網絡不連通或最短路徑不存在時才停止迭代，而是要求當前迭代所得路徑和上次迭代所得路徑不同時進入第2階段的修復過程。這樣，第1階段就記錄下了各類風險值下的運輸路徑，第2階段通過修正就進一步得到風險最大、次大、第k大路徑所對應的路段關閉方案。具體應用將在算例分析部分展示。

5 算例分析

5.1 算例描述

本文以包含20個節點、31條邊和10個脆弱點的拓撲網絡為例進行算例分析，如圖2所示。其中，節點2和節點18分別為承運商的起點O和終點D。各脆弱點p的人口權重Dp如表1所示，每個脆弱點表示為不同灰度的圓，將脆弱點的坐標定義為圓的中心位置，用其半徑來表示該脆弱點到臨近路段的最小歐式距離，而其著色深度和表示符號則對應了不同大小范圍的人口權重。每條邊(i,j)的長度lij及各邊和所有脆弱點間的最小加權距離θij如表2所示。

圖2 20個節點的拓撲網絡Fig.2 A topological network with 20 nodes

p12345678910Dp1682411201541192

在實際應用中，脆弱點的中心位置通常可取作醫院、學校等設施的坐標中心位置，而脆弱點的人口權重則可近似為對應場所的常住人口數、日客流量等。

5.2 計算過程演示

表2 各路段的長度及其距所有脆弱點的最小加權距離Table 2 Length of all road segments and their weighted distance from all vulnerable zones

表3 啟發式算法第1階段迭代過程Table 3 The first stage iteration process of heuristic algorithm

隨著迭代次數的增加，政府關閉的路段數不斷增多，承運商的運輸路徑發生改變，路徑的風險系數逐漸降低但路徑長度不斷變長。當進行到第3,6,7,10,19次迭代時，分別產生了風險最大的、次大的……第5大的路徑方案及對應的路段關閉方案。直到第20次迭代，源點和匯點間不存在開放的路徑，此時算法第1階段計算停止，將第19次迭代所得到的路徑2-3-4-20-19-18作為風險系數最小的路徑，并轉入第2階段計算。

算法第2階段針對第1階段第19次迭代中所有關閉的18條路段逐一進行“開放”測試，如果開放后的運輸路徑與開放前一致，則開放該路段，否則仍保留關閉狀態，迭代信息如表4所示。

如表4所示，當算法第2階段進行到第7,10,13,16次迭代時，開放測試路段會改變原有路徑并減少路徑和脆弱點間的最小加權距離，因此仍然保留路段(4,8)(3,7)(2,6)(1,5)的關閉狀態，并得到了運輸路徑風險系數為最小值2.7時的政府路段關閉方案。

結合表3～4發現，算法經過38次迭代后即收斂至最優解，驗證了4.4節性質1的正確性，且對應4.4節性質2，每次迭代僅需計算新增“被關閉路段”或“被開放路段”后的最短路徑，其計算時間成本與脆弱點個數無關，且計算時間復雜性滿足多項式函數形式。

5.3 最優決策

同理，根據表3依次選擇在第3次、第6次、第7次、第10次迭代時停止算法第1階段計算并轉入第2階段，進而可得到風險系數分別為7.4、6.3、5.2和4.4時的運輸路徑及對應的路段關閉方案。匯總整理所有可行方案并記錄于表5。

表4 啟發式算法第2階段迭代過程Table 4 The second stage iteration process of heuristic algorithm

表5 可行方案及其加權評分Table 5 Summary of all feasible solutions and their weighted score

表5包含6類可行方案，隨著序號的上升，對應方案下的風險系數不斷下降但行駛距離逐漸增加。為尋求兼顧運輸風險和運輸成本之間的最優方案，政府可通過加權評分法來實現最終決策。首先，對風險系數和行駛距離數據進行歸一化處理并用于消除量綱；其次，結合實際情況分配權重，例如分配給風險系數的權重為0.6而行駛距離的權重為0.4；最后，對表中的第7列和第8列數據進行加權求和，并選擇總得分最高的方案。本算例中，由于方案3的總得分最高，因此該方案最終入選。

6 結論

1)針對已有危險品運輸網絡設計問題進行拓展，考慮1類新的風險評估方法，通過計算路徑和脆弱點間的最短加權距離來評估路徑風險系數，兼顧路徑兩側的人口因素和脆弱點的距離因素。利用雙層理論構建模型，并設計啟發式算法求解。

2)通過算例分析發現：該啟發式算法經過有限次數的迭代即可獲取風險系數最小、次小、第k小的路徑及其對應的路段關閉方案，進一步利用加權評分法即可獲取最優方案，為尋求兼顧運輸風險和運輸成本間的最優方案提供決策支持。

3)未來研究可考慮多源多匯的情形，并對啟發式算法進行改進；可進階考慮運輸過程涉及多類危險品的情形，改進模型并對脆弱點設置不同的屬性類別，以實現各類危險品運輸的分類管理；也可針對行駛成本、脆弱點權重的隨機或時變特征展開研究，提出隨機/時變模型并更好地擬合現實情景。