A New Heuristic Formulation for a Competitive Maximal Covering Location Problem

We consider a competitive facility location problem in which two firms engage in a leader–follower game. Both firms would like to maximize the customer demand that they capture. Given the other player’s decision, each player’s problem is the classical maximal covering location problem. That is, the leader has to solve a bi-level problem in which the second-level problem is NP-hard. To overcome this, we use the greedy add algorithm as an approximation for the follower’s response and formulate a mixed-integer programming model that embeds the follower’s heuristic response into the leader’s constraints and solve it as a single-level problem. The resulting formulation is tractable and provides near-optimal solutions for the leader’s decision. We analyze the performance of the heuristic both theoretically and computationally. We also provide alternate formulations for the same problem and compare them.