有容量集合覆蓋選址問題的降階回溯算法

尚春劍，寧愛兵，彭大江，張惠珍

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

1 引 言

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

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

由于每個設施的容量有限，同時要滿足每個需求點的需求量，在精確算法領域中，有容量約束的LSCP問題研究難度較大，相關研究相對較少.本文針對上述現有算法的不足之處，首先研究有容量集合覆蓋問題具有的數學性質，這些數學性質能縮小問題規模，降低算法時間復雜度；然后利用上下界子算法對問題剪枝，加快問題求解速度；之后設計的分配子算法解決了傳統精確算法在有容量設施選址問題中的難點；最后結合數學性質、上界子算法、下界子算法、分配子算法，設計出一種能夠降低問題規模從而加快問題求解速度并且能求出問題最優解的降階回溯算法.

2 問題描述

2.1 數學符號及解釋

以下為數學模型中涉及的數學符號：

ei：表示第i個需求點；

fj：表示第j個設施；

m：表示需求點的個數；

n：表示設施的個數；

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

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

di：表示第i個需求點的需求量；

cj：表示第j個設施的容量；

xj∈{0，1}：若設施fj開設，則xj=1，否則xj=0；

yi，j：表示需求點ei的需求中被分配給設施fj的部分；

A(j)：表示第j個設施fj可服務的需求點集合；

B(i)：表示可以覆蓋第i個需求點ei的設施集合。

以下為后文設計的算法中涉及的數學符號：

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

gi：若需求點ei的需求量完全滿足，即ki=0，則gi=1，否則gi=0；

deg(ei)：表示需求點ei的度，即需求點ei可被deg(ei)個設施服務；

deg(fj)：表示設施fj的度，即設施fj可服務deg(fj)個需求點；

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

b：算法在某一狀態下的目標函數值下界，為局部變量；

u：算法在某一狀態下的目標函數值上界，為全局變量；

F1：一定開設的設施集合，若F1中任一設施不開設則不能取得最優解，為全局變量；

F0：一定不開設的設施集合，若F0中任一設施開設則不能取得最優解，為全局變量；

F5=FF1F0：暫時未確定是否開設的設施集合，為全局變量；

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

FF1：F5中的設施在回溯算法分情況時假設開設的設施放入集合FF1中，為全局變量；

FF0：F5中的設施在回溯算法分情況時假設不開設的設施放入集合FF0中，為全局變量；

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

Fbest：算法在當前狀態下已知最好的目標函數值對應的開設設施集合，為全局變量；

best_q：回溯算法在當前狀態下已知最好的目標函數值，best_q= |Fbest|，為全局變量；

cur_n：當前累計開設設施數，為局部變量；

cur_i：回溯算法的當前搜索層數，為局部變量。

2.2 數學模型

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

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

(1)

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

3 數學性質及子算法設計

3.1 數學性質

性質1.若圖G是非連通圖，則可對圖G的連通分量分別看作單獨的子問題，分別進行求解.

證明：由于子問題之間不存在通路，求解時相互獨立，互不影響，因此可以分別求解.

性質2.對于每個設施的容量rj和需求點的需求量ki，若全體rj和ki之間存在公約數，則可將當前問題中的容量和需求量同時約去該公約數，降低了問題求解過程中計算的復雜程度.

證明：由于對設施的容量和需求點的需求量同時進行約分，對于某個設施服務某個需求點的能力不產生影響，問題轉化為其等價問題，數值更小便于求解.

證明：因為fj在圖G中所起到的覆蓋作用完全可以由fh來代替，并且fh的剩余容量能滿足N(fh)中所有需求點的需求量.

證明：反證法，由于滿足該x個需求點的設施總容量恰好等于x個需求點的總需求量，若覆蓋x個需求點的設施中有設施未開設，則這x個需求點的需求量不能完全被滿足，因此fj∈B(i)的設施均開設，且服務于這x個需求點.

性質7.對于任意一個已確定開設的設施fj，且rj≥∑ei∈A(j)ki，則ei∈A(j)的需求點均由設施fj服務.

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

性質8.若需求點ei滿足deg(ei)=1，則ei對應的B(i)中唯一的設施fj一定開設，放入F1中，且服務ei.

證明：由于問題要求全覆蓋，因此需求點ei必須被服務，若需求點ei只能被一個設施fj服務，則設施fj一定開設且為需求點ei提供服務.

性質9.在問題以及在問題處理過程中出現的子問題中，若對于任意一個已確定開設的設施fj，滿足aj=1且deg(fj)=1，則fj一定服務于其當前對應的A(j)中唯一的需求點ei.

證明：由于設施fj已開設且有剩余容量，目標函數要求開設的設施數量最少，則設施fj剩余的容量應當服務于當前對應的A(j)中唯一的需求點ei，否則會浪費設施fj剩余的容量.

性質10.在假設某設施fj開設的情況下，此時若下界b大于之前的上界u，則設施fj一定不開設，其中上下界求解算法詳見3.3和4.4.

證明：新的下界大于之前的上界，說明設施fj開設則不可能獲得最優解，因此應關閉設施fj.

性質11.在假設某設施fj不開設的情況下，此時若下界b大于之前的上界u，則設施fj一定開設.

證明：新的下界大于之前的上界，說明設施fj關閉不可能獲得最優解，因此應開設設施fj.

性質12.在假設某設施fj不開設的情況下，若FF5中所有設施均開設，但分配子算法無解，則設施fj一定開設.

證明：若設施fj不開設，則該問題無解，因此設施fj一定開設.

性質13.算法執行過程中，若ki=0，則刪除對應的需求點ei及其鄰接邊，更新圖G；若rj=0，則刪除對應的設施點fj及其鄰接邊，更新圖G.

證明：顯然，當需求點ei完全被滿足就可以刪除；同樣，當設施點fj剩余容量為零時也可以刪除.

3.2 分配子算法

在集合覆蓋選址問題中，首先要從許多候選設施點中選取開設的設施，然后將需求點分配到所選取的設施上，經典的集合覆蓋問題選址中，需求點的不同分配順序不影響目標函數值，而本文研究的有容量集合覆蓋選址問題，由于設施和需求點都有容量的限制，因此每個需求點的不同分配順序會使得所得到的目標函數值不同.于是在算法設計中，有容量集合覆蓋選址問題不僅有設施的選擇過程，還有分配過程.

對于本文研究的問題，在開設設施已定的情況下，只要通過合理分配方法在多項式時間內找到一個可行解即可.本文通過下面的分配子算法對需求點進行分配，該子算法的具體內容如下：

Step 1.初始化所有需求點，令所有gi=0；

Step 2.根據性質4判斷開設的設施集合是否不可行，若不可行，則該問題無解，分配子算法結束，否則執行下一步；

Step 3.判斷問題是否滿足數學性質5，此時得到一個解，不需要執行分配子算法的后面步驟，將所有需求點標記gi=1，則已全部得到滿足的需求點個數dis=m，分配子算法結束；若不滿足數學性質5，執行下一步；

Step 4.將需求點和設施分別按照其度的大小升序排列標號，即度越小的結點越先處理.將滿足數學性質7的需求點標記為gi=1，若dis=m，分配子算法結束；若dis

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

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

3.3 下界子算法

本文設計的下界子算法的具體步驟如下：

Step 1.初始化b=|F1|，Ftemp={ }，計算開設的設施容量之和∑fj∈F1∪Ftemprj；

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

證明：該算法選出的設施集合Ftemp中任一設施的容量都大于等于未選中設施的容量，若選出的開設的設施個數小于|Ftemp|，那么此時開設設施的容量之和一定小于所有需求點的需求量之和，所以此時沒有可行解，因此開設的設施數一定大于等于|F1∪Ftemp|.

3.4 上界子算法

事實上，任何一個可行解對應的目標函數值均能作為該問題的上界.本文先利用前面所介紹的數學性質，將問題進行降階處理，之后執行如下的上界子算法求出上界：

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

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

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

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

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

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

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

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

1)選取N(ei)中已開設且剩余容量最大的設施fmax為ei提供服務，Ftemp=Ftemp∪{fmax}；

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

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

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

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

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

證明：若本子算法求出的解是可行解，那么最優解肯定小于等于可行解對應的目標函數值；若本子算法全部設施開設都不能滿足需求點的需求，此時u=+∞，可以作為目標函數的上界.

4 降階回溯算法

降階回溯算法包括降階算法和回溯算法兩個部分，降階算法通過結合前文介紹的數學性質對問題進行降階，從而縮小問題的規模，降低求解的難度；回溯算法采用深度優先的方法搜索問題的解空間，從根結點出發，對每一個結點判斷該情況下其理論下界b是否小于上界u，若滿足則繼續向下深度優先搜索，否則進行剪枝，逐級向上回溯.

4.1 降階子算法

降階算法步驟如下：

Step 1.初始化cur_i=1，cur_n=0，best_q=+∞，u=0，F1=F0={ }，F5=F={fj|j=1，2，…，n}；

Step 2.根據3.1介紹的數學性質確定一定開設和一定不開設的設施，對問題進行降階處理，若某設施fj一定開設，則F1=F1∪{fj}，F5=F5(〗fj}；若某個設施fj一定不開設，則F0=F0∪{fj}，F5=F5{fj}，更新圖G；

Step 3.根據3.4的上界子算法計算問題上界u；

Step 4.對F5中的每一個設施fj，若滿足性質10，即當fj開設時有下界b>u，則fj一定不開設，令F0=F0∪{fj}，F5=F5(〗fj}；若滿足性質11，即當fj不開設時有下界b>u，則fj一定開設，令F1=F1∪{fj}，F5=F5(〗fj}.

4.2 回溯子算法

執行4.1介紹的降階算法對問題規模進行降階處理后，調用下面的回溯子算法backtrack(1).回溯算法對設施集合FF5=F5中的每一個設施分為以下2種情況進行處理：

1)若設施fj開設，并搜索對應的左子樹；

2)若設施fj不開設，搜索對應的右子樹.

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

Step 1.初始化cur_i=1，cur_n=0，best_q=+∞，u=0，FF1=FF0={}，FF5=F5；

Step 2.當cur_i>|FF5|或|FF5|=0，說明搜索到達葉子結點，此時調用分配子算法，對需求點進行分配，此時若dis=m，則得到一個可行解.若對應目標函數值Q

Step 3.情況1：開設設施fcur_i，在此情況下計算下界b，若b≤best_q，表明此時可以開設設施fcur_i，令FF1=FF1∪{fcur_i}，FF5=FF5(〗fcur_i}，調用數學性質，確定此時一定不開設的設施集合為FF1_temp0，確定此時一定開設的設施集合為FF1_temp1，令FF1=FF1∪FF1_temp1，FF0=FF0∪FF1_temp0，FF5=FF5(FF1_temp1∪FF1_temp0)，調用backtrack(cur_i+1)進入左子樹搜索；若b>best_q，則說明若開設設施fcur_i則不能取得最優解，此時左子樹剪枝，跳到Step 5；

Step 4.算法跳到搜索樹的上一層之前，恢復FF1和FF5到Step 3的初始狀態，FF1=FF1({fcur_i}∪FF1_temp1)，FF5=FF5∪({fcur_i}∪FF1_temp1∪FF1_temp0)，FF0=FF0FF1_temp0；

Step 5.情況2：不開設設施fcur_i，在此情況下計算下界b，若b≤best_q，則說明不開設fcur_i可能取得最優解，令FF0=FF0∪{fcur_i}，FF5=FF5(〗fcur_i}，調用數學性質，確定此時一定不開設的設施集合為FF0_temp0，確定此時一定開設的設施集合為FF0_temp1，令FF1=FF1∪FF0_temp1，FF0=FF0∪FF0_temp0，FF5=FF5(FF0_temp1∪FF0_temp0)，調用backtrack(cur_i+1)進入右子樹搜索；若b>best_q，說明不開設設施fcur_i則不可能取得最優解，則結束該回溯子程序，此時右子樹剪枝；

Step 6.算法跳到搜索樹的上一層之前，恢復FF0和FF5到Step 5的初始狀態，FF0=FF0({fcur_i}∪FF0_temp0)，FF5=FF5∪({fcur_i}∪FF0_temp1∪FF0_temp0)，FF1=FF1FF0_temp1.

算法結束后，當前的最優目標函數值best_q和對應開設的設施Fbest就是整個問題的一個最優解.

4.3 主算法

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

Step 1.先調用降階子算法；

Step 2.調用上下界子算法，計算問題的上界u和下界b；

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

4.4 算法時間復雜度與對比分析

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

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

5 示例分析

為了更清晰的說明本文算法，下面給出一個示例對算法執行的整個過程進行說明.

