基于ACO算法的危險化學(xué)品車輛運輸路徑優(yōu)化方法*

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

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

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

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

1 運輸問題模型

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

1.1 運輸風(fēng)險計算

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

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

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

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

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

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

4 仿真分析

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

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

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

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

實例中的道路網(wǎng)絡(luò)、客戶和倉庫的位置，以及通過本文方法優(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)線路的運輸時間為214.5 min，風(fēng)險系數(shù)為3.423.其運輸時間與線路2的運輸時間213.7 min近乎一致，但風(fēng)險系數(shù)比線路2的3.662有明顯減小.這是因為本文優(yōu)化目標(biāo)中對風(fēng)險系數(shù)的權(quán)重較大，而對運輸時間的權(quán)重較小，只有在保證運輸安全的前提下才會進(jìn)一步縮短運輸時間.與MILP方法的對比可以看到，本文方法獲得的路線在運輸時間和風(fēng)險系數(shù)上都較優(yōu)，且優(yōu)化時間只需要35 s，比MILP有明顯提升.這是因為MILP是一種遍歷搜索過程，需要遍歷所有解空間，耗時較長.而本文采用了ACO智能優(yōu)化算法能夠快速收斂到最優(yōu)解.