一種求解帶寬限制的中位問題的啟發式算法?

陳麗豐 金 忠

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

設施選址問題是一類被廣泛研究的組合優化的問題，此類問題在物流運輸、規劃設計、運籌管理等領域都有廣泛的應用［1］。問題的模型一般是在給定的網絡拓撲圖上，從候選設施集中選擇一部分設施點構成設施集，將需求點與設施點相連接，并使兩者之間的連接代價可能小。設施選址問題大部分是NP-hard 問題，因此一般采用啟發式算法在有限的時間計算得到近似解作為結果，常用于設施選址問題的啟發式算法有禁忌搜索算法、蟻群算法、局部搜索算法、遺傳算法［2～3］和模擬退火算法［4～5］等。設施選址問題主要有三大研究分支，即覆蓋問題、中位問題和中心問題。其中，中位問題是一類典型的NP-hard［6］的設施選址問題，由Hakimi［7］最早提出，其假設每個節點既是需求點也是設施候選點，對于給定設施數P，目標是求取所有需求點到所分配設施的平均權重距離最小。由于其模型較為簡單，也有許多學者研究了添加了限制條件的中位問題，如動態P 中位問題［8］，條件中位問題［9～10］，可靠中位問題［11～12］等。

2 帶寬限制的中位問題

本文研究的問題是結合了費用流問題的中位問題，即帶寬限制的中位問題。該問題對網絡圖中的每條邊都添加了帶寬的限制，每個需求點都需求一定量的流量，設施點能通過到需求點的一系列邊連接成的路徑向需求點傳輸流量，但每條邊傳輸的流量不能超過其帶寬上限。

設網絡圖G=(V，E，I，J，u，c，f)，V 為點集，E為邊集，I 為設施候選點集合，J 為需求點集合，且有I ?V ，J ?V ，I ∩J=?，uij和cij分別表示邊(i，j)的帶寬和費用，若(i，j)?E ，則uij=0，fi表示點vi的需求流量，若vi?J ，則fi=0，w 表示設施費用。當設施集S ?I 及各邊的流量消耗u*確定時，則可以得到該方案的費用W 。

帶寬限制的中位問題的模型如下：

式（1）為費用函數，包括總設施費用和總路徑費用，總設施費用為設施費用w 與設施個數 ||S 之積，總路徑費用為每條邊的流量消耗與邊的單位費用積的總和。式（2）表明每條邊的流量消耗不能超過其帶寬上限。式（3）表明了對于非需求點，若其不是S 中的元素，則輸向該點的流量必須等于該點輸出的流量。式（4）表明輸向需求點的流量與需求點輸出的流量之差必須等于其需求量。

由于當設施集S 確定后，該問題轉化為最小費用流問題，用最小費用流算法［13］能得到唯一的路徑總費用最小值。因此可以把式（1）看成一個基于S的函數W(S)，即式（1）改寫為

最小費用流算法是一種計算最小費用流問題的算法。該算法引入了反向邊和殘余網絡，算法思想是每次選擇當前網絡圖中源點到匯點的最短通路傳輸流量，直到達到滿流或無法再找出這樣的通路，并且每次傳輸的流量不超過通路上的任意邊。若傳輸的流量為u*，對于通路上的所有邊(i，j)，其帶寬uij減少u*，其反向邊的帶寬uji增加u*，帶寬發生變化后的網絡圖即為殘余網絡，且后續的算法將在殘余網絡上繼續迭代。

3 基于廣義需求點思想的帶寬限制的中位問題的啟發式算法

3.1 廣義需求點思想

在用啟發式算法求解設施選址問題的過程中，會運用領域搜索的方法［14］嘗試對當前的解進行轉變，鄰域即為與當前設施集僅有一個元素差異的設施集。對于給定的設施集S ，為了方便描述，令S-為比S 少一個元素的設施集，S+為比S 多一個元素的設施集。

在鄰域搜索中，由于可行解需要用最小費用流算法才能得到其費用，而最小費用流算法求解的時間花費難以接受。但是如果新的設施集是當前設施集的鄰域，就意味著兩者用最小費用流對應的殘余網絡是非常相似的。因此，可以嘗試通過對當前設施集的殘余網絡進行轉變得到鄰域的殘余網絡。具體方法為通過將某些設施點視為廣義的需求點，并用其它設施點對其傳輸流量，以此得到鄰域的最小費用流。由于傳輸的流量一般來說非常少，而費用流算法的時間花費與總需求流量成正比，因此這種方法的時間花費是遠遠少于直接計算費用流的。

3.2 廣義需求點思想求解鄰域的最小費用流

3.2.1 理論證明

