基于改進蟻群算法的水產(chǎn)品運輸車路徑優(yōu)化策略

李鵬飛，沈最意

(1.浙江海洋大學(xué)港航與交通運輸工程學(xué)院,浙江舟山 316022;2.浙江海洋大學(xué)經(jīng)濟與管理學(xué)院,浙江舟山 316022)

我國東部海洋資源分布廣,東南方沿海城市是我國水產(chǎn)品企業(yè)聚集區(qū)域。目前,國內(nèi)市場上鮮活水產(chǎn)品的需求量增長迅速,加之水產(chǎn)養(yǎng)殖業(yè)的發(fā)展進程加快,與水產(chǎn)品息息相關(guān)的冷鏈物流建設(shè)逐漸表現(xiàn)出高速發(fā)展的趨勢。但中國幅員遼闊,在水產(chǎn)養(yǎng)殖業(yè)較不發(fā)達的內(nèi)地地區(qū),人們對于鮮活水產(chǎn)品的需求更加難以得到實現(xiàn),加之我國目前冷鏈布局分散,易腐產(chǎn)品在流通過程中得不到有效的質(zhì)量保障,導(dǎo)致了水產(chǎn)品不同地域價格的巨大差異[1]。

而水產(chǎn)品的運輸質(zhì)量由冷鏈物流中3T原則(time、temperature、tolerance)的實現(xiàn)程度所決定。其中第一項就是指運輸實時性,由于水產(chǎn)品冷鏈配送環(huán)節(jié)銜接的不緊密,容易出現(xiàn)斷鏈現(xiàn)象,會對水產(chǎn)品質(zhì)量產(chǎn)生不利的影響,則需要在配送過程中給各個需求點加上運達時間窗,而元啟發(fā)式算法中的蟻群算法對解決具有時間窗的大型多回路路徑規(guī)劃問題(VRP問題)具有良好的天然適應(yīng)性,雖然蟻群算法本身也存在著搜索時間長,過早收斂等問題。但通過公式的改進和參數(shù)的選取,這些不足都可以得到很好的改善。為此,國內(nèi)外學(xué)者也提出各種改進方法。

1991年,在歐洲人工生命會議上,意大利學(xué)者COLORNI,et al[2]第一次提出了蟻群算法。隨后為了國內(nèi)外專家學(xué)者提出大量的改進方法,STTITZLE,et al[3]提出了MMAS算法,將信息素限制在一定范圍內(nèi),防止出現(xiàn)信息素過度集中,提高了算法解的多樣性。BULLNHEIMER,et al[4]發(fā)表了基于路徑長度排序的蟻群算法,關(guān)鍵點是將每次迭代后,按照每只螞蟻路徑長度排列,只允許排名較前以及最優(yōu)螞蟻釋放信息素;國內(nèi)學(xué)者王穎等[5]提出了參數(shù)的自適應(yīng)變化,提高了解的多樣性,從而針對算法易得出局部最優(yōu)解的弊端;閔克學(xué)等[6]利用蟻群算法易與其它算法相結(jié)合的優(yōu)點,提出了一種將粒子群與蟻群優(yōu)化相結(jié)合的算法,從而提高了全局迭代求解效果。

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

1.1 水產(chǎn)品保鮮時間窗

每一種水產(chǎn)品都會有不同的耐藏性,假設(shè)某一種水產(chǎn)品的保質(zhì)時間窗為(ready time,due time),service time表示完成服務(wù)所需要的時間,即service time(st)=due time(dt)-ready time(rt),主要依據(jù)客戶接收貨物的效率以及貨物的量來設(shè)定。rt主要依據(jù)客戶方便接受貨物的時間決定,dt則是依據(jù)水產(chǎn)品的保質(zhì)期限以及客戶對該貨物下一步的處理方式來確定,而st主要根據(jù)該客戶點需求量的大小以及該點的服務(wù)。運輸車輛須在時間窗[rt,dt]滿足客戶服務(wù)要求,如果運輸車輛提前或者延期到達客戶點,則必須承擔一定的懲罰費用,并且客戶有權(quán)拒絕所配送的水產(chǎn)品[7]。

1.2 不確定性路況描述

