基于蟻群算法的速凍蔬菜配送路徑優(yōu)化研究

吳雨婷，葉 勇，駱宏敏

(安徽農(nóng)業(yè)大學 信息與計算機學院，安徽 合肥 230001)

中國是農(nóng)產(chǎn)品大國，隨著社會進步、人民生活水平提升，速凍蔬菜以其無需復(fù)雜的加工過程和不亞于新鮮蔬菜的營養(yǎng)程度等優(yōu)勢悄然興起。速凍蔬菜是指從采摘處理到加工處理整個過程控制在4～12 h內(nèi)，并確保在30 min以內(nèi)其中心溫度從-1 ℃降到-5 ℃再降到-15 ℃以下，同時整個流通環(huán)節(jié)控制在-18 ℃以下的蔬菜。因此，如何合理的安排速凍蔬菜的配送就顯得尤為關(guān)鍵。

禁忌算法可以用來求解車輛路徑問題，但這種算法只是對由遺傳算法得出的初始解進行優(yōu)化；模擬退火算法具有全局搜索、收斂速度快等特點，也可以求解車輛路徑問題；但當解決帶時間窗車輛路徑問題時應(yīng)選擇具有求解組合優(yōu)化問題良好特性的遺傳算法[1]。蟻群算法屬于仿生算法，是最近幾年迅速發(fā)展的一類算法，具有分布式、啟發(fā)式、魯棒性等特點，快速高效，原理簡單，相較而言不易陷入局部最優(yōu)解或過早收斂，搜索能力強，相對缺點不太突出。將蟻群算法結(jié)合時間窗建立配送優(yōu)化模型，通過對冷鏈物流配送路徑優(yōu)化的研究，構(gòu)建安全有效的冷鏈物流配送系統(tǒng)，對農(nóng)業(yè)、物流業(yè)以及民生都具有十分重要的意義[2]。

1 安徽某公司速凍蔬菜配送背景介紹

1.1 速凍蔬菜的市場需求

速凍蔬菜不僅可以保留其原料的各種生化形態(tài)和營養(yǎng)價值，同時解凍后的汁液中還含有無機鹽、有機酸和骨膠等可溶性營養(yǎng)物質(zhì)[3]。

中國報告大廳出版的2017-2022年中國保鮮速凍蔬菜行業(yè)市場發(fā)展現(xiàn)狀及投資前景預(yù)測報告對2017年1-10月中國速凍食品制造出口交貨值統(tǒng)計表(如表1所示)，直觀地表明了速凍食品的市場空間[4]。

中國速凍蔬菜的出口市場主要有日本、德國、韓國、泰國等國家，其中日本是最主要的市場，其次是德國，兩者之和占出口總量的90%。中國速凍蔬菜出口的前景仍十分樂觀[5]。

1.2 安徽某公司現(xiàn)狀

安徽某公司地處某市某縣開發(fā)區(qū)，主營進出口速凍蔬菜及蔬菜粉，海外市場開闊；地理位置相對比較優(yōu)越，距附近兩大機場只有100 km的路程；公司設(shè)備較為全面，技術(shù)較為先進，原料獲取較為便捷。

表1 2017年1-10月中國速凍食品制造出口交貨值統(tǒng)計表

在采購過程中，由于各生產(chǎn)基地與工廠有一定距離，所以新鮮蔬菜在進行簡單的保濕處理后就被運往工廠，途中各種生化反應(yīng)導(dǎo)致的貨物損耗一直難以避免；在加工過程中，由于員工都是就近招募的農(nóng)民，學歷水平低下，工作中難免會出現(xiàn)差錯而不自知，也會導(dǎo)致貨物出現(xiàn)損耗。而在運輸配送過程中，由于公司的地理位置不夠優(yōu)越，無論是就近的機場還是港口，都需要不近的一段距離，而速凍蔬菜的價格并不比新鮮蔬菜的價格昂貴多少，所以空運是極為不經(jīng)濟的；水運會因為配送時間過長而增加冷藏集裝箱的使用成本；對于相對來說最經(jīng)濟的陸運，由于公司沒有配備專門的物流人才，貨物的運輸路徑往往都是由經(jīng)驗豐富的駕駛員決定，也會導(dǎo)致配送時間、配送路線和配送成本不經(jīng)濟的情況發(fā)生。

綜上所述，在速凍蔬菜發(fā)展極為迅猛的今天，安徽某公司雖然作為一家主營進出口速凍蔬菜的公司，實際上其盈利空間并不高。

