An Empirical Investigation of the Effectiveness of a Vertex Substitution Heuristic

K E Rosing
Additional contact information
K E Rosing: Department of Applied Economics and Tinbergen Institute, Erasmus University Rotterdam, PO Box 1738, NL3000 Rotterdam, The Netherlands

Environment and Planning B, 1997, vol. 24, issue 1, 59-67

Abstract: Many problems require the identification of a subset of points to minimize (or maximize) some function. A vertex substitution heuristic (VSH) employs a strategy of one-by-one replacement to approximate, or perhaps find, the optimal set. The Teitz and Bart heuristic is the archetype of this procedure and is the heuristic most frequently used for the solution of the p -median problem. One study of the performance of this heuristic with increasing numbers of facilities ( p ) in problems with a very small number of demand nodes ( n ) has been published. However, no study satisfactorily indicates the relative effectiveness of this heuristic method with increasing values of n or p. In this paper we compare optimal and heuristic solutions for ninety problems varying the values of n and p systematically. The results indicate that there is a definite reduction in the effectiveness of the heuristic with increasing values of n or p.

Date: 1997
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://journals.sagepub.com/doi/10.1068/b240059 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:envirb:v:24:y:1997:i:1:p:59-67

DOI: 10.1068/b240059

Access Statistics for this article

More articles in Environment and Planning B
Bibliographic data for series maintained by SAGE Publications ().