English

运筹学学报 >

2019 , Vol. 23 >Issue 3: 15 - 26

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2019.03.002

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

展开
  • 1. 中国科学院数学与系统科学研究院, 北京 100190;
    2. 中国科学院大学数学科学学院, 北京 100049;
    3. 河北工业大学理学院, 天津 300401

收稿日期: 2019-05-09

  网络出版日期: 2019-09-09

基金资助

国家自然科学科学基金（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

Expand
  • 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 date: 2019-05-09

  Online published: 2019-09-09

Fold

摘要

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

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

本文引用格式

杨沐明, 黄亚魁, 戴彧虹 . 一类多商品设施选址问题的基于线性松弛解的启发式方法[J]. 运筹学学报, 2019 , 23(3) : 15 -26 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.002

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

参考文献

[1] Daskin M S. What you should know about location modeling[J]. Naval Research Logistics, 2008, 55:283-294.
[2] Klose A, Drexl A. Facility location models for distribution systemdesign[J]. European Journal of Operational Research, 2005,162:4-29.
[3] Conforti M, Cornuéjols G, Zambelli G. Integer Programming[M]. Berlin:Springer, 2014.
[4] Arya V, Garg N, Khandekar R, et al.Local search heuristic for k-median and facility location problems[C]//Proceedings on 33rd Annual ACM Symposium on Theory of Computing,2001, Heraklion, Crete, Greece. ACM, 2001.
[5] Korupolu M R, Plaxton C G, Rajaraman R. Analysis of a local searchheuristic for facility location problems[J]. Journal ofAlgorithms, 2000, 37:146-188.
[6] Zhang J, Chen B, Ye Y. A multiexchange local search algorithm forthe capacitated facility location problem[J]. Mathematics ofOperations Research, 2005, 30:389-403.
[7] Sun M. Solving the uncapacitated facility location problem usingtabu search[J]. Computers & Operations Research, 2006,33:2563-2589.
[8] Chudak F A, Shmoys D B. Improved approximation algorithms for theuncapacitated facility location problem[J]. SIAM Journal onComputing, 2003, 33:1-25.
[9] Huang H C, Li R. A k-product uncapacitated facility locationproblem[J]. European Journal of Operational Research, 2008,185:552-562.
[10] Mazzola J B, Neebe A W.Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type[J].European Journal of Operational Research, 1999, 115:285-299.
[11] Nezhad A M, Manzour H, Salhi S.Lagrangian relaxation heuristics for the uncapacitated single-source multi-product facility location problem[J].International Journal of Production Economics, 2013, 145:713-723.
[12] Geoffrion A M, Graves G W. Multicommodity distribution system designby Benders decomposition[J]. Management Science, 1974, 20:822-844.
[13] Lee C Y. A cross decomposition algorithm for amultiproduct-multitype facility location problem[J]. Computers & Operations Research, 1993, 20:527-540.
[14] Klincewicz J G, Luss H, Rosenberg E. Optimal and heuristicalgorithms for multiproduct uncapacitated facility location[J].European Journal of Operational Research, 1986, 26:251-258.
[15] Karkazis J, Boffey T B. The multi-commodity facilities locationproblem[J]. Journal of the Operational Research Society,1981, 32:803-814.
[16] Klincewicz J G, Luss H. A dual-based algorithm for multiproductuncapacitated facility location[J]. Transportation Science,1987, 21:198-206.
[17] Montoya A, Vélez-Gallego M C, Villegas J G. Multi-productcapacitated facility location problem with general production andbuilding costs[J]. NETNOMICS:Economic Research and ElectronicNetworking, 2016, 17:47-70.
[18] Gurobi Optimizer[EB/OL]. http://www.gurobi.com/
[19] IBM ILOG CPLEX Optimization Studio[EB/OL].https://www.ibm.com/analytics/cplex-optimizer
[20] Achterberg T. SCIP:solving constraint integer programs[J]. Mathematical Programming Computation, 2009, 1:1-41.
Options
文章导航

/

〈 〉