靜態單點多目標危險貨物運輸路線優化算法研究

章良

[摘要]本文通過對道路危險貨物運輸研究背景的介紹，引出靜態單點多目標危險貨物運輸路線優化問題，進而建立靜態單點多目標危險貨物運輸路線優化模型，并介紹模型的算法過程。

[關鍵詞]單點多目標；危險貨物；路線優化；算法

[中圖分類號]U11[文獻標識碼]A[文章編號]1005-6432（2014）49-0176-02

1研究背景

道路危險貨物運輸作為道路貨物運輸重要的組成部分，是一種技術業務復雜、安全條件要求高的特種運輸。隨著我省經濟和道路運輸的持續、快速發展，以及工農業生產和人民生活水平的提高，對危險貨物的需求越來越大，通過道路運輸的危險貨物的種類、數量不斷增長。

危險貨物運輸車輛在道路上行駛，就相當于“流動危險源”。然而我國對道路危險貨物運輸行業的管理還不盡如人意，行業內還存在各種問題，例如，從業人員的素質低、車輛技術狀況差等，從而引發各種危險貨物運輸事故，并且造成的危害程度也越來越高。

道路危險貨物運輸路線優化可以有效地降低運輸風險。通過合理地規劃運輸路線，選擇事故發生概率較小的路線進行運輸，這樣就可以減少道路危險貨物運輸風險，確保高質量的提供運輸服務。

2問題描述

無論是靜態還是動態的危險貨物運輸路線優化，其根本問題都是從運輸任務起點和終點之間所有可供選擇的路線中選出最佳的運輸路線，在滿足一定的約束條件（如運輸量、可接受風險標準等）下，達到一定的目標（如路程最短、費用最低、風險最小等）。這類問題又可以從兩個方面考慮：首先，“單對單”運輸路線問題，即單一起點，單一終點，單種危險貨物、單一運輸方式的路線優化。另外，還有一種道路危險貨物運輸路線優化問題是“多對多”的運輸路線優化問題，即多個起點、多個終點、多種危險貨物，可以用多種運輸方式分別運輸。從時間因素的角度出發，危險貨物運輸路線優化問題可以分為靜態和動態道路危險貨物運輸路線優化兩種。從優化目標數的角度出發，又可以分為單目標和多目標道路危險貨物運輸路線優化。其中，單目標道路危險貨物運輸路線優化問題已經有完善的解決方法，即經典的最短路線問題模型。

然而，在實際應用當中，僅僅考慮線路最短這一單一目標是不夠的。危險貨物運輸企業都會面臨經營成本增加和公共安全投入的雙重壓力。因此，道路危險貨物運輸路線優化問題也不再單純追求運輸風險最小或單純追求經濟效益（即選取最短路線、最低成本），而是同時考慮經濟效益和運輸安全，使其達到總效益最大。道路危險貨物運輸路線優化問題就演變成一個多目標優化決策問題，決策者可通過合理的規劃選擇能使多個目標同時最優或近似“最優”的路線，使得危險貨物運輸企業在確保運輸安全的前提下，達到經濟效益最優。然而，在危險貨物運輸路線優化過程中，我們所考慮的多個目標經常會相互矛盾，例如運輸費用減少，運輸時間就有可能延長；而運輸時間變短，運輸風險就可能變大。要使這些多目標同時達到最優往往是不可能實現的。在實際運輸過程中，由于受到諸多因素的影響，很難兼顧所有方面來做出決策。也就是說，決策者應該綜合比較分析應該考慮的多個目標，形成幾種可行的方案，并加以權衡，最終選擇一個令決策者較為滿意的方案。

3模型構建

下面我們先研究一下靜態“單對單”多目標道路危險貨物運輸路線優化，其模型可簡化為：

