TY - JOUR

T1 - Exact method for the capacitated competitive facility location problem

AU - Beresnev, Vladimir

AU - Melnikov, Andrey

N1 - Publisher Copyright: © 2018 Elsevier Ltd

PY - 2018/7/1

Y1 - 2018/7/1

N2 - We consider a competition between two parties maximizing their profit from servicing customers. A decision making process is assumed to be organized in a Stackelberg game framework. In the model, we are given with two finite sets: a set of customers and a set of potential facilities’ locations. The parties, called the Leader and the Follower, sequentially open their facilities in some of the potential locations. A party opening the most preferable facility for a customer captures him or her. Facilities’ capacities are assumed to be finite, and the problem is to decide where to open facilities and how to assign them to service captured customers provided that capacity constraints are satisfied. The Leader's problem is formalized as an optimistic bi-level mixed-integer program. We show that it can be considered as a problem to maximize a pseudo-Boolean function depending on a “small” number of Boolean variables. To find an optimal solution of this problem, we suggest a branch-and-bound algorithm where an estimating problem in a form of mixed-integer programming is utilized to calculate an upper bound for values of the objective function. In computational experiments, we study the quality of the upper bound and the performance of the method on randomly generated inputs.

AB - We consider a competition between two parties maximizing their profit from servicing customers. A decision making process is assumed to be organized in a Stackelberg game framework. In the model, we are given with two finite sets: a set of customers and a set of potential facilities’ locations. The parties, called the Leader and the Follower, sequentially open their facilities in some of the potential locations. A party opening the most preferable facility for a customer captures him or her. Facilities’ capacities are assumed to be finite, and the problem is to decide where to open facilities and how to assign them to service captured customers provided that capacity constraints are satisfied. The Leader's problem is formalized as an optimistic bi-level mixed-integer program. We show that it can be considered as a problem to maximize a pseudo-Boolean function depending on a “small” number of Boolean variables. To find an optimal solution of this problem, we suggest a branch-and-bound algorithm where an estimating problem in a form of mixed-integer programming is utilized to calculate an upper bound for values of the objective function. In computational experiments, we study the quality of the upper bound and the performance of the method on randomly generated inputs.

KW - Bi-level programming

KW - Branch-and-bound

KW - Discrete competitive location

KW - Stackelberg game

KW - ALGORITHM

KW - (R-VERTICAL-BAR-P)-CENTROID PROBLEM

KW - LOCAL SEARCH

KW - MODEL

UR - http://www.scopus.com/inward/record.url?scp=85043594642&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2018.02.013

DO - 10.1016/j.cor.2018.02.013

M3 - Article

AN - SCOPUS:85043594642

VL - 95

SP - 73

EP - 82

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -