Technical Note—A Branch-and-Bound Algorithm for Seeking the P-Median

Abstract

We construct a branch-and-bound algorithm for seeking the p-median, and make comparisons with the vertex-substitution method of Teitz and Bart [Opns. Res. 16, 955–961 (1968)]. We show how the vertex-substitution method can lead to a local optimum, and give a heuristic method for finding a good initial solution for this method.