关于蚁群算法的研究与分析

吴海侠 武晓霞

一、题目分析

电子商务的普及促进了物流行业的发展，然而与发达国家相比我国物流业仍处于起步阶段。物流信息化的程度较低，配送成本较高成为了急需解决的问题。物流路径的选择是物流体系当中至关重要的一环，路径直接决定了物流配送的效率。因此物流路径优化对降低企业成本、提高物流配送效率、合理资源配置有着重要的意义。物流路径优化问题的核心就是车辆路径优化（Vehicle Routing Problem），即VRP问题。针对该问题，目前已经有了很多研究方法，但是不同的方法的优缺点不同，本文主要针对蚁群算法的优缺点，以及如何优化蚁群算法展开分析。

二、检索过程

（一）在“知网”中检索

首先，在“知网”中输入“蚁群算法”，搜索出下图所示结果：

此次的搜索结果较为满意，下载相关文献。

（二）在“OA”中检索：

首先在“OA”中输入“Ant colony algorithm”，然后把选择的文献的DOI在SCI-HUB中搜索就可以看英文文献了。步骤如下：

三、文献阅读与分析

3.1 文献下载和管理

用Endnot来整理下载的文献。用CNKI E-Study也可以整理下载的文献以及导入参考文献。

3.2 文献阅读和分析

（1）军事定向越野路径优化问题建模及混合蚁群算法求解 作者：王书勤，黄茜

本文对军事定向越野中的路径优化问题，建立了数学模型，通过蚁群算法的改进和与遗传算法的结合，提出了一种混合蚁群算法，成功求解了军事定向越野中的路径优化问题，解决了军事定向越野中在点位多，分布散，时间紧的条件下如何选择最优路径问题。军事定向越野运动中存在点位多、分布散、时间紧、得分要求高等条件，为在规定时间内找到一条得分高的行进线路，找到衡量和分析运动成绩好坏的标准，文中对军事定向越野中的路径优化问题进行了深入分析，建立了混合整数规划模型，设计了一种混合蚁群算法。算法中，首先由改进蚁群算法找到初始解，然后再利用选择、交叉和变异算子进行解的优化，通过仿真实验和算法对比验证了混合蚁群算法的可行性和优越性，并在最后用遗传算法进行收敛，得到最优解。

（2）基于改进蚁群算法的众包配送路径研究  作者：蒋丽

文章以O2O 外卖平台的众包配送路径优化为研究对象，建立了带有单侧软时间窗的需求可延迟的开放式车辆路径优化模型，并使用高德地图API 获取实际节点。改进蚁群算法将下一步移动的潜在客户数量作为路径选择的影响因素，在求解质量和效率上具有明显优势，仿真對比实验验证了模型的合理性和算法的有效性，使路径选择和规划更具科学性，有助于有效降低配送成本。下一步研究工作是在静态路径规划基础上，着重研究配送员位置时刻变化以及继续接单的情况，考虑到配送员位置时刻变化以及继续接单的情况，建立软时间窗约束下的动态开放式路径优化模型，探讨动态路径优化的求解方法。

优点是针对现有O2O外卖众包配送的经验依赖性和随机性问题，建立以距离成本和时间惩罚成本之和最小化为目标的带有单侧软时间窗的需求可延迟的开放式车辆路径优化模型，并借助高德地图API 接口获得各实际节点的经纬度信息和各节点间距离。改进蚁群算法在状态转移规则中添加下一步移动的潜在客户数量影响因子，同时将确定性搜索与随机性搜索结合，缩小蚂蚁搜索范围。

（3）基于蚁群算法的双分区仓库拣货路径的优化  作者：刘建胜

合理地选择拣货路径对于降低物流配送成本有重大作用。针对问题的特点，建立了数学模型，设计了蚁群算法对其求解，并与多种方法对比了优化结果，结果显示蚁群算法能令人满意地解决问题。针对一单多车的情况，本文修改了一单一车时算法部分编码，对一单多车的仓库捡货情况进行了优化求解，两种情况表明蚁群算法能够很好地解决仓库拣货路径优化问题。本文用的三比较传统的蚁群算法，没有进行优化。

（4）基于改进蚁群算法物流配送路径优化的研究  作者：张勇

本文从物流配送路径优化问题的自身特点出发，采用蚁群算法加以分析，并进行了相应的改进，通过进行局部优化处理，尽量减少算法可能出现的停滞现象，同时对信息素的更新方式加以改进，增强了改进后蚁群算法的正反馈机制，提升了算法的自适应性，进一步加快了收敛的速度以及算法的全局搜索能力。结合实例计算与分析，我们不难发现，改进后的蚁群算法能更快速、有效地对物流配送路径问题进行优化处理，进而寻得最优解。由此得知，本文得出的相关结论，对物流配送路径优化问题具有一定的实用性与参考性。

（5）Non-dominated sorting differential evolution algorithm for the minimization of route based fuel consumption multiobjective vehicle routing problems

针对4个基于多目标路径的车辆路径选择问题，提出了3种并行多启动非支配排序差分进化算法，并将其结果与并行多启动NSGA算法的结果进行了比较。所有这些算法都使用多个初始解的总体。在每一种算法中都使用了一个变量领域搜索算法来分别改进每个解，用两个目标函数表示的问题是基于多个目标对称和非对称的车辆路径问题。优化目标函数对应于所需的时间之间的汽车旅行两个客户的旅行距离，所以本文采用的是蚁群算法来优化目标函数。

四、心得

通过阅读这些文献，掌握了蚁群算法的模型的建立，该模型在物流专业主要用于路径优化的问题上，能解决资源配置的优化以及成本最小化等问题。但是，该模型的不足之处在于后期收敛慢，需要再次进行优化。有些文献在蚁群算法模型上加上时间窗或者有多个目标的蚁群算法，都是对蚁群算法的进一步优化，其他的优化还有待考察。

通过学习信息检索课，收获颇大。明白了怎么合理的选择自己需要的文献，怎么择优选择，同时也会查阅外文文献，避免了之前盲目看文献的陋习。在创新的方面也有很大收获，不论对以后的学习还是工作都有很大的帮助。

（石家庄铁道大学 经济管理学院）