王婷婷 张惠珍 赵玉苹

摘要无容量设施选址问题（Uncapacitated Facility Location Problem， UFLP）是一类经典的组合优化问题，被证明是一种NP-hard问题，易于描述却难于求解.首先根据UFLP的数学模型及其具体特征，重新设计了蝙蝠算法的操作算子，给出了求解UFLP的蝙蝠算法.其次构建出三种可行化方法，并将其与求解UFLP的蝙蝠算法和拉格朗日松弛算法相结合，设计了求解该问题的拉格朗日蝙蝠算法.最后通过仿真实例和与其他算法进行比较的方式，验证了该混合算法用来求解UFLP的可行性，是解决离散型问题的一种有效方式.

关键词管理科学与工程；无容量设施选址问题；拉格朗日蝙蝠算法；拉格朗日松弛算法；蝙蝠算法

中图分类号TP301.6文献标识码A

Lagrangian Bat Algorithm for Solving

The Uncapacitated Facility Location Problem

Tingting Wang1， Huizhen Zhang1， Yuping Zhao2

（1.School of Management， University of Shanghai for Science & Technology， Shanghai200093， China；

2. State Grid Shanghai Procurement Company， Shanghai200093， China）

AbstractThe uncapacitated facility location problem is a classical combinatorial optimization problem and has been proved an NPhard problem， easy to describe but difficult to solve. Based on the mathematical model and specific features of UFLP， the operators of bat algorithm and proposed a bat algorithm for solving it has been redesigned. Secondly， three feasible methods were designed and lagrangian bat algorithm was presented by combining these three methods， the bat algorithm for UFLP and lagrangian relaxation algorithm. Lastly， the experimental results showed that the hybrid algorithm can feasibly solve UFLP through simulation examples and comparisons with other algorithms and it is an effective algorithm in solving the discrete problem.

Key wordsmanagement science and engineering； uncapacitated facility location problem； lagrangian bat algorithm； lagrangian relaxation algorithm； bat algorithm

1引言

設施选址问题是在各需求点已给定的条件下，选择设施的最佳位置，使设施的总成本降到最低[1].无容量设施选址问题是从给定没有容量限制的设施集中选择要开放的设施，使其以最小的总费用来服务所有客户.到目前为止，求解该问题的方法主要有近似算法、精确算法和智能优化算法.近似算法可以在多项式时间内求得问题的一个解，并且其目标函数值与最优解的目标函数值之比不超过一个常数[2]；精确算法是一种可以求得最优解的算法，但仅适用于小规模问题，且计算速度较慢.智能优化算法更期望在可接受时间内获得问题的最优解或近似最优解.近年来，许多学者运用各种智能优化算法来解决UFLP：Kole（2014）[3]等首次将蚁群算法用于UFLP的求解，并与粒子群算法进行对比，拓宽了蚁群算法的应用范围；……