趙曉俠， 鞠成恩

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

?

基于改進(jìn)蟻群算法的農(nóng)業(yè)運(yùn)輸車輛路徑優(yōu)化研究

趙曉俠， 鞠成恩

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

針對(duì)農(nóng)產(chǎn)品在運(yùn)輸過程中運(yùn)輸時(shí)間長易變質(zhì)等問題，合理規(guī)劃果蔬運(yùn)輸車輛的配送路徑。在基本蟻群算法的基礎(chǔ)上，提出適合求解路徑規(guī)劃的改進(jìn)型算法，同時(shí)提出了自適應(yīng)調(diào)整的方案，提高跳出局部優(yōu)解的能力以及算法的全局收斂性。仿真試驗(yàn)結(jié)果驗(yàn)證了改進(jìn)型算法的可行性和高效性，從而達(dá)到運(yùn)輸車輛路徑優(yōu)化的目的，為提高農(nóng)產(chǎn)品的運(yùn)輸效率、降低成本、提高收益提供了理論依據(jù)。

農(nóng)業(yè)；運(yùn)輸；路徑優(yōu)化；蟻群算法

農(nóng)產(chǎn)品自身的特點(diǎn)決定了農(nóng)產(chǎn)品在運(yùn)輸中要盡量降低運(yùn)輸費(fèi)用和減少產(chǎn)品損耗，所以，要合理地規(guī)劃農(nóng)產(chǎn)品運(yùn)輸?shù)穆肪€，降低因?yàn)檫\(yùn)輸而產(chǎn)生的經(jīng)濟(jì)損失。筆者從蟻群算法入手，通過加入路況關(guān)系系數(shù)改善了路徑選擇缺陷，進(jìn)而改進(jìn)了螞蟻算法，使得求解結(jié)果更加接近實(shí)際。再運(yùn)用適應(yīng)策略和以概率為基礎(chǔ)的輪盤賭策略，避免停留在局部最優(yōu)解，實(shí)現(xiàn)最優(yōu)路徑的選擇，達(dá)到優(yōu)化運(yùn)輸路線的目的。

1 農(nóng)業(yè)運(yùn)輸車輛路徑問題描述

于1959年由Dantzig提出的路徑問題來源于生活當(dāng)中的交通運(yùn)輸問題，它是一個(gè)典型的NP-hard問題。將該問題運(yùn)用在農(nóng)產(chǎn)品配送過程中，要求農(nóng)產(chǎn)品能在顧客規(guī)定的時(shí)間內(nèi)到達(dá)指定配送點(diǎn)，而應(yīng)根據(jù)客觀條件就近選擇配送點(diǎn)。車輛從配送中心出發(fā)，完成各配送點(diǎn)運(yùn)輸任務(wù)后再回到配送中心，問題的目標(biāo)函數(shù)通常是車輛行駛的距離最短以及車輛數(shù)和運(yùn)輸成本最小化[1-2]。由于該問題的復(fù)雜性，尋找一種高效、精確的算法按照普通的方法是非常困難的，于是筆者嘗試?yán)孟伻核惴▉砬蠼庠搯栴}。

2 蟻群算法概述及其在農(nóng)產(chǎn)品運(yùn)輸中的應(yīng)用

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

設(shè)螞蟻總數(shù)為m，當(dāng)在時(shí)刻t位于配送點(diǎn)i的螞蟻k(k=1，2，…，m)要選擇下一個(gè)配送點(diǎn)j時(shí)，根據(jù)下式的狀態(tài)轉(zhuǎn)移概率來選擇最優(yōu)路徑：

(1)

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

為模擬真實(shí)環(huán)境信息素的揮發(fā)與更新，使用如下規(guī)則：

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

(2)

(3)

3 算法的改進(jìn)

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

(4)

再根據(jù)傳統(tǒng)蟻群算法會(huì)過早陷入次優(yōu)解的特點(diǎn)應(yīng)用自適應(yīng)策略[4-5]，螞蟻根據(jù)概率閥值q0判斷是否使用先驗(yàn)選擇方式還是使用概率方式選擇路徑，當(dāng)選擇了概率方式后再使用輪盤賭策略來選擇下一條路徑，以避免算法過早地陷入次優(yōu)解。

