Note—Single and Double Vertex Substitution in Heuristic Procedures for the p-Median Problem

The p-median problem is an uncapacitated minisum network location problem where it is required to site p facilities in a network, so that the sum of the shortest distances from each of the nodes of the network to its nearest facility is minimized. An existing heuristic procedure for this problem is extended, and computational experience is provided for several cases. A simple vertex addition heuristic and its use as a “pre-processor” to the extended procedure is described and tested for a number of problems.