Title :
An iterated local search algorithm for the multi-vehicle covering tour problem
Author :
Yosuke Takada;Yannan Hu;Hideki Hashimoto;Mutsunori Yagiura
Author_Institution :
Dept. Computer Science and Mathematical Informatics, Graduate School of Information Science, Nagoya University, Japan
Abstract :
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.
Keywords :
"Vehicles","Heuristic algorithms","Search problems","Dynamic programming","Benchmark testing","Algorithm design and analysis","Reconstruction algorithms"
Conference_Titel :
Industrial Engineering and Engineering Management (IEEM), 2015 IEEE International Conference on
DOI :
10.1109/IEEM.2015.7385846