湯 定 一

(復(fù)旦大學軟件學院 上海 200433)

0 引 言

隨著互聯(lián)網(wǎng)行業(yè)的發(fā)展，在線視頻網(wǎng)站用戶數(shù)量和用戶時長快速增長，使用移動設(shè)備獲取視頻服務(wù)已成為眾多用戶的習慣。視頻內(nèi)容需要消耗較多流量，影響用戶體驗的關(guān)鍵在于帶寬。視頻內(nèi)容從視頻網(wǎng)站到用戶需要如下過程。首先，視頻存儲在視頻服務(wù)提供商的多個服務(wù)器中。當用戶請求視頻時，視頻服務(wù)提供商選擇城市通信網(wǎng)絡(luò)中距離用戶較近的服務(wù)器，通過鏈路將內(nèi)容發(fā)送給用戶。最后，用戶收到視頻進行觀看。為了確保用戶在觀看視頻時不會經(jīng)?？D，需要滿足用戶所需帶寬。

視頻服務(wù)提供商在提供視頻服務(wù)時，需要考慮服務(wù)器硬件成本、部署成本和帶寬租賃費用。在滿足所有用戶需求的前提下，選擇服務(wù)器部署節(jié)點集合、帶寬租賃方案，使得總成本最低。

在城市通信網(wǎng)絡(luò)中提供視頻服務(wù)在概念上與內(nèi)容網(wǎng)絡(luò)類似。內(nèi)容網(wǎng)絡(luò)通過在Internet上部署服務(wù)節(jié)點，并通過應(yīng)用層協(xié)議將這些服務(wù)節(jié)點組織形成一個構(gòu)建在IP網(wǎng)絡(luò)之上的覆蓋層，為用戶提供靈活高效的服務(wù)[1]。

服務(wù)節(jié)點部署一直是學術(shù)界和工業(yè)界研究的熱點問題。文獻[1]將服務(wù)節(jié)點部署歸納為選址問題，根據(jù)所需獲得的信息不同，分為三類：基于確定信息的選址、基于概率模型的選址和基于博弈論的選址模型。

這里重點討論與本文問題相關(guān)的基于確定信息的模型，即已知網(wǎng)絡(luò)拓撲和部署費用等信息。

基于確定信息的選址模型包括兩種設(shè)定：設(shè)施選址問題[2]和P中心問題[3]，它們的區(qū)別在于是否限定設(shè)施數(shù)量。如果候選地點建站成本允許不相等，那么稱為無容量限制設(shè)施選址問題(UFLP)，這時可用建站成本來擴展目標函數(shù)。在Mirchandani等[4]和ReVelle等[5]的文章中可以找到關(guān)于UFLP問題的廣泛研究。

Goldengorin等[6]提出了增強的分支界定算法解決無容量限制設(shè)施選址問題，最小化部署成本與距離組成的混合指標。Tcha等[7]提出了基于分支界定的方法解決多層無容量限制設(shè)施選址問題，適用于具有多層結(jié)構(gòu)的內(nèi)容網(wǎng)絡(luò)。這兩個工作都使用整數(shù)規(guī)劃類算法，在約束條件較少、模型較簡單時能夠計算出最優(yōu)解。但是，實際應(yīng)用場景中通常需要考慮的數(shù)據(jù)規(guī)模較大，約束條件也更為復(fù)雜，此時整數(shù)規(guī)劃類算法的時間復(fù)雜度劇增，難以滿足實際應(yīng)用需求。

