A drop algorithm is proposed for solving the p median problem. In solving for a fixed value of p, tight bounds on all other median solutions in the range m − 1 to p + 1 are generated where m is the number of possible location sites and p is the number of medians. A step by step numerical example is described, and extensive computational experience is reported for some standard sets of tests problems in the literature. Comparisons with the well-known greedy interchange heuristic confirm the effectiveness of this drop approach in solving a significant number of difficult median problems.
Get full access to this article
View all access options for this article.
References
1.
CornuejolsGFisherM LNemhauserG L, 1977“Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms”Management Science23789–810.
2.
CooperL, 1964“Heuristic methods for location-allocation problems”SIAM Review637–53.
3.
CooperL, 1967“Solutions of generalized locational equilibrium models”Journal of Regional Science71–18.
ErlenkotterD, 1978“A dual based procedure for uncapacitated facility location”Operations Research26992–1009.
6.
FeldmanELehrerF ARayT L, 1966“Warehouse location under continuous economies of scale”Management Science12670–684.
7.
HolmesJWilliamF BBrownL A, 1972“Facility location under a maximum travel restriction: An example using day care facilities”Geographical Analysis4258–266.
8.
JarvinenPRajalaJSinerroJ, 1972“A branch and bound algorithm for seeking the p median”Operations Research20173–178.
9.
KhumawalaB M, 1972“An efficient branch and bound algorithm for the warehouse location problem”Management Science18718–731.
10.
KhumawalaB M, 1973“An efficient algorithm for the p median problem with maximum distance constraints”Geographical Analysis5309–321.
11.
KuehnA AHamburgerM J, 1963“A heuristic program for locating warehouses”Management Science9643–666.
12.
LeaA C, 1973“Location-allocation systems: An annotated bibliography” DP-13, Department of Geography, University of Toronto, Canada.
13.
MaranzanaF E, 1964“On the location of supply points to minimize transport costs”Operational Research Quarterly15261–270.
14.
NarulaS COgbuU ISamuelssonH M, 1977“An algorithm for the p median problem”Operations Research25709–713.
SingerS, 1968“Multi centres and multi medians of a graph with an application to optimal warehouse location”Paper presented at the Joint ORSJA/TIMS National Meeting, San Francisco, Calif.
17.
SwainR W, 1974“A parametric decomposition approach 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–968.
19.
WardJ H, 1963“Hierarchical grouping to optimize an objective function”Journal of the American Statistical Association58236–244.
