基于改進蟻群算法的農業運輸車輛路徑優化研究

趙曉俠， 鞠成恩

(昆明理工大學信息工程與自動化學院，云南昆明 650500)

?

基于改進蟻群算法的農業運輸車輛路徑優化研究

趙曉俠， 鞠成恩

(昆明理工大學信息工程與自動化學院，云南昆明 650500)

針對農產品在運輸過程中運輸時間長易變質等問題，合理規劃果蔬運輸車輛的配送路徑。在基本蟻群算法的基礎上，提出適合求解路徑規劃的改進型算法，同時提出了自適應調整的方案，提高跳出局部優解的能力以及算法的全局收斂性。仿真試驗結果驗證了改進型算法的可行性和高效性，從而達到運輸車輛路徑優化的目的，為提高農產品的運輸效率、降低成本、提高收益提供了理論依據。

農業；運輸；路徑優化；蟻群算法

農產品自身的特點決定了農產品在運輸中要盡量降低運輸費用和減少產品損耗，所以，要合理地規劃農產品運輸的路線，降低因為運輸而產生的經濟損失。筆者從蟻群算法入手，通過加入路況關系系數改善了路徑選擇缺陷，進而改進了螞蟻算法，使得求解結果更加接近實際。再運用適應策略和以概率為基礎的輪盤賭策略，避免停留在局部最優解，實現最優路徑的選擇，達到優化運輸路線的目的。

1 農業運輸車輛路徑問題描述

于1959年由Dantzig提出的路徑問題來源于生活當中的交通運輸問題，它是一個典型的NP-hard問題。將該問題運用在農產品配送過程中，要求農產品能在顧客規定的時間內到達指定配送點，而應根據客觀條件就近選擇配送點。車輛從配送中心出發，完成各配送點運輸任務后再回到配送中心，問題的目標函數通常是車輛行駛的距離最短以及車輛數和運輸成本最小化[1-2]。由于該問題的復雜性，尋找一種高效、精確的算法按照普通的方法是非常困難的，于是筆者嘗試利用蟻群算法來求解該問題。

2 蟻群算法概述及其在農產品運輸中的應用

蟻群算法最早由意大利學者Dorigo于1991年提出，該算法模擬了自然界中螞蟻覓食路徑的搜索過程，是一種概率型的最優路徑搜索算法，目前已被廣泛應用于各種組合優化問題[3]。

設螞蟻總數為m，當在時刻t位于配送點i的螞蟻k(k=1，2，…，m)要選擇下一個配送點j時，根據下式的狀態轉移概率來選擇最優路徑：

(1)

式中，τij(t)表示t時刻配送點i到下一配送點j路徑上的信息素濃度，開始時刻t=0時τij(0)=C(C為常數)；j是螞蟻要選擇的下一個配送點，該配送點包含在該螞蟻還沒有到達的配送點集合“allowed”中；α是信息啟發因子，反映路徑上的信息量對螞蟻選擇下一條路徑的影響；ηij(t)是啟發信息，反映螞蟻對路徑的主觀選擇；β是期望啟發因子，啟發因子的大小反映了啟發信息在螞蟻自主選擇路徑過程中的受重視程度；s為還未被選擇的配送點，它被包含在“allowed”集合中。

為模擬真實環境信息素的揮發與更新，使用如下規則：

τij(t+n)=(1-ρ)·τij(t)+Δτij(t)

(2)

(3)

3 算法的改進

由于各條道路的路況和擁擠程度各不相同，在設置啟發信息時不能只從道路的遠近考慮，所以這里根據路況和擁擠程度將各條道路分成很好、比較好、一般、不好4個等級，在道路距離的基礎上乘以描述路況的系數K，使得求解過程更加接近實際。而且在傳統蟻群算法中，每次迭代時都需要重新計算狀態轉移概率，浪費了大量時間，為提高算法計算效率，在對信息素進行全局和局部更新后，可將信息素與路況系數相乘直接作為狀態轉移概率，由式(4)完成計算。

(4)

再根據傳統蟻群算法會過早陷入次優解的特點應用自適應策略[4-5]，螞蟻根據概率閥值q0判斷是否使用先驗選擇方式還是使用概率方式選擇路徑，當選擇了概率方式后再使用輪盤賭策略來選擇下一條路徑，以避免算法過早地陷入次優解。

