基于改進(jìn)蟻群算法的低碳車輛路徑優(yōu)化

摘" 要：為降低物流配送成本，提高配送效率，優(yōu)化物流車輛配送路徑，從節(jié)能減排角度出發(fā)，綜合考慮配送時(shí)間窗因素，以運(yùn)輸成本、碳排放成本、時(shí)間窗懲罰成本三者之和最小為目標(biāo)，構(gòu)建帶時(shí)間窗約束條件的低碳車輛配送路徑優(yōu)化模型。將基本蟻群算法的信息素更新策略改為局部更新與全局更新相結(jié)合的方式、再將其與A*算法、2-opt算法相結(jié)合，設(shè)計(jì)出改進(jìn)蟻群算法，用Solomon的測(cè)試數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，并將改進(jìn)蟻群算法與基本蟻群算法進(jìn)行結(jié)果對(duì)比。仿真實(shí)驗(yàn)結(jié)果表明，相較于基本蟻群算法，改進(jìn)蟻群算法在算法收斂速度更快、使用配送車輛更少的情況下，配送總成本降低了11.25%，配送效率提高了11.91%，說(shuō)明改進(jìn)蟻群算法在配送路徑優(yōu)化問(wèn)題上是有效且可靠的。

關(guān)鍵詞：路徑優(yōu)化；改進(jìn)蟻群算法；低碳車輛；時(shí)間窗

中圖分類號(hào)：F252.14" " 文獻(xiàn)標(biāo)志碼：A" " DOI：10.13714/j.cnki.1002-3100.2024.17.002

Abstract： In order to reduce the cost and improve the efficiency of logistics distribution， and optimize the path of logistics vehicles. Both consider the perspective of energy conservation and emission reduction and the factors of distribution time window. With the goal of minimizing the sum of transportation cost， carbon emission cost， and time window penalty cost， an optimization model， with time window constraints， of low-carbon vehicle distribution path was constructed. The pheromone updating strategy of the basic ant colony algorithm is changed to a combination of local and global updating， then combined with the A* algorithm and 2-opt algorithm to design the improving ant colony algorithm. Simulation experiment was conducted with Solomon's test data. The results were compared with the improving ant colony algorithm and the basic ant colony algorithm. The results of the experiment show that the improving ant colony algorithm reduces the total cost of distribution by 11.25% and improves the efficiency by 11.91%， when it converges faster and uses fewer vehicles. It shows that the improving ant colony algorithm is effective and reliable in the distribution path optimization problem.

Key words： routing optimization; improved ant colony algorithm; low-carbon vehicle; time window

0" 引" 言

隨著全球變暖日益嚴(yán)重，各國(guó)政府也開始注重在經(jīng)濟(jì)活動(dòng)中的節(jié)能減排問(wèn)題。在第75屆聯(lián)合國(guó)大會(huì)上，中國(guó)承諾爭(zhēng)取在2030年實(shí)現(xiàn)碳排放達(dá)到峰值，并在2060年達(dá)到碳中和的目標(biāo)[1]。有研究數(shù)據(jù)顯示，物流運(yùn)輸業(yè)產(chǎn)生的CO2占全球總量的14%[2]。低碳車輛路徑問(wèn)題是在普通車輛路徑問(wèn)題（VRP）的基礎(chǔ)上，考慮了節(jié)能減排，引入了碳排放的約束條件。將碳排放量作為約束條件構(gòu)建物流配送路徑優(yōu)化方案，可以有效控制運(yùn)輸成本[3-4]。

在客戶要求的時(shí)間窗口內(nèi)送達(dá)相關(guān)貨物，無(wú)疑可以提高客戶的滿意度，更利于企業(yè)的長(zhǎng)遠(yuǎn)發(fā)展。時(shí)間窗問(wèn)題可分為硬時(shí)間窗和軟時(shí)間窗[5]，硬時(shí)間窗要求車輛必須在時(shí)間窗內(nèi)到達(dá)服務(wù)點(diǎn)，而軟時(shí)間窗允許車輛早到或者遲到。實(shí)際商業(yè)活動(dòng)中，軟時(shí)間窗的車輛路徑問(wèn)題更加符合實(shí)際情況。本文在低碳車輛問(wèn)題上引入時(shí)間窗約束條件，兼顧節(jié)能減排與客戶滿意度。

