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

    徐伟+于凯丽

    

    

    

    摘 要：蟻群算法具有十分广阔的应用前景，但蚁群算法在求解路径优化问题中存在收敛速度慢、易陷于局部最优路径等缺点。文章通过改进传统的蚁群算法，使蚁群算法求最优解的性能显著提升，大幅提高了物流配送的效率。

    关键词：VRP；蚁群算法；路径优化；算法改进

    自从Dorigo在2004年编写出版了第一本详细介绍蚁群算法的著作之后，利用蚁群算法来解决物流配送车辆路径优化问题引起了大量学者的注意。本文通过改进传统蚁群算法，弥补了传统蚁群算法中容易陷于局部最优、在求解过程中出现停滞现象等缺点，力求车辆路径最优。

    1 模型建立

    3 实例仿真

    设各参数m=31，Nc=200，a=1，β=5，ρ=0.5，Q=100，q0=0.5，选取31个乡镇坐标，利用本文改进的蚁群算法，使用Matlab2014a仿真软件进行迭代计算，程序执行结果如下。

    仿真球的最短路径为shortest path=30→27→28→26→25→24→20→21→22→18→3→17→19→16→5→6→7→2→4→8→9→10→23→11→13→12→14→15→1→31→29 Shortest length =1.581 8 e+04。图像表明，改进后的蚁群算法相较于传统蚁群算法，在全局寻找最优解的能力方面有明显优化，同时改善了算法的执行效率，在求解物流配送中的车辆路径问题（Vehicle Routing Problem，VRP）问题上，能较快地取得较优结果。

    4 结语

    VRP问题是物流配送的关键，针对这一问题，笔者在大量阅读调研的基础上，通过调整状态转移规则及信息素更新策略，着重解决了传统的蚁群算法陷入局部最优解的这一缺陷，增强了蚁群算法的正反馈机制，明显提升了算法解的收敛速度及全局搜索能力。通过分析利用MATLAB软件进行仿真计算所得到的数据，可以发现改进后的蚁群算法对提高物流配送的效率是有效的。

    基金项目：2017年中国物流学会、中国物流与采购联合会研究课题；项目名称：基于禁忌搜索算法的车辆协作与路径规划研究；项目编号：2017CSLKT3-071。

    作者简介：徐伟（1979— ），男，山东巨野，博士，硕士生导师；研究方向：物流系统规划与设计。

    [参考文献]

    [1]DORIGO M. Ant colonies for the traveling salesman problem[J].Biosystems，1997（2）：73-81.

    [2]胡小兵，黄席樾.蚁群优化算法及其应用[ J].计算机仿真，2004（5）：81-85.

    [3]唐连生，程文明，张则强，等.基于改进蚁群算法的车辆路径仿真研究[J].计算机仿真，2007（4）：262-264.

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

    Abstract： Ant colony algorithm has a very broad application prospects. However， the ant colony algorithm has some shortcomings such as slow convergence speed and easy to trap the local optimal path in solving the path optimization problem. In this paper， by improving the traditional ant colony algorithm， the ant colony algorithm is improved greatly in the performance of the optimal solution， which greatly improves the efficiency of logistics distribution.

    Key words： Vehicle Routing Problem； ant colony algorithm； path optimization； algorithm improvement