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. 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.
    3. 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.
    4. Richard Church & Charles R. Velle, 1974. "The Maximal Covering Location Problem," Papers in Regional Science, Wiley Blackwell, vol. 32(1), pages 101-118, January.
    5. 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.
    6. 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.
    7. 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.
    8. Kathleen Hogan & Charles ReVelle, 1986. "Concepts and Applications of Backup Coverage," Management Science, INFORMS, vol. 32(11), pages 1434-1444, November.
    9. 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).
    10. 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.
    11. 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.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fragkogios, Antonios & Qiu, Yuzhuo & Saharidis, Georgios K.D. & Pardalos, Panos M., 2024. "An accelerated benders decomposition algorithm for the solution of the multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 317(2), pages 500-514.

    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. 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.
    12. 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).
    13. 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.
    14. 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.
    15. Jian Wang & Yin Wang & Mingzhu Yu, 2022. "A multi-period ambulance location and allocation problem in the disaster," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 909-932, July.
    16. Jiang, Zhoutong & Ouyang, Yanfeng, 2021. "Reliable location of first responder stations for cooperative response to disasters," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 20-32.
    17. Güney, Evren & Leitner, Markus & Ruthmair, Mario & Sinnl, Markus, 2021. "Large-scale influence maximization via maximal covering location," European Journal of Operational Research, Elsevier, vol. 289(1), pages 144-164.
    18. Jian Wang & Yin Wang & Mingzhu Yu, 0. "A multi-period ambulance location and allocation problem in the disaster," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-24.
    19. Xueping Li & Zhaoxia Zhao & Xiaoyan Zhu & Tami Wyatt, 2011. "Covering models and optimization techniques for emergency response facility location and planning: a review," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 74(3), pages 281-310, December.
    20. 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.

    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.