有容量集合覆蓋選址問(wèn)題的降階回溯算法

尚春劍，寧愛(ài)兵，彭大江，張惠珍

(上海理工大學(xué) 管理學(xué)院，上海 200093)

1 引 言

集合覆蓋問(wèn)題(Location Set Covering Problem，簡(jiǎn)稱(chēng)LSCP)最早由Toregas[1]等人提出，是運(yùn)籌學(xué)領(lǐng)域中一個(gè)經(jīng)典的NP-Hard問(wèn)題[2]，除非P=NP，否則該問(wèn)題不存在多項(xiàng)式時(shí)間的精確算法.集合覆蓋問(wèn)題要求設(shè)施以最少的開(kāi)設(shè)數(shù)量來(lái)覆蓋所有需求點(diǎn)，在實(shí)際生活中有許多應(yīng)用場(chǎng)合，如設(shè)施選址、車(chē)輛調(diào)度、資源分配、電路設(shè)計(jì)、網(wǎng)絡(luò)安全等領(lǐng)域.該問(wèn)題的重要性以及應(yīng)用的廣泛性引起了學(xué)者們廣泛的關(guān)注，目前針對(duì)該類(lèi)問(wèn)題研究的算法主要分為三類(lèi)：第一類(lèi)是精確算法，主要基于branch-and-bound算法和branch-and-cut算法[3，4]，20世紀(jì)70年代，Toregas和ReVelle[5，6]提出了精確求解LSCP的行和列簡(jiǎn)化算法，這類(lèi)精確算法雖然能夠得到最優(yōu)解，但是沒(méi)有研究問(wèn)題本身的數(shù)學(xué)性質(zhì)，求解速度相對(duì)較慢.第二類(lèi)是近似算法，HOCHBAUM[7]提出了一個(gè)求解LSCP時(shí)間復(fù)雜度為O(n3)的近似算法；GROSSMAN[8]等人對(duì)9種不同的LSCP近似算法進(jìn)行了比較研究，包括幾種貪婪變量、分?jǐn)?shù)松弛、隨機(jī)化算法和神經(jīng)網(wǎng)絡(luò)算法，近似算法雖然可以在多項(xiàng)式時(shí)間內(nèi)得到一個(gè)常數(shù)近似比的解，但缺點(diǎn)是無(wú)法取得最優(yōu)解.第三類(lèi)是啟發(fā)式算法，Vasko和Wilson[9]提出了求解LSCP的啟發(fā)式算法；Alminana和Pastor[10]提出了求解LSCP改進(jìn)形式的代理啟發(fā)式算法，目前有許多學(xué)者致力于該問(wèn)題的啟發(fā)式算法的研究[11-14]，啟發(fā)式算法的求解速度相對(duì)較快，但是缺點(diǎn)是容易陷入局部最優(yōu)解.

本文將集合覆蓋問(wèn)題的模型應(yīng)用到有容量設(shè)施選址問(wèn)題中，約束條件中添加了設(shè)施容量限制和需求點(diǎn)需求量約束，其中需求點(diǎn)的需求量可以分割，即一個(gè)需求點(diǎn)可由多個(gè)設(shè)施提供服務(wù)，集合覆蓋問(wèn)題是有容量集合覆蓋問(wèn)題的一個(gè)特殊子問(wèn)題，求解有容量集合覆蓋問(wèn)題的難度大于集合覆蓋問(wèn)題，Current和Storbeck[15]研究了此類(lèi)有容量約束的LSCP.

由于每個(gè)設(shè)施的容量有限，同時(shí)要滿(mǎn)足每個(gè)需求點(diǎn)的需求量，在精確算法領(lǐng)域中，有容量約束的LSCP問(wèn)題研究難度較大，相關(guān)研究相對(duì)較少.本文針對(duì)上述現(xiàn)有算法的不足之處，首先研究有容量集合覆蓋問(wèn)題具有的數(shù)學(xué)性質(zhì)，這些數(shù)學(xué)性質(zhì)能縮小問(wèn)題規(guī)模，降低算法時(shí)間復(fù)雜度；然后利用上下界子算法對(duì)問(wèn)題剪枝，加快問(wèn)題求解速度；之后設(shè)計(jì)的分配子算法解決了傳統(tǒng)精確算法在有容量設(shè)施選址問(wèn)題中的難點(diǎn)；最后結(jié)合數(shù)學(xué)性質(zhì)、上界子算法、下界子算法、分配子算法，設(shè)計(jì)出一種能夠降低問(wèn)題規(guī)模從而加快問(wèn)題求解速度并且能求出問(wèn)題最優(yōu)解的降階回溯算法.

2 問(wèn)題描述

2.1 數(shù)學(xué)符號(hào)及解釋

以下為數(shù)學(xué)模型中涉及的數(shù)學(xué)符號(hào)：

ei：表示第i個(gè)需求點(diǎn)；

fj：表示第j個(gè)設(shè)施；

m：表示需求點(diǎn)的個(gè)數(shù)；

n：表示設(shè)施的個(gè)數(shù)；

E={ei|i=1，2，…，m}：表示所有需求點(diǎn)的集合；

F={fj|j=1，2，…，n}：表示設(shè)施的集合；

di：表示第i個(gè)需求點(diǎn)的需求量；

cj：表示第j個(gè)設(shè)施的容量；

xj∈{0，1}：若設(shè)施fj開(kāi)設(shè)，則xj=1，否則xj=0；

