Scatter Search Methods for the Covering Tour Problem

Scatter Search Methods for the Covering Tour Problem
复制标题

覆盖巡视问题的散点搜索方法

DOI：
10.1007/0-387-23667-8_3
复制
发表时间：
2005
期刊：
INFORMS J. Comput.
影响因子：
--
通讯作者：
Marco Zamboni
Marco Zamboni
中科院分区：
--
文献类型：
--
作者：
Roberto Baldacci;Marco A. Boschetti;V. Maniezzo;Marco Zamboni

文献摘要

被引文献

相似文献

覆盖旅行问题（CTP）是旅行商问题（TSP）的推广，在分销网络设计领域有着广泛的应用。给定一个无向图，该问题要求确定一个通过顶点子集的最小成本循环，使得每个不在循环中的顶点位于距循环中至少一个节点的给定距离内。CTP是TSP的推广，是NP难的。本文提出了三种新颖的散点搜索启发式算法。计算结果的报告。
The Covering Tour Problem (CTP) is a generalization of the Traveling Salesman Problem (TSP) which has several practical applications in the area of distribution network design. Given an undirected graph, the problem asks to identify a minimum cost cycle passing through a subset of vertices such that every vertex not in the cycle lies within a given distance from at least one node in the cycle. Being a generalization of the TSP, CTP is NP-hard. This paper presents three original Scatter Search heuristic algorithms for the CTP. Computational results are reported.