Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Applying simulated annealing to location-planning models

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

Simulated annealing is a computational approach that simulates an annealing schedule used in producing glass and metals. Originally developed by Metropolis et al. in 1953, it has since been applied to a number of integer programming problems, including the p-median location-allocation problem. However, previously reported results by Golden and Skiscim in 1986 were less than encouraging. This article addresses the design of a simulated-annealing approach for the p-median and maximal covering location problems. This design has produced very good solutions in modest amounts of computer time. Comparisons with an interchange heuristic demonstrate that simulated annealing has potential as a solution technique for solving location-planning problems and further research should be encouraged.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • AbramsonD. (1991). “Constructing School Timetables Using Simulated-Annealing: Sequential and Parallel Algorithms.” Management Science 37, 98–113.

    Google Scholar 

  • BeasleyJ. (1990). “OR-Library: Distributing Test Problems by Electronic Mail”. Journal of the Operational Research Society 41, 1069–1072.

    Google Scholar 

  • BianchiG., and R.Church. (1992). “A Non-Binary Encoded Genetic Algorithm for a Facility Location Problem”. Working Paper, Department of Geography, University of California, Santa Barbara.

    Google Scholar 

  • CaptivoM.E. (1991). “Fast Primal and Dual Heuristics for the p-median Location Problem”. European Journal of Operational Research 52, 65–74.

    Google Scholar 

  • CernyV. (1985). “Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm”. Journal of Optimization Theory and Applications 45, 41–51.

    Google Scholar 

  • ChungC. (1986). “Recent Applications of the Maximal Covering Location Planning (MCLP) model”. Journal of the Operational Research Society 37, 735–746.

    Google Scholar 

  • ChurchR. (1990). “The Regionally Constrained p-median Problem”. Geographical Analysis 22, 22–32.

    Google Scholar 

  • ChurchR., and C.ReVelle. (1974). “The Maximal Covering Location Problem”. Papers of the Regional Science Association 32, 101–118.

    Google Scholar 

  • ChurchR., and C.ReVelle. (1976). “Theoretical and Computational Links Between the p-Median, Location Set-Covering, and the Maximal Covering Location Problem”. Geographical Analysis 8, 406–415.

    Google Scholar 

  • Church, R., and P. Sorensen. (1994). “Integrating Normative Location Models into GIS: Problems and Prospects with the p-Median Model.” NCGIA Technical Report 95-5.

  • ChurchR., and J.Weaver. (1986). “Theoretical Links Between Median and Coverage Location Problems”. Annals of Operations Research 6, 1–19.

    Google Scholar 

  • CornuejolsG., M.Fisher, and G.Nemhauser. (1977). “Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms”. Management Science 23, 789–810.

    Google Scholar 

  • CurrentJ., and M.O'Kelly. (1992). “Locating Emergency Warning Sirens”. Decision Sciences 23, 221–234.

    Google Scholar 

  • DenshamP., and M.Rushton. (1992). “A More Efficient Heuristic for Solving Large p-Median Problems”. Papers in Regional Science 71, 307–329.

    Google Scholar 

  • EatonD., M.Daskin, D.Simmons, B.Bulloch, and G.Jansma. (1985). “Determining Emergency Medical Service Vehicle Deployment in Austin, Texas”. Interfaces 15, 96–108.

    Google Scholar 

  • El-ShaiebA. (1973). “A New Algorithm for Locating Sources Among Destinations”. Management Science 20, 221–231.

    Google Scholar 

  • Forgues, P., Y. Chan, and T. Kelso (1992). “Network-with-Gains Solutions to a Mean-Variance Location Problem”. Paper presented at ORSA/TIMS San Francisco, Nov. 1–4, 1992.

  • FriezT., G.Snandalingam, H.Mehta, K.Nam, S.Shah, and R.Tobin (1993). “The Multiobjective Equilibrium Network Design Problem Revisited: A Simulated-Annealing Approach”. European Journal of Operational Research 65, 44–57.

    Google Scholar 

  • GoldbergJ., and L.Paz. (1991). “Locating Emergency Vehicle Bases When Service Time Depends on Call Location”. Transportation Science 25, 264–280.

    Google Scholar 

  • GoldenB., and C.Skiscim. (1986). “Using Simulated-Annealing to Solve Routing and Location Problems”. Naval Research Logistics Quarterly 33, 261–279.

    Google Scholar 

  • GoodchildM., and V.Noronha. (1983). Location-Allocation for Small Computers. Iowa City, Department of Geography, University of Iowa, Monograph No. 8.

    Google Scholar 

  • HakimiL. (1964). “Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph”. Operations Research 12, 450–459.

    Google Scholar 

  • HakimiL. (1965). “Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems”. Operations Research 13, 462–475.

    Google Scholar 

  • HalsethG., and M.Rosenberg. (1991). “Locating Emergency Medical Services in Small Town and Rural Settings”. Socio-Economic Planning Sciences 25, 295–304.

    Google Scholar 

  • HillsmanE. (1984). “The p-Median Structure as a Unified Linear Model for Location-Allocation Analysis”. Environment and Planning A 16, 305–318.

    Google Scholar 

  • HoganK. (1990). “Reducing Errors in Rainfall Estimates Through Rain Gauge Location”. Geographical Analysis 22, 13–49.

    Google Scholar 

  • HoneyR., G.Rushton, P.Lononis, B.Dalziel, M.Armstrong, S.De, and P.Densham. (1991). “Stages in the Adoption of a Spatial Decision Support System for Reorganizing Service Delivery Regions”. Environment and Planning C 9, 51–63.

    Google Scholar 

  • HosageC., and M.Goodchild. (1986). “Discrete Space Location-Allocation Solutions from Genetic Algorithms”. Annals of Operations Research 6, 35–46.

    Google Scholar 

  • International Business Machines (IBM) (1992). “Optimization Subroutine Library Guide and Reference”. IBM Corporation, Kingston, NY.

    Google Scholar 

  • JarvinenP., J.Rajala, and H.Sinervo. (1972). “A Branch-and-Bound Algorithm for Seeking the p-Median”. Operations Research 20, 173–178.

    Google Scholar 

  • JohnsonD., C.Aragon, L.McGeoch, and C.Schevon. (1989). “Optimization by Simulated-Annealing: An Experimental Evaluation—Part I, Graph Partitioning”. Oprational Research 37, 865–892.

    Google Scholar 

  • KincaidR. (1992). “Good Solutions to Discrete Noxious Location Problems via Metaheuristics”. Annals of Operations Research 40, 265–281.

    Google Scholar 

  • KirkpatrickS., C.Gelatt, and M.Vecchi. (1983). “Optimization by Simulated-Annealing”. Science 220, 671–680.

    Google Scholar 

  • LeeB., and R.Deninger. (1992) “Optimal Locations of Monitoring Stations in Water Distribution System”. Journal of Environmental Engineering 118, 4–16.

    Google Scholar 

  • MetropolisN., A.Rosenbluth, M.Rosenbluth, A.Teller, and E.Teller. (1953). “Equation of State Calculations by Fast Computing Machines”. Jopurnal of Chemical Physics 21, 1087–1092.

    Google Scholar 

  • Migereko, D. (1983). “An Analysis of the Coffee Cooperative Marketing System in Busoga, Uganda: Transportation and Facilities Location.” Masters thesis, Department of Geography, University of California, Santa Barbara.

  • MoonI.D. and S.Chaudhry. (1984). “An Analysis of Network Location Problems with Distance Constraints”. Management Science 30, 291–307.

    Google Scholar 

  • MurrayA., and R.Church. (1995). “Heuristic Solution Approaches to the Operational Forest Planning Problem”. OR Spektrum 17, 193–203.

    Google Scholar 

  • NarulaS., U.Ogbu, and H.Samuelsson. (1977). “An Algorithm for the p-Median Problem”. Operations Research 25, 709–713.

    Google Scholar 

  • ReVelleC., and R.Swain. (1970). “Central Facilities location”. Geographical Analysis 2, 30–42.

    Google Scholar 

  • Rolland, E., D. Schilling, and J. Current. (1992). “Heuristic Search Techniques for Location Problems.” Paper presented at ORSA/TIMS San Francisco, November 1–4, 1992.

  • RosingK., E.Hillsman, and H.Rosing. (1979). “A Note Comparing Optimal and Heuristic Solutions to the p-Median Problem”. Geographical Analysis 11, 86–89.

    Google Scholar 

  • RosingK., C.ReVelle, and H.Rosing. (1979). “The p-Median and Its Linear Programming Relaxation: An Approach to Large Problems”. Journal of the Operational Research Society 30, 815–823.

    Google Scholar 

  • Ruggles, A.J. (1992). “An Analysis of Late-Horizon Settlement Patterns in the Temascalapa-Teotihuacan Basins: The Creation of Idealized Settlement Patterns Through Location-Allocation Models and GIS.” Masters thesis, Department of Geography. University of California, Santa Barbara.

  • SchillingD., V.Jayaraman, and R.Barkhi. (1993). “A Review of Covering Problems in Facility Location”. Location Science 1, 25–55.

    Google Scholar 

  • SelimS., and K.Alsultan. (1991). “A Simulated-Annealing Algorithm for the Clustering Problem”. Pattern Recognition 10, 1003–1008.

    Google Scholar 

  • Swain, R. (1971). “A Decomposition Algorithm for a Class of Facility Location Problems.” Ph.D. dissertation, Cornell University, Ithaca, NY.

  • TanselB., R.Francis and T.Lowe. (1983). “Location on Networks: A Survey”. Management Science 29, 482–511.

    Google Scholar 

  • TeitzM. and P.Bart. (1968). “Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph”. Operations Research 16, 955–961.

    Google Scholar 

  • TryfosP. (1986). “An Integer Programming Approach to the Apparel Sizing Problem”. Journal of the Operational Research Society 37, 1001–1006.

    Google Scholar 

  • VanLaarhovenP., and E.Aarts. (1987). Simulated-Annealing: Theory and Application Dordrecht, Netherlands: Reidel.

    Google Scholar 

  • Weaver, J., and R. Church. (1984). “A Comparison of Direct and Indirect Primal/Dual Bounding Solution Procedures for the Maximal Covering Location Problem”. Working paper.

  • WeaverJ., and R.Church. (1985). “A Median Location Model with Nonclosest Facility Service”. Transportation Science 19, 58–74.

    Google Scholar 

  • Wilhelm, M., and T. Ward. (1987). “Solving the Quadratic Assignment Problems by Simulated-Annealing.” IIE Transactions (March), 107–119.

  • Willer, D. (1990). “A Spatial Decision Support System for Bank Location: A Case Study.” NCGIA Technical Report 90-9.

Download references

Author information

Authors and Affiliations

  1. Australian Housing and Urban Research Institute, Queensland University of Technology, 4000, Brisbane, Queensland, Australia

    Alan T. Murray

  2. National Center for Geographic Information and Analysis, University of California at Santa Barbara, 93106, Santa Barbara, CA, USA

    Richard L. Church

  3. the Department of Geography, University of California at Santa Barbara, 93106, Santa Barbara, CA, USA

    Richard L. Church

Authors
  1. Alan T. Murray
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Richard L. Church
    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

Murray, A.T., Church, R.L. Applying simulated annealing to location-planning models. J Heuristics 2, 31–53 (1996). https://doi.org/10.1007/BF00226292

Download citation

  • Issue Date:

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

Key Words

Search

Navigation