yi，j：表示需求點(diǎn)ei的需求中被分配給設(shè)施fj的部分；

A(j)：表示第j個(gè)設(shè)施fj可服務(wù)的需求點(diǎn)集合；

B(i)：表示可以覆蓋第i個(gè)需求點(diǎn)ei的設(shè)施集合。

以下為后文設(shè)計(jì)的算法中涉及的數(shù)學(xué)符號(hào)：

aj：若設(shè)施fj的容量有剩余，即rj> 0，則aj=1，否則aj=0；

gi：若需求點(diǎn)ei的需求量完全滿(mǎn)足，即ki=0，則gi=1，否則gi=0；

deg(ei)：表示需求點(diǎn)ei的度，即需求點(diǎn)ei可被deg(ei)個(gè)設(shè)施服務(wù)；

deg(fj)：表示設(shè)施fj的度，即設(shè)施fj可服務(wù)deg(fj)個(gè)需求點(diǎn)；

N(vi)：表示二分圖G中頂點(diǎn)vi的鄰點(diǎn)集；

b：算法在某一狀態(tài)下的目標(biāo)函數(shù)值下界，為局部變量；

u：算法在某一狀態(tài)下的目標(biāo)函數(shù)值上界，為全局變量；

F1：一定開(kāi)設(shè)的設(shè)施集合，若F1中任一設(shè)施不開(kāi)設(shè)則不能取得最優(yōu)解，為全局變量；

F0：一定不開(kāi)設(shè)的設(shè)施集合，若F0中任一設(shè)施開(kāi)設(shè)則不能取得最優(yōu)解，為全局變量；

F5=FF1F0：暫時(shí)未確定是否開(kāi)設(shè)的設(shè)施集合，為全局變量；

Ftemp：后文算法中將某些設(shè)施臨時(shí)放入集合Ftemp中，為局部變量；

FF1：F5中的設(shè)施在回溯算法分情況時(shí)假設(shè)開(kāi)設(shè)的設(shè)施放入集合FF1中，為全局變量；

FF0：F5中的設(shè)施在回溯算法分情況時(shí)假設(shè)不開(kāi)設(shè)的設(shè)施放入集合FF0中，為全局變量；

FF5=F5FF1FF0：回溯算法分情況時(shí)暫時(shí)未處理的設(shè)施放入集合FF5中，為全局變量；

Fbest：算法在當(dāng)前狀態(tài)下已知最好的目標(biāo)函數(shù)值對(duì)應(yīng)的開(kāi)設(shè)設(shè)施集合，為全局變量；

best_q：回溯算法在當(dāng)前狀態(tài)下已知最好的目標(biāo)函數(shù)值，best_q= |Fbest|，為全局變量；

cur_n：當(dāng)前累計(jì)開(kāi)設(shè)設(shè)施數(shù)，為局部變量；

cur_i：回溯算法的當(dāng)前搜索層數(shù)，為局部變量。

2.2 數(shù)學(xué)模型

本文用二分圖表示有容量集合覆蓋問(wèn)題：將E和F中的元素分別作為二分圖的兩個(gè)頂點(diǎn)子集E和F，若E中的ei可輻射F中的fj或F中的fj可輻射E中的ei，即ei與fj之間存在路徑，則將ei與fj連線(xiàn)，否則不連線(xiàn)，將所有路徑放入集合X中.處理后得到一個(gè)圖G= (V，X)，其中V=E∪F，顯然圖G是一個(gè)二分圖.

該有容量集合覆蓋選址問(wèn)題的具體模型如下[11]：

(1)

目標(biāo)函數(shù)(1)表示在滿(mǎn)足全部約束條件下，最小化開(kāi)設(shè)設(shè)施的數(shù)量；約束(2)表示對(duì)于任意一個(gè)需求點(diǎn)ei的全部需求均被完全滿(mǎn)足；約束(3)表示開(kāi)設(shè)的設(shè)施所服務(wù)的需求點(diǎn)的需求量總和不能超過(guò)所開(kāi)設(shè)設(shè)施本身的容量；約束(4)表示設(shè)施是否開(kāi)設(shè)的決策變量xj取值為0或1，xj=0表示設(shè)施fj不開(kāi)設(shè)，xj=1表示設(shè)施fj開(kāi)設(shè)；約束(5)中yi，j表示需求點(diǎn)ei的需求中被分配給設(shè)施fj的部分，取值為di與cj的最小值.該問(wèn)題已證明是NP-Hard問(wèn)題[2]，除非P=NP，否則該問(wèn)題不存在多項(xiàng)式時(shí)間的精確算法.

3 數(shù)學(xué)性質(zhì)及子算法設(shè)計(jì)

3.1 數(shù)學(xué)性質(zhì)

性質(zhì)1.若圖G是非連通圖，則可對(duì)圖G的連通分量分別看作單獨(dú)的子問(wèn)題，分別進(jìn)行求解.

證明：由于子問(wèn)題之間不存在通路，求解時(shí)相互獨(dú)立，互不影響，因此可以分別求解.

性質(zhì)2.對(duì)于每個(gè)設(shè)施的容量rj和需求點(diǎn)的需求量ki，若全體rj和ki之間存在公約數(shù)，則可將當(dāng)前問(wèn)題中的容量和需求量同時(shí)約去該公約數(shù)，降低了問(wèn)題求解過(guò)程中計(jì)算的復(fù)雜程度.

