Optimizing Sequential Competitive Facility Location and Attractiveness Design

We consider a sequential competitive facility location and attractiveness design problem (S-CFLAP) in which the leader and follower sequentially decide on the location and attractiveness design (e.g., building area) of new facilities to maximize their market shares. Customer demand follows a probabilistic choice model in which a gravity-based rule is employed to model customer behavior. In S-CFLAP, there are two types of players: the leader and the follower. Their interaction is modeled as a Stackelberg game, in which the leader makes decisions first by predicting the follower’s response and the follower acts afterward. This framework results in a bilevel mixed-integer nonlinear program (MINLP). This is the first study to propose an exact and efficient algorithm for the S-CFLAP with continuous attractiveness by choosing the appropriate utility function, reformulation, and valid inequality derivation. Specifically, we reformulate the bilevel model to a single-level MINLP by adopting the idea of solving the interdiction games. Then, we derive valid inequalities using the outer-approximation method and incorporate them in a branch-and-cut (B&C) algorithm. For the subproblem, in which the leader’s decisions are fixed, we propose two methods: outer approximation and a reformulation into a second-order cone programming (SOCP) model, which leads to two exact algorithms of the S-CFLAP. Also, we enhance the B&C algorithms by temporarily allowing suboptimal solutions of the subproblems to be added as cuts. Comprehensive experiments validate the efficiency and effectiveness of the proposed B&C algorithms, the reformulations, and the acceleration policy. We also derived several managerial insights for decision makers regarding the design budget assignment, leader-follower game-playing, spatial impedance effects, and so on, from comparisons with benchmark solution approaches and sensitivity analyses.