Radoslavov等[8]從考慮路由拓撲的角度使用貪心算法解決服務(wù)器選址問題，優(yōu)化目標為平均延遲和網(wǎng)絡(luò)容量。Laoutaris等[9]使用分布式和可擴展的方式解決內(nèi)容分發(fā)網(wǎng)絡(luò)中服務(wù)節(jié)點選址問題。脫立恒等[10]提出兩種貪心啟發(fā)式算法解決服務(wù)器節(jié)點部署問題，在保證平均轉(zhuǎn)發(fā)延遲的前提下最小化服務(wù)部署規(guī)模。史佩昌等[11]使用啟發(fā)式算法求解多維設(shè)施選址模型。Berman等[12]使用貪心啟發(fā)式算法解決網(wǎng)絡(luò)中位置覆蓋問題。這些工作使用貪心和啟發(fā)式算法，優(yōu)點在于能在較短時間內(nèi)給出較優(yōu)解，不足之處在于貪心算法通常容易陷入局部最優(yōu)解，而難以收斂到全局最優(yōu)。

綜上所述，現(xiàn)有工作通常使用整數(shù)規(guī)劃類算法和啟發(fā)式算法。然而，對于通信網(wǎng)絡(luò)中提供視頻服務(wù)的問題，難點在于：(1) 網(wǎng)絡(luò)和節(jié)點規(guī)模較大；(2) 在考慮服務(wù)器節(jié)點部署和網(wǎng)絡(luò)帶寬費用的基礎(chǔ)上，加入了服務(wù)器檔次的選擇?，F(xiàn)有的整數(shù)規(guī)劃類算法不能在短時間內(nèi)得出結(jié)果，而現(xiàn)有的啟發(fā)式算法通常缺乏普適性難以高效地解決此問題。因此，本文提出一種兩層迭代算法對該問題進行高效求解：外層為設(shè)施選址問題，通過模擬退火方法迭代選址方案。內(nèi)層在給定服務(wù)器部署方案的情況下通過將網(wǎng)絡(luò)中帶寬租賃問題建模為費用流問題，使用網(wǎng)絡(luò)單純形求解。通過迭代產(chǎn)生新的部署方案以及計算該方案的總費用，在滿足帶寬需求的前提下尋找更優(yōu)的服務(wù)器部署和鏈路租賃方案。該模型采用模擬退火算法，解決了貪心算法過早收斂到局部最優(yōu)解的問題。網(wǎng)絡(luò)單純形法能夠快速計算方案，使得整個算法在短時間內(nèi)能夠通過大量迭代得到更優(yōu)解。在采用模擬退火和網(wǎng)絡(luò)單純形算法的基礎(chǔ)上，本文創(chuàng)造性地提出分段迭代的方法。根據(jù)算法迭代前期和后期服務(wù)器位置和服務(wù)器檔次的選擇對于解的優(yōu)劣的影響程度不同，將算法迭代分為粗調(diào)和精調(diào)兩個階段，使得算法能夠在短時間內(nèi)得到更優(yōu)解。仿真結(jié)果表明，模擬退火-網(wǎng)絡(luò)單純形方案與貪心-Dinic算法相比，能夠減少10%以上的總成本，且隨著數(shù)據(jù)規(guī)模的擴大，優(yōu)勢更加明顯。

1 問題描述

考慮以下通信網(wǎng)絡(luò)的設(shè)施選址問題。城市的通信網(wǎng)絡(luò)由節(jié)點和鏈路構(gòu)成，其中每個節(jié)點的地位是等同的，它們可以通過鏈路將收到的數(shù)據(jù)轉(zhuǎn)發(fā)給另一個節(jié)點。整個網(wǎng)絡(luò)可以看作一幅無向圖，即數(shù)據(jù)的傳輸沒有方向的限制。同時這個網(wǎng)絡(luò)也是連通圖，即圖中任意兩個不同的節(jié)點之間存在路徑。圖中的一些節(jié)點有視頻帶寬需求，即這些點與小區(qū)鄰近，需要滿足用戶的需求的視頻帶寬，稱這些節(jié)點為消費節(jié)點。需要在網(wǎng)絡(luò)中選擇一些節(jié)點部署服務(wù)器，視頻由服務(wù)器通過網(wǎng)絡(luò)推送給消費節(jié)點。目標是尋找最優(yōu)的視頻服務(wù)器部署方案，在滿足所有消費節(jié)點的視頻帶寬需求的前提下，使得服務(wù)器部署成本與網(wǎng)絡(luò)帶寬租用成本之和最低。

