English

运筹学学报 >

2015 , Vol. 19 >Issue 4: 37 - 47

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

运筹学

求解无容量设施选址问题的半拉格朗日松弛新方法

展开
  • 1. 上海理工大学管理学院, 上海 200093; 2.上海理工大学超网络(中国)研究中心, 上海 200093

收稿日期: 2014-11-24

  网络出版日期: 2015-12-15

基金资助

1.国家自然科学基金(No.71401106);2.上海市教育委员会科研创新项目(No.14YZ090);

3.上海市一流学科建设项目(No.S1201YLXK);4.高等学校博士学科点专项科研基金联合资助课题(No.20123120120005);

5.上海高校青年教师培养资助计划(No.slg12010);6.沪江基金(No.A14006)

收起

A new semi-Lagrangian relaxation method to solve the un-capacitated facility location problem

Expand
  • 1.School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China; 2. Center for Supernetworks Research, University of Shanghai for Science and Technology, Shanghai 200093, China

Received date: 2014-11-24

  Online published: 2015-12-15

Fold

摘要

无容量设施选址问题Un-capacitated Facility Location, UFL是应用于诸多领域的经典组合优化难题, 半拉格朗日松弛方法是求解UFL问题的一种精确方法. 分析了半拉格朗日松弛方法在求解UFL问题时所具有的性质, 在此基础上, 对求解UFL问题的半拉格朗日松弛方法进行了一定的理论完善, 并探讨了提高半拉格朗日松弛方法求解性能的有效途径.数值计算结果表明：改进方法具有明显的可行性和有效性.

关键词： 无容量设施选址; 拉格朗日松弛; 半拉格朗日松弛; 原始-对偶最优解

本文引用格式

张惠珍, 魏欣, 马良 . 求解无容量设施选址问题的半拉格朗日松弛新方法[J]. 运筹学学报, 2015 , 19(4) : 37 -47 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.04.004

Abstract

The un-capacitated facility location (UFL) problem is a classical combinatorial optimization hard problem and has been applied in various fields. The semi-Lagrangian relaxation method is one of the exact solution methods to the UFL. In this paper, the mathematical nature of the SLR applied to solve the UFL is further studied. Based on this, the SLR applied to solve the UFL is improved from the theoretical point of view, and the approach is also discussed to enhance its
computational capability. The numerical results show that the improvement proposed in this paper is feasible and effective.

Key words： Un-capacitated facility location; Lagrangian relaxation; Semi-Lagrangian relaxation; Primal-dual optimal solution

参考文献

堵丁柱, 葛可一, 胡晓东. 近似算法的设计与分析 [M]. 北京：高等教育出版社, 2011.


Klose A. A branch and bound algorithm for an UFLP with a side constrain [J]. International Transactions in Operational Research, 1998,5(2): 155-168.

Al-Sultan K S, Al-Fawzan M A. A tabu search approach to the uncapacitated facility location problem [J].Annals of Operations Research, 1999, 86: 91-103.

Laurent M, Hentenryck P V. A simple tabu search for warehouse location [J]. European Journal of Operational Research, 2004,157(3): 576-591.

Jaramillo J H, Bhadury J, Batta R. On the use of genetic algorithms to solve location problems [J]. Computers and Operations Research, 2002, 29(6): 761-779.

Ghosh D. Neighborhood search heuristics for the uncapacitated facility location problem [J]. European Journal of Operational Research, 2003, 150(1): 150-162.

王大志, 闫杨, 汪定伟, 等. 基于OpenMP求解无容量设施选址问题的并行PSO算法 [J]. 东北大学学报(自然科学版), 2008, 29(12): 1681-1684.

Sujay Saha, Arnab Kole, Kashinath Dey. A Modified Continuous Particle Swarm Optimization Algorithm for Uncapacitated Facility Location Problem [A]//Information Technology and Mobile Communication, Communications in Computer and Information Science [C]//Berlin Heidelberg: Springer, 2011, 305-311.

Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem [J]. Information and Computation,2013, 222(1): 45-58.

Beltran-Royo C, Tadonki C, Vial J.-Ph. Solving the p-median problem with a semi-Lagrangian relaxation [J].  Computational Optimization and Applications, 2006,35(2): 239-260.

Beltran-Royo C, Vial J.-P, Alonso-Ayuso A. Semi-Lagrangian relaxation applied to the uncapacitated facility location problem [J]. Computational Optimization and Applications, 2012,51(1): 387-409.

M. Hoefer. Ufllib, 2006. http://www.mpi-inf.mpg.de/departments/d1/projects/benchmarks/ UflLib/index.html.

 
Options
文章导航

/

〈 〉