IDEAS home Printed from https://ideas.repec.org/a/spr/snopef/v2y2021i1d10.1007_s43069-020-00050-z.html
   My bibliography  Save this article

An Accelerated Benders Decomposition Algorithm for Solving a Double-Type Double-Standard Maximal Covering Location Problem

Author

Listed:
  • Ashkan Fakhri

    (University of Science and Technology of Mazandaran
    Institute for Research in Fundamental Sciences (IPM))

  • Antonios Fragkogios

    (University of Thessaly)

  • Georgios K. D. Saharidis

    (University of Thessaly)

Abstract

In this paper, a double-type double-standard model (DtDsM) for maximal covering location problem is proposed which has several applications in determining the location of public emergency facilities. DtDsM includes two types of facilities: normal and backup facilities. Although backup facilities have a greater coverage distance, they offer not a full service but only a primary service. In DtDsM, each demand point must lie within the coverage distance of a backup facility if it does not lie in the coverage distance of a normal facility ensuring it to receive minimal primary services within a predetermined time. Furthermore, an accelerated Benders decomposition algorithm is proposed to solve the model. The speed and accuracy of the algorithm are compared with the commercial solver CPLEX.

Suggested Citation

  • Ashkan Fakhri & Antonios Fragkogios & Georgios K. D. Saharidis, 2021. "An Accelerated Benders Decomposition Algorithm for Solving a Double-Type Double-Standard Maximal Covering Location Problem," SN Operations Research Forum, Springer, vol. 2(1), pages 1-24, March.
    • Handle: RePEc:spr:snopef:v:2:y:2021:i:1:d:10.1007_s43069-020-00050-z
    DOI: 10.1007/s43069-020-00050-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s43069-020-00050-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s43069-020-00050-z?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Mark S. Daskin, 1983. "A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution," Transportation Science, INFORMS, vol. 17(1), pages 48-70, February.
    2. Lixin Tang & Wei Jiang & Georgios Saharidis, 2013. "An improved Benders decomposition algorithm for the logistics facility location problem with capacity expansions," Annals of Operations Research, Springer, vol. 210(1), pages 165-190, November.
    3. Kathleen Hogan & Charles ReVelle, 1986. "Concepts and Applications of Backup Coverage," Management Science, INFORMS, vol. 32(11), pages 1434-1444, November.
    4. CREMER, Helmuth & de KERCHOVE, Anne-Marie & THISSE, Jacques-François, 1985. "An econometric theory of public facilities in space," LIDAM Reprints CORE 646, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Cordeau, Jean-François & Furini, Fabio & Ljubić, Ivana, 2019. "Benders decomposition for very large scale partial set covering and maximal covering location problems," European Journal of Operational Research, Elsevier, vol. 275(3), pages 882-896.
    6. Cremer, Helmuth & De Kerchove, Anne-Marie & Thisse, Jacques-Francois, 1985. "An economic theory of public facilities in space," Mathematical Social Sciences, Elsevier, vol. 9(3), pages 249-262, June.
    7. Schmid, Verena & Doerner, Karl F., 2010. "Ambulance location and relocation problems with time-dependent travel times," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1293-1303, December.
    8. Caunhye, Aakil M. & Nie, Xiaofeng & Pokharel, Shaligram, 2012. "Optimization models in emergency logistics: A literature review," Socio-Economic Planning Sciences, Elsevier, vol. 46(1), pages 4-13.
    9. Richard Church & Charles R. Velle, 1974. "The Maximal Covering Location Problem," Papers in Regional Science, Wiley Blackwell, vol. 32(1), pages 101-118, January.
    10. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    11. Gilbert Laporte & François V Louveaux & Frédéric Semet & Arnaud Thirion, 2009. "Application of the Double Standard Model for Ambulance Location," Lecture Notes in Economics and Mathematical Systems, in: Jo A.E.E. Nunen & M. Grazia Speranza & Luca Bertazzi (ed.), Innovations in Distribution Logistics, chapter 12, pages 235-249, Springer.
    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. Wajid, Shayesta & Nezamuddin, N., 2023. "Capturing delays in response of emergency services in Delhi," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    2. Wajid, Shayesta & Nezamuddin, N., 2022. "A robust survival model for emergency medical services in Delhi, India," Socio-Economic Planning Sciences, Elsevier, vol. 83(C).
    3. Boyacı, Burak & Geroliminis, Nikolas, 2015. "Approximation methods for large-scale spatial queueing systems," Transportation Research Part B: Methodological, Elsevier, vol. 74(C), pages 151-181.
    4. Bélanger, V. & Lanzarone, E. & Nicoletta, V. & Ruiz, A. & Soriano, P., 2020. "A recursive simulation-optimization framework for the ambulance location and dispatching problem," European Journal of Operational Research, Elsevier, vol. 286(2), pages 713-725.
    5. Iloglu, Suzan & Albert, Laura A., 2020. "A maximal multiple coverage and network restoration problem for disaster recovery," Operations Research Perspectives, Elsevier, vol. 7(C).
    6. Wang, Wei & Wu, Shining & Wang, Shuaian & Zhen, Lu & Qu, Xiaobo, 2021. "Emergency facility location problems in logistics: Status and perspectives," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    7. Shayesta Wajid & N. Nezamuddin, 2023. "Optimizing emergency services for road safety using a decomposition method: a case study of Delhi," OPSEARCH, Springer;Operational Research Society of India, vol. 60(1), pages 155-173, March.
    8. Nelas, José & Dias, Joana, 2020. "Optimal Emergency Vehicles Location: An approach considering the hierarchy and substitutability of resources," European Journal of Operational Research, Elsevier, vol. 287(2), pages 583-599.
    9. Su, Qiang & Luo, Qinyi & Huang, Samuel H., 2015. "Cost-effective analyses for emergency medical services deployment: A case study in Shanghai," International Journal of Production Economics, Elsevier, vol. 163(C), pages 112-123.
    10. Lin, Yun Hui & Wang, Yuan & Lee, Loo Hay & Chew, Ek Peng, 2022. "Omnichannel facility location and fulfillment optimization," Transportation Research Part B: Methodological, Elsevier, vol. 163(C), pages 187-209.
    11. Carvalho, A.S. & Captivo, M.E. & Marques, I., 2020. "Integrating the ambulance dispatching and relocation problems to maximize system’s preparedness," European Journal of Operational Research, Elsevier, vol. 283(3), pages 1064-1080.
    12. Cheng, Yung-Hsiang & Liang, Zheng-Xian, 2014. "A strategic planning model for the railway system accident rescue problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 75-96.
    13. Masashi Miyagawa, 2020. "Optimal number and length of point-like and line-like facilities of grid and random patterns," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(1), pages 213-230, April.
    14. DuBois, Eric & Schmidt, Adam & Albert, Laura A., 2021. "Location of trauma care resources with inter-facility patient transfers," Operations Research Perspectives, Elsevier, vol. 8(C).
    15. Sam Ratick & Jeffrey Osleeb & Kangping Si, 2016. "The Maximal Cover Location Model with Hedging," International Regional Science Review, , vol. 39(1), pages 77-107, January.
    16. Bertsimas, Dimitris & Ng, Yeesian, 2019. "Robust and stochastic formulations for ambulance deployment and dispatch," European Journal of Operational Research, Elsevier, vol. 279(2), pages 557-571.
    17. A Başar & B Çatay & T Ünlüyurt, 2011. "A multi-period double coverage approach for locating the emergency medical service stations in Istanbul," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(4), pages 627-637, April.
    18. Xu, Jing & Murray, Alan T. & Church, Richard L. & Wei, Ran, 2023. "Service allocation equity in location coverage analytics," European Journal of Operational Research, Elsevier, vol. 305(1), pages 21-37.
    19. Dirk Degel & Lara Wiesche & Sebastian Rachuba & Brigitte Werners, 2015. "Time-dependent ambulance allocation considering data-driven empirically required coverage," Health Care Management Science, Springer, vol. 18(4), pages 444-458, December.
    20. KC, Kiran & Corcoran, Jonathan & Chhetri, Prem, 2020. "Measuring the spatial accessibility to fire stations using enhanced floating catchment method," Socio-Economic Planning Sciences, Elsevier, vol. 69(C).

    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:spr:snopef:v:2:y:2021:i:1:d:10.1007_s43069-020-00050-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.