基于偽布爾模型和啟發(fā)式算法求解無容量設施選址問題

凌海峰

1.合肥工業(yè)大學管理學院，合肥，230009 2.過程優(yōu)化與智能決策教育部重點實驗室，合肥，230009

0 引言

無容量設施選址問題(uncapacitated facility location problem, UFLP)是組合優(yōu)化領域的著名問題之一，經典的應用包括醫(yī)療設施選址[1-2]、制造設施選址和物流設施選址等[3]。目前在智慧運輸和智慧城市中也有重要的應用，如在城市中如何放置傳感器和攝像頭來檢測交通的擁堵情況。

在UFLP問題中，存在一個設施位置的集合I={1,2,…,m}和一個客戶的集合J={1,2,…,n}，每個客戶有一個單位需求。 輸入數據包括:在位置i(i∈I)建立設施的固定成本向量F(F=(fi));從設施i到客戶j(j∈J)的運輸成本矩陣C(C=[cij])。 目標是求出一個集合P*(??P*?I), 使得滿足所有客戶需求的總成本最小?？偝杀景ń⒃O施的固定成本以及從設施位置到客戶的運輸成本。

目前，用于求解UFLP問題的算法大致可分為精確算法和智能優(yōu)化算法兩類。用于求解UFLP問題的智能優(yōu)化算法主要有遺傳算法[4-5]、模擬退火算法[6]、粒子群算法[7]、蟻群算法[8-9]等。這些算法搜索效率高，適合求解大規(guī)模問題，但容易陷入局部最優(yōu)。求解UFLP問題的精確算法主要有分支定界法[10-11]、半拉格朗日松弛法[12]等。這些算法能夠發(fā)現最優(yōu)解，但運算速度較慢，通常只適用于小規(guī)模的問題。

本文提出利用偽布爾模型和啟發(fā)式算法來求解UFLP問題。

1 UFLP問題的pseudo-Boolean 表示

P*∈argmin{f[F|C](P):??P?I}

(1)

首先定義

用向量y=(y1,y2, …,ym)表示任何解P，從而可以用pseudo-Boolean函數將式(1)表示為

y*∈argmin{f[F|C](y)|y∈{0,1}m,y≠I}

(2)

式中，I為單位矩陣。

總成本中的固定成本部分可以表示為

(3)

給定一個m×n維排序矩陣Π=[πij]，它的列向量Πj=(π1j,π2j…,πmj)T定義了一個關于1,2，…，m的排列。對于一個運輸成本矩陣C， 所有排序矩陣Π的集合表示為perm(C)，使得cπ1jj≤cπ2jj≤…≤cπmjj(j=1,2，…,n)。

給定一個運輸成本矩陣C和一個排序矩陣Π(Π∈perm(C)),對于任意j∈J，可以將運輸成本之間的差異表示為

Δc[0,j]=cπ1jj

那么, 對于任意j∈J有

min{cij|i∈P}=Δc[0,j]+Δc[1,j]yπ1j+

Δc[2,j]yπ1jyπ2j+…+Δc[m-1,j]yπ1j…yπ(m-1)j=

這樣，對應于一個排序矩陣Π，與解y對應的運輸成本部分可以表示為

(4)

根據式(3)和式(4), 對于排序矩陣Π，與實例[F|C]對應的解y的總成本可以用pseudo-Boolean多項式表示：

f[F|C],Π(y)=fF(y)+fC,Π(y)=

(5)

總成本函數f[F|C],Π(y) 對于所有的Π是相同的,稱對應于UFLP實例[F|C]和Π的pseudo-Boolean多項式為Hammer函數H[F|C](y)，即H[F|C](y)=f[F|C],Π(y)(Π∈perm(C))。

由式(5)可知，偽布爾表示法用多項式描述了與UFLP問題實例的解對應的總成本，包括實例中的固定成本和運輸成本，由pseudo-Boolean多項式容易得出在任何給定位置建立設施對于總成本的影響，這不僅有利于構建預處理規(guī)則來降低問題的規(guī)模，而且利用pseudo-Boolean多項式中的信息可以設計有效的分支準則來求解問題。

2 基于Khumawala規(guī)則和啟發(fā)式分支準則的算法

算法使用Khumawala規(guī)則作為初始階段的預處理規(guī)則，可以通過檢查與UFLP實例對應的pseudo-Boolean 多項式或Hammer函數中各決策變量的系數，在分支前確定子問題中某些變量的取值，即在當前的子問題中，確定某些設施能夠建立或不能建立。在Khumawala規(guī)則不可用時，算法根據Hammer函數中各項系數的特征來預測分支變量，從而設計出問題實例的啟發(fā)式分支準則。

