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

• 作者: 刘万峰 李霞
• 来源期刊: 深圳大学学报（理工版）
• 学科: 工学
• 关键词: 人工智能 启发式算法 车辆路径问题 多邻域 迭代局部搜索 可变长编码
• 年，卷（期）: 2015,（2）
• 所属期刊栏目: 【电子与信息科学】
• 页码范围: 196-204
• 页数: 9页
• 分类号: TP391
• 字数: 6853字
• 语种: 中文
• 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算法运算能力的提高大致与配送路线所服务的客户数成正比；对客户数介于200~500的容量/最大距离约束VRP问题,该算法能在短时间内获得较满意解,平均求解精度1．2%以内,平均耗时约96 s,仅为对比算法的6%或更少.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李霞	深圳大学信息工程学院	62	1137	17.0	32.0
5	刘万峰	深圳大学信息工程学院	1	10	1.0	1.0