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

0 引言

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

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

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

1 優(yōu)化模型

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

1.1 模型假設(shè)

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

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

(2)各個(gè)OD的危險(xiǎn)品的運(yùn)輸量由其目標(biāo)節(jié)點(diǎn)所在的地的需求量決定，而且危險(xiǎn)品到達(dá)倉庫時(shí)需滿足其時(shí)間窗的約束。

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

1.2 抽象描述

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

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

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

1.3 符號說明

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

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

1.4 模型建立

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

(1)

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

(2)

因此，在時(shí)間窗約束條件下，構(gòu)建危險(xiǎn)品儲(chǔ)運(yùn)一體化的優(yōu)化模型如下：

(3)

(4)

xijf∈{0,1}

(5)

(6)

(7)

(8)

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

2 模型求解

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

算法的重要步驟設(shè)計(jì)如下：

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

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

For k=1 to m

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

End for

(3)解的構(gòu)造。

WhileNc

For k = 1 to m

While 螞蟻游歷的節(jié)點(diǎn)中不包括第一個(gè)流向f1的目標(biāo)節(jié)點(diǎn)D1

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

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

②滿足到達(dá)節(jié)點(diǎn)j的時(shí)間timeok≤目標(biāo)節(jié)點(diǎn)D1的時(shí)間窗上限T2D1

If 存在可行節(jié)點(diǎn)

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

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

End if

End while

While 螞蟻游歷的節(jié)點(diǎn)中不包括第二個(gè)流向f2的目標(biāo)節(jié)點(diǎn)D2

……

While 螞蟻游歷的節(jié)點(diǎn)中不包括第m個(gè)流向fm目標(biāo)節(jié)點(diǎn)Dm

……

End while

按照下式更新信息素

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

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

End while

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

3 實(shí)例分析

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

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

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

按前文所述模型算法進(jìn)行計(jì)算，得到結(jié)果如表2所示。

表2 各流向危險(xiǎn)品路徑選擇結(jié)果

4 結(jié)束語

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

參 考 文 獻(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]任常興，吳宗之. 危險(xiǎn)品道路運(yùn)輸選線問題分析[J].安全與環(huán)境學(xué)報(bào)，2006，6(2)：84-88.

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

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

[6]《運(yùn)籌學(xué)》教材編寫組. 運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，2005.

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