證明：由于對(duì)設(shè)施的容量和需求點(diǎn)的需求量同時(shí)進(jìn)行約分，對(duì)于某個(gè)設(shè)施服務(wù)某個(gè)需求點(diǎn)的能力不產(chǎn)生影響，問(wèn)題轉(zhuǎn)化為其等價(jià)問(wèn)題，數(shù)值更小便于求解.

證明：因?yàn)閒j在圖G中所起到的覆蓋作用完全可以由fh來(lái)代替，并且fh的剩余容量能滿(mǎn)足N(fh)中所有需求點(diǎn)的需求量.

證明：反證法，由于滿(mǎn)足該x個(gè)需求點(diǎn)的設(shè)施總?cè)萘壳『玫扔趚個(gè)需求點(diǎn)的總需求量，若覆蓋x個(gè)需求點(diǎn)的設(shè)施中有設(shè)施未開(kāi)設(shè)，則這x個(gè)需求點(diǎn)的需求量不能完全被滿(mǎn)足，因此fj∈B(i)的設(shè)施均開(kāi)設(shè)，且服務(wù)于這x個(gè)需求點(diǎn).

性質(zhì)7.對(duì)于任意一個(gè)已確定開(kāi)設(shè)的設(shè)施fj，且rj≥∑ei∈A(j)ki，則ei∈A(j)的需求點(diǎn)均由設(shè)施fj服務(wù).

證明：由于目標(biāo)函數(shù)是最小化開(kāi)設(shè)設(shè)施數(shù)，fj開(kāi)設(shè)且剩余容量大于等于其所覆蓋的需求點(diǎn)的需求量之和，則ei∈A(j)的需求點(diǎn)均由設(shè)施fj服務(wù)使得該資源盡量更多的被利用，若其中有需求點(diǎn)不由設(shè)施fj服務(wù)，則浪費(fèi)設(shè)施fj的容量而造成要占用其他設(shè)施的容量.

性質(zhì)8.若需求點(diǎn)ei滿(mǎn)足deg(ei)=1，則ei對(duì)應(yīng)的B(i)中唯一的設(shè)施fj一定開(kāi)設(shè)，放入F1中，且服務(wù)ei.

證明：由于問(wèn)題要求全覆蓋，因此需求點(diǎn)ei必須被服務(wù)，若需求點(diǎn)ei只能被一個(gè)設(shè)施fj服務(wù)，則設(shè)施fj一定開(kāi)設(shè)且為需求點(diǎn)ei提供服務(wù).

性質(zhì)9.在問(wèn)題以及在問(wèn)題處理過(guò)程中出現(xiàn)的子問(wèn)題中，若對(duì)于任意一個(gè)已確定開(kāi)設(shè)的設(shè)施fj，滿(mǎn)足aj=1且deg(fj)=1，則fj一定服務(wù)于其當(dāng)前對(duì)應(yīng)的A(j)中唯一的需求點(diǎn)ei.

證明：由于設(shè)施fj已開(kāi)設(shè)且有剩余容量，目標(biāo)函數(shù)要求開(kāi)設(shè)的設(shè)施數(shù)量最少，則設(shè)施fj剩余的容量應(yīng)當(dāng)服務(wù)于當(dāng)前對(duì)應(yīng)的A(j)中唯一的需求點(diǎn)ei，否則會(huì)浪費(fèi)設(shè)施fj剩余的容量.

性質(zhì)10.在假設(shè)某設(shè)施fj開(kāi)設(shè)的情況下，此時(shí)若下界b大于之前的上界u，則設(shè)施fj一定不開(kāi)設(shè)，其中上下界求解算法詳見(jiàn)3.3和4.4.

證明：新的下界大于之前的上界，說(shuō)明設(shè)施fj開(kāi)設(shè)則不可能獲得最優(yōu)解，因此應(yīng)關(guān)閉設(shè)施fj.

性質(zhì)11.在假設(shè)某設(shè)施fj不開(kāi)設(shè)的情況下，此時(shí)若下界b大于之前的上界u，則設(shè)施fj一定開(kāi)設(shè).

證明：新的下界大于之前的上界，說(shuō)明設(shè)施fj關(guān)閉不可能獲得最優(yōu)解，因此應(yīng)開(kāi)設(shè)設(shè)施fj.

性質(zhì)12.在假設(shè)某設(shè)施fj不開(kāi)設(shè)的情況下，若FF5中所有設(shè)施均開(kāi)設(shè)，但分配子算法無(wú)解，則設(shè)施fj一定開(kāi)設(shè).

證明：若設(shè)施fj不開(kāi)設(shè)，則該問(wèn)題無(wú)解，因此設(shè)施fj一定開(kāi)設(shè).

性質(zhì)13.算法執(zhí)行過(guò)程中，若ki=0，則刪除對(duì)應(yīng)的需求點(diǎn)ei及其鄰接邊，更新圖G；若rj=0，則刪除對(duì)應(yīng)的設(shè)施點(diǎn)fj及其鄰接邊，更新圖G.

證明：顯然，當(dāng)需求點(diǎn)ei完全被滿(mǎn)足就可以刪除；同樣，當(dāng)設(shè)施點(diǎn)fj剩余容量為零時(shí)也可以刪除.

3.2 分配子算法