假設G=（M，N）為一個道路危險貨物運輸網絡圖，其中M為節點集合，N為弧的集合，設i， j∈M，則網絡中每條弧則可表示為（i，j）。任意兩節點間的運輸路線則可用Lij={i=i1， （i1， i2）， …， （ik-1， ik）， ik=j}，這個點、弧交錯的序列來表示，假設弧段（i，j）上賦有S維目標向量uij=（u1ij， u2ij， …， usij），向量中的元素usij表示弧段（i，j）的第s個目標變量值。則可用s維目標向量uLod=（u1Lod， u2Lod， …， usLod）來評價從起點o到終點d的道路危險貨物運輸路線Lod的優劣程度。因此，從起點o到終點d間，考慮s維目標的道路危險貨物運輸路線優化問題的數學模型可表述為：

第一個表達式表示尋找滿足s維目標向量非劣的道路危險貨物運輸路線；第二個表達式則是確保危險貨物運輸的流向是從起點到終點；第三個表達式則是限定判斷變量yij的取值范圍，當yij=1則表示節點i和節點j間存在運輸任務，當為yij=0則表示節點i和節點j間不存在運輸任務。

4算法過程

危險貨物運輸路線多目標優化一般情況下包括一組不能同時達到最優的目標或沖突的目標，找到能使全部目標同時最優的最優路線是幾乎不可能實現的，往往只存在一組有效路徑解集。解決多目標路線優化問題時，常見的解決方法是利用權重將多目標路線優化問題經過加權調整轉化為單目標最短路問題求解。權重的確定帶有很大主觀性，因此，最后確定的最優路線往往帶有很強的主觀性，會隨著決策者的意愿發生改變。為了盡量消除主觀因素對路線抉擇的影響，引用灰色關聯度理論，利用啟發式算法，在無法獲得絕對最優路線的條件下，構建虛擬的絕對最優路線目標向量，找出接近該虛擬最優路線來獲得滿意解。其具體步驟可分為：

第一步，構建特征值矩陣。

把多目標問題轉換為單目標問題，分別將單目標最短路問題一一解決，則S個不同目標函數需要連續進行S次。假設利用最短路算法求得S個目標所對應的最短路線共有N條，則可以構建N個路線方案的S個目標的特征值矩陣X。

第二步，確定虛擬的絕對最優路線的目標向量。

由于所追求的目標不同，路線的S維目標變量可劃分為越小越好型和越大越好型兩大類。顧名思義，對于越小越好型目標，其值越小越好，反之則越大越好。假設X0為灰色關聯分析的絕對最優目標向量，即X0=（x01， x02， …， x0P）。在第一步里構建的特征值矩陣X中加入向量X0，構造（N+1）×S階目標特征值矩陣。

第三步，進行規范化處理。

在目標特征值矩陣中的各個目標的物理意義不同，導致數據的量綱也不全相同，這就導致比較時較難獲得正確的結果。要保障所求各目標具有等效性和同序性，這就需要處理原始目標特征值矩陣，也就是將原始目標特征值矩陣無量綱化和歸一化。原始目標特征值矩陣經過規范化處理則可相應地轉化為T=（tij）（N+1）×S，向量X0則轉化為靶心T0=（1， 1， …， 1）。

第四步，確定差異信息空間。

通過公式Δij=1-tij處理規范化后的目標特征值矩陣T=（tij）（N+1）×S，就可得到新的（N+1）×S階差異信息矩陣。新構建的差異信息矩陣的所有元素中，最大值稱為兩極最大差Δmax；反之則稱為兩極最小差Δmin。由此，其差異信息空間可以表示成ΔCR=（Δ， ρ， Δmax， Δmin）， 上述公式中：Δ為全體差異信息，ρ為分辨系數，ρ∈（0，1），通常情況下為0.5。

第五步，計算灰色關聯度。

假設我們把xij和x0j在第j個目標上的靶心系數表示為ζ0i（j），就可以得到：

第六步，將各方案按照灰色關聯度大小進行排序。關聯度越大，則相應的運輸路線方案越好。

參考文獻：

[1]任常興，吳宗之.危險品道路安全運輸路徑優化方法探討[J].中國安全科學學報，2006，6（16）：129-134.

[2]郭曉琳，李軍.基于事故分級的有害物品運輸路徑風險度量模型研究[J].中國安全科學學報，2006，16（6）：35-39.

[3]沈小燕.道路危險貨物運輸風險分析及路線優化研究[D].西安：長安大學，2009.