4 仿真與分析

已知配送中心需要向18個(gè)農(nóng)產(chǎn)品配送點(diǎn)(n=18)配送農(nóng)產(chǎn)品，設(shè)置信息素的濃度τ0= 0.3、啟發(fā)信息因子β=5、啟發(fā)因子α=2、信息素的揮發(fā)系數(shù)ρ=0.2、螞蟻數(shù)量M=15、最大迭代次數(shù)Nmax=100、螞蟻釋放的信息素強(qiáng)度Q=1 000[6]?；谏鲜鱿伻核惴ㄔ?，按照?qǐng)D1所示的流程圖步驟解決上述問題。

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

在圖2中為某地區(qū)配送農(nóng)產(chǎn)品網(wǎng)點(diǎn)示意圖，配送中心位于星號(hào)處標(biāo)0，而其他各配送點(diǎn)標(biāo)明數(shù)字從1到18。

圖2 配送網(wǎng)點(diǎn)及車輛行駛路線Flg.2 Distribution network and vehicle routing

這里將整個(gè)區(qū)域劃分成3個(gè)子區(qū)域，采用3輛車的配送方式。第1條線路： 配送中心0→配送點(diǎn)2→配送點(diǎn)7→配送點(diǎn)10→配送點(diǎn)17→配送點(diǎn)14→配送點(diǎn)5→配送中心0。第2條線路：配送中心0→配送點(diǎn)3→配送點(diǎn)9→配送點(diǎn)16→配送點(diǎn)12→配送點(diǎn)6→配送中心0。第3條線路：配送中心0→配送點(diǎn)1→配送點(diǎn)4→配送點(diǎn)8→配送點(diǎn)11→配送點(diǎn)15→配送點(diǎn)18→配送點(diǎn)13→配送中心0。選擇其中一個(gè)區(qū)域?qū)⒒鞠伻核惴ㄅc改進(jìn)后的蟻群算法進(jìn)行比較，比較結(jié)果如圖3所示。 根據(jù)實(shí)際情況與仿真過程進(jìn)行分析，采用1輛車進(jìn)行配送，會(huì)受到路況影響或是配送量較大時(shí)無法滿足需要，所以該研究采用了3輛車的配送方式。這種選擇多輛車的分區(qū)

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

5 結(jié)論

該研究針對(duì)農(nóng)產(chǎn)品運(yùn)輸問題的特殊性，提出了增加路況關(guān)系系數(shù)，簡化道路選擇概率的方法，加快了算法的收斂速度，同時(shí)為了增強(qiáng)迭代過程跳出局部最優(yōu)解的能力，增加了自適應(yīng)能力策略。在隨后的仿真試驗(yàn)中表明，該研究的改進(jìn)算法與傳統(tǒng)基本蟻群算法相比，達(dá)到了加快收斂速度，提高跳出局部最優(yōu)解的能力，改善了蟻群算法優(yōu)化運(yùn)輸?shù)穆窂健?/p>

[1] 于航，張凱. 基于節(jié)約里程法的鮮活農(nóng)產(chǎn)品物流配送車輛路線的最優(yōu)設(shè)計(jì)[J].安徽農(nóng)業(yè)科學(xué) , 2011, 39(28):17701-17703.

[2] 王多宏，嚴(yán)余松．現(xiàn)代農(nóng)業(yè)物流運(yùn)作模式比較與構(gòu)建[J].安徽農(nóng)業(yè)科學(xué), 2007, 35(35):11670，11722.

[3] 段海濱．蟻群算法原理及其應(yīng)用[M]．北京:科學(xué)出版社，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] 陳崚,沈潔,秦玲,等.基于分布均勻度的自適應(yīng)蟻群算法[J].軟件學(xué)報(bào), 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

國家自然科學(xué)基金地區(qū)基金項(xiàng)目(KKGD201303043)。

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

2016-08-18

S 229+.1

A

0517-6611(2016)33-0237-02