何小虎

摘要：为了有效地降低车辆在粮食运输中的成本，采用改进的蚁群算法对粮食物流配送路径进行优化。通过建立数学模型，提出改进的蚂蚁转移规则、优化信息素浓度、改进全局信息素更新策略。结果表明，改进的蚁群算法比基本蚁群算法可以更好地解决粮食运输车辆的路径问题，使得运输距离明显缩短。

关键词：蚁群算法；车辆运输；路径优化

中图分类号：TP301.6；S274 文献标识码：A 文章编号：0439-8114（2016）20-5372-03

DOI：10.14088/j.cnki.issn0439-8114.2016.20.052

Abstract： A modified ant colony algorithm was adopted and optimized in grain logistics distribution path in order to reduce transportation cost effectively. The results showed that the modified algorithm provide a better solution in grain logistics distribution path optimization than the basic ant colony algorithm. It can cut down path length about 9% and therefore play a bigger role in utilization of the limited resources.

Key words： ant colony algorithm； grain logistics； path optimization

糧食问题关乎国家的国计民生，其价格高低直接影响国家经济的发展。在粮食价格的组成中，粮食流通成本比重很高，许多加工粮食企业对粮食配送采用人工方式，运输线路不合理，导致运输成本居高不下。因此，研究如何有效地降低粮食的运输成本，将有十分重要的现实意义。

降低粮食的流通成本，要根据各个配送点，设计出运输线路最短的路径，合理利用车辆的资源，用最小的成本达到粮食配送的目的。解决这类问题的方法较多，但是都存在一定的缺陷。蚁群算法是意大利学者Marco Dorigo等于1991年受自然界蚂蚁觅食过程启发而提出的一种新型智能搜索优化算法。随后将蚁群算法成功地应用于旅行商问题求解上，并取得了很好的试验结果。蚁群算法受到许多研究者的关注，并不断应用于实际问题求解，蚁群算法已经被广泛地应用到各个领域解决复杂组合优化问题。因此，本研究对基本蚁群算法进行改进优化，建立数学模型，进而对粮食配送线路进行了试验仿真。结果表明，改进优化的蚁群算法对配送线路优化取得了较好的效果。

1 粮食物流配送数学模型

由一个粮食配送中心向多个粮食配送点送粮，每个粮食配送点的地理位置和需求量固定，每辆运粮车辆的载重量和最大行驶距离固定，要求以最低的运输成本合理安排配送线路，同时满足每个粮食配送点的需求。为了保证数学模型满足配送要求，该模型应该满足以下条件：

1）各条配送线路上各个粮食配送点的粮食需求量之和不超过送粮车辆的最大载重量；

2）粮食配送中心能够完全满足各个配送点的粮食需求；

3）粮食必须在有效的时间内送到各个配送点；

4）粮食运输总费用与运输的总量是成正比。

多配送点粮食物流配送模型如下：设共有M个配送点，分别用1，2，3，…M表示。

式（2）表示粮食运输车在运输线路上成本最小。式（3）表示所有运输车都是从配送中心出发，完成后回到配送中心。式（4）表示每辆车运输粮食的重量不能超过车的最大载重量。式（5）表示每一条线路上只能由一辆运输车完成。式（6）表示变量的取值。

2 改进蚁群算法

蚁群算法是模拟自然界中蚂蚁觅食行为的随机仿生优化算法[1]，蚂蚁之间通过传递信息素和协同合作，从而找到食物到巢穴间最短路径。蚁群算法具有较好的鲁棒性、并行性、全局寻优、正反馈机制、分布性等优点，但是也存在收敛速度过慢和容易陷入局部最优等缺点[2]。

2.1 蚂蚁转移规则的改进[3]

为了避免蚂蚁在搜索过程中陷入局部最优而没有得到最优解，本研究对蚂蚁的转移规则进行了改进。初始路径上各个节点的信息素是相同的，当蚂蚁经过某个节点时信息素的值就会增加。蚂蚁就会快速聚集到这些节点上，从而导致算法陷入局部最优。因此，提出干扰策略，提高蚂蚁的搜索空间。

干扰因子表示路径上的蚂蚁拥挤程度，其计算公式为：

参数α是蚂蚁在运动过程中的信息素影响因子，主要表示蚂蚁在进行路径搜索时路径上所积累的信息素浓度对蚂蚁进行路径选择所起的作用大小。

参数β是期望因子或称为能见度因子，表示蚂蚁在运动过程中能见度对路径选择的重要性。

2.2 信息素浓度初始值的改进策略[4]

基本蚁群算法的信息素浓度初始值是一个常数，为了提高算法的收敛速度，提出了信息素浓度初始值的改进策略，在初始化信息素的同时加入了引导功能，让蚂蚁移动时趋向于终点移动，信息素初始化的公式是：

2.3 全局信息素更新策略[4，5]

采用最大最小蚂蚁系统MMAS，就是蚂蚁在进行一次搜索完后，仅对所走过的路径进行全局更新，可以大大缩小蚂蚁的搜索范围，使得蚂蚁的搜索更具有方向性。这种改进策略不但可以提高搜索效率，而且可以保证搜索到的最优解的充分利用。全局信息素更新如公式（10）所示：

2.4 蚁群算法主要步骤[6-8]

1）初始化参数α，β等参数以及蚂蚁的数量和迭代次数NCmax，利用公式（9）初始化每条边的信息素。

2）把n个蚂蚁放到粮食配送中心，利用公式（8）选择蚂蚁下一次移动的粮食配送点，同时把该配送点加入蚂蚁的禁忌表。

3）当蚂蚁完成一次路径搜索后回到出发点，并利用公式（10）更新当前较好路径的信息素。

4）判断迭代次数是否小于NCmax，如果成立，跳回步骤2，重復上述步骤，否则，程序结束。

5）当迭代次数等于NCmax，则输出粮食配送最优路径和长度，程序结束。

3 改进蚁群算法仿真试验

以某地区1个粮食配送中心和20个粮食配送点为例，使用改进的蚁群算法在实验室中用MATLAB2010进行模拟测试，配送中心用编号0，其他配送点分别用1，2，…，20，要求运输费用最少。各配送点的横纵坐标和需求量如表1所示。

参数设置为：NCmax=30，Q=2，m=20，α=1，=0.5，β=3，改进算法运行15次后得到了最优配送线路如图1所示。由图1可以看出，共需要4辆车，4辆车的具体配送线路是：0-18-4-3-9-0；0-2-12-5-7-14-15-0；0-8-10-13-11-0；0-6-17-16-20-19-1-0，路径长度为382.01 km。

4 小结

从仿真试验结果来看，用改进的蚁群算法求解粮食物流配送路径优化问题时，有以下几个优点：①找到最优解的概率更高；②求解效率和性能都进一步提升。但蚁群算法作为一种仿生智能优化算法，仍有许多问题和不足之处，需要以后进一步深入研究和完善。

参考文献：

[1] 余昌艳.基于蚁群算法的粮食加工企业物流配送路径优化研究[D].武汉：武汉科技大学，2009.

[2] 高 尚.蚁群算法理论、应用及其与其他算法的混合[D].南京：南京理工大学，2005.

[3] 龙 汀.基于蚁群算法的车辆路径问题的研究[D].合肥：合肥工业大学，2009.

[4] 汪采萍.蚁群算法的应用研究[D].合肥：合肥工业大学，2007.

[5] 刘 霞，杨 超.最小-最大车辆路径问题的蚁群算法[J].解放军理工大学学报，2012，13（3）：336-341.

[6] 郭天池.基于蚁群算法的粮食应急调度问题研究[D].郑州：河南工业大学，2011.

[7] 陈迎欣.基于改进蚁群算法的车辆路径优化问题研究[J].计算机应用研究，2012，29（6）：2031-2034.

[8] 吴虎发.蚁群优化算法在求解最短路径问题中的研究与应用[D].合肥：安徽大学，2012.