竞争选址问题的单层混合整数规划模型

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

工业工程 ›› 2017, Vol. 20 ›› Issue (5): 21-27.doi: 10.3969/j.issn.1007-7375.e17-3094

竞争选址问题的单层混合整数规划模型

程春¹, 张莹², 薛召杰³, 戚铭尧¹

1. 清华大学深圳研究生院, 广东深圳 518055;
2. 浙江菜鸟供应链管理有限公司, 浙江杭州 310023;
3. 深圳大学土木工程学院, 广东深圳 518060

收稿日期:2017-04-21 出版日期:2017-10-30 发布日期:2017-11-17
通讯作者: 戚铭尧(1974-),男,湖北省人,副教授,博士.Email:qimy@sz.tsinghua.edu.cn E-mail:qimy@sz.tsinghua.edu.cn
作者简介:程春(1987-),女,四川省人,博士研究生,主要研究方向为设施选址及库存路径问题.
基金资助:
国家自然科学基金资助项目（71272030）

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

CHENG Chun¹, ZHANG Ying², XUE Zhaojie³, QI Mingyao¹

1. Graduate School at Shenzhen, Tsinghua University, Shenzhen 518055, China;
2. Zhejiang Cainiao Supply Chain Management Co., Ltd., Hangzhou 310023, China;
3. College of Civil Engineering, Shenzhen University, Shenzhen 518060, China

Received:2017-04-21 Online:2017-10-30 Published:2017-11-17

摘要/Abstract

摘要： 经典设施选址问题基于空间垄断的假设，不考虑竞争设施的存在。而实际中，企业制定选址决策时需考虑对手的竞争。为此，研究了竞争性设施选址问题。考虑了一个离散的网络，两个服务提供者（领导者和跟随者）相继地开放一定数量的设施，以竞争市场份额。每个客户向最近的设施寻求服务。领导者需求解一个双层线性规划问题，其中下层问题是NP难问题，因为给定领导者的决策，跟随者需求解最大覆盖问题。假设跟随者采用贪婪策略，建立了一个单层的整数规划模型，将跟随者的响应集成到领导者问题的约束条件中。通过理论推导验证了模型的正确性，给出了最优解存在的条件。利用优化求解器Gurobi 6.5求解提出的模型，能在较短时间内给出40个节点的近似最优解。

关键词: 线性规划, 竞争选址, 零和博弈, 单层规划, 贪婪算法, 最优性条件

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

中图分类号:

程春, 张莹, 薛召杰, 戚铭尧. 竞争选址问题的单层混合整数规划模型[J]. 工业工程, 2017, 20(5): 21-27.

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.

参考文献

[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.

竞争选址问题的单层混合整数规划模型

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	李守荣, 张人千. 基于拓展经营的交叉销售产品的订货研究[J]. 工业工程, 2018, 21(2): 19-26.
[2]	方刚，徐哲，顾坤. 高校论文答辩排班模型与应用[J]. 工业工程, 2016, 19(6): 123-130.
[3]	丁雪枫. 电网系统突发受袭下的风险分析问题[J]. 工业工程, 2015, 18(6): 83-88.
[4]	关志民，陶瑾. 考虑风险规避行为的弹性供应链网络集成优化[J]. 工业工程, 2015, 18(4): 49-57.
[5]	刘衍，钟胜. 医院门诊就诊路径调度研究[J]. 工业工程, 2014, 17(4): 116-122.
[6]	侯艳1,2，伍乃骐1，白丽平1. 原油处理过程短期生产计划优化[J]. 工业工程, 2014, 17(3): 79-85.