基于改進蟻群算法的化學(xué)危險品車輛配送路徑優(yōu)化

李歡

摘 要：合理規(guī)劃化學(xué)危險品車輛的配送路徑，不僅可以提高配送效率，也減少了化學(xué)危險品在運輸時發(fā)生事故的風(fēng)險。為了優(yōu)化化學(xué)危險品車輛配送路徑，對蟻群算法提出了一些改進方法。首先，對客戶選擇策略采取分段計算的方法，以加快算法的收斂速度；其次，在構(gòu)建一條完整的閉合路徑時，過濾距離路徑較遠(yuǎn)的客戶，提高搜索最優(yōu)路徑的能力；最后，采用整體與局部相結(jié)合的方式完成信息素強度更新，避免算法出現(xiàn)停滯現(xiàn)象，提高算法的精確度。采用標(biāo)準(zhǔn)數(shù)據(jù)集進行仿真實驗，實驗數(shù)據(jù)表明改進后算法在收斂速度、路徑優(yōu)化能力和求解精確性方面都有較好的性能。

關(guān)鍵詞：化學(xué)危險品車輛；蟻群算法；改進方法；路徑優(yōu)化

中圖分類號：TQ086.5+2;U492.3+12

文獻標(biāo)志碼：A文章編號：1001-5922（2023）11-0126-05

Path optimization of chemical hazardous material vehicles based on improved ant colony algorithm

LI Huan

（School of Traffic and Transportation，Xian Traffic Engineering Institute，Xian Shaanxi 710300

）

Abstract：Reasonable planning of the distribution route of chemical hazardous material vehicles can not only improve the distribution efficiency，but also reduce the risk of accidents during transportation.In order to optimize the distribution route of chemical hazardous material vehicles，some improved methods of ant colony algorithm were proposed.Firstly，the method of segmental calculation was adopted forthe customer selection strategyto accelerate the convergence speedof the algorithm.Secondly，when constructing a complete closed path，the customers who were far away from the path were filtered to improve the ability of searching the optimal path.Finally，the intensity of pheromone was updated by combining the overall and the local to avoid the stagnation of the algorithm and improve the accuracy of the algorithm.Standard data sets were used for simulation experiments，and the experimental data showed that the improved algorithm had good performance in convergence speed，path optimization ability and solving accuracy.

Key words：chemical hazardous vehicles;ant colony algorithm;improvement methods;path optimization

化學(xué)危險品如果運輸不當(dāng)不僅會發(fā)生重大安全事故，還可能會造成嚴(yán)重經(jīng)濟損失。對化學(xué)危險品車輛的配送路徑進行合理規(guī)劃［1］，不僅可以降低運輸成本，也可以減小化學(xué)危險品發(fā)生事故的概率［2］。因此，合理規(guī)劃化學(xué)危險品在運輸過程中車輛的配送路徑，成為重要的研究課題。

為了保證化學(xué)危險品的安全運輸，需要對化學(xué)危險品車輛的配送路徑進行優(yōu)化［3］。研究人員提出了許多高效的路徑規(guī)劃算法，其中蟻群算法作為經(jīng)典的啟發(fā)式算法之一，常用于求解車輛路徑問題［4］，但傳統(tǒng)蟻群算法對路徑的優(yōu)化能力有限。對此，研究人員提出了多種改進策略，如以提高算法對路徑的優(yōu)化能力［5］。對蟻群算法引入變異算子提高了算法的全局搜索能力［6］。對信息素的更新規(guī)則進行改善，較明顯地提升了路徑搜索效率［7］。通過引入節(jié)約矩陣和2-opt法對蟻群算法進行改進，加快了算法尋找最優(yōu)路徑的速度，也減少了算法出現(xiàn)停滯的可能性［8］。

為解決化學(xué)危險品車輛路徑優(yōu)化問題中面臨的路徑優(yōu)化能力有限、算法的收斂速度和精度不足的問題，本文從客戶選擇策略、啟發(fā)函數(shù)以及信息素更新規(guī)則三方面進行改進，通過仿真實驗，驗證提出改進措施的可行性。

1 問題描述和數(shù)學(xué)模型

1.1 化學(xué)危險品配送問題描述

化學(xué)危險品在配送時通常是從一個配送中心給若干位客戶送貨。其中客戶分布在不同的位置，要保證所有客戶必須都能收到貨物，且一位客戶只能由一輛車配送。在符合化學(xué)危險品車輛載量限制的條件下，限定車輛的起點和終點均為配送中心，規(guī)劃每輛車的配送路徑，使得車輛配送距離相加之和最短［9］。圖1為車輛配送路徑示例，1個配送中心和15個客戶節(jié)點。

1.2 數(shù)學(xué)模型

