求解车辆路径问题的多邻域下降搜索蚁群优化算法

作者：张泽彬; 郝志峰; 黄翰; 李学强

来源：南京大学学报(自然科学版), 2012, 48(01): 91-98.

DOI：10.13232/j.cnki.jnju.2012.01.011

• 车辆路径问题
• 蚁群优化算法
• 多邻域下降搜索 vehicle routing problem
• ant colony optimization
• multiple neighborhood descent

本文提出一种结合改进蚁群优化算法和多邻域下降搜索的混合启发式算法IACO_MND,求解运力限制的车辆路径问题.利用改进的蚁群系统算法构造方法产生多个可行解,再将产生的解作为多邻域下降搜索的初始解.在搜索过程中使用三种不同的邻域结构:插入,交换和2-opt以扩大局部搜索的范围.实验对不同规模的benchmark算例进行求解,结果表明本文算法能在较短的时间内获得若干算例的已知最好解,求解效率高,收敛速度快,稳定性强.

• 单位
  广东工业大学; 计算机软件新技术国家重点实验室; 华南理工大学; 南京大学