基于改进蚁群算法的农业运输车辆路径优化研究

赵晓侠， 鞠成恩

(昆明理工大学信息工程与自动化学院，云南昆明 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