時間窗和改進算法在冷鏈物流路徑優(yōu)化中的應用研究

任傳榮 皇甫世誠 黃來望

摘 要：文章針對冷鏈物流運輸問題建立了優(yōu)化模型，使得冷鏈物流運輸過程中的碳成本、時間窗的懲罰成本以及貨物的變質(zhì)成本總和最小，再運用改進蟻群算法，對其信息素濃度做出新的更新規(guī)則，避免了求解較慢和陷入局部最優(yōu)解的問題；文章最后應用模型求解，得到最優(yōu)路徑和最低成本。

關(guān)鍵詞：冷鏈物流；優(yōu)化模型；時間窗；改進蟻群算法

中圖分類號：F259.22；U116文獻標志碼：ADOI：10.13714/j.cnki.1002-3100.2023.04.041

Abstract： This paper establishes an optimization model for the cold-chain logistics transportation problem to minimize the total cost of carbon cost， penalty cost of time window and deterioration cost of goods in the cold-chain logistics transportation process， and then uses the improved ant colony algorithm to make a new update rule for its pheromone concentration， avoiding the problem of slow solution and falling into local optimal solution. Finally， the model is applied to obtain the optimal path and the lowest cost.

Key words： cold chain logistics; optimization model; time window; improved ant colony algorithm

0? ? 引? ? 言

隨著網(wǎng)絡(luò)電子商務的發(fā)展，網(wǎng)購日漸成為人們?nèi)粘Ｙ徫锏氖滓绞?，其中一種購物類別便是對生鮮產(chǎn)品的購買。對于生鮮產(chǎn)品來說，最重要的就是保證生鮮產(chǎn)品送達時的新鮮度，因為其保質(zhì)期也就幾天左右，生鮮產(chǎn)品如果不及時送到，則會導致產(chǎn)品腐壞，為了解決這一問題，物流行業(yè)便推出了冷鏈物流運輸新方式。

冷鏈物流運輸在一定程度上保證了產(chǎn)品的新鮮性，但是由于冷鏈物流運輸?shù)奶厥庑?，其消耗成本也較大，其中包括較大的運輸成本、變質(zhì)成本、客戶滿意度成本[1]（由提前送達的車輛等待成本、合理時間送達的零成本和遲到送達的不滿意成本構(gòu)成），這就需要結(jié)合時間窗和蟻群算法[2]優(yōu)化路徑減小冷鏈運輸成本。

傳統(tǒng)蟻群算法收斂速度較慢，且由于傳統(tǒng)蟻群算法[3]正反饋的特性，為了避免傳統(tǒng)蟻群算法的求解結(jié)果為局部最優(yōu)解，本文對蟻群算法繼續(xù)改進。改進蟻群算法則是在原算法的基礎(chǔ)上給予信息素濃度區(qū)間，設(shè)定一定范圍，這樣就有效避免了由于某條路線信息素濃度過大而造成蟻群聚集情況，從而大大提高了優(yōu)化搜索效率。與此同時，必須限制變質(zhì)成本最低且結(jié)合時間窗提高客戶滿意度。

1? ? 模型建立

由于冷鏈物流運輸造成了大量碳排放，因此減少碳成本就在于減少運輸成本，與此同時也為綠色物流貢獻了力量。由上所述，本文建立了以碳成本、時間懲罰成本、變質(zhì)成本最小為目標的優(yōu)化模型，求得這些成本最低情況下的最短路徑情況。

1.1? ? 碳成本模型

2? ? 算法邏輯和模型的求解

2.1? ? 傳統(tǒng)蟻群算法

蟻群算法是一種模擬進化算法[5]，可以模擬出螞蟻的活動意向；其算法憑借魯棒性優(yōu)勢和正反饋機制被廣泛應用于路徑優(yōu)化問題。螞蟻在尋找食物時，在經(jīng)過的路徑中會分泌信息素，而信息素的濃度[6]會直接影響螞蟻對路徑的選擇，即信息素濃度越大，路徑選擇越多。

算法開始之前，所有目標點、路徑上各點的信息素的濃度為0，即T0=Tij（0）；ηij（t）為啟發(fā)函數(shù)，他表示在t螞蟻從目標點t處選擇下一目標點j的期望程度。用Prkij（t）表示在t時刻螞蟻k從i到j(luò)點的概率，計算方法如下。

信息素的濃度則可用上述公式中的τij（t）表示，ij是它的邊，α則表示信息素濃度的重要程度，ηij（t）則是相對于Prkij（t）來說的，它表示的則是螞蟻k從i地到j(luò)地的期望概率，β表示的是ηij（t）的重要程度因子。

2.2? ? 改進蟻群算法的信息素更新規(guī)則

