English

运筹学学报 ›› 2019, Vol. 23 ›› Issue (3): 15-26.doi: 10.15960/j.cnki.issn.1007-6093.2019.03.002

• • 上一篇    下一篇

一类多商品设施选址问题的基于线性松弛解的启发式方法

杨沐明1,2, 黄亚魁3, 戴彧虹1,2,*   

  1. 1. 中国科学院数学与系统科学研究院, 北京 100190;
    2. 中国科学院大学数学科学学院, 北京 100049;
    3. 河北工业大学理学院, 天津 300401
  • 收稿日期:2019-05-09 发布日期:2019-09-09
  • 通讯作者: 戴彧虹 E-mail:dyh@lsec.cc.ac.cn
  • 基金资助:
    国家自然科学科学基金（Nos.11631013，11701137），国家重点基础研究发展计划（973计划）项目（No.2015CB856002），科学大数据公共服务平台与创新应用示范项目（No.2016-999999-65-01-000696）

Linear relaxation solution based heuristics for a class of multi-product facility location problems

YANG Muming1,2, HUANG Yakui3, DAI Yuhong1,2,*   

  1. 1. Academy of Mathematics and Systems Science, ChineseAcademy of Sciences, Beijing 100190, China;
    2. School of MathematicalSciences, University of Chinese Academy of Sciences, Beijing 100049, China;
    3. School ofScience, Hebei University of Technology, Tianjin 300401, China
  • Received:2019-05-09 Published:2019-09-09

PDF

799

摘要： 多商品设施选址问题是众多设施选址问题中一类重要而困难的问题.在这一问题中，顾客的需求可能包含不止一种商品.对于大规模问题，成熟的商业求解器往往不能在满意的时间内找到高质量的可行解.研究了无容量限制的单货源多商品设施选址问题的一般形式，并给出了应用于此类问题的两个启发式方法.这两个方法基于原选址问题的线性规划松弛问题的最优解，分别通过求解紧问题和邻域搜索的方式给出了原问题的一个可行上界.理论分析指出所提方法可以实施于任意可行问题的实例.数值结果表明所提方法可以显著地提高求解器求解此类设施选址问题的求解效率.

关键词: 多商品设施选址问题, 启发式, 线性规划, 整数规划, 紧问题, 邻域搜索

Abstract: The multi-product facility location problem is an important but difficult class in facility location problems, which allows that customers have demand for different products. When solving large scale problems, commercial solvers hardly achieve high quality solutions in a reasonable time. In this paper, the general form of the uncapacitated single-source multi-product facility location problem is studied and two heuristic methods are proposed for this problem. Based on the linear relaxation optimal solution of the original problem, the two methods can provide a feasible upper bound via solving a compact problem and local search techniques, respectively. Through the theoretical analysis, it is guaranteed that these two methods can be implemented on any feasible instances. Numerical results show that the heuristic methods can significantly improve the performance of the commercial solver for solving this kind of problem.

Key words: multi-product facility location problem, heuristic, linear programming, integer programming, compact problem, localsearch

中图分类号: