基于改进蚁群算法的物流配送路径优化研究

2017-05-16夏鹏张玮

科学与财富 2017年12期

夏鹏+张玮

摘要：本文首先通过对传统蚁群算法在物流配送路径优化问题中的研究，得出蚁群算法存在如收敛速度较慢、算法易陷于局部最优等缺点，进而对蚁群算法进行优化改进，使物流配送路径优化研究得到更好的解决。

关键词：蚁群算法物流配送路径优化

一、引言

互联网在不断地发展，这一时代慢慢兴起，网购逐渐走进我们的生活大当中。伴随着网购而不断兴盛的就是物流行业。物流行业越来越繁荣，对物流配送路径进行优化也显得尤为重要，因为这直接关系到物流行业的成本控制、盈利水平及配送效率。调查显示，目前在我们国家物流行业的总成本一半以上花费在运输当中，这一项花费远远高于西方的一些发达国家。

在研究物流配送路径的时候，我们常将其归属于组合优化，即是一个NP完全问题。研究过程中，针对路径优化人们经常会用到诸如方案评价法、动态规划法、遗传算法等各类方法。不过就目前的一些研究而言，这些算法都存在着一定程度的缺点，并不是特别完美，比如遗传算法局部搜索能力不强，蚁群算法容易呈现停滞征象，等等。现在的研究中，针对以往在物流配送路径优化方面的一些算法进行改进完善，以便于原有算法的所存在的缺点和不足之处能够得到弥补。

近些年来，受到生物进化展现出来的先进特点的启发，部分学者研究发现了一些像遗传算法、蚁群算法等的智能算法，并常常将这些算法运用到一些复杂优化问题中去。在进行物流配送路径问题研究的时候，遗传算法具有收敛到全局最优的优点，不过在描述所求问题的约束条件时，这一算法往往表现的不尽如人意，而物流配送路径优化又是一种多约束问题。和遗传算法一样，蚁群算法也是一种随机搜索算法，不过蚁群算法有其自身的优点，比如其能同时兼顾解的局部构造和整体性能，适合用来求解具有复杂约束条件以及解的组成元素之间关联性较强的优化问题。

二、蚁群算法与物流配送路径问题

2.1 蚁群算法描述

蚁群算法（ant colony optimization， ACO）是由意大利的著名学者Marco Dorigo最先提出来的，它是一种随机搜索算法。这种算法是受到蚂蚁群体在寻找食物时探索路径行为的启发，它是对日常蚂蚁群体进行较优路径搜寻这一过程的模拟，蚁群中的每一只蚂蚁分别独自地在候选解空间中去搜索一个解，蚂蚁会在每次搜索完成之后留下一些信息量在相应的解上面在。根据所选择的解的性能的差异，蚂蚁会有选择的留下信息量，当解的性能较好的时候，蚂蚁会留下较多的信息量，反之留下的信息量则会比较少，其中留下较多信息量的解也相应的更加容易被再次选择。在刚开始执行算法的时候，每个解上面的信息量都是相同的，当算法不断地往前推进，就相当于蚂蚁不断地寻找路径，较优解上面留下来的信息量就会渐渐变多，这样不同解上的信息量就逐渐被拉开，进而收敛得到最优解或者近似的最优解。

在解决物流配送路径优化问题上，蚁群算法凭借其自身的优点表现出极其强大的作用。不过这种算法仍然在一定程度上存在着一些不足之处，例如收敛速度较慢、算法易陷于局部最优、各个参数的设置还建立在实验和经验的基础上、理论支持不是特别的严谨等。

与神经网络、遗传算法等一些其他的优化算法相比，蚁群算法的优点体现在它具有正反馈、分布式计算、较强的鲁棒性以及富于建设性的贪婪启发式搜索等特点。蚁群算法的这些不同于其他算法的特点，使得一些更加复杂的问题在求解方面难度有所降低。

2.2 物流配送路径问题描述

2.2.1 问题描述

针对物流配送问题，我们一般可以进行如下描述：为满足某一配送目标，从物流配送中心发出若干车辆，选择一条比较合适的的运输路线，在满足送货量、时间窗、车辆数量、载重量、行驶里程等条件下，完成配送目标，要求对形式路线作出合理安排，使运输总成本最小，并且还需要满足下列各项约束条件：

（1）当配送中心为完成一次配送任务后从该中心发出一辆运输车辆，运输车辆在完成配送中心布置的任务之后重新返回到配送中心；

（2）各条线路上的运输车辆的最大运输量应该大于或等于该路径上面各站点的一次配送需求量；

（3）每条配送路径的长度需控制在运输车辆单次配送的最大行驶距离以内；

（4）有且仅能有一辆运输车给每一位客户送货。

2.2.2 数学模型

在建立蚁群算法数学模型之初，我们要考虑设计出一条最优的配送路线，该线路要满足总的配送距离最短。现作出如下假设：某一区域有一个配送中心，该配送中心服务N个目标客户，每个目标客户的需求量为，从配送中心发出的运输车辆的最大运输量为G，定义二值函数如下：

根据假设作出如下数学模型：

（1）

（2）

2.3 蚁群算法在配送路径问题中的应用描述

根据以上建立起来的蚁群算法，我们用车辆去替代蚂蚁，从配送中心发出一辆车，为配送区域中的一个配送节点配送货物，如果从配送中心发出的车辆的货运量能够达到需配送的配送节点的需求量，就对货物进行配送，如否则返回配送中心重新装货，表示完成一次配送。从配送中心发出的一辆运输车辆在一个配送过程中完成了相應的配送任务之后，对每一条配送路径上的信息素进行更新。一趟任务接着一趟任务去完成，当每一辆从配送中心发出的车辆完成了各目标客户的配送任务之后，表示一次迭代成功的完成了，比较其便利的路径长度并保存最短路径，然后进行下一次迭代。

三、蚁群算法的改进与优化

3.1 改进算法数学模型

在2.2节建立的数学模型的基础上，结合实际的物流配送情况，对蚁群算法的数学模型进行改进与优化。优化之后的算法具体描述如下：

全局信息素更新规则：

基于增强蚂蚁全局搜索能力的目的，使得收敛这一现象不要发生的太快，每一只蚂蚁在相同的一条路径上通过的时候会留下相应的信息素，这些信息素对其他蚂蚁访问该路径有抑制作用。所以可以按照下述规则对t时刻在路径（i，j）上的信息素进行相应调整：

在（6）式中，我们用ρ表示信息素的持久化系数，其取值范围为0到1；用（t，n）表示蚂蚁在第n次迭代后留在路径（i，j）上的信息素增量；

∈[0，1]为一个系数；的含义是完成一次迭代后，蚂蚁

在前面n-1次迭代中在路径（i，j）上留下的信息素增量之和；这样

表示属于前面迭代中蚂蚁释放信息素加权抑制因子。

式（7）中：表示所有的蚂蚁第 n 次迭代后在路径（i，j）上留下

的信息量的总和，的取值采用蚁周系统模型，值为：

式（8）中：Lk表示的是第k只蚂蚁完成一次循环过程经历的总的路径长度；Q表示信息素强度。