2 模型建立

本模型旨在滿足所有消費節(jié)點的視頻帶寬需求的前提下，使得服務(wù)器硬件成本、部署服務(wù)器成本和網(wǎng)絡(luò)帶寬租賃的總成本最小。

2.1 模型假設(shè)

(1) 每條鏈路有帶寬上限，按照占用帶寬收取帶寬租賃費，不同鏈路的帶寬上限與單位帶寬租賃費可能不同。

(2) 同一條鏈路的上行、下行方向的帶寬上限相互獨立，且上下行帶寬上限與單位帶寬租賃費相同，如帶寬上限5 Gbit/s，若上行占用帶寬3 Gbit/s，下行可用帶寬仍為5 Gbit/s。

(3) 一臺服務(wù)器可以服務(wù)多個消費節(jié)點，一個消費節(jié)點也可以從多個服務(wù)器獲取視頻內(nèi)容服務(wù)。

(4) 每個節(jié)點上最多只能部署1臺服務(wù)器。

(5) 每臺服務(wù)器能提供的視頻輸出能力有上限，分為若干檔，不同檔位服務(wù)器的輸出能力與硬件成本不同。隨著檔次的提升，擴充單位容量的費用單調(diào)遞增。如從1檔到2檔輸出能力提升25，硬件成本增加200，若從2檔到3檔輸出能力提升25，則硬件成本至少增加200。

(6) 對于每個節(jié)點，部署服務(wù)器需要部署成本，不同節(jié)點的部署成本可能不同。部署一臺服務(wù)器到一個節(jié)點的成本為硬件成本與部署成本之和。

(7) 不同消費節(jié)點的帶寬需求可能不同。

(8) 服務(wù)器可以直接部署在消費節(jié)點，對于消費節(jié)點來說，該節(jié)點上服務(wù)器提供的帶寬沒有鏈路租賃費用，但該服務(wù)器向其他消費節(jié)點提供的視頻輸出能力上限相應(yīng)減少。

(9) 鏈路帶寬上限與單位帶寬租賃費、服務(wù)器硬件成本與輸出上限、每個節(jié)點的服務(wù)器部署費、消費節(jié)點的帶寬需求均為整數(shù)。

2.2 約束模型

(1) 決策。xi表示是否在節(jié)點i上部署服務(wù)器，yi表示節(jié)點i上部署服務(wù)器的檔位。

xi∈{0,1},yi∈{0,1,…,k}

(1)

(2) 目標函數(shù)。引入超級源點S和超級匯點T。S向所有部署了服務(wù)器的節(jié)點i(xi=1)連邊，容量為相應(yīng)服務(wù)器檔位輸出能力cap(yi)，費用為0。所有消費節(jié)點i向T連邊，容量為需求的帶寬di，費用為0。

目標為最小化服務(wù)器部署費、鏈路帶寬租賃費與服務(wù)器硬件成本之和。

式中：deployi為在節(jié)點i部署服務(wù)器的費用；fij為節(jié)點i到節(jié)點j實際占用的帶寬。

(3) 約束條件。流量守恒，所有節(jié)點(除了S、T)的流入流量與流出流量相等。

流量上限，每條邊的流量不超過容量上限。

fij≤biji,j∈N

服務(wù)器輸出上限，每臺服務(wù)器輸出的流量不超過檔位對應(yīng)的容量。

fSi≤bSii∈N

消費節(jié)點滿流，每個消費節(jié)點的帶寬需求都需要滿足。

fiT=biTi∈N

