IDEAS home Printed from https://ideas.repec.org/a/sae/envirb/v47y2020i6p1014-1030.html
   My bibliography  Save this article

Generating optimal and near-optimal solutions to facility location problems

Author

Listed:
  • Richard L Church
  • Carlos A Baez

Abstract

There is a decided bent toward finding an optimal solution to a given facility location problem instance, even when there may be multiple optima or competitive near-optimal solutions. Identifying alternate solutions is often ignored in model application, even when such solutions may be preferred if they were known to exist. In this paper we discuss why generating close-to-optimal alternatives should be the preferred approach in solving spatial optimization problems, especially when it involves an application. There exists a classic approach for finding all alternate optima. This approach can be easily expanded to identify all near-optimal solutions to any discrete location model. We demonstrate the use of this technique for two classic problems: the p -median problem and the maximal covering location problem. Unfortunately, we have found that it can be mired in computational issues, even when problems are relatively small. We propose a new approach that overcomes some of these computational issues in finding alternate optima and near-optimal solutions.

Suggested Citation

  • Richard L Church & Carlos A Baez, 2020. "Generating optimal and near-optimal solutions to facility location problems," Environment and Planning B, , vol. 47(6), pages 1014-1030, July.
    • Handle: RePEc:sae:envirb:v:47:y:2020:i:6:p:1014-1030
    DOI: 10.1177/2399808320930241
    as

    Download full text from publisher

    File URL: https://journals.sagepub.com/doi/10.1177/2399808320930241
    Download Restriction: no
    File URL: https://libkey.io/10.1177/2399808320930241?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Maria Scaparra & Richard Church & F. Medrano, 2014. "Corridor location: the multi-gateway shortest path model," Journal of Geographical Systems, Springer, vol. 16(3), pages 287-309, July.
    2. Price, James & Keppo, Ilkka, 2017. "Modelling to generate alternatives: A technique to explore uncertainty in energy-environment-economy models," Applied Energy, Elsevier, vol. 195(C), pages 356-369.
    3. Andrew C. Trapp & Renata A. Konrad, 2015. "Finding diverse optima and near-optima to binary integer programs," IISE Transactions, Taylor & Francis Journals, vol. 47(11), pages 1300-1312, November.
    4. Richard L. Church & Alan Murray, 2018. "Location Covering Models," Advances in Spatial Science, Springer, number 978-3-319-99846-6, december.
    5. Richard Church & Charles R. Velle, 1974. "The Maximal Covering Location Problem," Papers in Regional Science, Wiley Blackwell, vol. 32(1), pages 101-118, January.
    6. Baum, Sanford & Carlson, Robert, 1979. "On solutions that are better than most," Omega, Elsevier, vol. 7(3), pages 249-255.
    7. S. L. Hakimi, 1965. "Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems," Operations Research, INFORMS, vol. 13(3), pages 462-475, June.
    8. DeCarolis, Joseph F., 2011. "Using modeling to generate alternatives (MGA) to expand our thinking on energy futures," Energy Economics, Elsevier, vol. 33(2), pages 145-152, March.
    9. E. Downey Brill, Jr., 1979. "The Use of Optimization Models in Public-Sector Planning," Management Science, INFORMS, vol. 25(5), pages 413-422, May.
    10. Mark S. Daskin, 2008. "What you should know about location modeling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(4), pages 283-294, June.
    11. E. Downey Brill, Jr. & Shoou-Yuh Chang & Lewis D. Hopkins, 1982. "Modeling to Generate Alternatives: The HSJ Approach and an Illustration Using a Problem in Land Use Planning," Management Science, INFORMS, vol. 28(3), pages 221-235, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Schwaeppe, Henrik & Thams, Marten Simon & Walter, Julian & Moser, Albert, 2024. "Finding better alternatives: Shadow prices of near-optimal solutions in energy system optimization modeling," Energy, Elsevier, vol. 292(C).
    2. Michael J. Brusco, 2022. "Solving Classic Discrete Facility Location Problems Using Excel Spreadsheets," INFORMS Transactions on Education, INFORMS, vol. 22(3), pages 160-171, May.
    3. Aditya Sinha & Aranya Venkatesh & Katherine Jordan & Cameron Wade & Hadi Eshraghi & Anderson R. Queiroz & Paulina Jaramillo & Jeremiah X. Johnson, 2024. "Diverse decarbonization pathways under near cost-optimal futures," Nature Communications, Nature, vol. 15(1), pages 1-15, December.
    4. Finke, Jonas & Kachirayil, Febin & McKenna, Russell & Bertsch, Valentin, 2024. "Modelling to generate near-Pareto-optimal alternatives (MGPA) for the municipal energy transition," Applied Energy, Elsevier, vol. 376(PA).
    5. Dubois, Antoine & Dumas, Jonathan & Thiran, Paolo & Limpens, Gauthier & Ernst, Damien, 2023. "Multi-objective near-optimal necessary conditions for multi-sectoral planning," Applied Energy, Elsevier, vol. 350(C).
    6. Blanco, Víctor & Gázquez, Ricardo & Saldanha-da-Gama, Francisco, 2023. "Multi-type maximal covering location problems: Hybridizing discrete and continuous problems," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1040-1054.
    7. Jing, Rui & Kuriyan, Kamal & Kong, Qingyuan & Zhang, Zhihui & Shah, Nilay & Li, Ning & Zhao, Yingru, 2019. "Exploring the impact space of different technologies using a portfolio constraint based approach for multi-objective optimization of integrated urban energy systems," Renewable and Sustainable Energy Reviews, Elsevier, vol. 113(C), pages 1-1.
    8. Jiwon Baik & Alan T. Murray, 2022. "Locating a facility to simultaneously address access and coverage goals," Papers in Regional Science, Wiley Blackwell, vol. 101(5), pages 1199-1217, October.
    9. Xin Feng & Alan T. Murray, 2018. "Allocation using a heterogeneous space Voronoi diagram," Journal of Geographical Systems, Springer, vol. 20(3), pages 207-226, July.
    10. Jan-Philipp Sasse & Evelina Trutnevyte, 2023. "A low-carbon electricity sector in Europe risks sustaining regional inequalities in benefits and vulnerabilities," Nature Communications, Nature, vol. 14(1), pages 1-15, December.
    11. Sasse, Jan-Philipp & Trutnevyte, Evelina, 2023. "Cost-effective options and regional interdependencies of reaching a low-carbon European electricity system in 2035," Energy, Elsevier, vol. 282(C).
    12. Chang, Miguel & Lund, Henrik & Thellufsen, Jakob Zinck & Østergaard, Poul Alberg, 2023. "Perspectives on purpose-driven coupling of energy system models," Energy, Elsevier, vol. 265(C).
    13. Milosav Georgijevic & Sanja Bojic & Dejan Brcanov, 2013. "The location of public logistic centers: an expanded capacity-limited fixed cost location-allocation modeling approach," Transportation Planning and Technology, Taylor & Francis Journals, vol. 36(2), pages 218-229, April.
    14. Jinghong Shen & Jianquan Cheng & Wencong Huang & Fantao Zeng, 2020. "An Exploration of Spatial and Social Inequalities of Urban Sports Facilities in Nanning City, China," Sustainability, MDPI, vol. 12(11), pages 1-19, May.
    15. Murray, Alan T., 2021. "Contemporary optimization application through geographic information systems," Omega, Elsevier, vol. 99(C).
    16. Mingjian Wu & Tae J. Kwon & Karim El-Basyouny, 2020. "A Citywide Location-Allocation Framework for Driver Feedback Signs: Optimizing Safety and Coverage of Vulnerable Road Users," Sustainability, MDPI, vol. 12(24), pages 1-20, December.
    17. Grochowicz, Aleksander & van Greevenbroek, Koen & Benth, Fred Espen & Zeyringer, Marianne, 2023. "Intersecting near-optimal spaces: European power systems with more resilience to weather variability," Energy Economics, Elsevier, vol. 118(C).
    18. Xiujuan Zhao & Wei Xu & Yunjia Ma & Fuyu Hu, 2015. "Scenario-Based Multi-Objective Optimum Allocation Model for Earthquake Emergency Shelters Using a Modified Particle Swarm Optimization Algorithm: A Case Study in Chaoyang District, Beijing, China," PLOS ONE, Public Library of Science, vol. 10(12), pages 1-16, December.
    19. Dayanna Rodrigues da Cunha Nunes & Orivalde Soares da Silva Júnior & Renata Albergaria de Mello Bandeira & Yesus Emmanuel Medeiros Vieira, 2023. "A Robust Stochastic Programming Model for the Well Location Problem: The Case of The Brazilian Northeast Region," Sustainability, MDPI, vol. 15(14), pages 1-21, July.
    20. Makowski, David & Hendrix, Eligius M. T. & van Ittersum, Martin K. & Rossing, Walter A. H., 2001. "Generation and presentation of nearly optimal solutions for mixed-integer linear programming, applied to a case in farming system design," European Journal of Operational Research, Elsevier, vol. 132(2), pages 425-438, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:sae:envirb:v:47:y:2020:i:6:p:1014-1030. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: SAGE Publications (email available below). General contact details of provider: .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.