A Note Comparing Optimal and Heuristic Solutions To the p‐Median Problem

The p-median problem is to find, for p facilities on a network, the locations that minimize the aggregate distance traveled from all nodes on the network, along the network, to their closest facility.The problem has been optimally solved by branch and bound [1,6,8,9], linear programming [ l O , l l ] , and special decomposition algorithms [2,13].Problems of about fdty demand nodes seem to be the largest successfully solved by these optimal methods.A number of heuristics have been proposed for this problem because of the expense of optimal solutions even for small problems and the impossibility, at this time, of solving larger problems.The most commonly used heuristics appear to be those of Maranzana [ 71 and Teitz and Bart [ 141.The note reports the results of a test of these two heuristics and a standard linear programming system on six test problems. The ProblemsThe six test problems were defined using a forty-nine demand node network and six different values of p ( p =2,4,5,6,9,10).The data were for Talala block, Gujarat, India.The distances were the inter-village distances measured to the nearest 100 meters on the road and track network of the district.These distances were weighted by the 1971 population from the census of India.All demand nodes were eligible to be facility sites and no IIliudmum distance constraint was used.The data set is published by Hillsman [ 3 ] .Optimal Method Optimal solutions were found to all problems by using the linear programming formulation of ReVelle and Swain [ l o ] .The integer constraint on the +This research was conducted while the authors were at the University of Iowa.We wish to acknowledge the support of the Graduate College, University of Iowa, which met the costs incurred for computer time in the spring of 1977.