李 翼，趙茂先，李岳佳

（山東科技大學信息科學與工程學院，山東青島266590）

設施選址問題是經(jīng)典的優(yōu)化問題，其目的是為了覆蓋一個給定的區(qū)域，并且要滿足這個區(qū)域里所有客戶的需求，從而來選擇一個或多個設施中心，這些中心包括倉庫，廠房，超市，公共設施等．每個客戶的需求可以全部由一個中心提供，也可以由多個中心來提供．一個好的選址方法可以有效的節(jié)省費用，促進生產(chǎn)和消費的協(xié)調(diào)與配合，使得設施系統(tǒng)平衡發(fā)展．本文研究的是無容量限制的設施選址問題（Uncapacitated Facility Location Problem，UFLP），也稱為簡單設施選址，指的是物流中心的容量被認為是無界的．此類問題由Kuehn和Hamburger［1]在1963年提出，Shmoys等人［2]在1997年給出了UFLP的第一個常數(shù)近似度算法，Jaroslav和Buzna［3]在2008年提出了一個改進的Erlenkotters算法，用于解決大規(guī)模的UFLP非常有效．本質(zhì)上UFLP是一個組合優(yōu)化問題，因此處理小規(guī)模的問題一般使用精確算法，例如分支定界算法等．

本文研究的無容量限制的設施選址問題的算法是基于分支定界法技術提出的．

1 UFLP模型及等價形式

總費用通常由兩部分組成．第一部分為運輸費用，指的是由配送中心到需求點運輸貨物所需的費用，記為Trans（D）其中xij∈｛0，1｝，當設施中心i向需求點j提供服務時xij＝1；否則xij＝0．

根據(jù)以上假設，UFLP模型是下述整數(shù)規(guī)劃：

約束（1）保證了每個需求點j只由一個中心提供服務；約束（2）表示任何需求點只能由開放的設施提供服務；約束（3）表示xij和yi是0－1變量．由于cij≥0，當上述規(guī)劃的變量xij的約束變?yōu)?≤xij≤1時，問題的最優(yōu)解不變．約束（2）可轉(zhuǎn)化為下述約束：

對于（4），當yi＝0時，有≤0，所以對于?j∈D，有xij＝0；當yi＝1時≤m，再由約束（1）和（3）可得到對于?j∈D，有xij≤yi．故不等式族（4）和不等式族（2）等價．因此，（UFLP）可轉(zhuǎn)化為下面等價形式：

2 分支定界算法

記x＝（xij），y＝（yi），設X是問題P的可行域，用f（·）表示問題（·）的最優(yōu)值．

定義1 如果（x，y）∈X，稱（x，y）為問題P的可行解，即為UFLP的一個可行方案．

定義2 如果（x＊，y＊）∈X，且對?（x，y）∈X，有

則稱（x＊，y＊）為問題（P）的最優(yōu)解．

引理1 考慮如下兩個線性規(guī)劃問題：

證明 線性規(guī)劃（LP1）和（LP2）的對偶問題分別為

設u1＝（w1，v1）和u2＝（w2，v2）分別是（LP1）和（LP2）的最優(yōu)對偶可行解，由上述模型得，u1＝（w1，v1）同時為（LP2）對偶問題的一個可行解，則有

設x0，y0為（P）的一個可行解，對y0建立下列線性規(guī)劃問題：

它的對偶線性問題為

其中（w，v）為具有相應維數(shù)的對偶乘子．

令k表示求解問題（P）的分支定界樹生成的第k個結(jié)點，記

定理1 設z＊和u＊＝（w＊，v＊）分別是（DLP（y0））的最優(yōu)值和最優(yōu)解，在分支定界樹的任一節(jié)點k處，考慮問題（p（k））：

證明 考慮下述線性規(guī)劃（P＊）：

由引理1可知

上述定理給出了分支定界樹在任一結(jié)點k處最優(yōu)目標函數(shù)值下界的一個估計公式，即

根據(jù)上述公式，下面給出求解UFLP的分支定界算法：

（2）令y0＝（1，1，…，1）T，求解線性規(guī)劃（LP（y0）），設最優(yōu)解為x0＝，并記

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

（3）解對偶問題（DLP（y0）），設其最優(yōu)目標函數(shù)值和最優(yōu)解分別為z＊和（w＊，v＊）．

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

Step3 計算LB＝z＊＋＋如果LB≥UB，轉(zhuǎn)Step5．

Step4 如果N＜p－1轉(zhuǎn)Step2，否則令N＝N＋1，k＝k＋1＝＼｛N｝＝∪｛N｝＝?），由和可唯一確定變量y的值，設為，轉(zhuǎn)Step 7．

Step8 若ˉz＜UB，令（x＊，y＊）＝），UB＝，轉(zhuǎn)Step9．

Step10 算法停止，此時（x＊，y＊）是問題（P）的最優(yōu)解．

算法第1步為初始步，任意給定問題的一個初始可行解和目標函數(shù)的一個上界，第2步是分支，第3步和第4步是在分支節(jié)點處定出下界，并進行探測、剪枝或產(chǎn)生新的節(jié)點，第5步到第9步是改進上界，并進行探測、剪枝或產(chǎn)生新的節(jié)點．在探測過程中，如果分支定界樹中沒有活結(jié)點，算法將在第10步終止．

3 算例

對文獻［4－5] 中的例子，假定需求點有14個城市，各個需求點的需求量已知，由于受客觀條件的影響，現(xiàn)欲將其中的5個城市作為備選設施中心，然后再選擇其中的若干個建造中心為每個需求點提供服務，并且使得總費用最低．該問題的有關數(shù)據(jù)見表1．

表1 問題對應的參數(shù)表

通過上述算法得開放的設施為1、2，各需求點被服務的情況見表2，總費用為4．405×106元．

表2 問題結(jié)果

4 結(jié)束語

本文結(jié)合實際問題研究了無容量限制的設施選址問題，該問題的模型是一個具有0－1變量的整數(shù)規(guī)劃，而我們將其轉(zhuǎn)化為一個混合型的0－1整數(shù)規(guī)劃問題，這樣可以減少分支定界樹的結(jié)點個數(shù)，從而縮小了分支定界樹的規(guī)模，進而降低其計算復雜性．最后通過具體算例說明了所給算法的可行性，并證明應用此方法可以有效快速地解決中小規(guī)模的選址問題，因此可進一步探討其他更加有效地精確算法來解決實際選址問題．

［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] 張燕，胡賢滿，李珍萍．重心法和模糊層次分析相結(jié)合的配送中心選址方法［J] ．物流技術，2009（10）：56－58．

［5] 魯曉雪，李菲，叢茗，張燕，等．雙配送中心選址方法［J] ．物流技術，2010（2）：29－33．