在水產(chǎn)品的運輸配送中,可能會發(fā)生一些常發(fā)性交通擁堵例如上下班高峰期、假期等,從而導(dǎo)致配送效率的降低。此時,不應(yīng)該認為各個客戶點之間運輸時間固定不變,而是具有相應(yīng)的分布函數(shù)以及分布規(guī)律的隨機變量?？蓪⒎南鄳?yīng)分布函數(shù)的不確定性路況條件轉(zhuǎn)變?yōu)榇_定性條件,再加入到路徑規(guī)劃數(shù)學(xué)模型中求解。同時在大部分的實際狀況下,配送過程中,準確的兩點之間運輸時間分布函數(shù)難以得知,但在不同時間內(nèi)某一路段的運輸時間長短(tij)的概率(pij)可以通過某些參考因素的定量分析和估算或者按照之前的運輸經(jīng)驗得知。則可以通過經(jīng)驗分布得到該路段新的通過時間,即：

1.3 VRP問題運輸模型描述

假設(shè)有一個水產(chǎn)品物流配送中心,各個需求點的坐標矩陣為C,其每輛水產(chǎn)品運輸車的最大貨物載重量為D,客戶i的需求量為為di(i∈V),V客戶集合,S為V的任一子集合。rti表示客戶i允許卸載貨物的最早時刻,dti表示客戶i允許完成卸載的最遲時刻,sti表示完成卸貨所需的時間,tij為運輸車從客戶i到客戶j的運輸時間,wi表示開始為i點供貨所需的等待時間,a0是出車的單位成本,a1表示水產(chǎn)品不能在規(guī)定服務(wù)時間送達而增加的單位成本,ti表示貨物到達點的時間,ei為客戶i所容許卸貨最早開始時刻,li為客戶i容許卸貨最晚開始的時刻[8]?；炯僭O(shè)條件為：(a)所有需求點和水產(chǎn)品物流配送中心的坐標位置已知;(b)各個需求點的供貨量和水產(chǎn)品保鮮時間窗已知;(c)每個需求點只由一輛車經(jīng)過一次;(d)運輸車從水產(chǎn)品物流配送中心開始,通過幾個需求點后返回配送中心,期間行駛方向是一直連續(xù)的,不能發(fā)生折返;(e)假定不確定性的道路通行狀況服從相應(yīng)統(tǒng)計分布,即某兩點之間運輸時間的概率分布在車輛運輸之前是已知的。配送的目標函數(shù)為：

其中,包含四項：第一項為水產(chǎn)品運輸車輛的出車成本。第二項為水產(chǎn)品運輸車輛在路程上消耗的總運輸費用。第三項為水產(chǎn)品運輸車輛的時間懲罰成本,即運輸車輛在時間窗之外到達所造成的違約金。其約束條件為：設(shè)

約束(5)為水產(chǎn)品運輸車輛負載限制;約束(6)保證每個水產(chǎn)品運輸車輛對每個客戶只訪問過一次;約束(7)～(9)保證了可行回路;約束(10)是某條道路上相鄰任務(wù)并存的前提;約束(11)表示時間窗約束。

2 改進的蟻群算法

2.1 路徑構(gòu)造

設(shè)tik為第k輛車到達i點的時刻,為了在選擇下一個客戶點時,使等待時間較短的客戶被選擇作為下一運輸點的可能性更大,在狀態(tài)轉(zhuǎn)移規(guī)則中加入等待因素

因此對狀態(tài)轉(zhuǎn)移概率公式進行如下修改：

使用了偽隨機比例規(guī)則,在解的快速收斂以及解的多樣性之間取得較好的平衡。其中n0∈ [0.1]為一

2.2 信息素改進

2.2.1 信息素全局更新步驟

當m只螞蟻都完成一次循環(huán)后,即所有螞蟻構(gòu)造完可行路徑R時,將它與全局最優(yōu)路徑R*進行比較,其中

為了使每只螞蟻的迭代運輸方案對信息素增減產(chǎn)生正負反饋,依據(jù)圖1規(guī)則使每一次迭代所有螞蟻R上的信息素實行全局更新[9]：

圖1 全局信息素更新步驟Fig.1 Global pheromone updating steps

