A number of interchange heuristics are described for solving p-median location problems. The robustness of these algorithms is extensively evaluated in terms of optimality and mean percentage errors. The best of the proposed heuristics generated optimal solutions to 307 of 319 median problems solved drawn from six data sets.
Get full access to this article
View all access options for this article.
References
1.
ChurchR LReVelleC S, 1976“Theoretical and computational links between the p median, location set covering and maximal covering location problem”Geographical Analysis8406–415
2.
CooperL, 1964“Heuristic methods for location-allocation problems”SIAM Review637–53
3.
CornuejolsGFisherM LNemhauserG L, 1977“Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms”Management Science23789–810
4.
CrowderH P, 1976“Computational improvements for subgradient optimization”Symposia Mathematica19357–372
5.
EfroymsonM ARayT L, 1966“A branch-bound algorithm for plant location”Operations Research14361–368
6.
El-ShaiebA M, 1973“A new algorithm for locating sources among destinations”Management Science20221–231
7.
ErlenkotterD, 1978“A dual based procedure for uncapacitated facility location”Operations Research26992–1009
8.
FeldmanELehrerF ARayT L, 1966“Warehouse location under continuous economies of scale”Management Science12670–684
9.
HeldMWolfePCrowderH P, 1974“Validation of subgradient optimization”Mathematical Programming662–88
KhumawalaB M, 1972“An efficient branch and bound algorithm for the warehouse location problem”Management Science18718–731
12.
KhumawalaB M, 1973“An efficient algorithm for the p median problem with maximum distance constraints”Geographical Analysis5309–321
13.
KrolakPFeltsWMarbleG, 1971“A man machine approach toward solving the travelling salesman problem”Comm. ACM14327–334
14.
KuehnA AHamburgerM J, 1963“A heuristic program for locating warehouses”Management Science9643–666
15.
MaranzanaF E, 1964“On the location of supply points to minimize transport costs”Operational Research Quarterly15261–270
16.
MulveyJ MCrowderH P, 1979“Cluster analysis: An application of Lagrangian relaxation”Management Science25329–340
17.
NarulaS COgbuU ISamuelssonH M, 1977“An algorithm for the p median problem”Operations Research25709–713
18.
NaussR MMarklandR E, 1981“Theory and application of an optimizing procedure for lock box location analysis”Management Science27855–865
19.
OstreshL M, 1973“ALTERN—heuristic solution to the M-center location-allocation problem” in Monograph 6. Computer Programs for Location Allocation Problems Eds RushtonGGoodchildM FOstreshL M (Department of Geography, University of Iowa, Iowa City, IA)
RosingK EHillsmanE LRosing-VogelaarH, 1979“The robustness of two common heuristics for the p-median problem”Environment and Planning A11373–380
22.
SchrageL, 1975“Implicit representation of variable upper bounds in linear programming”Mathematical Programming Study4118–132
23.
ScottA J, 1970“Location allocation: A review”Geographical Analysis295–119
24.
TeitzM BBartP, 1968“Heuristic methods for estimating the generalized vertex median of a weighted graph”Operations Research16955–961
25.
WhitakerR A, 1980“A fast algorithm for the greedy-interchange for large scale clustering and median location problems”Central Statistics Bureau, Ministry of Industry and Small Business Development, Province of British Columbia, Victoria, BC; also forthcoming in INFOR: Canadian Journal of Operations Research and Information Processing either late 1982 or early 1983
26.
WhitakerR A, 1981“A tight bound drop exchange algorithm for solving the p median problem”Environment and Planning A13669–680