由文獻［15］可知，在殘余網絡圖中若不存在負環路，則當前的費用流為最小費用流。因此當得到了當前設施集的最小費用流的殘余網絡，通過計算廣義需求點的費用流問題時，需要對增流的路徑進行選擇，使得達到滿流后的殘余網絡中依然不存在負環路。為了確定增流的路徑，首先需要證明一個引理。

引理：在殘余網絡中若不存在負環路，選擇設施點到需求點的最短路徑進行增流，則增流后的殘余網絡也不存在負環路。

證明：假設圖G=(V，E，s，t，u，c，f) 不存在負環路，對G 中從s 到t 的最短路L 進行增流后的殘余網絡圖為G'，且G'中存在負環路C 。不失一般性，假設C 的環路不會經過重復的點（若負環路經過重復的點，則一定可以拆分出一個不經過重復點的負環路）。易知，C 至少經過L 中的2個點。

設L 的路徑為(a1，a2，…，al)，?0 ＜i ＜j ＜l ，定義Dai，aj為沿著L 從ai到aj的距離，另外定義Daj，ai=-Dai，aj。此時根據定義，給定任意3 個不大于l 的正整數i，j，k ，有：

設C 沿著其環路的方向經過L 上的點的序列為(b1，b2，…，bc)，且C 上從bc到b1的路徑不經過L，定義映射關系φ(i)，使：?0 ＜i ≤c，?0 ＜j ≤l ，且bi=aj，并使φ( )i =j。由于C 不經過重復的點，故φ(i)為單射。另外，定義dbi，bj為沿著C 從bi到bj的距離。

對 于 給 定 的 正 整 數 i ＜c ，則 bi=aφ(i)，bi+1=aφ(i+1)，此時有：

若φ( i )＜φ( i +1) ，則：

當φ( i )+1 ＜φ( i +1) 時，由于C 中bi到bi+1的路徑不經過L 中除這兩點之外的其他點，因此這段路徑在對L 增流之前就存在，由于L 是最短路徑，因此有dbi，bi+1≥Daφ(i)，aφ(i+1)。

當φ( i )+1=φ(i +1) 時，即L 中從aφ(i)到aφ(i+1)的路徑為一條邊，若C 中從bi到bi+1的路徑也為這 條 邊，則 有 dbi，bi+1=Daφ(i)，aφ(i+1)，否 則 同 理 有dbi，bi+1≥Daφ(i)，aφ(i+1)。

因此，當φ( i )＜φ( i +1) 時，有dbi，bi+1≥Daφ(i)，aφ(i+1)。若φ( i )＞φ( i +1) ，則：

當φ( i )＞φ( i +1) +1時，同理可知C 中bi到bi+1的路徑在對L 增流之前就存在，且該路徑與L 中從aφ(i+1)到aφ(i)的路徑構成了環路。由于對L 增流前的殘余網絡不存在負環路，因此dbi，bi+1+Daφ(i)，aφ(i+1)≥0。

當φ( i )=φ( i +1) +1 時，即L 中從aφ(i+1)到aφ(i)的路徑為一條邊，若C 中從bi到bi+1的路徑為這條邊的反向邊，則有dbi，bi+1+Daφ(i)，aφ(i+1)=0，否則同理有dbi，bi+1+Daφ(i)，aφ(i+1)≥0。

因 此 ，當 φ( i )＞φ( i +1) 時 ，有 dbi，bi+1+Daφ(i)，aφ(i+1)≥0，即dbi，bi+1≥Daφ(i)，aφ(i+1)。

綜上可得，有：

根據式（6）、（7），且C 為負環路，有：

根據式（8）、（9）可得：

由于C 中從bc到b1的路徑在對L 增流前就存在。若φ(1)＞φ(c)，則該路徑和L 中從aφ(1)到aφ(c)的路徑構成了環路，由式（10）得，該環路為負環路，而對L 增流前的殘余網絡中不存在負環路，因此矛盾。若φ(1) ＜φ(c)，由于L是最短路，因此有Daφ(c)，aφ(1)≤dbc，b1，因此和式（11）存在矛盾。

由反證法可知，引理得證。

3.2.2 計算S+的最小費用流

設S+相比S 增加的設施點為vk，S 的最小費用流的殘余網絡為G'。易知S+的最小費用流的費用必定小于S ，否則vk的存在就沒有意義，因此可以把vk視為一個減小當前殘余網絡的費用的設施點。因為G'同樣對應S+的可行費用流，所以只需要考慮如何利用vk減少路徑費用。在G'通過vk向S 的元素的費用為負的通路傳輸流量，可以使路徑費用減小，并最終得到S+的最小費用流。

vk到其它設施點的負費用通路可能有很多，可以采用貪心的思想，每次選擇所有通路中費用最小的進行增流。可以證明最終得到殘余網絡一定對應S+的最小費用流。由于G'對應S 的最小費用流，由文獻［15］的結論可以知道，G'中不含有費用為負的環路，而將vk加入設施集的行為可以視為在G'中添加了由總源點連向vk的邊。若G'不對應S+的最小費用流，那么可知正是這條邊使圖中產生了負環路，即所有的負環路均經過這條邊。而由引理可知，當無視這條邊的存在時，對vk到廣義需求點的最短路徑傳輸流量，并不會使原本不存在負環路的G'在增流后產生負環路。因此，增流后的殘余網絡依然保持所有負環路經過總源點連向vk的邊這條性質，而這種增流行為會使這種性質的負環路逐漸減少，直至消失，即得到S+的最小費用流。

3.2.3 計算S-的最小費用流

與計算S+的最小費用流不同的是，S 的最小費用流不是S-的可行費用流，那么需要對殘余網絡進行調整，使其轉變為S-的可行費用流。從約束式的角度來看，需要在滿足其它約束式保持成立的條件下，使得式（3）也對S-成立。設S-相比S缺少的元素為vk，從廣義需求點的思想來看，需要將vk視為需求點，需求的流量為其原本輸出的流量，并用S-的設施點對vk傳輸流量，使其達到滿流。由引理可知，在不存在負環路的殘余網絡中，每次選擇從S-的設施點到vk的最短路進行增流，則增流后的殘余網絡中依然不存負環路。因此當vk達到滿流后，此時的殘余網絡即為S-的最小費用流。

3.3 基于廣義需求點思想的啟發式算法

給定圖G=(V，E，I，J，u，c，f)，及可行解S ，首先用基于spfa 最短路算法［16］的最小費用流算法得到S 的最小費用流對應的殘余網絡G'。則算法分為2個步驟交替進行。

1）貪心步驟。將設施候選集I 的元素隨機排列并遍歷，設當前的設施候選點為vk，當vk∈S 時，在G'上計算S-=S-{vk}的最小費用流，得到的殘余網絡為G'-，若S-為可行解，且W( )S-＜W(S)，則接受改動；當vk?S 時，在G'上計算S+=S+{vk}的最小費用流，得到的殘余網絡為G'+，若W( )S+＜W(S)，則接受改動。若接受改動，則直接用G'-或者G'+作為當前的殘余網絡。

2）退火步驟。將當前的設施集S 里的元素隨機排列并遍歷，設當前的設施點為vk，以隨機的順序遍歷與vk連接的點。設連接的點為vj，在G'上用廣義需求點思想計算S+=S+{vj}的最小費用流，得到的殘余網絡為G'+。然后在G'+上用廣義需求點思想計算S+-=S+-{vk}的最小費用流，得到的殘余網絡為G'+，若S+-是可行解且W(S+-)＜W(S)，則接受改動；若S+-是可行解且W(S+-) ≥W(S)，則依據兩者的差距和當前的退火溫度以一定概率接受改動。接受改動的操作同于貪心步驟。

在退火步驟中，S+-被接受的概率為

在第t 輪的退火溫度T 的設定如下：

4 實驗結果與分析

本節實驗的數據集來自華為軟件精英挑戰賽，數據集總共包含9 個樣例，每個樣例均為由800 個設施候選點與360 個需求點組成的網絡圖，平均邊數約為3000 條。此外，每個設施候選點僅與一個設施候選點連接，連接的邊的費用為0，且帶寬為其需求流量。

在本文的實驗中，設置設施費用w=400，算法中退火步驟的初始退火溫度T0=0.5，初始解為所有設施點候選點構成的集合。此外，每個樣例均限定150s 的時間，并用模擬退火算法和遺傳算法作為對比。實驗結果如表1所示。

表1 9個樣例可行解的費用對比

可以看出，在相同的時間限定內，本文的算法在9 個樣例上均得到了比傳統的啟發式算法更好的解，解的費用相比兩種啟發式算法減少了500～1500，這說明本文的算法有著明顯優于傳統啟發式算法的性能。

5 結語

本文提出了一種基于廣義需求點思想的啟發式算法，通過設施點之間流量傳輸的方法，大幅度提高了鄰域最小費用流的計算速度，這使得算法在有限的時間能進行更多次的搜索。實驗證明，在帶寬限制的設施選址問題的求解上，本文的方法相較于傳統用于求解設施選址問題的啟發式算法有著更好的尋優性能。但是算法缺少篩選較優鄰域的方法，因此是以遍歷的方式搜索鄰域，這使得算法會在一些較差的鄰域上花費較多無用的時間，因此本文的算法仍有改進空間。