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

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

作　　者：程春 张莹 薛召杰 戚铭尧[1] 

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

出　　处：《工业工程》2017年第5期21-27,共7页Industrial Engineering Journal

基　　金：国家自然科学基金资助项目(71272030)

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

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

分 类 号：O221.1[理学—运筹学与控制论] F224.33[理学—数学]