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

作者：程春; 张莹; 薛召杰; 戚铭尧

来源：工业工程, 2017, 20(05): 21-27.

DOI：10.3969/j.issn.1007-7375.e17-3094

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

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

• 单位
  清华大学深圳研究生院; 土木工程学院; 深圳大学