4 仿真與分析

已知配送中心需要向18個農產品配送點(n=18)配送農產品，設置信息素的濃度τ0= 0.3、啟發信息因子β=5、啟發因子α=2、信息素的揮發系數ρ=0.2、螞蟻數量M=15、最大迭代次數Nmax=100、螞蟻釋放的信息素強度Q=1 000[6]。基于上述蟻群算法原理，按照圖1所示的流程圖步驟解決上述問題。

圖1 蟻群算法流程Flg.1 Ant colony algorithm flow chart

在圖2中為某地區配送農產品網點示意圖，配送中心位于星號處標0，而其他各配送點標明數字從1到18。

圖2 配送網點及車輛行駛路線Flg.2 Distribution network and vehicle routing

這里將整個區域劃分成3個子區域，采用3輛車的配送方式。第1條線路： 配送中心0→配送點2→配送點7→配送點10→配送點17→配送點14→配送點5→配送中心0。第2條線路：配送中心0→配送點3→配送點9→配送點16→配送點12→配送點6→配送中心0。第3條線路：配送中心0→配送點1→配送點4→配送點8→配送點11→配送點15→配送點18→配送點13→配送中心0。選擇其中一個區域將基本蟻群算法與改進后的蟻群算法進行比較，比較結果如圖3所示。 根據實際情況與仿真過程進行分析，采用1輛車進行配送，會受到路況影響或是配送量較大時無法滿足需要，所以該研究采用了3輛車的配送方式。這種選擇多輛車的分區

域運輸方式，保證了行駛路徑最短，同時提高了運輸效率、節約了運輸時間和運輸成本，更合理地完成配送。

5 結論

該研究針對農產品運輸問題的特殊性，提出了增加路況關系系數，簡化道路選擇概率的方法，加快了算法的收斂速度，同時為了增強迭代過程跳出局部最優解的能力，增加了自適應能力策略。在隨后的仿真試驗中表明，該研究的改進算法與傳統基本蟻群算法相比，達到了加快收斂速度，提高跳出局部最優解的能力，改善了蟻群算法優化運輸的路徑。

[1] 于航，張凱. 基于節約里程法的鮮活農產品物流配送車輛路線的最優設計[J].安徽農業科學 , 2011, 39(28):17701-17703.

[2] 王多宏，嚴余松．現代農業物流運作模式比較與構建[J].安徽農業科學, 2007, 35(35):11670，11722.

[3] 段海濱．蟻群算法原理及其應用[M]．北京:科學出版社，2005.

[4] GAJPAL Y,RAJENDRAN C,ZIEGLER H.An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs[J].The international journal of advanced manufacturing technology,2006,30(5):416-424.

[5] 陳崚,沈潔,秦玲,等.基于分布均勻度的自適應蟻群算法[J].軟件學報, 2003,14(8):1379-1387.

[6] DUAN H，WANG D B，YU X F.Research on the optimum configuration strategy for the adjustable parameters in ant colony algorithm[J].Journal of communication and computer, 2005(9):32-35.

Research on Path Optimization of Agricultural Transport Vehicles Based on Improved Ant Colony Algorithm

ZHAO Xiao-xia, JU Cheng-en

(Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming, Yunnan 650500)

In view of the problems of agricultural products in transportation, such as long time and easy to go bad, the distribution path of fruit and vegetable transport vehicles is reasonably planned. Based on the basic ant colony algorithm, an improved algorithm is proposed, which is suitable for solving path planning. The adaptive scheme is proposed to improve the ability of avoiding local optimal solution and the global convergence of the algorithm. The simulation results show that the improved algorithm is feasible and efficient. It can achieve the purpose of optimizing the route of transport vehicles, and provide theoretical basis for improving the efficiency of agricultural products transportation, reducing costs and improving income.

Agriculture; Transportation; Route optimization; Ant colony algorithm

國家自然科學基金地區基金項目(KKGD201303043)。

趙曉俠(1965- )，女，湖南長沙人，副教授，從事計算機應用及工業自動化等研究。

2016-08-18

S 229+.1

A

0517-6611(2016)33-0237-02