23rd Euro Conference on Operational Research , 2009-07-05

Title : ( Generalized Covering Salesman Problem )

Authors: Majid Salari , Zahra Naji Azimi , Bruce Goldenb , Raghu S. Raghavanb , Paolo Toth ,

Citation: BibTeX | EndNote


Given n cities, the Covering Salesman Problem (CSP) is to identify the minimum length tour “covering” all the nodes, i.e. the minimum length tour visiting a subset of the n cities and such that each city not on the tour is within a predetermined distance from the cities on the tour. In this paper we define and develop a generalized version of this problem, and name it Generalized Covering Salesman Problem (GCSP), in which each city i needs to be covered at least times and there is a visiting cost associated with each city. We define three variants of this new problem. In the first case, each city can be visited by the tour at most once. In the second version visiting a node i more than once is possible but it is not allowed to stay overnight, i.e. for revisiting a city i the tour has to visit at least another city before to return to i. Finally, in the third variant the tour can visit each city more than once consecutively. In this paper, we develop two heuristics for solving CSP and the three GCSP variants. For testing the proposed algorithms, we generate some datasets based on TSP Library instances. Moreover, we define some regular datasets, whose good solutions can be estimated virtually, and demonstrate the quality of our best heuristic, by examining it on these test bed. Overall results show that our suggested method is strong and fast enough


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

author = {Salari, Majid and Naji Azimi, Zahra and Bruce Goldenb and Raghu S. Raghavanb and Paolo Toth},
title = {Generalized Covering Salesman Problem},
booktitle = {23rd Euro Conference on Operational Research},
year = {2009},
location = {Bonn, GERMANY},
keywords = {Covering Salesman Problem; Generalized Covering Salesman Problem; Heuristic Algorithms.},


%0 Conference Proceedings
%T Generalized Covering Salesman Problem
%A Salari, Majid
%A Naji Azimi, Zahra
%A Bruce Goldenb
%A Raghu S. Raghavanb
%A Paolo Toth
%J 23rd Euro Conference on Operational Research
%D 2009