求解CVRP问题的快速迭代局部搜索算法.pdf

中国科技论文在线

求解 CVRP 问题的快速迭代局部搜索算法#
刘万峰，李霞**
（深圳大学信息工程学院，深圳 518060）
5 摘要：本文提出了一种求解带有容量约束的车辆路径问题(Capacitated VRP，CVRP)的快速
迭代局部搜索算法(Fast iterated local search，FILS)。该算法通过引入“前载重”和“后载重”
的概念，减少了在局部搜索算法中计算相邻解适应度值的复杂度，从而提高算法的运行速度。
此外，算法将派车成本折算为运输成本，使得 CVRP 问题简化为一个单目标优化问题。实
10 验结果表明，与其他相关算法相比较，该算法能在更短时间内求得满意解，具有很强的实用
性。
关键词：车辆路径问题；迭代局部搜索；启发式算法
中图分类号：

15 A fast iterated local searching algorithm for capacitated
vehicle routing problem
LIU Wanfeng, LI Xia
(Information Engineering School, Shenzhen University, Shenzhen 518060)
Abstract: This paper proposes a fast iterated local searching algorithm (FILS) to solve the
20 capacitated vehicle routing problem. The concepts of “pre-load” and “post-load” are defined
which can be skillfully used to compute fitness, so that the computation complexity in the local
search algorithm is reduced. Meanwhile, the CVRP can be viewed as a single-objective