Paper Info
Title
An integer programming-based local search for the covering salesman problem
Abstract
We consider a generalized version of the well known Traveling Salesman Problem called Covering Salesman problem. In this problem, we are given a set of vertices while each vertex i can cover a subset of vertices within its predetermined covering distance r"i. The goal is to construct a minimum length Hamiltonian cycle over a subset of vertices in which those vertices not visited on the tour has to be within the covering distance of at least one vertex visited on the tour. The paper proposes an Integer Linear Programming based heuristic method which takes advantage of Integer Linear Programming techniques and heuristic search to improve the quality of the solutions. Extensive computational tests on the standard benchmark instances and on a new set of large sized datasets show the effectiveness of the proposed approach.
Year
DOI
Venue
2012
10.1016/j.cor.2012.01.004
Computers & OR
Keywords
DocType
Volume
Covering Salesman problem,minimum length Hamiltonian cycle,heuristic search,Integer Linear Programming technique,extensive computational test,salesman problem,heuristic method,new set,Salesman Problem,generalized version,local search,Integer Linear Programming
Journal
39
Issue
ISSN
Citations 
11
0305-0548
20
PageRank 
References 
Authors
0.80
14
2
Name
Order
Citations
PageRank
Majid Salari115210.08
Zahra Naji Azimi21367.51