INFORMS Journal on Computing, ( ISI ), Volume (24), No (4), Year (2012-4) , Pages (534-553)

Title : ( The Generalized Covering Salesman Problem )

Authors: Bruce Golden , Zahra Naji Azimi , S. Raghavan , Majid Salari , Paolo Toth ,

Access to full-text not allowed by authors

Citation: BibTeX | EndNote


Given a graph , the Covering Salesman Problem (CSP) is to identify the minimum length tour “covering” all the nodes. More specifically, it seeks the minimum length tour visiting a subset of the nodes in N such that each node i not on the tour is within a predetermined distance di of a node on the tour. In this paper, we define and develop a generalized version of the CSP, and refer to it as the Generalized Covering Salesman Problem (GCSP). Here, each node i needs to be covered at least times and there is a cost associated with visiting each node. We seek a minimum cost tour such that each node i is covered at least times by the tour. We define three variants of the GCSP. In the first case, each node can be visited by the tour at most once. In the second version, visiting a node i more than once is possible, but an overnight stay is not allowed (i.e. to revisit a node i, the tour has to visit another node before it can return to i). Finally, in the third variant, the tour can visit each node more than once consecutively. In this paper, we develop two local search heuristics to find high-quality solutions to the three GCSP variants. In order to test the proposed algorithms, we generated datasets based on TSP Library instances. Since the CSP and the Generalized Traveling Salesman Problem are special cases of the GCSP, we tested our heuristics on both of these two problems as well. Overall, the results show that our proposed heuristics find high-quality solutions very rapidly


, Covering Salesman Problem, Generalized Covering Salesman Problem, Generalized Traveling Salesman Problem, Heuristic Algorithms, Local Search.
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

author = {Bruce Golden and Naji Azimi, Zahra and S. Raghavan and Salari, Majid and Paolo Toth},
title = {The Generalized Covering Salesman Problem},
journal = {INFORMS Journal on Computing},
year = {2012},
volume = {24},
number = {4},
month = {April},
issn = {1091-9856},
pages = {534--553},
numpages = {19},
keywords = {Covering Salesman Problem; Generalized Covering Salesman Problem; Generalized Traveling Salesman Problem; Heuristic Algorithms; Local Search.},


%0 Journal Article
%T The Generalized Covering Salesman Problem
%A Bruce Golden
%A Naji Azimi, Zahra
%A S. Raghavan
%A Salari, Majid
%A Paolo Toth
%J INFORMS Journal on Computing
%@ 1091-9856
%D 2012