李 翼，赵茂先，李岳佳

（山东科技大学信息科学与工程学院，山东青岛266590）

设施选址问题是经典的优化问题，其目的是为了覆盖一个给定的区域，并且要满足这个区域里所有客户的需求，从而来选择一个或多个设施中心，这些中心包括仓库，厂房，超市，公共设施等．每个客户的需求可以全部由一个中心提供，也可以由多个中心来提供．一个好的选址方法可以有效的节省费用，促进生产和消费的协调与配合，使得设施系统平衡发展．本文研究的是无容量限制的设施选址问题（Uncapacitated Facility Location Problem，UFLP），也称为简单设施选址，指的是物流中心的容量被认为是无界的．此类问题由Kuehn和Hamburger［1]在1963年提出，Shmoys等人［2]在1997年给出了UFLP的第一个常数近似度算法，Jaroslav和Buzna［3]在2008年提出了一个改进的Erlenkotters算法，用于解决大规模的UFLP非常有效．本质上UFLP是一个组合优化问题，因此处理小规模的问题一般使用精确算法，例如分支定界算法等．

本文研究的无容量限制的设施选址问题的算法是基于分支定界法技术提出的．

1 UFLP模型及等价形式

总费用通常由两部分组成．第一部分为运输费用，指的是由配送中心到需求点运输货物所需的费用，记为Trans（D）其中xij∈｛0，1｝，当设施中心i向需求点j提供服务时xij＝1；否则xij＝0．

根据以上假设，UFLP模型是下述整数规划：

约束（1）保证了每个需求点j只由一个中心提供服务；约束（2）表示任何需求点只能由开放的设施提供服务；约束（3）表示xij和yi是0－1变量．由于cij≥0，当上述规划的变量xij的约束变为0≤xij≤1时，问题的最优解不变．约束（2）可转化为下述约束：