與傳統(tǒng)車輛路徑問(wèn)題一樣，帶時(shí)間窗的低碳車輛路徑問(wèn)題也是一個(gè)NP-hard問(wèn)題[6]，即較難獲得全局最優(yōu)解，各種啟發(fā)式優(yōu)化算法常被運(yùn)用到相關(guān)研究中。Niu et al[7]以成本最小作為目標(biāo)，提出基于鄰域搜索的混合禁忌搜索算法；Bing et al[8]在考慮車輛行駛距離的限制條件下，將速度優(yōu)化子程序嵌入自適應(yīng)大鄰域搜索算法中；Yuan et al[9]建立多配送中心網(wǎng)點(diǎn)模型，將自適應(yīng)模擬退火算法與人工魚群算法相結(jié)合進(jìn)行實(shí)例求解；Ji et al[10]在時(shí)間窗約束的條件下，驗(yàn)證了神經(jīng)網(wǎng)絡(luò)算法在路徑優(yōu)化問(wèn)題上的有效性；Carmen et al[11]考慮不同車型的不同容量約束條件，將k-中值算法與蒙特卡洛樹搜索算法結(jié)合求解；il et al[12]在傳統(tǒng)模擬退火的基礎(chǔ)上提出約束規(guī)劃模型來(lái)解決車輛路徑問(wèn)題；于建芳等[13]提出一種基于黃金正弦的模擬退火算法，提高了傳統(tǒng)模擬退火算法的全局優(yōu)化性能；王勇等[14]提出以運(yùn)輸成本和配送車輛的雙目標(biāo)最小優(yōu)化模型，設(shè)計(jì)了一種TS-NSGA-II算法，該算法結(jié)合了禁忌搜索算法（TS）和非支配排序遺傳算法（NSGA-II）；張聞強(qiáng)等[15]針對(duì)帶時(shí)間窗車輛配送路徑優(yōu)化問(wèn)題，提出了一種多目標(biāo)混合進(jìn)化優(yōu)化算法；周建軍等[16]構(gòu)建低碳車輛配送優(yōu)化模型，通過(guò)優(yōu)化的貓群算法對(duì)模型進(jìn)行求解；陸文星等[17]以低碳為切入點(diǎn)利用改進(jìn)鯨魚算法對(duì)冷鏈物流配送路徑模型進(jìn)行求解。

1991年，受自然界中螞蟻覓食行為的啟發(fā)，意大利學(xué)者Dorigo[18]提出了蟻群算法。此后，蟻群算法常作為求解路徑規(guī)劃問(wèn)題的現(xiàn)代啟發(fā)式算法之一。本文聚焦于帶有時(shí)間窗口的低碳車輛路徑問(wèn)題，以車輛運(yùn)輸成本、碳排放成本、軟時(shí)間窗懲罰成本三者之和最小為目標(biāo)，建立TCVRPTW數(shù)學(xué)模型，利用改進(jìn)蟻群算法模擬計(jì)算得出優(yōu)化路徑。

1" 問(wèn)題描述與數(shù)學(xué)模型

1.1" 問(wèn)題描述。在實(shí)際經(jīng)營(yíng)中，企業(yè)由于成本原因一般不會(huì)建立過(guò)多的配送中心[19]，因此，考慮到實(shí)際商業(yè)情況，本文研究的是單配送中心下的車輛配送路徑優(yōu)化問(wèn)題。具體假設(shè)如下：（1）對(duì)配送中心的條件假設(shè)：有且僅有一個(gè)配送中心，配送車輛從配送中心出發(fā)，在完成配送任務(wù)后，需全部返回配送中心。（2）對(duì)運(yùn)輸車輛的條件假設(shè)：有足夠多的車輛來(lái)滿足配送任務(wù)；所有配送車輛的裝載量，在滿足初始方案路徑上各客戶需求量之和的基礎(chǔ)上，不能超出自身的最大裝載限制；所有車輛滿油狀態(tài)從配送中心出發(fā)，滿足配送路線的最大里程；所有車輛型號(hào)相同。（3）對(duì)客戶點(diǎn)的條件假設(shè)：一個(gè)客戶只能由一輛車進(jìn)行配送服務(wù)；客戶對(duì)產(chǎn)品的需求量、配送時(shí)間窗、服務(wù)時(shí)間已知。

1.2" 參數(shù)符號(hào)說(shuō)明

1.3" 建立數(shù)學(xué)模型

1.3.1" 車輛運(yùn)輸成本。車輛的運(yùn)輸成本可分為兩個(gè)部分：車輛行駛的燃油成本與啟用車輛的固定成本。

1.3.2" 碳排放成本。Hoen et al[21]的研究表明碳排放量與油耗量呈正相關(guān)，則碳排放成本：

1.3.3" 時(shí)間窗懲罰成本

式（7）表示每輛車的配送任務(wù)不超過(guò)其最大載重；式（8）表示每個(gè)客戶節(jié)點(diǎn)均會(huì)被服務(wù)；式（9）至式（10）表示每個(gè)客戶只由一輛車對(duì)其進(jìn)行配送；式（11）至式（12）表示車輛從配送中心出發(fā)完成配送后返回配送中心。

