帶時間窗約束的道路危險品運輸路徑選擇研究

(西南交通大學 交通運輸與物流學院，四川 成都 610031)

0 引言

危險品(Hazardous chemicals)是一種具有物理、 化學或是生物特性的物品，它容易在生產、儲存、運輸中引起燃燒、爆炸、中毒等災害事故。隨著工業(yè)的發(fā)展，危險品的生產量和運輸量均在逐年增加。

在國外，危險品運輸路徑選擇問題已經成了一個非?；钴S的研究領域，引起了很多學者的關注。Current[1]等提出了一個雙目標模型，最小化路徑包括人口數(shù)和最小化行駛里程，產生連接于預先確定的OD組合權衡交換曲線。Abkowitz M和Cheng P[2]提出了一個考慮風險和成本的雙目標路徑模型，并綜合風險與成本組成了一條對單個OD組合的Pareto最優(yōu)路徑。在我國，任常興[3]構建了最小化運輸事故概率和暴露人口風險模型，應用權數(shù)調整節(jié)點標號算法和邊線標號算法解決危險品道路運輸選線。王妍霞[4]綜合考慮事故所造成的損失最小和運輸成本最小時，運輸方式和運輸路徑的選擇方法。馬昌喜[5]以運輸風險、運營時間及敏感目標人數(shù)最小化為目標，建立了危險品公路運輸路徑多目標決策模型，然后用擴展標號法[6]計算最優(yōu)折衷解。

縱觀國內外現(xiàn)狀可知，目前在危險品配送網(wǎng)絡路徑選擇研究中已經取得了一些成果，但現(xiàn)有研究成果忽略了危險品運輸過程中的動態(tài)性，即沒有考慮危險品在道路運輸?shù)南臅r間隨時段的不同而改變，以及時間窗的約束。本文將在時間窗和運輸時間動態(tài)變化的條件下，研究危險品運輸路徑的優(yōu)化選擇。

1 優(yōu)化模型

研究的問題描述如下：在一個城市道路運輸網(wǎng)絡中，假設每種運輸方式在各路段上發(fā)生事故的概率以及事故所造成的損失已知，各路段上不同時段的危險品的運輸時間已知?，F(xiàn)有多種流向的危險品要從相同的起訖點運輸?shù)讲煌慕K點，每一個OD之間都有多條運輸路徑可以選擇，在綜合考慮運輸社會總期望損失和運輸成本的情況下，如何確定各種流向危險品的運輸路徑。

1.1 模型假設

為降低運輸成本和倉儲成本，明確層次和關系以方便管理，對于危險品配送網(wǎng)絡來講，一般有如下要求：

(1)為了方便網(wǎng)絡中危險品配送的運輸，所有危險品必須從起訖點發(fā)出，目標節(jié)點相互間不存在危險品的調配運輸。

(2)各個OD的危險品的運輸量由其目標節(jié)點所在的地的需求量決定，而且危險品到達倉庫時需滿足其時間窗的約束。

(3)為了簡化研究問題，假設網(wǎng)絡中只有一種危險品需要運輸，且同一流向危險品的運量在某兩節(jié)點之間不能分割。

1.2 抽象描述

圖1 現(xiàn)代危險品物流配送網(wǎng)絡

在建立優(yōu)化模型前，首先對運輸網(wǎng)絡G=(V,E,R)的拓撲結構進行抽象描述，其中,V表示節(jié)點集合，E表示有向弧集合，R表示弧的權重集合。將圖中的節(jié)點和連接這些節(jié)點的道路分別類比為網(wǎng)絡中的頂點和有向弧，某城市物流運輸網(wǎng)絡簡圖如圖1所示。

頂點集V包括危險品運輸網(wǎng)絡中的起訖點、轉運節(jié)點以及目標節(jié)點，所有OD流向的首末節(jié)點表示運輸網(wǎng)絡中的起訖點與目標節(jié)點，其余節(jié)點即為運輸網(wǎng)絡中的轉運節(jié)點；有向弧E為起訖點、轉運節(jié)點以及目標節(jié)點之間的連接弧；弧權重R包括危險品通過該路段所造成的風險R1、影響人數(shù)R2以及消耗時間R3。

1.3 符號說明

(1)已知常量。令f表示網(wǎng)絡中危險品的某種流向，o(f)為第f種危險品流向的起訖點，d(f)為第f種危險品流向的目標點，所有流向的集合即為F，即f∈F；plf表示第f種流向的危險品在網(wǎng)絡G中的第l條可選路徑，各條路徑的集合記為Pf，即plf∈Pf；rij表示危險品在路段(i,j)上運輸?shù)氖鹿拾l(fā)生概率；Qij表示路段(i,j)上暴露的人口數(shù)量；tij表示在危險品通過路段(i,j)所消耗時間；[T1f,T2f]表示第f種危險品的送達時間窗約束，T1f為最早送達時間，T2f為最晚送達時間；

(2)決策變量。xijf為0-1變量，表示f流向危險品是否通過路段(i,j)，取1時為是，取0時為否。

1.4 模型建立

在危險品運輸過程中，整個路網(wǎng)中發(fā)生事故的總期望為

(1)

整個路網(wǎng)中危險品運輸所影響的人數(shù)為

(2)

因此，在時間窗約束條件下，構建危險品儲運一體化的優(yōu)化模型如下：

(3)

(4)

xijf∈{0,1}

(5)

(6)

(7)

(8)

