基于多邻域的车辆路径优化迭代局部搜索算法  

A Multi-Operator Based Iterated Local Search Algorithm for the Capacitated Vehicle Routing Problem

作　　者：陈萍[1] 黄厚宽[1] 董兴业[1] 

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044

出　　处：《北京交通大学学报》2009年第2期1-5,共5页JOURNAL OF BEIJING JIAOTONG UNIVERSITY

基　　金：国家"973"重点基础研究发展计划项目资助(2006CB705500)

摘　　要：针对物流配送中的带有容量约束的车辆路径优化问题,提出了一个基于多邻域的迭代局部搜索算法HILS.首先用简单插入法构造可行解,然后从该初始解出发,在多邻域内进行局部优化.当陷入局部最优解后,根据解的接受准则,选择某个解,并对该解进行扰动,然后从扰动后的解出发重新进行局部优化.为提高搜索效率,局部优化过程只在限定邻域内进行.在国际通用的14个benchmark问题上进行仿真实验,结果验证了本文算法HILS的有效性和稳定性,与文献中的其他几种算法的比较结果表明,算法HILS的总体性能更优.A multi-operator based local search heuristic algorithm HILS is proposed for solving the capacitated vehicle routing problem （CVRP）. Firstly, a simple insertion heuristic method is used to construct a feasible initial solution. After that, the local search process improves the incumbent solution in the multi-neighborhood until no more improvement can be obtained. Select a solution according to the acceptance criterion, and perturb it to get a new solution, which is set as the starting point of the local search process in the next iteration. To accelerate the local search process, only the restricted neighborhood is searched. Experiments results on the 14 benchmark problems demonstrate the effectiveness and stability of the proposed HILS. Furthermore, the HILS performs better in a whole compared with the other state-of-the-art heuristics from the literature.

关 键 词：车辆路径问题 多邻域 扰动 限定邻域 局部搜索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]