2 案例分析

螞蟻在運動過程中，會留下一種稱為信息素的東西，信息素的濃度決定著螞蟻的運動方向，同時其本身具有一定的揮發(fā)作用[6]。利用蟻群算法解決安徽某公司速凍蔬菜配送至華東九大海關(guān)出口國外路徑優(yōu)化問題，可簡化為利用蟻群算法解決旅行商問題。

安徽某公司速凍蔬菜的華東配送目的地有福州、杭州、合肥、南昌、南京、寧波、青島、上海、廈門9個海關(guān)。使用在線地圖開放平臺坐標拾取器功能，確定安徽某公司與華東配送地區(qū)九大海關(guān)實際地理坐標。根據(jù)兩兩城市實際配送路線，確定安徽某公司與華東配送地區(qū)九大海關(guān)實際地理距離，如表2所示。根據(jù)安徽某與華東地區(qū)九大海關(guān)實際地理坐標畫出他們的地理位置，如圖1所示。

安徽某公司向華東地區(qū)九大海關(guān)配送速凍蔬菜在和縣以北、無須過江的海關(guān)如合肥、青島為第一批次；須過江但距和縣地理位置不遠的海關(guān)如杭州、南昌、南京、寧波、上海為第二批次；距和縣地理位置稍遠的海關(guān)如福州、廈門為第三批次。

表2 安徽某公司與華東地區(qū)九大海關(guān)實際地理距離 km

圖1 安徽某公司與九大海關(guān)實際地理位置 圖2 安徽某公司現(xiàn)在實施的配送路徑

根據(jù)表2中安徽某公司與華東地區(qū)九大海關(guān)實際地理距離，得出安徽某公司公司正實施的速凍蔬菜配送里程數(shù)為：

147.5+698.5+600.6+904.2+257.6+1 088.4+70.2+582.9+522.9+155.9+221.4+378.1=5 628.2(km)

3 基于蟻群算法的速凍蔬菜配送路徑優(yōu)化研究

3.1 優(yōu)化分析

通過對安徽某公司與華東地區(qū)九大海關(guān)實際地理坐標進行 [(橫坐標-24)×100，(縱坐標-115)×100] 數(shù)據(jù)處理。為便于后期模擬，按四舍五入對橫縱坐標數(shù)據(jù)進行取整，獲得改進后的相對坐標如表3所示。改進后的安徽某公司與華東地區(qū)九大海關(guān)相對地理坐標在坐標系中的相對位置如圖3所示。

在安徽某公司第一批與第三批銜接過程中需返回公司造成不必要的經(jīng)濟損失的前提下，可以合并第一批次與第三批次；同時每一批次都需要至少兩位駕駛員，一次完整的配送任務(wù)完成至少需要四位駕駛員；而且并非每批次配送貨物都占滿冷藏集裝箱，三批次貨物每周配送總量大致在20 t左右，一輛裝有20尺柜冷藏集裝箱的貨車足夠滿足需求。故而，將九大海關(guān)配送路線整合成用蟻群算法解決旅行商問題的思想。只使用一輛裝有20尺柜冷藏集裝箱的貨車以一個批次完成配送任務(wù)。鑒于旅行商問題的特殊性，暫不考慮中心配送點安徽某公司，先得出旅行商問題的最優(yōu)結(jié)果，即9個海關(guān)的配送順序，再從中確定哪兩個相鄰海關(guān)與該公司的總距離最短，斷開并將其穿插進去，即可得到車輛路徑問題的最優(yōu)結(jié)果。

表3 改進后的安徽某公司與華東地區(qū)九大海關(guān)相對地理坐標

圖3 改進后的安徽某公司與九大海關(guān)相對地理坐標

3.2 參數(shù)設(shè)置

(1)螞蟻數(shù)量m。根據(jù)蟻群算法的特性以及大量實驗數(shù)據(jù)得知，蟻群系統(tǒng)算法的性能是否優(yōu)良取決于螞蟻數(shù)量m是否滿足城市規(guī)模與m值相等。

(2)信息啟發(fā)式因子α。根據(jù)蟻群算法的特性以及大量實驗數(shù)據(jù)得知，蟻群系統(tǒng)算法的性能是否優(yōu)良取決于信息啟發(fā)式因子α是否滿足α∈[1,1.5]。

(3)期望值啟發(fā)式因子β。根據(jù)蟻群算法的特性以及大量實驗數(shù)據(jù)得知，蟻群系統(tǒng)算法的性能是否優(yōu)良取決于期望值啟發(fā)式因子β是否滿足β∈[0,3]。