在集合覆蓋選址問(wèn)題中，首先要從許多候選設(shè)施點(diǎn)中選取開(kāi)設(shè)的設(shè)施，然后將需求點(diǎn)分配到所選取的設(shè)施上，經(jīng)典的集合覆蓋問(wèn)題選址中，需求點(diǎn)的不同分配順序不影響目標(biāo)函數(shù)值，而本文研究的有容量集合覆蓋選址問(wèn)題，由于設(shè)施和需求點(diǎn)都有容量的限制，因此每個(gè)需求點(diǎn)的不同分配順序會(huì)使得所得到的目標(biāo)函數(shù)值不同.于是在算法設(shè)計(jì)中，有容量集合覆蓋選址問(wèn)題不僅有設(shè)施的選擇過(guò)程，還有分配過(guò)程.

對(duì)于本文研究的問(wèn)題，在開(kāi)設(shè)設(shè)施已定的情況下，只要通過(guò)合理分配方法在多項(xiàng)式時(shí)間內(nèi)找到一個(gè)可行解即可.本文通過(guò)下面的分配子算法對(duì)需求點(diǎn)進(jìn)行分配，該子算法的具體內(nèi)容如下：

Step 1.初始化所有需求點(diǎn)，令所有g(shù)i=0；

Step 2.根據(jù)性質(zhì)4判斷開(kāi)設(shè)的設(shè)施集合是否不可行，若不可行，則該問(wèn)題無(wú)解，分配子算法結(jié)束，否則執(zhí)行下一步；

Step 3.判斷問(wèn)題是否滿(mǎn)足數(shù)學(xué)性質(zhì)5，此時(shí)得到一個(gè)解，不需要執(zhí)行分配子算法的后面步驟，將所有需求點(diǎn)標(biāo)記gi=1，則已全部得到滿(mǎn)足的需求點(diǎn)個(gè)數(shù)dis=m，分配子算法結(jié)束；若不滿(mǎn)足數(shù)學(xué)性質(zhì)5，執(zhí)行下一步；

Step 4.將需求點(diǎn)和設(shè)施分別按照其度的大小升序排列標(biāo)號(hào)，即度越小的結(jié)點(diǎn)越先處理.將滿(mǎn)足數(shù)學(xué)性質(zhì)7的需求點(diǎn)標(biāo)記為gi=1，若dis=m，分配子算法結(jié)束；若dis

Step 5.下面的分配采用求最大流的算法進(jìn)行分配，具體操作步驟如下：設(shè)立一個(gè)超級(jí)源點(diǎn)和超級(jí)匯點(diǎn)，將超級(jí)源點(diǎn)連向所有的需求點(diǎn)，每條邊的流量為所連需求點(diǎn)的需求量；將所有設(shè)施連向超級(jí)匯點(diǎn)，每條邊的流量為設(shè)施的容量.當(dāng)ei∈A(j)時(shí)，將需求點(diǎn)ei連接到設(shè)施fj，并將該邊的容量設(shè)為min{di，cj}.然后按照最大流算法求解：計(jì)算從超級(jí)源點(diǎn)到超級(jí)匯點(diǎn)的最大流[15]，將超級(jí)源點(diǎn)到需求點(diǎn)的弧是飽和弧的需求點(diǎn)標(biāo)記為gi=1，若已全部得到滿(mǎn)足的需求點(diǎn)個(gè)數(shù)dis=m，此時(shí)分配可行，分配子算法結(jié)束；若dis

證明：當(dāng)問(wèn)題所開(kāi)設(shè)設(shè)施確定之后，問(wèn)題的關(guān)鍵在于在多項(xiàng)式時(shí)間內(nèi)怎樣把已開(kāi)設(shè)設(shè)施的容量合理地分配到所有需求點(diǎn)且使所有需求點(diǎn)的容量得到滿(mǎn)足.分配子算法中用到的數(shù)學(xué)性質(zhì)已經(jīng)在前文證明過(guò)，若最大流中的超級(jí)源點(diǎn)到所有的需求點(diǎn)都是飽和弧，由最大流算法可知，每一個(gè)需求點(diǎn)的需求量都能得到滿(mǎn)足；若最大流中的超級(jí)源點(diǎn)到某一個(gè)需求點(diǎn)不是飽和弧，由最大流算法可知，至少有一個(gè)需求點(diǎn)的需求量不能得到滿(mǎn)足，因此此時(shí)不存在可行解.由文獻(xiàn)[15-21]可知，最大流問(wèn)題能在多項(xiàng)式時(shí)間內(nèi)解決，其中文獻(xiàn)[15]中的最大流算法時(shí)間復(fù)雜度為O(mnlog(n2/ m))，因此該分配子算法可以在多項(xiàng)式時(shí)間內(nèi)結(jié)束.

3.3 下界子算法

本文設(shè)計(jì)的下界子算法的具體步驟如下：

Step 1.初始化b=|F1|，F(xiàn)temp={ }，計(jì)算開(kāi)設(shè)的設(shè)施容量之和∑fj∈F1∪Ftemprj；

Step 3.在圖G中，將設(shè)施按照其容量降序排列，開(kāi)設(shè)容量最大的設(shè)施fj放入設(shè)施集合Ftemp中，跳到Step 2.

證明：該算法選出的設(shè)施集合Ftemp中任一設(shè)施的容量都大于等于未選中設(shè)施的容量，若選出的開(kāi)設(shè)的設(shè)施個(gè)數(shù)小于|Ftemp|，那么此時(shí)開(kāi)設(shè)設(shè)施的容量之和一定小于所有需求點(diǎn)的需求量之和，所以此時(shí)沒(méi)有可行解，因此開(kāi)設(shè)的設(shè)施數(shù)一定大于等于|F1∪Ftemp|.

3.4 上界子算法

事實(shí)上，任何一個(gè)可行解對(duì)應(yīng)的目標(biāo)函數(shù)值均能作為該問(wèn)題的上界.本文先利用前面所介紹的數(shù)學(xué)性質(zhì)，將問(wèn)題進(jìn)行降階處理，之后執(zhí)行如下的上界子算法求出上界：

將所有需求點(diǎn)按照其需求量降序排列，將設(shè)施按照其容量降序排列；依次針對(duì)每個(gè)需求點(diǎn)ei，檢查ei的鄰接結(jié)點(diǎn)N(ei)是否存在已開(kāi)設(shè)的設(shè)施，若存在，則N(ei)中開(kāi)設(shè)的設(shè)施為ei服務(wù)，若不存在，選取ei鄰接結(jié)點(diǎn)中容量最大的設(shè)施開(kāi)設(shè)并服務(wù)需求點(diǎn)ei，直到需求點(diǎn)ei的需求量完全被滿(mǎn)足，每個(gè)需求點(diǎn)的需求量均被滿(mǎn)足，算法結(jié)束.

Step 1.初始化Ftemp={ }，i=1，將所有需求點(diǎn)按照其需求量降序排列，將設(shè)施按照其容量降序排列；

Step 2.若ki>0，則分以下三種情況處理：

情況1：若N(ei)中不存在開(kāi)設(shè)的設(shè)施，此時(shí)按照下面步驟處理：

1)若N(ei)中的設(shè)施剩余容量之和大于等于ei的剩余需求量，則選取N(ei)中剩余容量最大的設(shè)施fmax開(kāi)設(shè)并為ei提供服務(wù)，F(xiàn)temp=Ftemp∪{fmax}；若N(ei)中的設(shè)施剩余容量之和小于ei的剩余需求量，則本次分配不可行，令上界u=+∞，結(jié)束上界子算法；

2)若fmax的剩余容量大于等于ei的剩余需求量，那么此時(shí)ei的所有需求都能得到滿(mǎn)足，情況1的處理結(jié)束；

3)若fmax的剩余容量小于ei的剩余需求量，那么此時(shí)ei的部分需求不能得到滿(mǎn)足，跳到情況1的步驟(1).

情況2：若N(ei)中存在開(kāi)設(shè)的設(shè)施且N(ei)中開(kāi)設(shè)的設(shè)施剩余容量之和大于等于ei的剩余需求量，此時(shí)按照下面步驟處理：

1)選取N(ei)中已開(kāi)設(shè)且剩余容量最大的設(shè)施fmax為ei提供服務(wù)，F(xiàn)temp=Ftemp∪{fmax}；

2)若fmax的剩余容量大于等于ei的剩余需求量，那么此時(shí)ei的所有需求都能得到滿(mǎn)足，情況2的處理結(jié)束；

3)若fmax的剩余容量小于ei的剩余需求量，那么此時(shí)ei的部分需求不能得到滿(mǎn)足，跳到情況2的步驟(1)；

情況3：若N(ei)中存在開(kāi)設(shè)的設(shè)施且N(ei)中開(kāi)設(shè)的設(shè)施剩余容量之和小于ei的剩余需求量，此時(shí)N(ei)中已開(kāi)設(shè)設(shè)施的全部剩余容量為ei提供服務(wù)，(Ftemp=Ftemp∪{fj}(fj∈N(ei)且xj=1)，把N(ei)中已開(kāi)設(shè)的設(shè)施移除，然后跳到情況1處理.

Setp 3.若ki= 0，i=i+1；

Step 4.若i>m或F5=?，輸出開(kāi)設(shè)設(shè)施數(shù)|F1∪Ftemp|作為上界u，本上界子算法結(jié)束；否則跳到Step 2.

證明：若本子算法求出的解是可行解，那么最優(yōu)解肯定小于等于可行解對(duì)應(yīng)的目標(biāo)函數(shù)值；若本子算法全部設(shè)施開(kāi)設(shè)都不能滿(mǎn)足需求點(diǎn)的需求，此時(shí)u=+∞，可以作為目標(biāo)函數(shù)的上界.

4 降階回溯算法

降階回溯算法包括降階算法和回溯算法兩個(gè)部分，降階算法通過(guò)結(jié)合前文介紹的數(shù)學(xué)性質(zhì)對(duì)問(wèn)題進(jìn)行降階，從而縮小問(wèn)題的規(guī)模，降低求解的難度；回溯算法采用深度優(yōu)先的方法搜索問(wèn)題的解空間，從根結(jié)點(diǎn)出發(fā)，對(duì)每一個(gè)結(jié)點(diǎn)判斷該情況下其理論下界b是否小于上界u，若滿(mǎn)足則繼續(xù)向下深度優(yōu)先搜索，否則進(jìn)行剪枝，逐級(jí)向上回溯.

4.1 降階子算法

降階算法步驟如下：

Step 1.初始化cur_i=1，cur_n=0，best_q=+∞，u=0，F(xiàn)1=F0={ }，F(xiàn)5=F={fj|j=1，2，…，n}；

Step 2.根據(jù)3.1介紹的數(shù)學(xué)性質(zhì)確定一定開(kāi)設(shè)和一定不開(kāi)設(shè)的設(shè)施，對(duì)問(wèn)題進(jìn)行降階處理，若某設(shè)施fj一定開(kāi)設(shè)，則F1=F1∪{fj}，F(xiàn)5=F5(〗fj}；若某個(gè)設(shè)施fj一定不開(kāi)設(shè)，則F0=F0∪{fj}，F(xiàn)5=F5{fj}，更新圖G；

Step 3.根據(jù)3.4的上界子算法計(jì)算問(wèn)題上界u；

Step 4.對(duì)F5中的每一個(gè)設(shè)施fj，若滿(mǎn)足性質(zhì)10，即當(dāng)fj開(kāi)設(shè)時(shí)有下界b>u，則fj一定不開(kāi)設(shè)，令F0=F0∪{fj}，F(xiàn)5=F5(〗fj}；若滿(mǎn)足性質(zhì)11，即當(dāng)fj不開(kāi)設(shè)時(shí)有下界b>u，則fj一定開(kāi)設(shè)，令F1=F1∪{fj}，F(xiàn)5=F5(〗fj}.

4.2 回溯子算法

執(zhí)行4.1介紹的降階算法對(duì)問(wèn)題規(guī)模進(jìn)行降階處理后，調(diào)用下面的回溯子算法backtrack(1).回溯算法對(duì)設(shè)施集合FF5=F5中的每一個(gè)設(shè)施分為以下2種情況進(jìn)行處理：

1)若設(shè)施fj開(kāi)設(shè)，并搜索對(duì)應(yīng)的左子樹(shù)；

2)若設(shè)施fj不開(kāi)設(shè)，搜索對(duì)應(yīng)的右子樹(shù).

回溯子算法backtrack(cur_i)的詳細(xì)步驟如下：

Step 1.初始化cur_i=1，cur_n=0，best_q=+∞，u=0，F(xiàn)F1=FF0={}，F(xiàn)F5=F5；

Step 2.當(dāng)cur_i>|FF5|或|FF5|=0，說(shuō)明搜索到達(dá)葉子結(jié)點(diǎn)，此時(shí)調(diào)用分配子算法，對(duì)需求點(diǎn)進(jìn)行分配，此時(shí)若dis=m，則得到一個(gè)可行解.若對(duì)應(yīng)目標(biāo)函數(shù)值Q

Step 3.情況1：開(kāi)設(shè)設(shè)施fcur_i，在此情況下計(jì)算下界b，若b≤best_q，表明此時(shí)可以開(kāi)設(shè)設(shè)施fcur_i，令FF1=FF1∪{fcur_i}，F(xiàn)F5=FF5(〗fcur_i}，調(diào)用數(shù)學(xué)性質(zhì)，確定此時(shí)一定不開(kāi)設(shè)的設(shè)施集合為FF1_temp0，確定此時(shí)一定開(kāi)設(shè)的設(shè)施集合為FF1_temp1，令FF1=FF1∪FF1_temp1，F(xiàn)F0=FF0∪FF1_temp0，F(xiàn)F5=FF5(FF1_temp1∪FF1_temp0)，調(diào)用backtrack(cur_i+1)進(jìn)入左子樹(shù)搜索；若b>best_q，則說(shuō)明若開(kāi)設(shè)設(shè)施fcur_i則不能取得最優(yōu)解，此時(shí)左子樹(shù)剪枝，跳到Step 5；

Step 4.算法跳到搜索樹(shù)的上一層之前，恢復(fù)FF1和FF5到Step 3的初始狀態(tài)，F(xiàn)F1=FF1({fcur_i}∪FF1_temp1)，F(xiàn)F5=FF5∪({fcur_i}∪FF1_temp1∪FF1_temp0)，F(xiàn)F0=FF0FF1_temp0；

Step 5.情況2：不開(kāi)設(shè)設(shè)施fcur_i，在此情況下計(jì)算下界b，若b≤best_q，則說(shuō)明不開(kāi)設(shè)fcur_i可能取得最優(yōu)解，令FF0=FF0∪{fcur_i}，F(xiàn)F5=FF5(〗fcur_i}，調(diào)用數(shù)學(xué)性質(zhì)，確定此時(shí)一定不開(kāi)設(shè)的設(shè)施集合為FF0_temp0，確定此時(shí)一定開(kāi)設(shè)的設(shè)施集合為FF0_temp1，令FF1=FF1∪FF0_temp1，F(xiàn)F0=FF0∪FF0_temp0，F(xiàn)F5=FF5(FF0_temp1∪FF0_temp0)，調(diào)用backtrack(cur_i+1)進(jìn)入右子樹(shù)搜索；若b>best_q，說(shuō)明不開(kāi)設(shè)設(shè)施fcur_i則不可能取得最優(yōu)解，則結(jié)束該回溯子程序，此時(shí)右子樹(shù)剪枝；

Step 6.算法跳到搜索樹(shù)的上一層之前，恢復(fù)FF0和FF5到Step 5的初始狀態(tài)，F(xiàn)F0=FF0({fcur_i}∪FF0_temp0)，F(xiàn)F5=FF5∪({fcur_i}∪FF0_temp1∪FF0_temp0)，F(xiàn)F1=FF1FF0_temp1.

算法結(jié)束后，當(dāng)前的最優(yōu)目標(biāo)函數(shù)值best_q和對(duì)應(yīng)開(kāi)設(shè)的設(shè)施Fbest就是整個(gè)問(wèn)題的一個(gè)最優(yōu)解.

