Branch-and-cut approach based on generalized benders decomposition for facility location with limited choice rule

Yun Hui Lin and Qingyun Tian

European Journal of Operational Research, 2021, vol. 293, issue 1, 109-119

Abstract: This paper studies the exact solution approaches for a generalized competitive facility location problem. We consider a company that plans to introduce a service by opening a set of facilities. The objective is to maximize the profit taking into account the revenue and the fixed cost. It is assumed that when customers are offered with a set of open facilities, they first form the consideration set, i.e., the subset of open facilities that the customers are willing to patronize. They then split the buying power among the facilities in the set plus some outside option, according to Luce’s choice axiom. The resulting location problem provides a generalized framework that covers many existing models in competitive facility location problems where customers follow either the proportional choice rule or the partially binary choice rule. As our main contribution, we propose a branch-and-cut algorithm based on the generalized Benders decomposition scheme (B&C-Benders), which projects out high-dimensional continuous variables in modeling the consideration set and only works on the projected decision space. Our extensive computational experiment shows that B&C-Benders outperforms state-of-the-art exact approaches, both in terms of the computational time, and in terms of the number of instances solved to optimality. In the special case where customers follow the partially binary choice rule, B&C-Benders turns out to be efficient for large-scale instances with thousands of customer zones and hundreds of facilities.

Keywords: Combinatorial optimization; Competitive facility location; Consideration set; Discrete choice model; Generalized Benders decomposition (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720310456
Full text for ScienceDirect subscribers only

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:eee:ejores:v:293:y:2021:i:1:p:109-119

DOI: 10.1016/j.ejor.2020.12.017

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().