將化學(xué)危險品配送問題轉(zhuǎn)化為數(shù)學(xué)模型［10］可以描述為有向圖G=（V，A），其中V=v0，v1，…，vn表示全部節(jié)點的集合，v0為配送中心；A表示所有節(jié)點連接邊的集合；V'=v1，v2，…，vn表示客戶節(jié)點；K=1，2，…k表示配送車輛的集合；Rk=v0k，v1k，v2k，...，vlk，v0k，vlk表示由車輛k配送的第l位客戶，Rk表示車輛k配送貨物的路線；S=R1，R2…Rkk∈K，表示k輛車配送路線的集合。

建立化學(xué)危險品配送問題數(shù)學(xué)模型：

minD=∑k∈K，∑n+1j=0i≠jdijxijk

（1）

且應(yīng)滿足如下約束條件：

∑i∈V'qi

∑n+1j=0i≠jxijk≤B，k∈K（2）

R1∪R2∪…∪Rk=V（3）

Rk∩k≠lRl=，k∈K，l∈V'（4）

∑n+1j=0xijk=∑n+1j=0xjik=1，k∈K（5）

式中：D表示總距離；dij示節(jié)點i和節(jié)點j之間的距離；xijk=1表示車輛k從客戶i出發(fā)前往客戶j，否則xijk=0；qi為客戶i的需求量；B表示每輛車的最大載貨量；

式（1）為目標(biāo)函數(shù)，表示所有車輛配送路徑長度之和最短；式（2）約束了每輛車的實際裝載量必須小于或等于最大裝載量；式（3）、式（4）為約束每位客戶僅由一輛車送貨；式（5）表示每輛車起點和終點均為v0。

2 算法設(shè)計

2.1 算法改進

2.1.1 改進客戶選擇策略

車輛k∈K，K=1，2，…k，Pkij表示車輛k搜尋下一客戶j的概率，傳統(tǒng)蟻群算法尋找下一客戶時采用輪盤賭的方式，計算規(guī)則［11］：

Pkij=τ（i，j）αη（i，j）β∑s∈Nkiτ（i，s）αη（i，s）β（6）

式中：Nki表示車輛k在客戶i位置時可選下一配送客戶的集合，隨著車輛配送的客戶越來越多，Nk中的元素會逐漸減少，客戶全部被訪問之后變成空集；τ（i，j）為客戶i到客戶j路徑上的信息素強度；η（i，j）為啟發(fā)函數(shù)，表示路徑節(jié)點i到j(luò)的能見度；α為信息素強度因子；β為能見度因子。

改進后的客戶選擇策略：

j=arg maxs∈Nkiτ（i，s）αη（i，s）β，r

式中：r、r0都為常數(shù)，r，r0∈（0，1），r0為設(shè)定的閾值，把車輛每次選擇的路徑標(biāo)記為一個隨機數(shù)r，通過比較r和r0的大小計算節(jié)點的轉(zhuǎn)移概率。當(dāng)r≥r0時，需要計算下一位配送客戶被選擇的概率；當(dāng)r

2.1.2 改進啟發(fā)函數(shù)

傳統(tǒng)蟻群算法的啟發(fā)函數(shù)η（i，j）=1dij為節(jié)點i到節(jié)點j之間距離的倒數(shù)［12］。本文利用蟻群算法求解化學(xué)危險品配送問題時，車輛從配送中心出發(fā)，最后的終點都是回到配送中心，所以每條路徑的第一段都是由配送中心到客戶，每條路徑的末段都是由客戶到配送中心。考慮客戶到配送中心的距離，構(gòu)建新的啟發(fā)函數(shù)：

η（i，j）=1dij+dj0，dij≤d0i1dij，dij>d0i（8）

式中：dij為客戶i、j之間的距離；d0i表示配送中心與當(dāng)前配送客戶i的距離；dj0表示下一位配送客戶j到配送中心的距離。當(dāng)dij>d0i時，說明客戶j與客戶i之間的距離較遠(yuǎn)，此時不考慮給客戶j配送；否則客戶j可以作為下一位配送客戶。此方法可以過濾距離該路徑的較遠(yuǎn)的客戶，加快算法對最優(yōu)路徑的搜索速度，減少算法的求解時間。

2.1.3 信息素更新規(guī)則改進

蟻群算法解決化學(xué)危險品配送問題的關(guān)鍵環(huán)節(jié)就是信息素的更新方式。傳統(tǒng)蟻群算法當(dāng)一只螞蟻構(gòu)建一條完整路徑后才會對信息素強度進行更新［13］，如果某些邊的信息素強度過高會導(dǎo)致螞蟻都集中在同一條路徑，這樣就會出現(xiàn)搜索停滯，無法找到最優(yōu)路徑，因此每次迭代后將邊（i，j）的信息素強度τ（i，j）限定在區(qū)間τmin，τmax內(nèi)，即符合以下規(guī)則：