Q是一個常量,表示螞蟻完成一次搜索所釋放的信息素總量;L*為螞蟻探索到的最優(yōu)路徑長度。ρ為信息素保留程度,在算法初期為了解的多樣性可以取相對較大值,而在中后期為了最優(yōu)解的快速收斂,使信息素較為集中,可以取較小值。

2.2.2 MMAS思想的引入

為了避免在初期陷入局部最優(yōu)解,可以借鑒MMAS,對信息素在一定范圍內(nèi)進行限制,避免喪失摸索新路徑的可能[11]。即

2.3 算法步驟

Step1：定義各參數(shù),C,Q,α,β,λ,ρ,任意兩點間路段上的信息素值初始為τmax,設(shè)定NC max為最大迭代次數(shù)。

Step2：將m只螞蟻置于水產(chǎn)品配送中心點,并使該點置于當前解,采用依序構(gòu)建解的方法。

Step3：對m只螞蟻,根據(jù)式(13)計算轉(zhuǎn)移概率,同時要求滿足保鮮時間窗以及載重約束,選擇除當前解集外的另一需求點,然后將其置于當前解中;若找不到滿足運輸車輛載重約束或時間約束的下一個節(jié)點時,則返回水產(chǎn)品配送中心[10]。

Step4：循環(huán)步驟(3),直至m只螞蟻都到訪了所有點,得到了相應(yīng)條以水產(chǎn)品配送中心為起點并且滿足約束條件的回路,每只螞蟻的若干個回路相當于由配送中心所發(fā)出的若干個運輸車輛所形成的配送路徑,計算并保存最短路徑R*。

Step5：根據(jù)2.2節(jié)所述方法實行全局更新以及對ρ進行調(diào)整,調(diào)整規(guī)則為：

Step6：判斷迭代數(shù)是否達到最大值,如果是,終止運輸,不然則清空禁忌表,轉(zhuǎn)到步驟2。

3 算例仿真

為了檢驗算法的性能,以舟山市地圖為基礎(chǔ),通過MATLAB進行實例仿真實驗。

在浙江省舟山市的百度地圖上截取一部分平面交通圖(圖2),將水產(chǎn)品生產(chǎn)加工公司或者單位作為需求點,以舟山國際水產(chǎn)城物流配送中心為始發(fā)點。共有25個節(jié)點,其中1號節(jié)點為配送點(表1)。為了使得到的解更科學(xué)有效,進行了10次隨機測試,10次測試中取得的最優(yōu)試驗結(jié)果并且與基本蟻群算法最優(yōu)結(jié)果進行比較。

圖2 平面交通圖Fig.2 Flat road map

表1 節(jié)點經(jīng)緯度Tab.1 Node latitude and longitude

m=30,Q=100,α=1,β=3,λ=1,ρ=0.9,τmax=1,τmin=0.3,迭代次數(shù)限制為 50 次,運輸車速率為 40 km/h,水產(chǎn)品物流中心出車費用為100,單位公里車費為1,單位時間超前或延期懲罰費用為0.4,客戶數(shù)量為24,目標函數(shù)曲線為運輸總費用[12]。通過基本蟻群算法仿真的最優(yōu)結(jié)果如圖3～4所示。

圖3 基本蟻群算法迭代過程Fig.3 Iterative process of basic ant colony algorithm

圖4 基本蟻群算法最優(yōu)路徑Fig.4 The optimal path of basic ant colony algorithm

基本蟻群算法路徑方案為：

(1)1-＞15-＞16-＞14-＞17-＞18-＞22-＞19-＞1

(2)1-＞6-＞3-＞8-＞10-＞21-＞7-＞5-＞2-＞1

(3)1-＞12-＞9-＞4-＞23-＞20-＞11-＞25-＞1

(4)1-＞13-＞24-＞1

Least_Cost=725.309 7

通過同樣的參數(shù),使用改進蟻群算法對舟山市部分地圖上的水產(chǎn)品生產(chǎn)加工公司或者單位進行仿真實驗,得出以下結(jié)果(圖5、圖6)。

圖5 改進蟻群算法迭代過程Fig.5 The iterative process of improved ant colony algorithm

圖6 改進蟻群算法最優(yōu)規(guī)劃路徑Fig.6 The optimal planning path of the Improved ant colony algorithm

