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

Lazar Mrkela () and Zorica Stanimirović ()
Additional contact information
Lazar Mrkela: Belgrade Metropolitan University
Zorica Stanimirović: University of Belgrade

Operational Research, 2022, vol. 22, issue 5, No 40, 5913-5951

Abstract: 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.

Keywords: Maximal covering location problem; Customer preference ordering; Metaheuristics; Variable neighborhood search; 90B10; 68T20; 90C10 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-021-00652-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:22:y:2022:i:5:d:10.1007_s12351-021-00652-3

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-021-00652-3

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().