2.1 Khumawala規(guī)則

對于Hammer函數Khumawala規(guī)則描述如下：設H(y)是對應于UFLP實例的Hammer函數，其中同類項已經合并。對于每一個設施k, 設ak為對應于yk的線性項的系數，tk為包含yk的所有非線性項的系數之和。那么下面兩條規(guī)則成立。

上述規(guī)則表明，如果Hammer函數中的線性項yi的系數為非負值，則在最優(yōu)解中，設施i是開放的。同樣地，如果在Hammer函數中，包含yi的所有項的系數之和是非正的，則在最優(yōu)解中，設施i是關閉的。

2.2 分支準則

對于一個|I|=m和|J|=n的UFLP實例，它的解是一個長度為m的向量y，可用 {0,1,#}表示。yj=0 (yj=1) 表示設施j開放(關閉)。yj=#表示設施j還沒有確定(開放或關閉)。含有yj=#的解稱為部分解，否則稱為完整解。

若ak<0,ak靠近0的自由變量yk比ak遠離0的自由變量yk在最優(yōu)解中為0的可能性更大。反之，ak遠離0的自由變量yk比ak靠近0的自由變量yk在最優(yōu)解中為1的可能性更大。

若ak+tk>0,ak+tk靠近0的自由變量yk比ak+tk遠離0的自由變量yk在最優(yōu)解中為1的可能性更大。反之，ak+tk遠離0的自由變量yk比ak+tk靠近0的自由變量yk在最優(yōu)解中為0的可能性更大。

若ak<0且ak+tk>0,設 |ai|=min{|ak|}以及aj+tj=min{ak+tk},ai靠近0的自由變量yi比aj+tj遠離0的自由變量yj在最優(yōu)解中為0的可能性更大。反之，aj+tj靠近0的自由變量yj比ai遠離0的自由變量yi在最優(yōu)解中為1的可能性更大。

類似地，設|ai|=max{|ak|} 以及aj+tj=max{ak+tk}, 那么，ai遠離0的自由變量yi比aj+tj靠近 0的自由變量yj在最優(yōu)解中為1的可能性更大。反之，aj+tj遠離0的自由變量yj比ai靠近0的自由變量yi在最優(yōu)解中為0的可能性更大。

根據上述分析，可得如下分支準則。

(1)最大分支準則：若r=argmax{-ak,ak+tk}, 則從自由變量集合中選擇自由變量yr作為分支變量。

(2)最小分支準則：若r=argmin{-ak,ak+tk},則從自由變量集合中選擇自由變量yr作為分支變量。

2.3 算法的執(zhí)行

首先定義HammerFunction和PartialSolution兩個過程來應用Khumawala規(guī)則。圖1中的過程HammerFunction取增廣矩陣[F|C]作為輸入，返回pseudo-Boolean多項式。圖2中的過程PartialSolution以Hammer函數為輸入，重復執(zhí)行Khumawala規(guī)則, 直到不能再應用Khumawala 規(guī)則作進一步的預處理為止。

圖1 構建Hammer函數的偽代碼Fig.1 Pseudocode for construction of Hammer function

圖2 執(zhí)行Khumawala規(guī)則的偽代碼Fig.2 Pseudocode for execution of Khumawala rule

圖2中的過程PartialSolution 返回的解一般情況下是部分解。圖3中的過程LargestBranchingVariable(最大分支準則)和SmallestBranchingVariable(最小分支準則)取預處理后的部分解為輸入, 返回最好的分支變量。

圖3 最大分支準則和最小分支準則的偽代碼Fig.3 Pseudocodes for maximum branching criterion and minimum branching criterion

使用最大分支準則(LBA)和最小分支準則(SBA)的兩種算法遞歸執(zhí)行的偽代碼見圖4。兩種算法都執(zhí)行了預處理步驟(使用了PartialSolution過程)。

3 在物流配送中心選址中的應用算例

一家制造企業(yè)在5個不同的地點進行生產，計劃建立一個或多個配送中心，用來存儲大量的原材料，然后按照要求將它們配送到生產地點。選擇4個位置作為候選的配送中心，配送中心i產生的固定成本以及從配送中心到生產地點的運輸成本數據見表1，現需要確定配送中心的位置，以使總成本最小。

圖4 兩種算法執(zhí)行的偽代碼Fig.4 Pseudocodes for execution of two algorithms

表1 物流配送中心選址問題的數據

下面以LBA算法為例，說明該算法在上述具體問題中的應用。首先建立成本矩陣：

用一個向量y=(y1,y2,y3,y4)來表示任何解P，其中

最優(yōu)解

y*∈argmin{f[F|C](y)|y∈{0,1}4,y≠I}

總成本中的固定成本

3(1-y2)+3(1-y3)+6(1-y4)

與運輸成本矩陣C對應的一個可能的排序矩陣：

與矩陣C對應的運輸成本間的差異矩陣

因此，總成本中的運輸成本

(7+3y1+1y1y2+5y1y2y4)+(7+0y3+8y3y4+

2y1y3y4)+(4+2y2+0y2y3+4y2y3y4)+(7+4y1+

1y1y2+6y1y2y4)+(8+2y4+4y1y4+8y1y3y4)

于是，總成本的Hammer函數為

[7(1-y1)+3(1-y2)+3(1-y3)+6(1-y4)]+

(7+3y1+1y1y2+5y1y2y4)+(7+0y3+8y3y4+

2y1y3y4)+(4+2y2+0y2y3+4y2y3y4)+(7+4y1+

1y1y2+6y1y2y4)+(8+2y4+4y1y4+8y1y3y4)=

52+0y1-y2-3y3-4y4+2y1y2+4y1y4+

8y3y4+11y1y2y4+10y1y3y4+4y2y3y4

(6)

計算δ+=max{ak}=0。由于δ+≥0,計算r+=min{k:ak=0}=1，因此，可以應用RO規(guī)則設置y1=0。將y1=0代入式(6)，可得

H(y)=52-y2-3y3-4y4+8y3y4+4y2y3y4

(7)

ak、tk和ak+tk的值如表2中的a列所示。

如果y3=0,代入式(7)可得

H(y)=52-y2-4y4

(8)

ak、tk和ak+tk的值如表2中的b列所示。

計算δ-=min{ak+tk}=-4。由于δ-≤0,計算r-=min{k:ak+tk=-4}=4。因此，我們應用RC規(guī)則設置y4=1。

將y4=1代入式(8)可得

H(y)=48-y2

(9)

ak、tk和ak+tk的值如表2中的c列所示。

表2 ak、tk和tk+tk的值

計算δ-=min{ak+tk}=-1。由于δ-≤0,故計算r-=min{k:ak+tk=-1}=2。由此，可應用RC規(guī)則設置y2=1。將y2=1代入式(9)，可得解(0,1,0,1)，成本H(y)=47。由于47<60,設置best=(0,1,0,1),H(best)=47。

如果y3=1,代入式(7)可得H(y)=49-y2+4y4+4y2y4。

類似地，注意到a4=4,可以應用RO規(guī)則設置y4=0。從而H(y)=49-y2。

由于a2+t2=-1,可以應用RC規(guī)則設置y2=1,從而產生解(0,1,1,0)，成本H(y)=48，由于48>H(best),故最優(yōu)解y*=(0,1,0,1)，最優(yōu)成本為H(y*)=47。即在位置1和位置3建立配送中心，最小成本為47。

4 實驗結果

本文采用OR-Library中的benchmark實例評價LBA和SBA算法的性能(http://people.brunel.ac.uk/～mastjjb/jeb/orlib/files/)。OR-Library庫中有12個中等規(guī)模的實例，其中4個實例的規(guī)模是m=16和n=50, 4個實例的規(guī)模是m=25和n=50, 其余4個實例的規(guī)模是m=n=50。

算法使用兩個不同的分支準則執(zhí)行。采用2.20 GHz的Intel i5機器，內存為4 GB。代碼使用C++語言，操作系統為Windows 7。

表3中列出了OR-Library中12個benchmark實例的計算結果，包括兩種算法計算的最優(yōu)成本。與文獻[9]中的蟻群算法(ACO)進行比較，結果表明LBA算法和SBA算法都能求出benchmark實例的最優(yōu)解。

表4為使用OR-Library中的12個bench-mark實例進一步對兩種算法性能的差異進行比較。實驗結果表明，LBA算法要優(yōu)于SBA算法的執(zhí)行效果，尤其在較大規(guī)模的問題上。如問題實例Cap131， LBA算法的運行時間要遠短于SBA算法的時間，表明LBA算法簡單高效。

表3 OR-Library中實例的計算結果

表4 LBA算法和SBA算法的性能比較

5 結語

本文在對無容量設施選址問題(UFLP)建立pseudo-Boolean模型的基礎上，提出了基于Khumawala規(guī)則和啟發(fā)式分支準則相結合的問題求解方法。從仿真實驗結果可以看出，兩種新的算法都可以發(fā)現問題的最優(yōu)解。就兩種啟發(fā)式分支準則而言，最大分支準則比最小分支準則能夠更加快速有效地解決UFLP問題。今后將進行更廣泛的測試并對該方法作適當的改進。此外，將新算法應用到其他組合優(yōu)化問題也是一個值得研究的方向。