改進蟻群算法路徑方案為：

(1)1-＞15-＞16-＞22-＞19-＞17-＞18-＞14-＞1

(2)1-＞13-＞9-＞7-＞21-＞10-＞2-＞5-＞4-＞1

(3)1-＞6-＞3-＞12-＞8-＞23-＞24-＞25-＞1

(4)1-＞20-＞11-＞1

Least_Cost=625.1464

從圖3～6的對比可知,改進蟻群算法相對于基本蟻群算法得到全局最優(yōu)解的迭代次數(shù)更少。求解效果方面,改進蟻群算法得到的最少總費用是625.146 4,基本蟻群算法得到最少總費用是725.309 7,并且種群平均費用兩者也相差較大,可見路徑規(guī)劃方案的質(zhì)量明顯上升。表明改進的蟻群算法相對于一般的蟻群算法,可以通過相對較少的迭代得到全局最優(yōu)解,并且收斂效果好,全局收斂效率高。

4 結(jié)論

運輸配送是水產(chǎn)品冷鏈物流中至關(guān)重要的節(jié)點之一。選擇合理、高效的運輸路徑有利于保證水產(chǎn)品的鮮活性,不僅節(jié)省了運輸成本,并且加強了配送的準確性以及速率。針對水產(chǎn)品耐藏性較差的特點,提出了水產(chǎn)品的保質(zhì)時間窗以及道路狀況的不確定性,降低了可能由斷鏈現(xiàn)象以及擁堵所造成的成本損耗,更加符合了配送作業(yè)實際情況。并且使用改進的蟻群算法求解該運輸模型,包括信息素全局更新方法的改進、狀態(tài)轉(zhuǎn)移規(guī)則中等待因素引入以及信息素的限制等,最后利用MATLAB進行仿真模擬。仿真測試結(jié)果說明改進蟻群算法優(yōu)于基本蟻群算法,是可靠有效的。

[1]李 利,江 敏,馬 允,等.水產(chǎn)品?；钸\輸方法綜述[J].安徽農(nóng)業(yè)科學(xué),2009,37(15)：7 303-7 305.

[2]COLORNI A,DORIGO M,MANIEZZO V.Distributed Optimization by Ant Colonies[C].Ecal91-European Conference on Artificial Life,1992：134-142.

[3]STUTZLE T,HOOS H.MAX-MIN Ant System and local search for the traveling salesman problem[C].IEEE International Conference on Evolutionary Computation.IEEE,2002：309-314.

[4]BULLNHEIMER B,HARTL R F,STRAUSS C.A New Rank Based Version of the Ant System-A Computational Study[J].Central European Journal of Operations Research,1999,7(1)：25-38.

[5]王 穎,謝劍英.一種自適應(yīng)蟻群算法及其仿真研究[J].系統(tǒng)仿真學(xué)報,2002,14(1)：31-33.

[6]閔克學(xué),葛宏偉,張 毅,等.基于蟻群和粒子群優(yōu)化的混合算法求解TSP問題[J].吉林大學(xué)學(xué)報：信息科學(xué)版,2006,24(4)：402-405.

[7]黃華芳,門建婷,陳紹慧,等.基于改進蟻群算法的果蔬運輸車輛路徑優(yōu)化的研究[J].保鮮與加工,2011,11(3)：24-25.

[8]蔣 波.基于遺傳算法的帶時間窗車輛路徑優(yōu)化問題研究[D].北京：北京交通大學(xué),2010：8-17.

[9]李 琳,劉士新,唐加福.改進的蟻群算法求解帶時間窗的車輛路徑問題[J].控制與決策,2010,25(9)：1 381-1 382.

[10]楊仁法,龔延成.帶時間窗車輛調(diào)度問題的蟻群算法[J].交通運輸工程學(xué)報,2009,9(4)：71-74.

[11]費瑞玉,馬文華.基于鄰域搜索的改進最大最小蟻群算法[J].計算機仿真,2014,34(12)：261-262.

[12]樊世清,婁 丹,孫 瑩.生鮮農(nóng)產(chǎn)品冷鏈物流車輛配送路徑優(yōu)化研究[J].保鮮與加工,2017,17(6)：106-111.