4.3 主算法

有了前面的子算法，就可以執(zhí)行下面的主算法：

Step 1.先調(diào)用降階子算法；

Step 2.調(diào)用上下界子算法，計(jì)算問(wèn)題的上界u和下界b；

Step 3.調(diào)用回溯子算法backtrack(1).

4.4 算法時(shí)間復(fù)雜度與對(duì)比分析

本文研究的集合覆蓋選址問(wèn)題規(guī)模即設(shè)施個(gè)數(shù)為n，該算法在搜索空間中最多產(chǎn)生2n個(gè)葉子結(jié)點(diǎn)，在降階算法被調(diào)用后，問(wèn)題規(guī)模減少為|F5|，令k=|F5|，因此算法在最壞情況下的時(shí)間復(fù)雜度為O(2k)，k≤n.

許多學(xué)者提出不同算法針對(duì)集合覆蓋選址問(wèn)題進(jìn)行求解[22]，這些算法主要分為精確算法、近似算法和啟發(fā)式算法.近似算法與啟發(fā)式算法的優(yōu)點(diǎn)在于求解速度快，但是一般無(wú)法得到問(wèn)題的最優(yōu)解，不能保證解的質(zhì)量.本文設(shè)計(jì)的精確算法，首先保證了所求的解為最優(yōu)解；其次，相對(duì)于其他一般的精確算法而言，本文通過(guò)研究問(wèn)題的數(shù)學(xué)性質(zhì)，這些數(shù)學(xué)性質(zhì)能對(duì)問(wèn)題進(jìn)行降階，降低了問(wèn)題規(guī)模，設(shè)計(jì)的上下界算法對(duì)搜索樹(shù)進(jìn)行合理剪枝，縮小了問(wèn)題的解空間，只對(duì)部分解子樹(shù)搜索，使得時(shí)間復(fù)雜度由O(2n)降低為O(2k)，其中k=|F5|且k≤n.

5 示例分析

為了更清晰的說(shuō)明本文算法，下面給出一個(gè)示例對(duì)算法執(zhí)行的整個(gè)過(guò)程進(jìn)行說(shuō)明.

示例1:如圖1所示，現(xiàn)有6個(gè)需求點(diǎn)ei，7個(gè)設(shè)施fj，若設(shè)施fj能為需求點(diǎn)ei提供服務(wù)，則用實(shí)線(xiàn)連接.現(xiàn)從中選出若干個(gè)設(shè)施服務(wù)于需求點(diǎn)，使得每個(gè)需求點(diǎn)的需求量均得到滿(mǎn)足，求所選取設(shè)施個(gè)數(shù)的最小值Q.

對(duì)示例1的分析過(guò)程可描述如下：

圖1 設(shè)施服務(wù)需求點(diǎn)服務(wù)二分圖Fig.1 Bipartite graph of facility service demand point service

經(jīng)過(guò)分析，圖1為非連通圖，根據(jù)性質(zhì)1，可將示例1分成兩個(gè)單獨(dú)的子問(wèn)題分別進(jìn)行求解.{j1、j6、i1、i6}可構(gòu)成子問(wèn)題1，{j2、j3、j4、j5、j7、i2、i3、i4、i5}可構(gòu)成子問(wèn)題2，問(wèn)題分解后如圖2所示.

圖2 問(wèn)題分解后二分圖Fig.2 Bipartite graph after problem decomposition

1)對(duì)于子問(wèn)題1，n1=2：經(jīng)判斷，子問(wèn)題1不滿(mǎn)足性質(zhì)4；根據(jù)性質(zhì)3，j1、j6有N(v6)?N(v1)且c1≥(d1+d6)，則將設(shè)施j6及其關(guān)聯(lián)邊從圖中刪除，即設(shè)施j6關(guān)閉；根據(jù)性質(zhì)8，設(shè)施j1開(kāi)設(shè)，為需求點(diǎn)j1提供2個(gè)需求，為需求點(diǎn)j6提供3個(gè)需求.將設(shè)施j1標(biāo)記a1=1，需求點(diǎn)i1、i6標(biāo)記g1=1，g6=1，則子問(wèn)題1中有dis=n1=2.

2)對(duì)于子問(wèn)題2，n2=5：經(jīng)判斷，子問(wèn)題2不滿(mǎn)足性質(zhì)4；子問(wèn)題2中{j2、j3、j4、j5、j7、i2、i3、i4、i5}的容量或需求量存在公約數(shù)3，根據(jù)性質(zhì)2，可將當(dāng)前問(wèn)題中的容量和需求量同時(shí)約去3；根據(jù)性質(zhì)8，設(shè)施j5開(kāi)設(shè)，標(biāo)記a5=1，為需求點(diǎn)i5提供1個(gè)需求，將需求點(diǎn)i5標(biāo)記g5=1；根據(jù)性質(zhì)9，設(shè)施j5為需求點(diǎn)i4提供1個(gè)需求，需求點(diǎn)i4剩余需求量k4=2.

3)問(wèn)題經(jīng)過(guò)降階處理后，更新問(wèn)題規(guī)模如圖3所示.

4)執(zhí)行回溯算法，執(zhí)行過(guò)程如圖4所示的二叉樹(shù).