上述優(yōu)化模型中，目標函數(shù)(3)表示整個路網(wǎng)中發(fā)生事故的總期望最小，目標函數(shù)(4)表示整個路網(wǎng)中危險品運輸所影響的人數(shù)最少；約束條件(5)表示決策變量取整數(shù)變量0或1，即貨物運輸過程中不能分割，同一流向危險品的運輸路徑相同；約束條件(6)表示用于保證危險品在節(jié)點運輸?shù)姆较蛐院土髌胶?；約束條件(7)表示危險品兩節(jié)點間只能選擇一條路徑；約束條件(8)表示某種流向的危險品滿足目標節(jié)點的到達時間窗約束，即危險品不能早于目標節(jié)點的最早送達時間，且不能晚于最晚送達時間。

2 模型求解

由于模型的求解難度隨著路網(wǎng)的復雜程度增加而呈幾何級數(shù)上升，具有NP-hard的特性，本文設計了基于螞蟻系統(tǒng)(AS)[7]的搜索策略，所有螞蟻從起訖點O出發(fā)，在危險品運輸路網(wǎng)中尋找第一個流向f1的優(yōu)化路徑，螞蟻完成路徑的構建后，重新回到O點搜索第二個流向f2的優(yōu)化路徑，直至所有目標節(jié)點都出現(xiàn)在路徑中。

算法的重要步驟設計如下：

(1)用層次分析法確定權重w=(w1,w2)，并選擇合適的加權開方乘方平均數(shù)Pw(α)將危險品公路運輸路徑多目標決策模型中的目標函數(shù)表示單目標函數(shù)。

(2)算法初始化。設置信息素重要系數(shù)α，啟發(fā)式信息重要系數(shù)β，信息素蒸發(fā)系數(shù)ρ，信息素增強系數(shù)P，最大迭代次數(shù)Ncmax，螞蟻個數(shù)m，路段啟發(fā)式信息計算公式η(i,j)=1/w1rij+ηw2Qij，信息素τij←τ0，當前迭代次數(shù)Nc←0。

For k=1 to m

將所有螞蟻置于起訖點O，時間timeok←Sk(0)

End for

(3)解的構造。

WhileNc

For k = 1 to m

While 螞蟻游歷的節(jié)點中不包括第一個流向f1的目標節(jié)點D1

對螞蟻k判斷下一個要到達的節(jié)點j是否滿足可行的約束條件：

①未被訪問過：節(jié)點j?螞蟻的記憶表Tabu(k)；

②滿足到達節(jié)點j的時間timeok≤目標節(jié)點D1的時間窗上限T2D1

If 存在可行節(jié)點

按照如下概率轉移公司選擇下一節(jié)點j；

Tabu(k)←[Tabu(k)，j],timejk←timeik+tij

End if

End while

While 螞蟻游歷的節(jié)點中不包括第二個流向f2的目標節(jié)點D2

……

While 螞蟻游歷的節(jié)點中不包括第m個流向fm目標節(jié)點Dm

……

End while

按照下式更新信息素

記錄本次迭代中最優(yōu)路徑的螞蟻

當前迭代次數(shù)Nc←Nc+1

End while

為實現(xiàn)上述算法步驟，可以通過一些具有高級程序語言編譯功能的計算軟件如Matlab7.0進行求解。

3 實例分析

下面給出一個簡單的算例，危險品運輸網(wǎng)絡如圖1所示，其中,V1=1表示危險品的輸出節(jié)點，V2=(2,3,4,5,6,7)表示危險品運輸網(wǎng)絡中的轉運節(jié)點，V3=(8,9)表示危險品運輸?shù)哪繕斯?jié)點。運輸網(wǎng)絡中存在1→8、1→9兩種危險品流向，兩種流向的危險品送達時間窗約束分別為[9:00,11:00]，[11:00,12:00]。危險品出發(fā)時間為早上6:00。

危險品在不同路段的事故發(fā)生概率和運輸消耗時間如表1所示。

表1 各條路段的事故概率、消耗時間及影響人數(shù)

按前文所述模型算法進行計算，得到結果如表2所示。

表2 各流向危險品路徑選擇結果

4 結束語

在探討現(xiàn)代危險品配送網(wǎng)絡模型特點的基礎上，提出了帶時間窗約束的多流向危險品配送模型，給出了求解算法和過程，最后以實例證明該模型的可行性。本模型在時間窗約束條件下對整個危險品運輸網(wǎng)絡進行優(yōu)化，對危險品的運輸管理工作具有現(xiàn)實的指導作用。

參 考 文 獻

[1]Current JR. The minimum-covering shortest-path problem[J]. Decision Science, 1988,19:490-503.

[2]Abkowtiz.M and Cheng P. Developing a risk-cost frame work for routing truck movement of hazardous materials[J]. Accident Annual Prevent, 1988,20:39-51.

[3]任常興，吳宗之. 危險品道路運輸選線問題分析[J].安全與環(huán)境學報，2006，6(2)：84-88.

[4]開妍霞，王海燕. 危險品運輸網(wǎng)絡中運輸方式和路徑優(yōu)化研究[J].中國安全生產科學技術，2009，5(1)：37-41.

[5]馬昌喜，廣曉平. 發(fā)達運輸網(wǎng)絡環(huán)境下危險品公路運輸路徑決策[J].交通運輸系統(tǒng)工程與信息，2009，9(4)：134-139.

[6]《運籌學》教材編寫組. 運籌學[M].北京：清華大學出版社，2005.

[7]Marco Dorigo. 蟻群優(yōu)化[M].北京：清華大學出版社，2006.