| 求解车辆路径问题的改进扰动机制的ILS算法 |
| |
| 引用本文： | 侯彦娥,孔云峰,党兰学.求解车辆路径问题的改进扰动机制的ILS算法[J].计算机科学,2016,43(1):264-269. |
| |
| 作者姓名： | 侯彦娥 孔云峰 党兰学 |
| |
| 作者单位： | 河南大学黄河中下游数字地理技术教育部重点实验室 开封475004;河南大学计算机与信息工程学院 开封475004,河南大学黄河中下游数字地理技术教育部重点实验室 开封475004,河南大学计算机与信息工程学院 开封475004 |
| |
| 基金项目： | 本文受国家自然科学基金项目(41401461),河南省教育厅自然科学重点项目(15A520009)资助 |
| |
| 摘 要： | 针对车辆路径问题,提出一种改进的迭代局部搜索(ILS)算法。该算法基于破坏再重建(Ruin and Recreate)的思想,设计了一种新的扰动机制。扰动过程包含破坏和重建两个阶段,即先使用一种兼顾随机性和相关性的破坏方法对解进行破坏,并引入扰动因子控制解的破坏强度,然后再随机选择基本贪婪插入和改进贪婪插入算法完成解的修复。利用国际标准测试案例对常规扰动机制和改进后的扰动机制进行了测试,并与量子进化算法、蜂群算法进行了比较,实验结果表明改进后的ILS算法更加有效。
|
| 关 键 词： | 车辆路径问题 迭代局部搜索 破坏再重建 元启发 |
| 收稿时间： | 2015/3/15 0:00:00 |
| 修稿时间： | 2015/6/23 0:00:00 |
Iterated Local Search Algorithm with Improved Perturbation Mechanism for Vehicle Routing Problem |
| |
| HOU Yan-e,KONG Yun-feng and DANG Lan-xue.Iterated Local Search Algorithm with Improved Perturbation Mechanism for Vehicle Routing Problem[J].Computer Science,2016,43(1):264-269. |
| |
| Authors: | HOU Yan-e KONG Yun-feng and DANG Lan-xue |
| |
| Affiliation: | Key Laboratory of Geospatial Technology for the Middle and Lower Yellow River Regions,Ministry of Education, Henan University,Kaifeng 475004,China;College of Computer and Information Engineering,Henan University,Kaifeng 475004,China,Key Laboratory of Geospatial Technology for the Middle and Lower Yellow River Regions,Ministry of Education, Henan University,Kaifeng 475004,China and College of Computer and Information Engineering,Henan University,Kaifeng 475004,China |
| |
| Abstract: | This paper proposed an iterated local search (ILS) algorithm with a new perturbation mechanism for vehicle routing problem.The perturbation mechanism is based on ruin and recreating principle,which includes destroying and repair procedures.The best local neighborhood solution is firstly destroyed by a method which takes randomness and correlation into account.In the destroying process,a perturbation factor is also introduced into the perturbation mechanism to control the strength of destroying.And then the destroyed solution is repaired by randomly selecting basic greedy insertion and regret greedy insertion algorithms.The experiments on the benchmark instances prove that the developed algorithm is more effective when compared with quantum evolutionary algorithm and artificial bee colony. |
| |
| Keywords: | Vehicle routing problem Iterated local search Ruin and recreate Metaheuristic |
|
|
点击此处可从《计算机科学》下载全文 |
|