針對本文問題的多個成本優(yōu)化，如果選擇傳統(tǒng)蟻群算法求解則會出現(xiàn)求解較慢且結(jié)果是局部最優(yōu)結(jié)果而不是全局最優(yōu)結(jié)果，因此需要對蟻群算法進行改進。經(jīng)過學習與分析，本文最終對算法中的信息素濃度加以改進，即在信息素濃度的更新過程中給予信息素濃度的上下限，本文將其確定為[τmin，τmax] ，蟻群算法效率就會極大提高，能夠較快搜索出全局最優(yōu)解。信息素濃度的計算具體如下。

其中，迭代次數(shù)為t、迭代最優(yōu)解數(shù)量為σ；C（t）則是對應求解的三類成本之和、ρ則是信息素蒸發(fā)系數(shù)。

改進蟻群算法步驟如下。

步驟1： 定義參數(shù)，導入客戶時間窗數(shù)據(jù)，將dij定義為客戶之間的距離，將Qi定義為客戶需求；接著，定義迭代次數(shù)，設(shè)置開始迭代次數(shù)Nc=0，將Ncmax定義為70；然后定義其他參數(shù)，將n設(shè)置為網(wǎng)點內(nèi)的客戶數(shù)量，將m設(shè)置為螞蟻數(shù)，最后設(shè)置α、β、ρ、參數(shù)的值。

步驟2： 建立好禁忌表，將所以螞蟻設(shè)定好，準備遍歷。

3? ? 模型應用

通過搜集資料，查詢冷鏈相關(guān)數(shù)據(jù)有中心點坐標（80，80）、需求量0t、服務時間0、最佳時間窗為5：30—9：30、可接受時間為5：00—10：00；其他客戶點坐標（40，66）、需求量0.33t、服務時間15、最佳時間窗6：00—6：30、可接受時間為5：30—7：00等，客戶點共32個。

通過改進蟻群算法在考慮客戶滿意度、碳排放成本和車輛最大載重量等因素下計算最優(yōu)配送路徑，求得最優(yōu)配送方案如表1所示。

由表1可知，最優(yōu)配送方案為調(diào)用6輛車分別按以下路徑配送，配送路程和成本如表2所示。

由表2可知，改進蟻群算法有效降低了配送總路程、配送總成本，相較傳統(tǒng)蟻群算法，改進蟻群算法的總路程縮短0.71%、成本減少17.6%，由此可見，改進蟻群算法較傳統(tǒng)蟻群算法提高了配送效率、更加經(jīng)濟性。

由圖1可以看出，改進蟻群算法計算求得的路徑有效縮短了配送距離，由起初的1 400km不斷優(yōu)化最終達到1 100km到1 150km，通過優(yōu)化路程減少了33%左右，大大縮短了配送時間，更大程度地滿足了客戶需求。

由圖2可知，通過算法有效降低了配送成本，配送成本從最大峰值6 400元變?yōu)? 891元，通過優(yōu)化成本節(jié)省了近8.64%，減輕了配送的經(jīng)濟負擔，使得配送中心的配送方案更加經(jīng)濟化，實現(xiàn)合理分配。

4? ? 結(jié)? ? 語

本文針對冷鏈物流運輸過程中的成本問題建立了優(yōu)化模型，以碳成本、時間懲罰成本、變質(zhì)成本最低為目標；并利用改進蟻群算法對模型進行求解，避免了傳統(tǒng)蟻群算法求解較慢和求解局部最優(yōu)的情況，求解效果較好。

參考文獻：

[1] 李海波．農(nóng)產(chǎn)品冷鏈物流體系及配送路徑優(yōu)化研究[J]． 現(xiàn)代食品，2022，28（5）：89-92.

[2] 陳靜，劉玒玒．基于蟻群算法的冷鏈物流路徑優(yōu)化研究[J]．交通科技與經(jīng)濟，2021，23（5）：38-44.

[3] 劉志碩，劉若思，陳哲．基于混合蟻群算法的冷鏈電動汽車車輛路徑問題[J]．計算機應用，2022，42（10）：3244-3251.

[4] 王曉寧．農(nóng)超對接模式下生鮮農(nóng)產(chǎn)品冷鏈物流車輛配送路徑研究[D]．南昌：華東交通大學，2014.

[5] 王靜．眾包環(huán)境下基于改進蟻群算法的外賣配送路徑優(yōu)化研究[D]．合肥：合肥工業(yè)大學，2019.

[6] 陳鑫，王海寶，羅強，等．基于改進蟻群算法的柑橘采摘最優(yōu)路徑[J]．安徽大學學報（自然科學版），2022，46（1）：68-74.