The p-median problem involves the locating of a fixed number of facilities to serve a set of customers such that the aggregate distance travelled is minimized. Considers the p-median problem with and without distance constraints. Solves the two versions of the p-median problems utilizing the heuristic proposed by Teitz and Bart using three different data sets. Also provides optimal solutions to these problems using the Lagrangian relaxation and subgradient methods in the branch-and-bound procedure. Shows that the heuristic performs quite well except for the cases where the constraints are tight (few facilities and/or small maximum distance).
