A matheuristic for solving the bilevel approach of the facility location problem with cardinality constraints and preferences. (December 2020)

• Record Type: Journal Article
• Authors: Calvete, Herminia I.; Galé, Carmen; Iranzo, José A.; Camacho-Vallejo, José-Fernando; Casas-Ramírez, Martha-Selene
• Is Part Of: Computers & operations research. Volume 124(2020)
• Publication Date: 2020-12
• Subjects: Facility location -- Cardinality constraint -- Capacity -- Preferences -- Bilevel optimization -- Matheuristic -- Evolutionary algorithm; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105066
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A facility location problem with customer preferences and cardinality constraints. Two approaches that extend the uncapacitated facility location formulation. Single level formulation of the bilevel approach without additional binary variables. A simple and effective matheuristic based on evolutionary algorithms. Abstract: This paper addresses a generalized version of the facility location problem with customer preferences which includes an additional constraint on the number of customers which can be allocated to each facility. The model aims to minimize the total cost due to opening facilities and allocating customers while taking into account both customer preferences for the facilities and these cardinality constraints. First, two approaches to deal with this problem are proposed, which extend the single level and bilevel formulations of the problem in which customers are free to select their most preferred open facility. After analyzing the implications of assuming any of the two approaches, in this research, we adopt the approach based on the hierarchical character of the model which leads to the formulation of a bilevel optimization problem. Then, taking advantage of the characteristics of the lower level problem, a single level reformulation of the bilevel optimization model is developed based on duality theory which does not require the inclusion of additional binary variables. Finally, we develop a simple but effective matheuristic for solving the bilevel optimization problem whose general framework follows that of an evolutionary algorithm and exploits the bilevel structure of the model. The chromosome encoding pays attention to the upper level variables and controls the facilities which are open. Then, an optimization model is solved to allocate customers in accordance with their preferences and the availability of the open facilities. A computational experiment shows the effectiveness of the matheuristic in terms of the quality of the solutions yielded and the computing time.