A Single-level Mixed-integer Programming Model for the Competitive Facility Location Problem

doi:10.3969/j.issn.1007-7375.e17-3094

Abstract

Abstract: The classic facility location problem, based on the assumption of space monopoly, does not consider the existence of competition facilities. However, in application, companies have to consider rivals when making location decisions. Therefore, a competitive facility location problem is studied. A discrete network is considered, in which two players (a leader and a follower) sequentially located a fixed number of facilities, competing to capture market share. Each customer sought the nearest facility for service. The leader had to solve a bilevel linear programming problem in which the lower level was NP hard, given the leader's decision, and the follower was faced with the classical maximum covering location. It is assumed that the follower used the greedy addition algorithm and formulated a single-level mixed-integer programming model that embedded the follower's response into the leader's constraints. The proposed model is verified and the condition of the optimal solution given. The model is also solved using the optimization solver Gurobi 6.5, which was able to generate suboptimal solutions for instances with 40 nodes in a short time.

Key words: linear programming, competitive location, zero-sum game, single-level programming, greedy add algorithm, optimal condition

CLC Number:

CHENG Chun, ZHANG Ying, XUE Zhaojie, QI Mingyao. A Single-level Mixed-integer Programming Model for the Competitive Facility Location Problem[J]. Industrial Engineering Journal , 2017, 20(5): 21-27.

References

[1] DASKIN M S. Network and discrete location: models, algorithms, and applications[M]. New York: Wiley, 1995.
[2] ZHANG Y, SNYDER L V, RALPHS T K, et al. The competitive facility location problem under disruption risks[J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 93: 453-473.
[3] 杨丰梅, 华国伟, 黎建强. 一个竞争选址问题的新模型及其求解算法[J]. 系统工程理论与实践, 2006, 26(7): 18-24.
YANG Fengmei, HUA Guowei, LI Jianqiang. A new model for Competitive Location and its algorithms [J]. Systems Engineering - Theory & Practice, 2006, 26(7): 18-24.
[4] KÜÇÜKAYDıN H, ARAS N, ALTıNEL İ K. A leader-follower game in competitive facility location[J]. Computers & Operations Research, 2012, 39(2): 437-448.
[5] HAKIMI S L. On locating new facilities in a competitive environment[J]. European Journal of Operational Research, 1983, 12(1): 29-35.
[6] ALEKSEEVA E, KOCHETOV Y. Matheuristics and exact methods for the discrete (r|p)-centroid problem[M]. Berlin: Springer, 2013: 189-219.
[7] DAVYDOV I, KOCHETOV Y, MLADENOVIC N, et al. Fast metaheuristics for the discrete (r|p)-centroid problem[J]. Automation and Remote Control, 2014, 75(4): 677-687.
[8] BIESINGER B, HU B, RAIDL G. A hybrid genetic algorithm with solution archive for the discrete (r|p)-centroid problem[J]. Journal of Heuristics, 2015, 21(3): 391-431.
[9] NOLTEMEIER H, SPOERHASE J, WIRTH H C. Multiple voting location and single voting location on trees[J]. European journal of operational research, 2007, 181(2): 654-667.
[10] ALEKSEEVA E, KOCHETOVA N, KOCHETOV Y, et al. A hybrid memetic algorithm for the competitive p-median problem[J]. IFAC Proceedings Volumes, 2009, 42(4): 1533-1537.
[11] DAVYDOV I A. Tabu search for the discrete (r|p)-centroid problem[J]. Diskretnyi Analiz i Issledovanie Operatsii, 2012, 19(2): 19-40.
[12] ALEKSEEVA E, KOCHETOVA N, KOCHETOV Y, et al. Heuristic and exact methods for the discrete (r|p)-centroid problem[C]. Berlin: Springer, 2010.
[13] ROBOREDO M C, PESSOA A A. A branch-and-cut algorithm for the discrete (r|p)-centroid problem[J]. European Journal of Operational Research, 2013, 224(1): 101-109.
[14] 谢天保, 张晓雯, 仵凯博, 等. 电子商务下基于协同配送的配送中心选址研究[J]. 工业工程, 2015, 18(3): 75-81.
XIE Tianbao, ZHANG Xiaowen, WU Kaibo, et al. A study of distribution center location based on collaborative distribution under e-commerce [J]. Industrial Engineering Journal, 2015, 18(3): 75-81.
[15] 杜博, 周泓. 不确定环境下应急设施选址问题两阶段鲁棒优化模型[J]. 工业工程, 2016, 19(5): 45-50.
DU Bo, ZHOU Hong. A two-stage robust optimization model for emergency facility location problems under uncertainties [J]. Industrial Engineering Journal, 2016, 19(5): 45-50.