(4)全局信息素揮發(fā)參數(shù)ρ。根據(jù)蟻群算法的特性以及大量實驗數(shù)據(jù)得知，蟻群系統(tǒng)算法的性能是否優(yōu)良取決于全局信息素揮發(fā)參數(shù)ρ是否滿足ρ∈[0.1,0.5]。

(5)局部信息素揮發(fā)參數(shù)ζ。根據(jù)蟻群算法的特性以及大量實驗數(shù)據(jù)得知，蟻群系統(tǒng)算法的性能是否優(yōu)良取決于局部信息素揮發(fā)參數(shù)ζ是否滿足ζ∈[0.1,0.3]。

(6)狀態(tài)轉(zhuǎn)移公式中的q0。根據(jù)蟻群算法的特性以及大量實驗數(shù)據(jù)得知，蟻群系統(tǒng)算法的性能是否優(yōu)良取決于狀態(tài)轉(zhuǎn)移公式中的q0是否滿足q0∈[0.6,0.9][7]。

綜上可知，可對該模型中有關(guān)參數(shù)進行確定，當城市節(jié)點數(shù)目為9時，螞蟻數(shù)量為9，信息啟發(fā)式因子定為1.25，期望值啟發(fā)式因子定為1.5，全局信息素揮發(fā)參數(shù)定為0.3，局部信息素揮發(fā)參數(shù)定為0.2，狀態(tài)轉(zhuǎn)移公式中的q0定為0.75。

3.3 模型求解

3.3.1 編寫代碼并運行

圖4 基于蟻群算法的冷鏈物流配送路徑優(yōu)化結(jié)果

根據(jù)蟻群算法數(shù)學模型及算法流程編寫代碼，同時將城市節(jié)點數(shù)目N=9、螞蟻數(shù)量M=9、最大循環(huán)次數(shù)NcMax=200、信息啟發(fā)式因子alpha=1.25、期望值啟發(fā)式因子beta=1.5、全局信息素揮發(fā)參數(shù)rou=0.3、局部信息素揮發(fā)參數(shù)alpha1=0.2、狀態(tài)轉(zhuǎn)移公式中的q0=0.75帶入。設(shè)定安徽某公司速凍蔬菜華東配送地區(qū)九大海關(guān)編號如下：0代表福州，1代表杭州，2代表合肥，3代表南昌，4代表南京，5代表寧波，6代表青島，7代表上海，8代表廈門。

安徽某公司速凍蔬菜華東配送地區(qū)九大海關(guān)坐標如下：

double C[N][2]={

{201,441},{627,514},{778,221},{467,87},{803,380},

{587,654},{1 206,531},{694,679},{46,307}

}；

運行結(jié)果如圖4所示。

3.3.2 優(yōu)化結(jié)果

圖5 改進后的速凍蔬菜配送路徑1 圖6 改進后的速凍蔬菜配送路徑2

優(yōu)化后的總配送路線長度為：

70.2+559.3+709.8+221.4+155.9+641.7+257.6+630.7+435.8+147.5=3 829.9(km)

根據(jù)上文，安徽某公司正實施的速凍蔬菜配送總里程數(shù)為5 628.2 km，改進后的基于蟻群算法的冷鏈物流配送路徑優(yōu)化研究模型得出的配送總里程數(shù)為3 829.9 km，是原數(shù)值的0.68倍，足夠投入實施、完成優(yōu)化。此外，改進后的基于蟻群算法的冷鏈物流配送路徑優(yōu)化研究模型完成一次完整的配送任務(wù)只需要兩位駕駛員，很大程度上節(jié)省了人力物力財力，而并沒有阻礙公司正常運營。

4 結(jié) 語

利用蟻群算法建立了安徽某公司速凍蔬菜在華東地區(qū)的配送路線優(yōu)化模型，通過優(yōu)化將配送里程節(jié)省了32%，配送人員減少了一半，可以很好地為公司節(jié)約相關(guān)的人力、物力、財力成本。蟻群算法在眾多領(lǐng)域中已展現(xiàn)出它獨特的魅力與力量，作為新興仿生進化算法中一種相對簡單的新原理，蟻群算法的發(fā)展空間相當可觀。但同時，冷鏈物流行業(yè)的發(fā)展空間也不容小覷，行業(yè)的具體實施標準、對設(shè)備和技術(shù)的投入、行業(yè)理念的推廣、管理與資金的回收等，都是可以研究的方向。