2" 改進(jìn)蟻群算法

本文結(jié)合蟻群法特性，提出改進(jìn)蟻群算法。為加快搜索速度，先將蟻群算法與A*算法相結(jié)合求出初始信息素濃度；再利用局部貪心策略與全局只更新最優(yōu)路徑相結(jié)合的方式進(jìn)行信息素濃度更新；最后利用改進(jìn)2-opt的方法對(duì)最優(yōu)路線進(jìn)行局部?jī)?yōu)化改進(jìn)。

2.1nbsp; 初始信息素的設(shè)置

2.2" 設(shè)置車輛轉(zhuǎn)移概率。

2.3" 信息素更新策略。信息素釋放和信息素蒸發(fā)的平衡對(duì)于蟻群算法的性能至關(guān)重要。本文采用局部更新與全局更新相結(jié)合的方式作為信息素更新策略。

2.4" 改進(jìn)2-opt局部?jī)?yōu)化檢驗(yàn)。為了對(duì)蟻群算法求得的最優(yōu)路徑進(jìn)行優(yōu)化檢驗(yàn)，本文采用改進(jìn)2-opt方法對(duì)路線進(jìn)行局部改進(jìn)。2-opt方法的核心思想是對(duì)當(dāng)前路線中的兩點(diǎn)進(jìn)行交換以獲得更短的路徑。由于本文是以最小總成本為目標(biāo)，所以對(duì)傳統(tǒng)2-opt方法進(jìn)行改進(jìn)，具體方法如下：（1）從當(dāng)前配送路線中隨機(jī)交換兩個(gè)非相鄰客戶點(diǎn)的配送順序；（2）檢查新的路線總成本是否比原來(lái)的更小，如果新路徑的成本更小，接受這個(gè)新路線作為當(dāng)前最優(yōu)路徑；否則，保留原路徑。重復(fù)以上兩個(gè)步驟，直至沒(méi)有改進(jìn)為止。

3" 算例仿真

3.1" 算法實(shí)例分析

3.2" 算法對(duì)比。為了進(jìn)一步驗(yàn)證算法的有效性，針對(duì)本文實(shí)例，在不改變客戶信息及相關(guān)參數(shù)的情況下，用基本蟻群算法進(jìn)行結(jié)果對(duì)比。基本蟻群算法運(yùn)算得出共有7輛貨車參與配送，具體配送路線如圖2所示。

此外，將改進(jìn)蟻群算法與基本蟻群算法各運(yùn)行10次，運(yùn)行結(jié)果平均值如表1所示。

從多次運(yùn)行的平均結(jié)果上來(lái)看，在同時(shí)考慮碳排放成本與時(shí)間窗懲罰成本的車輛配送路徑優(yōu)化的問(wèn)題中，改進(jìn)蟻群算法總里程、總成本、碳排放量及時(shí)間窗懲罰成本分別降低了11.25%、32.01%、15.71%、90.68%；而配送效率提高了18.91%。這說(shuō)明了改進(jìn)蟻群算法在求解帶時(shí)間窗的低碳車輛路徑優(yōu)化問(wèn)題上的優(yōu)越性。

4" 結(jié)束語(yǔ)

（1）利用改進(jìn)蟻群算法得出的配送方案，總里程降低了11.25%、總成本降低了32.01%，這說(shuō)明將基本蟻群算法與A*算法、2-opt算法相結(jié)合，不僅能夠提高收斂速度，還能避免得到次優(yōu)解；（2）根據(jù)實(shí)驗(yàn)結(jié)果，隨著配送里程減少了47.1km，碳排放成本也隨之降低了42.2元。碳排放量與車輛配送距離呈正相關(guān)，將碳排放量作為約束，能夠進(jìn)一步減少配送距離，提升配送效率；（3）本文中僅用測(cè)試數(shù)據(jù)進(jìn)行了仿真實(shí)驗(yàn)，在構(gòu)建成本模型時(shí)只考慮了車輛運(yùn)輸成本、碳排放成本和軟時(shí)間窗懲罰成本。然而，現(xiàn)實(shí)生活中物流企業(yè)的經(jīng)營(yíng)活動(dòng)是復(fù)雜多變的，經(jīng)營(yíng)利潤(rùn)也受多重因素影響。因此，未來(lái)在取得真實(shí)的物流企業(yè)研究數(shù)據(jù)時(shí)，則會(huì)進(jìn)一步開展更加符合物流企業(yè)經(jīng)營(yíng)場(chǎng)景的低碳車輛配送實(shí)證研究。

參考文獻(xiàn)：

