车辆路径问题的快速多邻域迭代局部搜索算法

作者：刘万峰; 李霞

来源：深圳大学学报(理工版), 2015, 32(02): 196-204.

DOI：10.3724/SP.J.1249.2015.02196

• 人工智能
• 启发式算法
• 车辆路径问题
• 多邻域
• 迭代局部搜索
• 可变长编码

对于容量约束的车辆路径问题(capacitated vehicle routing problem,CVRP)以及容量和最大行驶距离约束的车辆问题(capacitated and distance constrained vehicle routing problem,CDVRP),邻域解的评估包含了适应值计算及合法性评估.设计一种可变长编码的可行解表示,提出用于CVRP/CDVRP问题的邻域解合法性快速评估策略.该策略针对交换、插入、2-opt和2-opt*四种常用的局部搜索算子,通过引入前载重、后载重、前向距离和后向距离的概念,实现了邻域解合法性的快速评估.将改进后的局部搜索算子与迭代局部搜索(iterated local search,ILS)算法相结合,提出用于车辆路径问题的快速多邻域迭代局部搜索(fast multi-neighborhood ILS,FMNILS)算法.该快速评估策略将评估一个邻域解的时间复杂度由O(N)降至O(1),算法仿真结果表明,FMNILS算法运算能力的提高大致与配送路线所服务的客户数成正比;对客户数介于200500的容量/最大距离约束VRP问题,该算法能在短时间内获得较满意解,平均求解精度1.2%以内,平均耗时约96 s,仅为对比算法的6%或更少.

• 单位
  深圳市现代通信与信息处理重点实验室; 深圳大学信息工程学院