Scatter search methods for the covering tour problem

Roberto Baldacci; Marco A. Boschetti; Vittorio Maniezzo; Marco Zamboni

doi:10.1007/0-387-23667-8_3

Scatter search methods for the covering tour problem

Roberto Baldacci, Marco A. Boschetti, Vittorio Maniezzo^*, Marco Zamboni

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

27 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	59-91
Number of pages	33
Journal	Operations Research/ Computer Science Interfaces Series
Volume	30
DOIs	https://doi.org/10.1007/0-387-23667-8_3
Publication status	Published - 2005
Externally published	Yes

Keywords

Covering tour problem
Cutting planes
Scatter search algorithms

Access to Document

10.1007/0-387-23667-8_3

Cite this

@article{2a3bbab9595b47f59f0cd6dda958b77a,

title = "Scatter search methods for the covering tour problem",

abstract = "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.",

keywords = "Covering tour problem, Cutting planes, Scatter search algorithms",

author = "Roberto Baldacci and Boschetti, {Marco A.} and Vittorio Maniezzo and Marco Zamboni",

year = "2005",

doi = "10.1007/0-387-23667-8_3",

language = "English",

volume = "30",

pages = "59--91",

journal = "Operations Research/ Computer Science Interfaces Series",

issn = "1387-666X",

publisher = "Springer Science + Business Media",

}

TY - JOUR

T1 - Scatter search methods for the covering tour problem

AU - Baldacci, Roberto

AU - Boschetti, Marco A.

AU - Maniezzo, Vittorio

AU - Zamboni, Marco

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

KW - Covering tour problem

KW - Cutting planes

KW - Scatter search algorithms

UR - http://www.scopus.com/inward/record.url?scp=84863981808&partnerID=8YFLogxK

U2 - 10.1007/0-387-23667-8_3

DO - 10.1007/0-387-23667-8_3

M3 - Article

AN - SCOPUS:84863981808

SN - 1387-666X

VL - 30

SP - 59

EP - 91

JO - Operations Research/ Computer Science Interfaces Series

JF - Operations Research/ Computer Science Interfaces Series

ER -

Scatter search methods for the covering tour problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this