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

doi:10.15960/j.cnki.issn.1007-6093.2015.04.004

Operations Research Transactions ›› 2015, Vol. 19 ›› Issue (4): 37-47.doi: 10.15960/j.cnki.issn.1007-6093.2015.04.004

Previous Articles Next Articles

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

ZHANG Huizhen^1,2,*, WEI Xin¹, MA Liang¹

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:2014-11-24 Online:2015-12-15 Published:2015-12-15
Contact: 张惠珍 zhzzywz@gmail.com

Abstract

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

ZHANG Huizhen, WEI Xin, MA Liang. A new semi-Lagrangian relaxation method to solve the un-capacitated facility location problem[J]. Operations Research Transactions, 2015, 19(4): 37-47.

References

堵丁柱, 葛可一, 胡晓东. 近似算法的设计与分析 [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.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments