徐少甫， 陳家晨， 胡瑩石， 方寧生

(1.江蘇省物聯(lián)網(wǎng)應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫 214064;2.無(wú)錫太湖學(xué)院 計(jì)算機(jī)應(yīng)用與外語(yǔ)學(xué)習(xí)中心，江蘇 無(wú)錫 214064;3.東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 210000)

危險(xiǎn)化學(xué)品通過(guò)不同模式運(yùn)輸，危險(xiǎn)大部分(超過(guò)80%)都發(fā)生在公路上[1].因此，需要合理規(guī)劃公路運(yùn)輸路線，以此減少運(yùn)輸危險(xiǎn)化學(xué)品造成的公共風(fēng)險(xiǎn).目前，有學(xué)者已經(jīng)提出了多種求解模型，一些是使用單目標(biāo)路徑優(yōu)化算法，將最短路徑確定為最佳路線，或以最小化給定起點(diǎn)-目的地的風(fēng)險(xiǎn)作為目標(biāo)[2-5].然而，在許多實(shí)際應(yīng)用中(如氣瓶的運(yùn)輸)，危險(xiǎn)品的運(yùn)輸要求一組卡車來(lái)同時(shí)服務(wù)一組客戶.另外，為了獲得更好的路線，需要考慮多種目標(biāo)因素，即同時(shí)考慮運(yùn)輸風(fēng)險(xiǎn)和運(yùn)輸成本[6].一些學(xué)者利用混合整數(shù)線性規(guī)劃(MILP)方法[7]進(jìn)行路線求解，但這種方法中掃描解空間的量是巨大的，有時(shí)無(wú)法在多項(xiàng)式時(shí)間內(nèi)計(jì)算.元啟發(fā)式技術(shù)能夠在適度的計(jì)算時(shí)間內(nèi)生成解決方案，通過(guò)使用復(fù)雜的進(jìn)化程序?qū)鉀Q方案空間中最佳區(qū)域進(jìn)行探索，獲得的解決方案具有更高質(zhì)量.常用的智能優(yōu)化算法有遺傳算法、粒子群算法、蟻群算法和蜂群算法等[8]，其中蟻群算法具有較快的收斂速度且能避免陷入局部最優(yōu)等優(yōu)點(diǎn)[9].

為此，綜合考慮運(yùn)輸風(fēng)險(xiǎn)和運(yùn)輸成本來(lái)構(gòu)建目標(biāo)函數(shù)，通過(guò)蟻群優(yōu)化(ACO)算法來(lái)獲得最優(yōu)運(yùn)輸路線.仿真中將本文方法與MILP進(jìn)行了比較，結(jié)果證明了本文方法的有效性和可行性.

1 運(yùn)輸問(wèn)題模型

本研究的問(wèn)題可以定義為確定一組攜帶危險(xiǎn)品的車輛的帕累托最優(yōu)路線，以滿足給定一組客戶的需求問(wèn)題.其中具有以下約束條件：路徑選擇必須是多目標(biāo)的，并且應(yīng)該作為一個(gè)單步過(guò)程來(lái)執(zhí)行；盡量減少總的預(yù)定行程時(shí)間以及路線的總風(fēng)險(xiǎn)值，這是路線規(guī)劃中最小化的兩個(gè)主要目標(biāo)；所有車輛必須在倉(cāng)庫(kù)站點(diǎn)出發(fā)；車輛開始和結(jié)束操作的時(shí)間必須在倉(cāng)庫(kù)指定的時(shí)間范圍內(nèi)；客戶的需求必須在預(yù)先規(guī)定的時(shí)間范圍內(nèi)滿足.

1.1 運(yùn)輸風(fēng)險(xiǎn)計(jì)算

運(yùn)輸中的風(fēng)險(xiǎn)區(qū)別于其他運(yùn)輸問(wèn)題，其直接影響生命安全.因此，風(fēng)險(xiǎn)最小化是主要目標(biāo)之一.學(xué)者已經(jīng)進(jìn)行了充分的研究，努力獲得更好的定性和定量風(fēng)險(xiǎn)模型.考慮到在道路鏈路l上發(fā)生事故H，該事故可以由O類型泄漏事故，U類型交通事故和人口受傷后果D聯(lián)系起來(lái). 因此，與道路鏈路l相關(guān)的總運(yùn)輸風(fēng)險(xiǎn)Rl可表示為：

1.2 目標(biāo)函數(shù)

2 蟻群優(yōu)化算法

3 基于ACO的運(yùn)輸路徑優(yōu)化

本文利用ACO來(lái)獲得最優(yōu)的運(yùn)輸路線.但是，為了利用所有基于運(yùn)輸時(shí)間和風(fēng)險(xiǎn)目標(biāo)的非支配路徑進(jìn)行路徑選擇和單步優(yōu)化，所提出的算法還包括局部搜索步驟以提高帕累托最優(yōu)解的質(zhì)量.在進(jìn)行解決方案構(gòu)建步驟之前，在所有客戶和倉(cāng)庫(kù)節(jié)點(diǎn)執(zhí)行標(biāo)簽算法以獲得集合P，從而獲得集合N.集合P包括用于路徑選擇的所有路徑.ACO中的螞蟻使用這些路徑來(lái)構(gòu)建它們的路線(解決方案).采用局部搜索方法來(lái)提高每次迭代中構(gòu)建的解決方案的質(zhì)量.ACO運(yùn)輸路徑優(yōu)化算法的流程如算法1所示.

算法1:ACO運(yùn)輸路徑優(yōu)化過(guò)程步驟1:在所有節(jié)點(diǎn)(客戶和倉(cāng)庫(kù))執(zhí)行標(biāo)記算法以找到集合P,并且定義G(N,L).步驟2:設(shè)置參數(shù).使用最近的鄰域搜索,基于初始解初始化路徑信息素值和Pareto最優(yōu)集合S.對(duì)于迭代次數(shù)n = 1,根據(jù)信息素的值來(lái)初始化N中所有鏈路的信息素值.步驟3:For螞蟻編號(hào)m=1 to M3.1:設(shè)置車輛數(shù)K = 1,將螞蟻放在倉(cāng)庫(kù)節(jié)點(diǎn),其中i = 0.3.2:從i中識(shí)別可行的客戶節(jié)點(diǎn)集合,即N',設(shè)定一個(gè)將i連接到N'的鏈路L'集合.如果N'為空,則添加從i到倉(cāng)庫(kù)節(jié)點(diǎn)的所有鏈路到L'中.3.3:從L'中選擇一個(gè)鏈路i,j . IF已被利用,選擇具有最大啟發(fā)式和信息素值的鏈路i,j . Else,使用選擇概率隨機(jī)選擇.3.4:所選鏈路i,j 的信息素值進(jìn)行局部更新.3.5:IF與選定鏈路i,j 對(duì)應(yīng)的節(jié)點(diǎn)是倉(cāng)庫(kù)節(jié)點(diǎn),則設(shè)置K =K +1,i = 0. Else,設(shè)置i =與選定i,j 對(duì)應(yīng)的客戶節(jié)點(diǎn).3.6:IF有更多的客戶需要服務(wù),則轉(zhuǎn)到步驟3.2.3.7:設(shè)定總車輛= K-1.步驟4:IF m<螞蟻總數(shù)M,m= m+1并轉(zhuǎn)到步驟3.步驟5:根據(jù)優(yōu)勢(shì)規(guī)則更新S.步驟6:將本地搜索應(yīng)用于S中的每個(gè)解決方案.步驟7:根據(jù)當(dāng)前S的平均目標(biāo)函數(shù)值查找新的跟蹤信息素值.步驟8:IF之前的路徑信息素值<新的路徑信息素,則設(shè)置當(dāng)前路徑的信息素值=新的路徑信息素,并初始化L中所有鏈路的信息素值.Else,對(duì)屬于S中解的所有鏈路i,j 進(jìn)行信息素的全局更新.步驟9:迭代次數(shù)n=n+ 1,轉(zhuǎn)到步驟3,直到n=最大迭代次數(shù)Nmax.

4 仿真分析

測(cè)試實(shí)例是一個(gè)現(xiàn)實(shí)中的道路網(wǎng)絡(luò)數(shù)據(jù)，網(wǎng)絡(luò)中有225個(gè)節(jié)點(diǎn)和781個(gè)鏈接.每條單向道路用單向鏈路建模，每條雙向道路由兩個(gè)單向鏈路建模.在網(wǎng)絡(luò)中的225個(gè)節(jié)點(diǎn)中，有8個(gè)客戶節(jié)點(diǎn)和1個(gè)倉(cāng)庫(kù)節(jié)點(diǎn).客戶節(jié)點(diǎn)編號(hào)分別為1、7、8、13、18、20、22和24；倉(cāng)庫(kù)節(jié)點(diǎn)編號(hào)為17. 客戶的時(shí)間窗口是隨機(jī)生成的，每個(gè)客戶假定需求量為3 300 L化學(xué)品.設(shè)置車隊(duì)有2輛卡車同時(shí)運(yùn)輸，所有車輛均具有20 000 L的容量.

在配備Intel i5-7500 CPU，8 G內(nèi)存的PC機(jī)上，通過(guò)MATLAB R2014軟件執(zhí)行優(yōu)化算法.所有鏈接都在GIS地圖中進(jìn)行識(shí)別，以確定該地區(qū)人口的地理分布.此人口數(shù)據(jù)用于計(jì)算實(shí)例中每個(gè)鏈接的相關(guān)風(fēng)險(xiǎn).對(duì)于ACO算法中參數(shù)，設(shè)置α=10，β0=1，ρ0=0.1，Nmax=200.

表1 排名前3的路線指標(biāo)

優(yōu)化方法路線排名運(yùn)輸時(shí)間/min風(fēng)險(xiǎn)系數(shù)優(yōu)化時(shí)間/s本文方法1214.53.4232213.73.6623237.53.68334.6MILP1221.83.4672223.93.6923236.33.745103.2

實(shí)例中的道路網(wǎng)絡(luò)、客戶和倉(cāng)庫(kù)的位置，以及通過(guò)本文方法優(yōu)化后獲得的最優(yōu)路線如圖1所示.從圖1可以看到，車輛1的路線為17-13-22-20-1-7-18-17，車輛2的路線為17-22-1-20-7-24-8-17.由于城區(qū)人口密集，這些路線都避開了城區(qū)核心區(qū)域.

另外，將本文方法與混合整數(shù)線性規(guī)劃(MILP)方法進(jìn)行比較，表1給出了兩種方法獲得的排名前3的路線的總體指標(biāo).可以看到，本文方法的優(yōu)化結(jié)果中，最優(yōu)線路的運(yùn)輸時(shí)間為214.5 min，風(fēng)險(xiǎn)系數(shù)為3.423.其運(yùn)輸時(shí)間與線路2的運(yùn)輸時(shí)間213.7 min近乎一致，但風(fēng)險(xiǎn)系數(shù)比線路2的3.662有明顯減小.這是因?yàn)楸疚膬?yōu)化目標(biāo)中對(duì)風(fēng)險(xiǎn)系數(shù)的權(quán)重較大，而對(duì)運(yùn)輸時(shí)間的權(quán)重較小，只有在保證運(yùn)輸安全的前提下才會(huì)進(jìn)一步縮短運(yùn)輸時(shí)間.與MILP方法的對(duì)比可以看到，本文方法獲得的路線在運(yùn)輸時(shí)間和風(fēng)險(xiǎn)系數(shù)上都較優(yōu)，且優(yōu)化時(shí)間只需要35 s，比MILP有明顯提升.這是因?yàn)镸ILP是一種遍歷搜索過(guò)程，需要遍歷所有解空間，耗時(shí)較長(zhǎng).而本文采用了ACO智能優(yōu)化算法能夠快速收斂到最優(yōu)解.