τij=τmin，τij≤τmin

τmax，τij≥τmax（9）

本文采取整體信息素更新與局部信息素更新［14］相結(jié)合的方法，在限制信息素強度的基礎(chǔ)上，避免局部信息素強度較大，出現(xiàn)搜索停滯現(xiàn)象，使算法的精確度提高。

2.2 算法步驟

根據(jù)以上提出的改進策略，使用改進后的蟻群算法對化學(xué)危險品配送問題進行求解。

步驟1：初始化參數(shù)。設(shè)置最大車輛數(shù)目為K、讀取n位客戶位置及需求量qi，初始迭代NU=0，初始化每輛車的路徑記錄表route_k，所走路徑長度length-k，車輛的負(fù)載量load-k，以及各路徑原始信息素強度τij（i，j=0，1，2…n）;

步驟2：車輛從配送中心o出發(fā)，將o加入路徑記錄表route-k中;

步驟3：在滿足車輛最大載貨量的前提下，根據(jù)式（7）計算車輛k的下一個配送客戶j；否則車輛返回配送中心;

步驟4：根據(jù)式（10）局部更新車輛走過路徑的信息素［12］;

步驟5：判斷車輛是否已完成所有客戶配送，否則返回步驟3;

步驟6：當(dāng)車輛對所有客戶配送完畢之后，計算所有車輛行駛的路徑長度之和，根據(jù)式（11）和式（12）對信息素進行整體更新;

步驟7：如果迭代次數(shù)NU≥MAXNU，則算法結(jié)束，輸出最短路徑的總長度和最優(yōu)配送路線；否則返回步驟2，繼續(xù)迭代NU=NU+1。

基于改進蟻群算法解決化學(xué)危險品配送問題，流程如下圖2。

3 仿真實驗

為了驗證本文提出的蟻群算法改進策略的可行性，采用CVRPLIB中的標(biāo)準(zhǔn)數(shù)據(jù)集進行實驗，使用MATLAB R2018a軟件進行仿真，并在CPU為英特爾i5-12400，內(nèi)存16 GB的計算機上運行。仿真參數(shù)設(shè)置為：ρ0=0.2，ρ1=0.2，α=1，β=3，r0=0.7～0.9，m=客戶數(shù)量×1.5［15］，最大迭代次數(shù)MAXNU設(shè)置200。

將本文算法與傳統(tǒng)算法的性能進行對比，測試案例為P-n20-k2和P-n70-k10，仿真曲線如圖3和圖4所示。

從圖3、圖4可以看出，在迭代初期，本文算法求得的最短路徑總長度就明顯比傳統(tǒng)蟻群算法小，并且可以不斷跳出局部最優(yōu)，避免算法出現(xiàn)停滯現(xiàn)象。從迭代曲線圖還可以看出，相對于傳統(tǒng)蟻群算法，本文的算法可以用較少的迭代次數(shù)找到最優(yōu)解，說明收斂速度更快。

表1給出了數(shù)據(jù)集中部分案例的計算結(jié)果，為了使計算結(jié)果更加精確，每個案例都計算10次。其中，Instance表示案例的名稱；n表示客戶數(shù)量；K表示車輛數(shù)量；BK表示該案例在數(shù)據(jù)集中已知的最優(yōu)解；BR表示用本文算法求出的最優(yōu)路徑總長度；DP表示用本文算法求出的最優(yōu)解與BK的偏差率；Average表示運用本文算法求解該案例10次的平均值。

由表1可知，12個案例，配送客戶數(shù)量有大、中、小3種規(guī)模，將本文算法的計算結(jié)果與已知最優(yōu)解進行對比，有8個案例求得的結(jié)果非常接近最優(yōu)解，與最優(yōu)解的偏差率均小于0.5%；在剩余4個案例中，案例M-n200-k16的偏差率最大，最大偏差率也僅為2.54%，說明本文算法在大、中、小3種客戶規(guī)模下，均有較強的尋優(yōu)能力［16］，適用范圍較廣，求得的結(jié)果也有較高的精確性。

為進一步驗證本文算法改進的效果，使用傳統(tǒng)蟻群算法、文獻［8］提出的改進算法和本文算法分別對以下5個案例進行求解，表2中給出不同算法的求解結(jié)果，其中Average表示對應(yīng)項的平均值。

由表2可知，本文算法求出的最優(yōu)路徑總長度都明顯小于傳統(tǒng)蟻群算法，其中有4個案例的計算結(jié)果小于文獻［8］算法的結(jié)果，案例P-n23-k8計算結(jié)果與文獻［8］相同。從時間和精確性方面分析，本文算法求解消耗的平均時間最短，與傳統(tǒng)蟻群算法相比偏差率明顯降低，其中4個案例的偏差率都減小了10%以上；與文獻［8］算法相比，本文算法求解案例P-n19-k2、P-n20-k2、P-n50-k8和P-n70-k10的偏差率都更小，且平均偏差率在3個算法中最小，僅為0.63%。以上比較說明本文算法不僅對路徑的優(yōu)化能力更強，且求解的精確性大幅度提升，具有更高效的路徑搜索能力。

