IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v22y2022i5d10.1007_s12351-021-00652-3.html
   My bibliography  Save this article

A variable neighborhood search for the budget-constrained maximal covering location problem with customer preference ordering

Author

Listed:
  • Lazar Mrkela

    (Belgrade Metropolitan University)

  • Zorica Stanimirović

    (University of Belgrade)

Abstract

This paper introduces a variant of Maximal Covering Location Problem (MCLP) with customer preference ordering and limited budget for establishing facilities. It is assumed that a set of facilities belonging to competitors are already present at the market. Customers are free to choose among facilities located within a given coverage radius, according to their preferences. Instead of fixed number of facilities to be located, the new problem assumes limited budget for establishing the network of facilities of the considered firm. The goal is to choose optimal locations for opening facilities and find optimal allocations of customers to opened facilities, such that the covered demand of customers is maximized. The newly introduced variant of MCLP is formulated as an integer linear program. As we are dealing with an NP-hard optimization problem, an efficient Variable Neighborhood Search (VNS) is proposed as solution approach. In addition, the effects of incorporating strategies of accepting a worse solution or exploring neighborhood of an infeasible solution in the VNS framework were investigated. Computational results on modified MCLP instances from the literature show that VNS quickly reaches optimal solutions or improves lower bounds obtained by exact Gurobi solver. The advantages of VNS over Gurobi solver are more obvious on newly generated large-scale MCLP instances, especially in cases when Gurobi fails to provide a feasible solution. The proposed VNS is additionally tested on modified real-world MCLP instances, and the obtained results clearly indicate its capacity to solve realistic-sized test examples in short running times.

Suggested Citation

  • Lazar Mrkela & Zorica Stanimirović, 2022. "A variable neighborhood search for the budget-constrained maximal covering location problem with customer preference ordering," Operational Research, Springer, vol. 22(5), pages 5913-5951, November.
    • Handle: RePEc:spr:operea:v:22:y:2022:i:5:d:10.1007_s12351-021-00652-3
    DOI: 10.1007/s12351-021-00652-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-021-00652-3
    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/s12351-021-00652-3?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. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    2. Pierre Hansen & Nenad Mladenović & Raca Todosijević & Saïd Hanafi, 2017. "Variable neighborhood search: basics and variants," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(3), pages 423-454, September.
    3. Deniz Aksen & Nuray Piyade & Necati Aras, 2010. "The budget constrained r-interdiction median problem with capacity expansion," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 18(3), pages 269-291, September.
    4. José-Fernando Camacho-Vallejo & Álvaro Eduardo Cordero-Franco & Rosa G. González-Ramírez, 2014. "Solving the Bilevel Facility Location Problem under Preferences by a Stackelberg-Evolutionary Algorithm," Mathematical Problems in Engineering, Hindawi, vol. 2014, pages 1-14, February.
    5. Olivera Janković & Stefan Mišković & Zorica Stanimirović & Raca Todosijević, 2017. "Novel formulations and VNS-based heuristics for single and multiple allocation p-hub maximal covering problems," Annals of Operations Research, Springer, vol. 259(1), pages 191-216, December.
    6. Watson-Gandy, C. D. T., 1982. "Heuristic procedures for the m-partial cover problem on a plane," European Journal of Operational Research, Elsevier, vol. 11(2), pages 149-157, October.
    7. Maya Duque, Pablo A. & Coene, Sofie & Goos, Peter & Sörensen, Kenneth & Spieksma, Frits, 2013. "The accessibility arc upgrading problem," European Journal of Operational Research, Elsevier, vol. 224(3), pages 458-465.
    8. Charles ReVelle & Kathleen Hogan, 1989. "The Maximum Availability Location Problem," Transportation Science, INFORMS, vol. 23(3), pages 192-200, August.
    9. 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.
    10. Fred Glover & Jin-Kao Hao, 2011. "The case for strategic oscillation," Annals of Operations Research, Springer, vol. 183(1), pages 163-173, March.
    11. Fabio Colombo & Roberto Cordone & Guglielmo Lulli, 2015. "A variable neighborhood search algorithm for the multimode set covering problem," Journal of Global Optimization, Springer, vol. 63(3), pages 461-480, November.
    12. Richard Church & Charles R. Velle, 1974. "The Maximal Covering Location Problem," Papers in Regional Science, Wiley Blackwell, vol. 32(1), pages 101-118, January.
    13. Hanjoul, Pierre & Peeters, Dominique, 1987. "A facility location problem with clients' preference orderings," Regional Science and Urban Economics, Elsevier, vol. 17(3), pages 451-473, August.
    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. 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.
    2. Fadda, Edoardo & Manerba, Daniele & Tadei, Roberto, 2024. "How to locate services optimizing redundancy: A comparative analysis of K-Covering Facility Location models," Socio-Economic Planning Sciences, Elsevier, vol. 94(C).
    3. 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).
    4. 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.
    5. Wang, Wei & Wang, Shuaian & Zhen, Lu & Qu, Xiaobo, 2022. "EMS location-allocation problem under uncertainties," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    6. Karl Schneeberger & Karl Doerner & Andrea Kurz & Michael Schilde, 2016. "Ambulance location and relocation models in a crisis," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 24(1), pages 1-27, March.
    7. Erhan Erkut & Armann Ingolfsson & Güneş Erdoğan, 2008. "Ambulance location for maximum survival," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(1), pages 42-58, February.
    8. 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.
    9. Akdogan, M. Altan & Bayındır, Z. Pelin & Iyigun, Cem, 2023. "An analysis of ambulance location problem from an equity perspective," Socio-Economic Planning Sciences, Elsevier, vol. 90(C).
    10. Mohri, Seyed Sina & Akbarzadeh, Meisam & Sayed Matin, Seyed Hamed, 2020. "A Hybrid model for locating new emergency facilities to improve the coverage of the road crashes," Socio-Economic Planning Sciences, Elsevier, vol. 69(C).
    11. Wajid, Shayesta & Nezamuddin, N., 2023. "Capturing delays in response of emergency services in Delhi," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    12. Yıldız, Gazi Bilal & Soylu, Banu, 2019. "A multiobjective post-sales guarantee and repair services network design problem," International Journal of Production Economics, Elsevier, vol. 216(C), pages 305-320.
    13. Wajid, Shayesta & Nezamuddin, N., 2022. "A robust survival model for emergency medical services in Delhi, India," Socio-Economic Planning Sciences, Elsevier, vol. 83(C).
    14. 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.
    15. Wu, Zhongqi & Jiang, Hui & Liang, Xiaoyu & Zhou, Yangye, 2024. "Multi-period distributionally robust emergency medical service location model with customized ambiguity sets," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 181(C).
    16. 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.
    17. Inkyung Sung & Taesik Lee, 2018. "Scenario-based approach for the ambulance location problem with stochastic call arrivals under a dispatching policy," Flexible Services and Manufacturing Journal, Springer, vol. 30(1), pages 153-170, June.
    18. Zhang, Ying & Snyder, Lawrence V. & Ralphs, Ted K. & Xue, Zhaojie, 2016. "The competitive facility location problem under disruption risks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 453-473.
    19. 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.
    20. Bélanger, V. & Ruiz, A. & Soriano, P., 2019. "Recent optimization models and trends in location, relocation, and dispatching of emergency medical vehicles," European Journal of Operational Research, Elsevier, vol. 272(1), pages 1-23.

    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:operea:v:22:y:2022:i:5:d:10.1007_s12351-021-00652-3. 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.