(4) 模型參數(shù)。N為通信網(wǎng)絡(luò)中節(jié)點集合。S為加入的超級源，T為加入的超級匯。hardware函數(shù)表示檔位對應(yīng)硬件成本，cap函數(shù)表示檔位對應(yīng)輸出能力。bij表示節(jié)點i到節(jié)點j的帶寬上限，根據(jù)模型中鏈路上下行帶寬上限相等假設(shè)，有bij=bji，i,j∈N。rij為節(jié)點i到節(jié)點j的單位帶寬租賃費。bSi為超級源S到節(jié)點i的帶寬上限，代表節(jié)點i上部署服務(wù)器的視頻輸出能力。biT為節(jié)點i到超級匯的帶寬上限，代表節(jié)點i的視頻帶寬需求。

(5) 變量。fij，i,j∈{N,S,T}代表節(jié)點i到j(luò)的鏈路實際占用帶寬。xi∈{0,1}代表節(jié)點i是否部署服務(wù)器。yi∈{0,1,…,k}代表節(jié)點i部署服務(wù)器的檔位，共k個檔位可供選擇，其中0檔代表沒有部署服務(wù)器。

3 算 法

本文將問題分為兩部分：1) 在網(wǎng)絡(luò)節(jié)點中選擇服務(wù)器部署節(jié)點集合與服務(wù)器檔位。2) 根據(jù)服務(wù)器部署方案求最小網(wǎng)絡(luò)租賃費。其中第一個問題由兩層NP難問題組成，第一層是在網(wǎng)絡(luò)節(jié)點中選取服務(wù)器部署點集，屬于設(shè)施選址類問題，屬于NP難問題；第二層是確定服務(wù)器的檔次，比如已經(jīng)選擇在30個節(jié)點上部署服務(wù)器，服務(wù)器可選檔次共10檔，因此，即便確定了服務(wù)器的數(shù)量和部署點集，還需要考慮1030種可能檔位組合。第二個問題可用費用流在多項式時間求解。

如何高效快速地得到較優(yōu)解面臨兩個挑戰(zhàn)：(1) 外層算法的選擇，需要在速度和全局優(yōu)化能力之間進行權(quán)衡。(2) 內(nèi)層費用流算法的選擇，由于已有多項式算法，需要速度足夠快。

對于第一個挑戰(zhàn)，有兩種類型的算法，遺傳算法維護一定數(shù)量的解，通過使用交叉、變異等算子進行迭代，推動種群的進化。其優(yōu)點是全局優(yōu)化能力強，但速度較慢。貪心算法從一個初始可行解出發(fā)，通過迭代優(yōu)化當前解，優(yōu)點是速度快，但容易陷入局部最優(yōu)。我們使用模擬退火算法，具備貪心算法速度快的優(yōu)點，同時又能通過策略跳出局部最優(yōu)解。

對于第二個挑戰(zhàn)，主流的費用流算法分為增廣算法(如Dinic算法)與消圈算法(如網(wǎng)絡(luò)單純形)。網(wǎng)絡(luò)單純形算法在本文問題的費用流構(gòu)圖中更快。

我們在采用模擬退火和網(wǎng)絡(luò)單純形算法的基礎(chǔ)上，提出分段迭代的方法進行優(yōu)化。根據(jù)算法迭代前期和后期服務(wù)器位置和服務(wù)器檔次的選擇對于解的優(yōu)劣的影響程度不同，將算法迭代分為粗調(diào)和精調(diào)兩個階段，使得算法能夠在短時間內(nèi)得到更優(yōu)解。

3.1 外層模擬退火

模擬退火算法[13]能有效地在一個大的搜索空間中尋找最優(yōu)解。其包含兩個部分：Metropolis算法和退火過程。Metropolis算法用于跳出局部最優(yōu)解，通過重要性采樣方法，以概率來接受新狀態(tài)。退火過程通過調(diào)節(jié)初始溫度與退火速率，確保目標函數(shù)能夠在有限的時間內(nèi)收斂。

模擬退火算法的流程是首先構(gòu)造一個初始可行解，然后不斷迭代“產(chǎn)生新解，計算目標函數(shù)，接受或放棄新解”這個過程。通過設(shè)置初始溫度與退火速率得到當前溫度T，然后根據(jù)新解相對當前解的代價函數(shù)增量計算接受新解的概率。當溫度低于給定值或程序運行時間達到預(yù)設(shè)值時停止迭代。