4 結(jié)語

本文為了解決化學(xué)危險品車輛路徑優(yōu)化問題，從客戶選擇策略、啟發(fā)函數(shù)和信息素更新規(guī)則3個角度進行優(yōu)化。為驗證改進方法的實際優(yōu)化效果，使用改進后的算法對標(biāo)準(zhǔn)數(shù)據(jù)集中的案例進行求解。通過與傳統(tǒng)算法、其他優(yōu)化算法以及已知最優(yōu)解的對比，證明本文的優(yōu)化算法在收斂速度、路徑優(yōu)化能力和求解精確性方面都具有更佳的表現(xiàn)。本文工作僅包括蟻群算法在載量受限車輛路徑規(guī)劃方面的研究，今后將思考通過蟻群算法與其他智能算法協(xié)同作用，解決更為復(fù)雜的路徑規(guī)劃問題。

【參考文獻】

［1］ 魏子秋，何雍禎.基于蟻群算法的多車揀貨路徑優(yōu)化［J］.物流工程與管理，2023，45（1）：29-31.

［2］ 蘇菠，姜軍，張志偉，等.基于連續(xù)視頻分析的化學(xué)危險品碼頭車輛測速方法研究［J］.粘接，2020，41（1）：180-184.

［3］ 崔虎.碳排放的鐵路集裝箱多式聯(lián)運路徑優(yōu)化研究［J］.粘接，2021，48（10）：193-196.

［4］ 郭城成，田立勤，武文星.蟻群算法求解旅行商問題中的應(yīng)用綜述［J］.計算機系統(tǒng)應(yīng)用：1-15.

［5］ 徐少甫，陳家晨，胡瑩石，等.基于ACO算法的危險化學(xué)品車輛運輸路徑優(yōu)化方法［J］.湘潭大學(xué)自然科學(xué)學(xué)報，2018，40（3）：66-69.

［6］ 楊雷博，周俊.改進蟻群算法下的車間物料配送路徑規(guī)劃研究［J］.制造業(yè)自動化，2022，44（11）：128-131.

［7］ 陳高華，郗傳松.求解多目標(biāo)車輛路徑優(yōu)化的改進蟻群算法研究［J］.機械設(shè)計與制造，2023（9）：231-236.

［8］ 劉紫玉，趙麗霞，薛建越，等.面向車輛路徑問題的改進蟻群算法研究［J］.河北科技大學(xué)學(xué)報，2022，43（1）：80-89.

［9］ 圣文順，徐愛萍，徐劉晶.基于蟻群算法與遺傳算法的TSP路徑規(guī)劃仿真［J］.計算機仿真，2022，39（12）：398-402.

［10］ 張強.基于改進蟻群算法的物流運輸最優(yōu)路徑優(yōu)化模型構(gòu)建［J］.自動化技術(shù)與應(yīng)用，2021，40（11）：122-126.

［11］ 劉海鵬，念紫帥.一種改進蟻群算法的路徑規(guī)劃研究［J］.小型微型計算機系統(tǒng)，2023（2）：1-7

［12］ 程玉芳，劉海斌，鄭東晗.基于改進蟻群算法的空鐵聯(lián)運路徑自動控制方法［J］.自動化與儀器儀表，2022（4）：107-110.

［13］ 寧雨舟，趙蕊.基于改進蟻群算法的物流無人機路徑規(guī)劃［J］.電子技術(shù)與軟件工程，2023（2）：142-146.

［14］ 馬世軒，游曉明，劉升.動態(tài)信息素更新和路徑獎懲的蟻群算法［J］.計算機工程與應(yīng)用，2023，59（4）：64-76.

［15］ 張松燦，普杰信，司彥娜，等.基于種群相似度的自適應(yīng)改進蟻群算法及應(yīng)用［J］.計算機工程與應(yīng)用，2021，57（8）：70-77.

［16］ 梁兆楷，高建明.基于負(fù)載均衡的Kubernetes改進優(yōu)化算法研究［J］.粘接，2023，50（3）：192-196.

收稿日期：2023-05-16；修回日期：2023-09-04

作者簡介：李 歡（1993-），女，碩士，講師，研究方向：智能交通、路徑規(guī)劃；E-mail：1493119220@qq.com。

基金項目：西安交通工程學(xué)院2022年度中青年基金項目（項目編號：2022KY-10）。

引文格式：李 歡.基于改進蟻群算法的化學(xué)危險品車輛配送路徑優(yōu)化［J］.粘接，2023，50（11）：126-129.