無容量限制設施選址問題的分支定界法

李 翼，趙茂先，李岳佳

（山東科技大學信息科學與工程學院，山東青島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．