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

任傳榮 皇甫世誠(chéng) 黃來(lái)望

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

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

中圖分類號(hào)：F259.22；U116文獻(xiàn)標(biāo)志碼：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ò)電子商務(wù)的發(fā)展，網(wǎng)購(gòu)日漸成為人們?nèi)粘Ｙ?gòu)物的首要方式，其中一種購(gòu)物類別便是對(duì)生鮮產(chǎn)品的購(gòu)買(mǎi)。對(duì)于生鮮產(chǎn)品來(lái)說(shuō)，最重要的就是保證生鮮產(chǎn)品送達(dá)時(shí)的新鮮度，因?yàn)槠浔Ｙ|(zhì)期也就幾天左右，生鮮產(chǎn)品如果不及時(shí)送到，則會(huì)導(dǎo)致產(chǎn)品腐壞，為了解決這一問(wèn)題，物流行業(yè)便推出了冷鏈物流運(yùn)輸新方式。

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

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

1? ? 模型建立

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

1.1? ? 碳成本模型

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

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

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

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

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

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

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

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

改進(jìn)蟻群算法步驟如下。

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

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

3? ? 模型應(yīng)用

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

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

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

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

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

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

4? ? 結(jié)? ? 語(yǔ)

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

參考文獻(xiàn)：

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

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

[3] 劉志碩，劉若思，陳哲．基于混合蟻群算法的冷鏈電動(dòng)汽車(chē)車(chē)輛路徑問(wèn)題[J]．計(jì)算機(jī)應(yīng)用，2022，42（10）：3244-3251.

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

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

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