Optimal p-median solutions were computed for six test problems on a network of forty-nine demand nodes and compared with solutions from two heuristic algorithms. Comparison of the optimal solutions with those from the Teitz and Bart heuristic indicates that this heuristic is very robust. Tests of the Maranzana heuristic, however, indicate that it is efficient only for small values of p (numbers of facilities) and that its robustness decreases rapidly as problem size increases.
Get full access to this article
View all access options for this article.
References
1.
El-ShaiebA M, 1973“A new algorithm for locating sources among destinations”Management Science20221–231
2.
GarfinkelRNeebARaoM, 1974“An algorithm for the M-median plant location problem”Transportation Science8217–236
3.
HillsmanE L, 1979“User's guide to ALLOC IV, ALLOC V, and ALLOC VI: Heuristic algorithms for solving p-median problems”Institute of Urban and Regional Research, University of Iowa, Iowa City, Iowa (forthcoming)
4.
HillsmanE LRushtonG, 1975“The p-median problem with maximum distance constraints: A comment”Geographical Analysis785–89
5.
IBM, 1971Mathematical Programming System—Extended'(MPSX), Control Language Users Manual Program 5734-XM4, IBM, White Plains, NY
6.
IBM, 1972Mathematical Programming System—Extended (MPSX) and Generalized Upper Bounding Programming Description Program 5734-XM4, IBM, Whiter Plains, NY
7.
JarvinenPRajalaJSinervoH, 1972“A branch and bound algorithm for seeking the p-median”Operations Research20173–178
8.
MaranzanaF E, 1964“On the location of supply points to minimize transport costs”Operational Research Quarterly15261–270
9.
OdellP RRosingK E, 1976Optimal Development of North Sea Oil Fields (Kogan Page, London)
10.
OdellP RRosingK EVogelaarH, 1976“Optimising the oil pipeline system in the UK sector of the North Sea”Energy Policy450–55
11.
OstreshL, 1973“An investigation of the multiple location allocation problem” unpublished PhD thesis, Department of Geography, University of Iowa, Iowa City, Iowa
12.
ReVelleC SChurchR, 1980Design of Location Systems (Pergamon Press, New York) forthcoming
13.
ReVelleC SRosingK E, 1979“Planning of oil pipeline systems at sea: An application of a branch and bound p-median algorithm”Naval Research Logistical Quarterly (forthcoming)
RosingK EReVelleC S, 1978“Clustering Dutch water transportation zones: A p-median approach” WP A-78-5, Economisch-Geografisch Instituut, Erasmus Universiteit, Rotterdam
16.
RushtonGKohlerJ A, 1973“ALLOC—heuristic solutions to multi-facility location problems on a graph” in Monograph 6. Computer Programs for Location Allocation Problems Eds RushtonGGoodchildM FOstreshL MJr, (Department of Geography, University of Iowa, Iowa City, Iowa)
17.
SwainR, 1974“A parametric decomposition algorithm for the solution of uncapacitated location problems”Management Science21189–198
18.
TeitzM BBartP, 1968“Heuristic methods for estimating the generalized vertex median of a weighted graph”Operations Research16955–961