1) 初始解的構(gòu)造。令xi∈{0,1}表示編號為i的節(jié)點是否部署服務(wù)器，yi∈{0,1,…,k}表示編號為i的節(jié)點部署服務(wù)器的檔次。初始解的構(gòu)造方式為所有節(jié)點均部署最高檔次的服務(wù)器，顯然，如果圖中存在可行解，則初始解一定是可行解。

2) 新解產(chǎn)生策略。根據(jù)當前服務(wù)器的部署方案產(chǎn)生新的服務(wù)器部署方案，隨機采用以下6種策略：(1) 隨機選取1個沒有部署服務(wù)器的節(jié)點，在其上新增服務(wù)器；(2) 隨機選取1個已經(jīng)部署服務(wù)器的節(jié)點，撤掉其服務(wù)器；(3) 隨機選取1個部署了服務(wù)器的節(jié)點，將其上部署的服務(wù)器移動到相鄰節(jié)點；(4) 隨機選取1個已經(jīng)部署服務(wù)器的節(jié)點，將其服務(wù)器檔次提級；(5) 隨機選取1個已經(jīng)部署服務(wù)器的節(jié)點，將其服務(wù)器檔次降低；(6) 隨機選取2個已經(jīng)部署服務(wù)器的節(jié)點，交換兩個服務(wù)器的檔次。

3) 初始溫度與退火速度。初始溫度影響迭代的有效性和避免陷入局部最優(yōu)解的能力，過高則增加迭代次數(shù)，過低會影響解的質(zhì)量。采用初始解總成本乘以常數(shù)K，這里使用0.01。退火速率采用指數(shù)式下降方式：T(n)=λT(n-1),n=1,2,3,…。其中：T(n)為當前的溫度；λ為衰減速率；T(n-1)為上一步的溫度。

3.2 內(nèi)層網(wǎng)絡(luò)單純形

在給定服務(wù)器部署方案時，網(wǎng)絡(luò)鏈路帶寬租用問題可以建模為費用流問題。

費用流，也稱最小費用最大流，是指在網(wǎng)絡(luò)流圖中，每條邊除了流量上限外，也有單位流量費用，求出一組可行解，使得滿足它是最大流的情況下，總的費用最小。

費用流建圖過程如下，首先，費用流圖中點集為通信網(wǎng)絡(luò)中所有節(jié)點。由于鏈路是無向邊，在建邊時將每條從節(jié)點s到節(jié)點t的鏈路拆分為2條邊：s到t的邊，流量為帶寬上限，費用為單位帶寬租賃費。t到s的邊，流量和費用與s到t的相同。加入超級源點S與T。其中：S與所有部署服務(wù)器的點建邊，流量為服務(wù)器輸出帶寬，費用為0。所有消費節(jié)點與超級匯點T建邊，流量為帶寬需求，費用為0。如果求得的最大流等于所有消費節(jié)點的帶寬需求之和，則為可行解。

網(wǎng)絡(luò)單純形法[14]采用消圈思想，首先構(gòu)造一條從超級源S到T的邊，流量大于從S流出的所有邊的流量之和，也大于流入T的所有邊的流量之和。它的費用大于所有邊的費用之和。這時如果在原網(wǎng)絡(luò)中找到任意一條從S到T的路徑，將S到T的邊的流量導(dǎo)入這條路徑，總費用必然減小。求最小費用的過程是不斷地在網(wǎng)絡(luò)中尋找負環(huán)，直到找不到負環(huán)時得到最小費用。

3.3 分段迭代優(yōu)化

在算法迭代的初始階段，服務(wù)器的位置選擇是影響總成本更重要的因素。而在算法迭代的后期，服務(wù)器檔次選擇為與服務(wù)器位置選擇同等重要。我們將模擬退火分為兩個階段：粗調(diào)階段和精調(diào)階段。

