English

运筹学学报 ›› 2015, Vol. 19 ›› Issue (4): 37-47.doi: 10.15960/j.cnki.issn.1007-6093.2015.04.004

• 运筹学 • 上一篇    下一篇

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

张惠珍1,2,*, 魏欣1, 马良1   

  1. 1. 上海理工大学管理学院, 上海 200093; 2.上海理工大学超网络(中国)研究中心, 上海 200093
  • 收稿日期:2014-11-24 出版日期:2015-12-15 发布日期: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

ZHANG Huizhen1,2,*, WEI Xin1, MA Liang1   

  1. 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

PDF

589

被引次数

2

摘要：

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

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

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