| 基于多邻域的车辆路径优化迭代局部搜索算法 |
| |
| 引用本文： | 陈萍,黄厚宽,董兴业.基于多邻域的车辆路径优化迭代局部搜索算法[J].北京交通大学学报(自然科学版),2009,33(2). |
| |
| 作者姓名： | 陈萍 黄厚宽 董兴业 |
| |
| 作者单位： | 北京交通大学,计算机与信息技术学院,北京,100044
|
| |
| 基金项目： | 国家重点基础研究发展规划(973计划) |
| |
| 摘 要： | 针对物流配送中的带有容量约束的车辆路径优化问题,提出了一个基于多邻域的迭代局部搜索算法HILS.首先用简单插入法构造可行解,然后从该初始解出发,在多邻域内进行局部优化.当陷入局部最优解后,根据解的接受准则,选择某个解,并对该解进行扰动,然后从扰动后的解出发重新进行局部优化.为提高搜索效率,局部优化过程只在限定邻域内进行.在国际通用的14个benchmark问题上进行仿真实验,结果验证了本文算法HILS的有效性和稳定性,与文献中的其他几种算法的比较结果表明,算法HILS的总体性能更优.
|
| 关 键 词： | 车辆路径问题 多邻域 扰动 限定邻域 局部搜索 |
A Multi-Operator Based Iterated Local Search Algorithm for the Capacitated Vehicle Routing Problem |
| |
| CHEN Ping,HUANG Houkuan,DONG Xingye.A Multi-Operator Based Iterated Local Search Algorithm for the Capacitated Vehicle Routing Problem[J].JOURNAL OF BEIJING JIAOTONG UNIVERSITY,2009,33(2). |
| |
| Authors: | CHEN Ping HUANG Houkuan DONG Xingye |
| |
| Institution: | School of Computer and Information Technology;Beijing Jiaotong University;Beijing 100044;China |
| |
| Abstract: | 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 multineighborhood 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 proce... |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