(2) 精調(diào)階段。在精調(diào)階段，模擬退火在構(gòu)造新解時，同時考慮服務(wù)器位置與檔次的選擇。此時使用原本的費用流圖，即超級源連向服務(wù)器部署節(jié)點的邊，容量為cap(yi)，費用為0。在新解產(chǎn)生策略上，使用全部6種策略，特別是在隨機時更多選用后3種關(guān)于服務(wù)器檔次的策略。

4 仿真實驗

通過在兩種不同規(guī)模的網(wǎng)絡(luò)上進行實驗，在90 s內(nèi)將模擬退火-網(wǎng)絡(luò)單純形算法給出的方案與貪心-Dinic算法得到的方案進行對比，說明模擬退火-網(wǎng)絡(luò)單純形方案能在給定時間內(nèi)得到顯著優(yōu)于貪心-Dinic算法的解。

4.1 數(shù)據(jù)集

在兩種規(guī)模的數(shù)據(jù)上進行實驗：

(1) 中等規(guī)模，節(jié)點數(shù)600，邊數(shù)2 000左右，消費節(jié)點240個。

(2) 大規(guī)模，節(jié)點數(shù)1 200，邊數(shù)6 000左右，消費節(jié)點480個。

其中鏈路總帶寬與網(wǎng)絡(luò)租用費為[0,100]的整數(shù)，視頻服務(wù)器檔次數(shù)不超過10個。視頻服務(wù)器輸出能力為不超過300的整數(shù)，節(jié)點部署服務(wù)器成本為不超過2 000的整數(shù)，消費節(jié)點的視頻帶寬需求為不超過200的整數(shù)。

圖1中，通信網(wǎng)絡(luò)包含50個節(jié)點，其編號從0開始。其中：黑色節(jié)點為消費節(jié)點，比如7號節(jié)點是消費節(jié)點，有帶寬需求；邊的粗細表示鏈路容量，較粗的邊比如左上角22號與23號之間的邊的可用帶寬上限較大，較細的邊比如8號到9號之間的邊容量較小。

圖1 通信網(wǎng)絡(luò)結(jié)構(gòu)

4.2 對比實驗

在兩種規(guī)模的數(shù)據(jù)上各使用10組隨機數(shù)據(jù)進行對比。將模擬退火-網(wǎng)絡(luò)單純形算法在90 s以內(nèi)給出的方案與貪心-Dinic方案進行對比。這里選擇貪心算法作為傳統(tǒng)啟發(fā)式算法的代表，選擇Dinic算法[15]作為通用的費用流算法進行實驗對比。

圖2展示的是中等規(guī)模數(shù)據(jù)上兩種算法在90秒以內(nèi)給出的方案在總成本上的對比。在第一組數(shù)據(jù)中，本文算法給出的方案總成本為199 063，貪心-Dinic法得到的總成本為227 604,差距百分比12.5%。在所有的10組數(shù)據(jù)上，本文算法給出的方案相比貪心-Dinic法的總成本減少10.2%到16.9%，特別是第2組數(shù)據(jù)，本文算法相比貪心-Dinic法總成本減少了16.9%。

圖2 中等規(guī)模數(shù)據(jù)(總共10組數(shù)據(jù))上模擬退火-網(wǎng)絡(luò)單純形方案與貪心-Dinic方案的總成本對比

圖3展示的是大規(guī)模數(shù)據(jù)上兩種算法在90 s以內(nèi)給出的方案在總成本上的對比。在所有的10組數(shù)據(jù)上，本文算法給出的方案相比貪心-Dinic法總成本減少了19.3%到25.2%。對比中等規(guī)模數(shù)據(jù)與大規(guī)模數(shù)據(jù)上兩種算法的總成本差距百分比，可以得出結(jié)論，隨著數(shù)據(jù)規(guī)模的增加，模擬退火-網(wǎng)絡(luò)單純形法相比貪心-Dinic法的優(yōu)勢更大。這主要是由于隨著數(shù)據(jù)規(guī)模的增加，解的空間指數(shù)級別增大，得到更優(yōu)解的難度也隨之增加。這說明本文算法在不同規(guī)模的數(shù)據(jù)上具有高效性。

