凌海峰

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

0 引言

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

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

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

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

1 UFLP問題的pseudo-Boolean 表示

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

(1)

首先定義

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

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

(2)

式中，I為單位矩陣。

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

(3)

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

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

Δ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īng)于一個(gè)排序矩陣Π，與解y對應(yīng)的運(yùn)輸成本部分可以表示為

(4)

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

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

(5)

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

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

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

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

2.1 Khumawala規(guī)則

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

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

2.2 分支準(zhǔn)則

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

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

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

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

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

根據(jù)上述分析，可得如下分支準(zhǔn)則。

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

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

2.3 算法的執(zhí)行

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

圖1 構(gòu)建Hammer函數(shù)的偽代碼Fig.1 Pseudocode for construction of Hammer function

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

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

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

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

3 在物流配送中心選址中的應(yīng)用算例

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

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

表1 物流配送中心選址問題的數(shù)據(jù)

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

用一個(gè)向量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)

與運(yùn)輸成本矩陣C對應(yīng)的一個(gè)可能的排序矩陣：

與矩陣C對應(yīng)的運(yùn)輸成本間的差異矩陣

因此，總成本中的運(yùn)輸成本

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

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

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

于是，總成本的Hammer函數(shù)為

[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)

計(jì)算δ+=max{ak}=0。由于δ+≥0,計(jì)算r+=min{k:ak=0}=1，因此，可以應(yīng)用RO規(guī)則設(shè)置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列所示。

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

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

H(y)=48-y2

(9)

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

表2 ak、tk和tk+tk的值

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

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

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

由于a2+t2=-1,可以應(yīng)用RC規(guī)則設(shè)置y2=1,從而產(chǎn)生解(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 實(shí)驗(yàn)結(jié)果

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

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

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

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

表3 OR-Library中實(shí)例的計(jì)算結(jié)果

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

5 結(jié)語

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