An iterated local search algorithm for the multi-vehicle covering tour problem
An iterated local search algorithm for the multi-vehicle covering tour problem
复制标题
DOI：
10.1109/ieem.2015.7385846
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Yosuke Takada;Yannan Hu;H. Hashimoto;M. Yagiura
中科院分区：
文献类型：
--
作者：
Yosuke Takada;Yannan Hu;H. Hashimoto;M. Yagiura
给定两组顶点V和W，其中V中的每个顶点覆盖W的一个子集，多车辆覆盖巡回问题要求在W中的每个顶点必须被路径中的顶点覆盖的约束下，确定若干车辆在V的一个子集上的路线，以使总距离最小。我们提出了一种迭代局部搜索算法，该算法具有两个步骤来改进解决方案：一个由三个操作组成，从路由中移除或插入顶点；另一种是路径重构，即用最优路径代替部分路径，为此我们提出了一种动态规划算法。我们还提出了有效的方法来减少在邻域中寻找改进解的计算时间。在基准实例上的计算结果表明，该算法的性能优于现有方法，对于大规模实例是有效的。
Given two sets of vertices V and W, where each vertex in V covers a subset of W, the multi-vehicle covering tour problem asks to determine a number of vehicle routes on a subset of V so as to minimize the total distance under the constraint that every vertex in W must be covered by vertices in the routes. We propose an iterated local search algorithm that features two procedures to improve solutions: one consists of three operations to remove or insert vertices from or into a route; the other is path reconstruction that replaces a partial path with an optimal one, for which we propose a dynamic programming algorithm. We also propose efficient methods to reduce the computation time to search for improved solutions in neighborhoods. The computational results on benchmark instances show that our algorithm performs better than existing methods and is efficient for large-scale instances.