A New Heuristic Formulation for a Competitive Maximal Covering Location Problem

Tolga H. Seyhan (), Lawrence V. Snyder () and Ying Zhang ()
Additional contact information
Tolga H. Seyhan: Amazon.com, Seattle, Washington 98109
Lawrence V. Snyder: Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, Pennsylvania 18015
Ying Zhang: Zhejiang Cainiao Supply Chain Management Co., Ltd., Hangzhou 311122, China

Transportation Science, 2018, vol. 52, issue 5, 1156-1173

Abstract: 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.

Keywords: competitive facility location; Stackelberg game; bi-level programming; greedy add algorithm (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/trsc.2017.0769 (application/pdf)

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:inm:ortrsc:v:52:y:2018:i:5:p:1156-1173

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().