示例1:如圖1所示，現有6個需求點ei，7個設施fj，若設施fj能為需求點ei提供服務，則用實線連接.現從中選出若干個設施服務于需求點，使得每個需求點的需求量均得到滿足，求所選取設施個數的最小值Q.

對示例1的分析過程可描述如下：

圖1 設施服務需求點服務二分圖Fig.1 Bipartite graph of facility service demand point service

經過分析，圖1為非連通圖，根據性質1，可將示例1分成兩個單獨的子問題分別進行求解.{j1、j6、i1、i6}可構成子問題1，{j2、j3、j4、j5、j7、i2、i3、i4、i5}可構成子問題2，問題分解后如圖2所示.

圖2 問題分解后二分圖Fig.2 Bipartite graph after problem decomposition

1)對于子問題1，n1=2：經判斷，子問題1不滿足性質4；根據性質3，j1、j6有N(v6)?N(v1)且c1≥(d1+d6)，則將設施j6及其關聯邊從圖中刪除，即設施j6關閉；根據性質8，設施j1開設，為需求點j1提供2個需求，為需求點j6提供3個需求.將設施j1標記a1=1，需求點i1、i6標記g1=1，g6=1，則子問題1中有dis=n1=2.

2)對于子問題2，n2=5：經判斷，子問題2不滿足性質4；子問題2中{j2、j3、j4、j5、j7、i2、i3、i4、i5}的容量或需求量存在公約數3，根據性質2，可將當前問題中的容量和需求量同時約去3；根據性質8，設施j5開設，標記a5=1，為需求點i5提供1個需求，將需求點i5標記g5=1；根據性質9，設施j5為需求點i4提供1個需求，需求點i4剩余需求量k4=2.

3)問題經過降階處理后，更新問題規模如圖3所示.

4)執行回溯算法，執行過程如圖4所示的二叉樹.

① 在搜索過程中，從根結點0出發，計算該結點下界b=5，上界u=6.假設j2開設，進入左子樹，該結點下界b=5，小于上界u=6，因此假設j3開設，進入左子樹，該結點下界b=5，上界u=6，因此假設j4開設，該結點下界b=5，上界u=6，因此假設j7開設，到達結點1.調用分配子算法，結點1處x2=1，x3=1，x4=1，x7=1構成可行解，此時目標函數值為6；

圖3 問題降階處理后二分圖Fig.3 Bipartite graph after problem reduction

② 結點1搜索完成，回溯到上一層.假設設施j7不開設，進入右子樹，到達結點2.根據數學性質4，結點2處x2=1，x3=1，x4=1，x7=0，不能構成可行解；

圖4 解空間二叉樹Fig.4 Solution space binary tree

③ 結點2搜索完成，回溯到上一層.假設設施j4不開設，進入右子樹，假設設施j7開設，到達結點3.調用分配子算法，結點3處x2=1，x3=1，x4=0，x7=1構成可行解，此時目標函數值為5；

④ 結點3搜索完成，回溯到上一層.假設設施j7不開設，進入右子樹，到達結點4，根據數學性質4，結點4處x2=1，x3=1，x4=0，x7=0，不能構成可行解；

⑤ 結點4搜索完成，回溯到上一層.假設設施j3不開設，進入右子樹，到達結點5，根據數學性質4，j2不開設時不能構成可行解，于是剪枝，結點5以下的子樹不再搜索；

⑥ 結點5搜索完成，回溯到上一層.假設設施j2不開設，進入右子樹，到達結點6，根據數學性質4，j2不開設時不能構成可行解，于是剪枝，結點6以下的子樹不再搜索.

通過上述算法得到該問題的最優解集Fbest={j1，j2，j3，j5，j7}，最優目標函數值Q=5，Fbest={j1，j2，j3，j5，j7}其中一個可行的分配如下：j1為需求點i1提供2個需求，為需求點i6提供3個需求；j2為需求點i2提供6個需求，為需求點i4提供3個需求；j3為需求點i3提供6個需求，為需求點i4提供3個需求；j5為需求點i4提供3個需求，為需求點i5提供3個需求；j7為需求點i3提供6個需求，算法結束.從這個例子可以清楚地看到，數學性質能降低問題的規模，上下界子算法能對問題解空間大量剪枝，加快了算法的執行速度.

6 結 論

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