Skip to main content
SpringerLink
Log in

Theoretical links between median and coverage location problems

  • Covering Problems
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The relationship between the maximal covering problem and the P-median problem is reviewed. It is shown that two multiple coverage models, themaximumexpectedcoverageproblem (MECP) and thebackupcoverageproblem (BACOP), are special cases of thevectorassignmentP-medianproblem (VAPMP). This relationship is utilized to solve both MECP and BACOP on test sets from the literature. Computational experience is reported.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E. Balas and A. Ho, Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study, Mathematical Programming Study 12(1980)37.

    Google Scholar 

  2. G.N. Berlin, Facility location and vehicle allocation for the provision of an emergency service, Ph.D. Dissertation, The John Hopkins University, Baltimore, Maryland (1972).

    Google Scholar 

  3. O. Berman, Dynamic positioning of mobile servers on networks, TR-144, MIT, Operations Research Center, Cambridge, Massachusetts (1978).

    Google Scholar 

  4. A. Charnes and J. Storbeck, A goal programming model for the siting of multilevel EMS systems, Socio-Economic Planning Sciences 14(1980)155.

    Article  PubMed  Google Scholar 

  5. K.R. Chelst and J. Anderson, An algorithm to convert the weightedp-median to the uncapacitated location problem, unpublished paper (1982).

  6. R.L. Church, Solid waste wasteshead identification in the Tennessee Valley region utilizing multiobjective programming, Dept. of Civil Engineering, University of Tennessee, Knoxville (1979).

    Google Scholar 

  7. R.L. Church and T. Bell, Incorporating preferences in location-allocation models, Geographical Perspectives 48(1981)22.

    Google Scholar 

  8. R.L. Church and G. Bianchi, Recent developments in covering models for the location of emergency facilities, Paper presented at the ORSA/TIMS Meeting, Detroit, Michigan (1982).

  9. R.L. Church and D. Eaton, Hierarchical location analysis utilizing covering objectives, Working paper, Dept. of Geography, University of California at Santa Barbara (1981).

  10. R.L. Church and C.S. ReVelle, Maximal covering location problem, Papers of the Regional Science Association 32(1974)101.

    Article  Google Scholar 

  11. R.L. Church and C.S. ReVelle, Theoretical and computational links between thep-median, location set-covering, and maximal covering location problems, Geographical Analysis 8(1976)406.

    Google Scholar 

  12. R.L. Church and K.L. Roberts, Generalized coverage models and public facility location, Papers of the Regional Science Association 53(1983)117.

    Article  Google Scholar 

  13. G. Cornuejols, M.L. Fisher and G.L. Nemhauser, Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms, Management Science 23(1977)789.

    Google Scholar 

  14. M.S. Daskin, Application of an expected covering model to emergency medical service system design, Decision Sciences 13(1982)416.

    Google Scholar 

  15. M.S. Daskin, A maximum expected covering location model: Formulation, properties, and heuristic solution, Transportation Science 17(1983)48.

    Google Scholar 

  16. M.S. Daskin and E.H. Stern, A hierarchical objective set covering model for emergency medical service vehicle deployment, Transportation Science 15(1981)137.

    Google Scholar 

  17. D. Erlenkotter, A dual-based procedure for uncapacitated facility location, Oper. Res. 26(1978)992.

    Google Scholar 

  18. S.L. Hakimi, Optimum distribution of switching centers in a communication network and some related group theoretic problems, Oper. Res. 13(1965)562.

    Google Scholar 

  19. J. Halpern, The location of a center-median convex combination on an undirected tree, Journal of Regional Science 16(1976)237.

    Google Scholar 

  20. E.L. Hillsman, A system for location-allocation analysis, Ph.D. Dissertation, University of Iowa, Iowa City (1979).

    Google Scholar 

  21. K. Hogan and C.S. ReVelle, Backup coverage concepts in the location emergency service, Modeling and Simulation 14(1983)1423.

    Google Scholar 

  22. T.D. Klastorin, On the maximal covering location problem and the generalized assignment problem, Management Science 25(1979)107.

    Google Scholar 

  23. P.B. Mirchandani, Locational decisions on stochastic networks, Geographical Analysis 12(1980)172.

    Google Scholar 

  24. P.B. Michandani, A. Oudjit and R.T. Wong, Multi-dimensional extensions and a nested dual approach for theM-median problem, Eur. J. Oper. Res. submitted.

  25. G.C. Moore and C.S. ReVelle, The hierarchical service location problem, Management Science 28(1982)775.

    Article  Google Scholar 

  26. J.M. Mulvey and H.P. Crowder, Cluster analysis: An application of Lagrangian relaxation, Management Science 25(1979)329.

    Google Scholar 

  27. S.C. Narula, U.I. Ogbu and H.M. Samuelsson, An algorithm for thep-median problem, Oper Res. 25(1977)709.

    Article  Google Scholar 

  28. A.W. Neebe, A branch and bound algorithm for thep-median transportation problem, J. Oper. Res. Soc. 29(1978)989.

    Google Scholar 

  29. J. Penalba, Incorporating preference objectives into facility location models, Masters Paper, University of Tennessee, Knoxville (1980).

    Google Scholar 

  30. D.R. Plane and T.E. Hendrick, Mathematical programming and the location of fire companies for the Denver fire department, Oper. Res. 25(1977)563.

    Google Scholar 

  31. C.S. ReVelle and R.W. Swain, Central facilities location, Geographical Analysis 2(1970)30.

    Google Scholar 

  32. P. Rojeski and C.S. ReVelle, Central facilities location under an investment constraint, Geographical Analysis 2(1970)343.

    Google Scholar 

  33. G.T. Ross and R.M. Soland, Modeling facility location problems as generalized assignment problems, Management Science 24(1977)345.

    Google Scholar 

  34. T.W. Ruefli and J.E. Storbeck, Behaviorally linked hierarchies, Environment and Planning 9(1982)257.

    Google Scholar 

  35. D.A. Schilling, Dynamic location modeling for public-sector facilities: A multicriteria approach, Decision Sciences 11(1980)714.

    Google Scholar 

  36. D.A. Schilling, D.J. Elizinga, J. Cohon, R.L. Church and C.S. ReVelle, The team fleet models for simultaneous facility equipment siting, Transportation Science 13(1979)163.

    Google Scholar 

  37. D.E. Shobrys, A model for the selection of shipping routes and storage locations for hazardous substances, Ph.D. Dissertation, The John Hopkins University, Baltimore, Maryland (1981).

    Google Scholar 

  38. J. Storbeck, Slack, natural slack, and location covering, Socio Economic Planning Sciences 16(1982)99.

    Article  PubMed  Google Scholar 

  39. R. Swain, A decomposition algorithm for a class of facility location problems, Ph.D. Dissertation, Cornell University, Itaca, New York (1971).

    Google Scholar 

  40. C. Swoveland, D. Uyeno, I. Vertinsky and R. Vickson, Ambulance location: A probabilistic enumeration approach, Management Science 20(1973)686.

    Google Scholar 

  41. M.B. Teitz and P. Bart, Heuristic methods for estimating the generalized vertex median of a weighted graph, Oper. Res. 16(1968)995.

    Google Scholar 

  42. C. Toregas and C.S. ReVelle, Optimal location under time or distance constraints, Papers of the Regional Science Association 28(1972)133.

    Article  Google Scholar 

  43. F.J. Vasko and G.R. Wilson, An efficient heuristic for large set covering problems, Naval Research Logistics Quarterly 31(1984)163.

    Google Scholar 

  44. J.R. Weaver and R.L. Church, Computational procedures for location problems on stochastic networks, Transportation Science 17(1983)168.

    Article  Google Scholar 

  45. J.R. Weaver and R.L. Church, A median location model with nonclosest facility service, Transportation Science 19(1985)58.

    Google Scholar 

  46. J.R. Weaver and R.L. Church, A comparison of solution procedures for covering location problems, Modeling and Simulation 14(1983)1417.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Geography, University of California, 93106, Santa Barbara, California, USA

    R. L. Church

  2. Department of Management Science and Statistics, University of Alabama, 35486, Alabama, USA

    J. R. Weaver

Authors
  1. R. L. Church
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. R. Weaver
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Church, R.L., Weaver, J.R. Theoretical links between median and coverage location problems. Ann Oper Res 6, 1–19 (1986). https://doi.org/10.1007/BF02034236

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02034236

Keywords and phrases

Search

Navigation