无容量限制设施选址问题的分支定界法

李 翼，赵茂先，李岳佳

（山东科技大学信息科学与工程学院，山东青岛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）可转化为下述约束：

对于（4），当yi＝0时，有≤0，所以对于∀j∈D，有xij＝0；当yi＝1时≤m，再由约束（1）和（3）可得到对于∀j∈D，有xij≤yi．故不等式族（4）和不等式族（2）等价．因此，（UFLP）可转化为下面等价形式：

2 分支定界算法

记x＝（xij），y＝（yi），设X是问题P的可行域，用f（·）表示问题（·）的最优值．

定义1 如果（x，y）∈X，称（x，y）为问题P的可行解，即为UFLP的一个可行方案．

定义2 如果（x＊，y＊）∈X，且对∀（x，y）∈X，有

则称（x＊，y＊）为问题（P）的最优解．

引理1 考虑如下两个线性规划问题：

证明 线性规划（LP1）和（LP2）的对偶问题分别为

设u1＝（w1，v1）和u2＝（w2，v2）分别是（LP1）和（LP2）的最优对偶可行解，由上述模型得，u1＝（w1，v1）同时为（LP2）对偶问题的一个可行解，则有

设x0，y0为（P）的一个可行解，对y0建立下列线性规划问题：

它的对偶线性问题为

其中（w，v）为具有相应维数的对偶乘子．

令k表示求解问题（P）的分支定界树生成的第k个结点，记

定理1 设z＊和u＊＝（w＊，v＊）分别是（DLP（y0））的最优值和最优解，在分支定界树的任一节点k处，考虑问题（p（k））：

证明 考虑下述线性规划（P＊）：

由引理1可知

上述定理给出了分支定界树在任一结点k处最优目标函数值下界的一个估计公式，即

根据上述公式，下面给出求解UFLP的分支定界算法：

（2）令y0＝（1，1，…，1）T，求解线性规划（LP（y0）），设最优解为x0＝，并记

（x＊，y＊）＝（x0，y0）；计算初始上界UB＝

（3）解对偶问题（DLP（y0）），设其最优目标函数值和最优解分别为z＊和（w＊，v＊）．

（4）对所有i＝1，2…，p，计算L（i）＝fi－

Step3 计算LB＝z＊＋＋如果LB≥UB，转Step5．

Step4 如果N＜p－1转Step2，否则令N＝N＋1，k＝k＋1＝＼｛N｝＝∪｛N｝＝Ø），由和可唯一确定变量y的值，设为，转Step 7．

Step8 若¯z＜UB，令（x＊，y＊）＝），UB＝，转Step9．

Step10 算法停止，此时（x＊，y＊）是问题（P）的最优解．

算法第1步为初始步，任意给定问题的一个初始可行解和目标函数的一个上界，第2步是分支，第3步和第4步是在分支节点处定出下界，并进行探测、剪枝或产生新的节点，第5步到第9步是改进上界，并进行探测、剪枝或产生新的节点．在探测过程中，如果分支定界树中没有活结点，算法将在第10步终止．

3 算例

对文献［4－5] 中的例子，假定需求点有14个城市，各个需求点的需求量已知，由于受客观条件的影响，现欲将其中的5个城市作为备选设施中心，然后再选择其中的若干个建造中心为每个需求点提供服务，并且使得总费用最低．该问题的有关数据见表1．

表1 问题对应的参数表

通过上述算法得开放的设施为1、2，各需求点被服务的情况见表2，总费用为4．405×106元．

表2 问题结果

4 结束语

本文结合实际问题研究了无容量限制的设施选址问题，该问题的模型是一个具有0－1变量的整数规划，而我们将其转化为一个混合型的0－1整数规划问题，这样可以减少分支定界树的结点个数，从而缩小了分支定界树的规模，进而降低其计算复杂性．最后通过具体算例说明了所给算法的可行性，并证明应用此方法可以有效快速地解决中小规模的选址问题，因此可进一步探讨其他更加有效地精确算法来解决实际选址问题．

［1] Kuehn A A，Hamburger M J．A heuristic program for locating warehouses［J] ．Management Science，1963，9：643－666．

［2] Shmoys D B，Tardos E，Aardal K．Approximation algorithm for facility location problems［C] ／／Proceedings of the 29th Annual ACM Symposium on Theory of Computing，1997，265－274．

［3] Jaroslay J，Lubos B．An acceleration of Erlenkotter－K rkel＇s algorithms for the uncapacitated facility location problem［J] ．Annals of Operation Research，2008，164：97－109．

［4] 张燕，胡贤满，李珍萍．重心法和模糊层次分析相结合的配送中心选址方法［J] ．物流技术，2009（10）：56－58．

［5] 鲁晓雪，李菲，丛茗，张燕，等．双配送中心选址方法［J] ．物流技术，2010（2）：29－33．