[1] 中國(guó)企業(yè)改革與發(fā)展研究會(huì). 國(guó)務(wù)院關(guān)于印發(fā)2030年前碳達(dá)峰行動(dòng)方案的通知[Z]. 北京：中國(guó)商務(wù)出版社，2021.

[2]" AGLIARDI E， CASAR M， XEPAPADEAS A. Introduction： Special issue on the economics of climate change and sustainability[J]. Environment and Development Economics， 2020，25（1）：1-4.

[3]" COSTA D， MAUCERI S， CARROLL P， et al. A genetic algorithm for a green vehicle routing problem[J]. Electronic Notes in Discrete Mathematics， 2018：65-74.

[4] 唐慧玲，唐恒書，朱興亮. 基于改進(jìn)蟻群算法的低碳車輛路徑問(wèn)題研究[J]. 中國(guó)管理學(xué)，2021，29（7）：118-127.

[5]" HE M， WEI Z， WU X， et al. An adaptive variable neighborhood search ant colony algorithm for vehicle routing problem with soft time windows[J]. IEEE Access， 2021，99：21258-21266.

[6] 楊欣潼，張婷，白麗平，等. 社區(qū)居家養(yǎng)老服務(wù)的預(yù)約調(diào)度與路徑規(guī)劃問(wèn)題研究：基于改善蟻群算法[J]. 系統(tǒng)工程理論與實(shí)踐，2019，39（5）：1212-1224.

[7]" NIU Y， YANG Z H， CHEN P， et al. Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost[J]. Journal of Cleaner Production， 2018，171（10）：962-971.

[8]" BING M， DA H， XI C， et al. The vehicle routing problem with speed optimization for shared autonomous electric vehicles service[J]. Computers Industrial Engineering， 2021，161：333-357.

[9]" YUAN M， KAN X， CHI C， et al. An adaptive simulated annealing and artificial fish swarm algorithm for the optimization of multi-depot express delivery vehicle routing[J]. Intelligent Data Analysis， 2022，26（1）：239-256.

[10]" JI B， ZHOU S， ZHANNG D， et al. A branch-and-price-based heuristic for the vehicle routing problem with two-dimensional loading constraints and time windows[J]. International Transactions in Operational Research， 2023，31（2）：658-691.

[11]" CARMEN B， WOLFGAN G， CHRISTOPHER T， et al. Hybrid fleet capacitated vehicle routing problem with flexible Monte-carlo tree search[J]. International Journal of Systems Science： Operations Logistics， 2023，10（1）：1-12.

[12]" ？覶IL Z A， ？魻ZTOP H， DIRI K Z. Integrating distributed disassembly line balancing and vehicle routing problem in supply chain[J]. International Journal of Production Economics， 2023，65：1-22.

[13] 于建芳，劉升. 黃金正弦模擬退火算法求解低碳有能力約束的車輛路徑問(wèn)題[J]. 科學(xué)技術(shù)與工程，2020，20（11）：4202-4209.

[14] 王勇，張杰，劉永，等. 基于資源共享和溫度控制的生鮮商品多中心車輛路徑優(yōu)化問(wèn)題[J]. 中國(guó)管理科學(xué)，2022，30（11）：272-285.

[15] 張聞強(qiáng)，王曉萌，張曉曉，等. 集配一體化車輛路徑規(guī)劃的混合進(jìn)化多目標(biāo)優(yōu)化[J/OL]. （2023-10-11）[2023-12-08]. https：//doi.org/10.16182/j.issn1004731x.joss.

[16] 周建軍，李林，陳飛. 改進(jìn)貓群算法在車輛配送路徑優(yōu)化中的應(yīng)用研究[J/OL]. （2023-7-25）[2023-12-08]. https：//doi.org/10.19356/j.cnki.

[17] 陸文星，王璐，任少彤，等. 基于改進(jìn)鯨魚優(yōu)化算法的冷鏈配送路徑優(yōu)化[J]. 物流科技，2023，46（24）：145-150.

[18]" SOLOMON M. Algorithms for the vehicle routing problem with time window constraints[J]. Operations Research， 1987，35（2）：254-265.

[19] 方文婷，艾時(shí)鐘，王晴，等. 基于混合蟻群算法的冷鏈物流配送路徑優(yōu)化研究[J]. 中國(guó)管理科學(xué)，2019，27（11）：107-115.

[20]" XIAO Y Y， ZHAO Q H， et al. Development of a fuel consumption optimization model for the capacitated vehicle routing problem[J]. Computers amp; Operations Research， 2012，39（7）：1419-1431.

[21]" HONE K M R， TAN T， FRANSOO J C， et al. Effect of carbon emission regulations on transport mode selection under stochastic demand[J]. Flexible Services and Manufacturing Journal， 2012，26：170-195.