The Covering Salesman Problem

descriptionPublicationkeyboard_double_arrow_right Article 01 Aug 1989 English Publisher:Institute for Operations Research and the Management Sciences (INFORMS)Journal:Transportation Science, volume 23, pages 208-213 (issn: 0041-1655, eissn: 1526-5447,

Copyright policy )

Authors: John R. Current; David A. Schilling;

doi: 10.1287/trsc.23.3.208

The Covering Salesman Problem

- Summary
- Subjects
- Metrics

Abstract

The primary purpose of this paper is to introduce and mathematically formulate the covering salesman problem (CSP). The CSP may be stated as follows: identify the minimum cost tour of a subset of n given cities such that every city not on the tour is within some predetermined covering distance standard, S, of a city that is on the tour. The CSP may be viewed as a generalization of the traveling salesman problem. A heuristic procedure for solving the CSP is presented and demonstrated with a sample problem.

Related Organizations

The Ohio State University
United States

Keywords

minimum cost tour, Numerical mathematical programming methods, covering salesman, traveling salesman, heuristic, Boolean programming, Programming involving graphs or networks

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	197
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 1%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average