深圳大学学报理工版

对于容量约束的车辆路径问题(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%或更少.

For capacitated vehicle routing problems without/with maximum traveling distance constraint(CVRP/CDVRP), the evaluation of neighborhood solutions involves fitness calculation and feasibility assessment. This paper proposes a fast feasibility assessment strategy in which variable length coding is used to represent feasible solutions of vehicle routing problem. We introduce the concepts of pre-load, post-load, pre-distance and post-distance to obtain fast feasibility assessments for neighborhood solutions achieved by four widely used local search operations(insert, exchange, 2- opt, and 2- opt*). By combining the improved local search operations and iterated local search(ILS), we propose a fast multi-neighborhood iterated local search(FMNILS)for CVRP. The feasibility assessment strategy can reduce computational complexity of the neighborhood solution assessment from O(N)to O(1). Experimental results show that the improvement in speed is approximately linearly proportional to the average customer number in a route. For CVRP/CDVRP problems with 200—500 customers, the algorithm can give satisfactory solutions with an average deviation of less than 1.2%. The average running time is 96 seconds, which is 6% of the time required for the counterpart algorithms, or even less.

引言
1 车辆路径问题及可行解编码
2 快速多邻域迭代局部搜索算法
3 实验仿真及分析
4 结语

图1 FMNILS算法的伪代码<br/>Fig.1 Pseudo-code for FMNILS

图1 FMNILS算法的伪代码
Fig.1 Pseudo-code for FMNILS

图2 2- opt*局部算子示意图<br/>Fig.2 Two- opt* local operator

图2 2- opt*局部算子示意图
Fig.2 Two- opt* local operator

图3 4- opt局部算子示意图<br/>Fig.3 Four- opt local operator

图3 4- opt局部算子示意图
Fig.3 Four- opt local operator

图4 3- opt扰动示意图<br/>Fig.4 Three- opt perturbation

图4 3- opt扰动示意图
Fig.4 Three- opt perturbation

图5 FMNILS算法运行速度提高度与配送路线平均服务客户数的关系图<br/>Fig.5 Relationship between the average number of customers in a route and the improvement level of running speed by FMNILS

图5 FMNILS算法运行速度提高度与配送路线平均服务客户数的关系图
Fig.5 Relationship between the average number of customers in a route and the improvement level of running speed by FMNILS