Voir la notice de l'article provenant de la source Numdam
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.
Murakami, Keisuke 1
@article{RO_2018__52_2_577_0,
author = {Murakami, Keisuke},
title = {A generalized model and a heuristic algorithm for the large-scale covering tour problem},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {577--594},
publisher = {EDP-Sciences},
volume = {52},
number = {2},
year = {2018},
doi = {10.1051/ro/2017090},
zbl = {1401.90122},
mrnumber = {3880546},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2017090/}
}
TY - JOUR AU - Murakami, Keisuke TI - A generalized model and a heuristic algorithm for the large-scale covering tour problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 577 EP - 594 VL - 52 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2017090/ DO - 10.1051/ro/2017090 LA - en ID - RO_2018__52_2_577_0 ER -
%0 Journal Article %A Murakami, Keisuke %T A generalized model and a heuristic algorithm for the large-scale covering tour problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 577-594 %V 52 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2017090/ %R 10.1051/ro/2017090 %G en %F RO_2018__52_2_577_0
Murakami, Keisuke. A generalized model and a heuristic algorithm for the large-scale covering tour problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 577-594. doi: 10.1051/ro/2017090
Cité par Sources :