① 在搜索過(guò)程中，從根結(jié)點(diǎn)0出發(fā)，計(jì)算該結(jié)點(diǎn)下界b=5，上界u=6.假設(shè)j2開(kāi)設(shè)，進(jìn)入左子樹(shù)，該結(jié)點(diǎn)下界b=5，小于上界u=6，因此假設(shè)j3開(kāi)設(shè)，進(jìn)入左子樹(shù)，該結(jié)點(diǎn)下界b=5，上界u=6，因此假設(shè)j4開(kāi)設(shè)，該結(jié)點(diǎn)下界b=5，上界u=6，因此假設(shè)j7開(kāi)設(shè)，到達(dá)結(jié)點(diǎn)1.調(diào)用分配子算法，結(jié)點(diǎn)1處x2=1，x3=1，x4=1，x7=1構(gòu)成可行解，此時(shí)目標(biāo)函數(shù)值為6；

圖3 問(wèn)題降階處理后二分圖Fig.3 Bipartite graph after problem reduction

② 結(jié)點(diǎn)1搜索完成，回溯到上一層.假設(shè)設(shè)施j7不開(kāi)設(shè)，進(jìn)入右子樹(shù)，到達(dá)結(jié)點(diǎn)2.根據(jù)數(shù)學(xué)性質(zhì)4，結(jié)點(diǎn)2處x2=1，x3=1，x4=1，x7=0，不能構(gòu)成可行解；

圖4 解空間二叉樹(shù)Fig.4 Solution space binary tree

③ 結(jié)點(diǎn)2搜索完成，回溯到上一層.假設(shè)設(shè)施j4不開(kāi)設(shè)，進(jìn)入右子樹(shù)，假設(shè)設(shè)施j7開(kāi)設(shè)，到達(dá)結(jié)點(diǎn)3.調(diào)用分配子算法，結(jié)點(diǎn)3處x2=1，x3=1，x4=0，x7=1構(gòu)成可行解，此時(shí)目標(biāo)函數(shù)值為5；

④ 結(jié)點(diǎn)3搜索完成，回溯到上一層.假設(shè)設(shè)施j7不開(kāi)設(shè)，進(jìn)入右子樹(shù)，到達(dá)結(jié)點(diǎn)4，根據(jù)數(shù)學(xué)性質(zhì)4，結(jié)點(diǎn)4處x2=1，x3=1，x4=0，x7=0，不能構(gòu)成可行解；

⑤ 結(jié)點(diǎn)4搜索完成，回溯到上一層.假設(shè)設(shè)施j3不開(kāi)設(shè)，進(jìn)入右子樹(shù)，到達(dá)結(jié)點(diǎn)5，根據(jù)數(shù)學(xué)性質(zhì)4，j2不開(kāi)設(shè)時(shí)不能構(gòu)成可行解，于是剪枝，結(jié)點(diǎn)5以下的子樹(shù)不再搜索；

⑥ 結(jié)點(diǎn)5搜索完成，回溯到上一層.假設(shè)設(shè)施j2不開(kāi)設(shè)，進(jìn)入右子樹(shù)，到達(dá)結(jié)點(diǎn)6，根據(jù)數(shù)學(xué)性質(zhì)4，j2不開(kāi)設(shè)時(shí)不能構(gòu)成可行解，于是剪枝，結(jié)點(diǎn)6以下的子樹(shù)不再搜索.

通過(guò)上述算法得到該問(wèn)題的最優(yōu)解集Fbest={j1，j2，j3，j5，j7}，最優(yōu)目標(biāo)函數(shù)值Q=5，F(xiàn)best={j1，j2，j3，j5，j7}其中一個(gè)可行的分配如下：j1為需求點(diǎn)i1提供2個(gè)需求，為需求點(diǎn)i6提供3個(gè)需求；j2為需求點(diǎn)i2提供6個(gè)需求，為需求點(diǎn)i4提供3個(gè)需求；j3為需求點(diǎn)i3提供6個(gè)需求，為需求點(diǎn)i4提供3個(gè)需求；j5為需求點(diǎn)i4提供3個(gè)需求，為需求點(diǎn)i5提供3個(gè)需求；j7為需求點(diǎn)i3提供6個(gè)需求，算法結(jié)束.從這個(gè)例子可以清楚地看到，數(shù)學(xué)性質(zhì)能降低問(wèn)題的規(guī)模，上下界子算法能對(duì)問(wèn)題解空間大量剪枝，加快了算法的執(zhí)行速度.

6 結(jié) 論

在精確算法領(lǐng)域，有容量約束的LSCP問(wèn)題的相關(guān)研究較少，本文通過(guò)研究有容量集合覆蓋選址問(wèn)題設(shè)計(jì)了一種精確算法，首先總結(jié)出該問(wèn)題的數(shù)學(xué)性質(zhì)并給出證明，這些數(shù)學(xué)性質(zhì)能對(duì)問(wèn)題進(jìn)行降階從而縮小問(wèn)題的規(guī)模，同時(shí)這些數(shù)學(xué)性質(zhì)不僅能用于本文的算法中，而且可以應(yīng)用于其他各種算法；然后利用上界子算法、下界子算法和分配子算法設(shè)計(jì)出一種能夠快速降低問(wèn)題規(guī)模并且能求出最優(yōu)解的降階回溯算法.通過(guò)理論證明分析以及示例1中對(duì)算法執(zhí)行過(guò)程的演示可以看出，本文設(shè)計(jì)的算法不僅能求出最優(yōu)解，還能縮小問(wèn)題的規(guī)模，降低算法時(shí)間復(fù)雜度，加快問(wèn)題的求解速度.