李歡

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

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

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

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

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

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

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

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

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

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

將化學(xué)危險品配送問題轉(zhuǎn)化為數(shù)學(xué)模型［10］可以描述為有向圖G=（V，A），其中V=v0，v1，…，vn表示全部節(jié)點(diǎn)的集合，v0為配送中心；A表示所有節(jié)點(diǎn)連接邊的集合；V'=v1，v2，…，vn表示客戶節(jié)點(diǎn)；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é)點(diǎn)i和節(jié)點(diǎn)j之間的距離；xijk=1表示車輛k從客戶i出發(fā)前往客戶j，否則xijk=0；qi為客戶i的需求量；B表示每輛車的最大載貨量；

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

2 算法設(shè)計(jì)

2.1 算法改進(jìn)

2.1.1 改進(jìn)客戶選擇策略

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

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

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

改進(jìn)后的客戶選擇策略：

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

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

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

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

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

τij=τmin，τij≤τmin

τmax，τij≥τmax（9）

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

2.2 算法步驟

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

為了驗(yàn)證本文提出的蟻群算法改進(jìn)策略的可行性，采用CVRPLIB中的標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，使用MATLAB R2018a軟件進(jìn)行仿真，并在CPU為英特爾i5-12400，內(nèi)存16 GB的計(jì)算機(jī)上運(yùn)行。仿真參數(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)算法的性能進(jìn)行對比，測試案例為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ù)集中部分案例的計(jì)算結(jié)果，為了使計(jì)算結(jié)果更加精確，每個案例都計(jì)算10次。其中，Instance表示案例的名稱；n表示客戶數(shù)量；K表示車輛數(shù)量；BK表示該案例在數(shù)據(jù)集中已知的最優(yōu)解；BR表示用本文算法求出的最優(yōu)路徑總長度；DP表示用本文算法求出的最優(yōu)解與BK的偏差率；Average表示運(yùn)用本文算法求解該案例10次的平均值。

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

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

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

4 結(jié)語

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

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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