The cardinality constrained covering traveling salesman problem

The cardinality constrained covering traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20031639
Country: United Kingdom
Volume: 30
Issue: 1
Start Page Number: 97
End Page Number: 116
Publication Date: Jan 2003
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

In this paper, we propose a new method for partitioning a graph into an unspecified number of Hamiltonian subgraphs with minimum and maximum size requirements on the subgraphs. We refer to this problem as the cardinality constrained covering traveling salesman problem. Special cases of this problem include the assignment problem and the traveling salesman problem. This paper proposes a heuristic solution methodology to a general class of problems that is important because by setting the parameters, one can obtain different important problems including the traveling salesman problem and the assignment problem. Although these specific problems have been studied extensively in the past, the generalized version proposed here and the solution methodology set forth, are new contributions. The solution methodology presented in this paper produces solutions within known error bounds of the optimal solution value. The computational results indicate an ability to obtain very high-quality solutions by expending a modest computational effort for problems in excess of 200 nodes.

Reviews

Required fields are marked *. Your email address will not be published.