A generalized model and a heuristic algorithm for the large-scale covering tour problem
A generalized model and a heuristic algorithm for the large-scale covering tour problem
复制标题
大规模覆盖旅游问题的广义模型和启发式算法
DOI：
10.1051/ro/2017090
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Murakami Keisuke
中科院分区：
文献类型：
--
作者：
田路貴浩;足立裕司他;Murakami Keisuke
覆盖巡回问题（CTP）定义在一个图上，其中存在两种类型的顶点。一个称为访问顶点，可以访问。另一种称为覆盖顶点，必须覆盖但不能访问。每个访问顶点覆盖覆盖顶点的子集，并访问顶点之间的边的成本。CTP的目标是在覆盖所有已覆盖顶点的同时，在已访问顶点的子集上获得最小成本的路线。在本文中，我们处理的大规模的CTP，这是由成千上万的顶点，在以前的研究中，实验中的实例的规模最多只有几百个顶点。我们提出了一个启发式算法，使用局部搜索技术的大规模CTP。通过计算实验，我们证明了我们的算法优于现有的方法。
The covering tour problem (CTP) is defined on a graph, where there exist two types of vertices. One is called visited vertex, which can be visited. The other is called covered vertex, which must be covered but cannot be visited. Each visited vertex covers a subset of covered vertices, and the costs of edges between visited vertices are given. The objective of the CTP is to obtain a minimum cost tour on a subset of visited vertices while covering all covered vertices. In this paper, we deal with the large-scale CTPs, which are composed of tens of thousands of vertices; in the previous studies, the scales of the instances in the experiments are at most a few hundred vertices. We propose a heuristic algorithm using local search techniques for the large-scale CTP. With computational experiments, we show that our algorithm outperforms the existing methods.
k互连多车场多旅行推销员问题的进化算法
影响因子：
2.3
作者：
Carlos Eduardo de Andrade;F. Miyazawa;M. G. Resende
通讯作者：
M. G. Resende
影响因子：
3
作者：
Hodgson, MJ;Laporte, G;Semet, F
通讯作者：
Semet, F
覆盖巡视问题的散点搜索方法
DOI：
10.1007/0-387-23667-8_3
发表时间：
2005
期刊：
INFORMS J. Comput.
影响因子：
--
作者：
Roberto Baldacci;Marco A. Boschetti;V. Maniezzo;Marco Zamboni
通讯作者：
Marco Zamboni