圖3 大規(guī)模數(shù)據(jù)(總共10組數(shù)據(jù))上模擬退火-網(wǎng)絡(luò)單純形方案與貪心-Dinic方案的總成本對比

通過在兩種規(guī)模各10組數(shù)據(jù)上的對比實驗，說明本文方案可以在給定時間內(nèi)得到總成本顯著優(yōu)于貪心-Dinic法的方案。在實際應(yīng)用場景中，我們能夠快速給出方案以對實際部署提供指導(dǎo)。

4.3 兩階段優(yōu)化的有效性

下面通過兩種不同規(guī)模數(shù)據(jù)的實驗，說明兩階段模擬退火算法的有效性。

首先，以中等規(guī)模第一組數(shù)據(jù)舉例。如圖4所示，在粗調(diào)階段，在前1 000輪迭代內(nèi)，總成本快速地從45萬(千元)下降到20萬(千元)，并在接下來的1 000次到8 000次迭代中在20萬(千元)左右持續(xù)優(yōu)化。如圖5所示，在精調(diào)階段，在前5 000輪迭代內(nèi)總成本快速從20萬(千元)優(yōu)化到19萬(千元)，并在接下來的5 000到38 000次迭代中持續(xù)優(yōu)化。

圖4 中等規(guī)模第一組數(shù)據(jù)在粗調(diào)階段總成本隨迭代次數(shù)變化曲線

圖5 中等規(guī)模第一組數(shù)據(jù)在精調(diào)階段總成本隨迭代次數(shù)變化曲線

然后，以大規(guī)模第一組數(shù)據(jù)舉例。如圖6所示，在粗調(diào)階段，在前1 000次迭代內(nèi)，總成本快速從1百萬(千元)降低到40萬(千元)，并在1 000次到3 500次迭代中持續(xù)優(yōu)化。如圖7所示，在精調(diào)階段，總成本在前5 000次迭代快速從40萬(千元)優(yōu)化到39萬(千元)，并在5 000到10 100次迭代中持續(xù)優(yōu)化。

圖6 大規(guī)模第一組數(shù)據(jù)在粗調(diào)階段總成本隨迭代次數(shù)變化曲線

圖7 大規(guī)模第一組數(shù)據(jù)在精調(diào)階段總成本隨迭代次數(shù)變化曲線

5 結(jié) 語

將通信網(wǎng)絡(luò)中服務(wù)器部署方案這一實際問題建模為服務(wù)器選址問題與費用流問題的整合。本文同時考慮服務(wù)器部署選址與服務(wù)器檔次選擇這兩個NP難問題的疊加。通過適合大規(guī)模組合優(yōu)化問題的模擬退火算法與適合大規(guī)模網(wǎng)絡(luò)中快速求解費用流的網(wǎng)絡(luò)單純形算法結(jié)合，求解總成本更低的服務(wù)器部署方案。

本文創(chuàng)造性地運用兩階段模擬退火對問題進行求解。服務(wù)器部署方案的總費用由服務(wù)器硬件成本、部署服務(wù)器成本和網(wǎng)絡(luò)帶寬租賃費用組成。在滿足消費節(jié)點帶寬需求的前提下，得出總成本盡可能小的部署方案。通過在90 s的時間內(nèi)，在兩種規(guī)模數(shù)據(jù)上對比模擬退火-網(wǎng)絡(luò)單純形算法給出的方案與貪心-Dinic算法給出的方案，本文算法能夠減少10%以上的總成本，且隨著數(shù)據(jù)規(guī)模的擴大，優(yōu)勢更加明顯。

本文探索了引入檔次選擇的服務(wù)設(shè)施選址問題，同時兩階段模擬退火的設(shè)計也為這一類問題提供了參考解決方案。