閆志遠(yuǎn)，孫文彬，周長江，熊婷，王江

（中國礦業(yè)大學(xué)（北京）地球科學(xué)與測繪工程學(xué)院，北京 100083）

0 引言

p－中心定位是一類基本的網(wǎng)絡(luò)選址問題［1］，由Hakimi在1964年首次提出［2］。p－中心定位算法是解算許多地理網(wǎng)絡(luò)分析問題的基礎(chǔ)，如公共設(shè)施選址、服務(wù)區(qū)域規(guī)劃等。p－中心定位問題是一個NP（Non－deterministic Polynomial）完全問題［3］，無法在多項式時間內(nèi)獲得精確解，多采用啟發(fā)式算法來獲取近似解。隨著網(wǎng)絡(luò)數(shù)據(jù)規(guī)模的不斷增加，串行啟發(fā)式算法已無法滿足快速獲取高質(zhì)量解的需求，而并行技術(shù)能夠通過任務(wù)分解或數(shù)據(jù)分割提高算法的效率［4］。因此，在大規(guī)模地理網(wǎng)絡(luò)中，通過并行化技術(shù)提升啟發(fā)式算法的效率，是快速獲取p－中心定位問題高質(zhì)量解的有效途徑。

目前，用于解算p－中心定位問題的啟發(fā)式算法可分為兩大類［5］：經(jīng)典啟發(fā)式算法和元啟發(fā)算法。經(jīng)典啟發(fā)式算法解算效率高，但解的質(zhì)量相對較差；而元啟發(fā)算法解的質(zhì)量高，但解算時間較長［6］。為了保證解的質(zhì)量，近年來國內(nèi)外學(xué)者多采用元啟發(fā)算法進(jìn)行p－中心定位問題的求解［7－10］。分散搜索算法是一種應(yīng)用廣泛的元啟發(fā)算法［11］，該算法提供了一種求解問題的通用框架，具有良好的可并行性。算法的子過程實現(xiàn)方式靈活多樣，既可以采用局部搜索、整數(shù)規(guī)劃等策略，也可采用其它元啟發(fā)算法［12］。因此，本文擬以分散搜索框架為基礎(chǔ)，設(shè)計并行的分散搜索算法（Parallel Scatter Search Algorithm，PSSA），在保證高質(zhì)量解的前提下，提高p－中心定位算法的執(zhí)行效率。

1 并行分散搜索算法的實現(xiàn)

1.1 p－中心定位問題

p－中心定位問題的數(shù)學(xué)描述如下：記U＝｛ui｜i＝1，…，n｝為用戶點集合；F＝｛fj｜j＝1，…，m｝為備選設(shè)施點集合；D＝｛dij｜i＝1，…，n；j＝1，…，m｝為距離矩陣，dij表示U中第i個用戶點到F中第j個備選設(shè)施點的服務(wù)距離，如果該備選設(shè)施點無法為該用戶點提供服務(wù)，則令dij＝＋∞；尋找一個合適的子集S?F，｜S｜＝p，使得目標(biāo)函數(shù)達(dá)到最小值。

1.2 分散搜索算法的實現(xiàn)

分散搜索算法的基本框架包含5個子模塊：多樣性解的產(chǎn)生過程、解優(yōu)化過程、參考集更新過程、子集產(chǎn)生過程和解組合過程。算法的基本流程［12］如圖1所示：首先，通過多樣性解產(chǎn)生過程生成若干初始解，并對部分或全部解進(jìn)行優(yōu)化，得到初始解集（Population）；然后，進(jìn)行參考集（Refset）更新、子集（Subset）產(chǎn)生和解組合的迭代過程；最后，當(dāng)參考集不再發(fā)生變化時，算法結(jié)束。根據(jù)以上基本框架，將串行分散搜索算法實現(xiàn)分為初始化和計算兩個主要步驟。初始化包括：初始解產(chǎn)生、部分解的優(yōu)化、初始解集和參考集的構(gòu)建；計算包括：子集的產(chǎn)生、解組合和參考集的更新。串行分散搜索算法的具體實現(xiàn)過程描述如下：

圖1 分散搜索算法的基本流程Fig.1 Scatter search diagram

（1）構(gòu)建初始解集（Population）。初始解集大小為PSize，其中包含HSize個高質(zhì)量解。首先，用隨機(jī)方法生成PSize個初始解構(gòu)成Population，依據(jù)初始解的目標(biāo)函數(shù)值（cost）由小到大的順序排序；然后，從Population中任取HSize個初始解，分別對其進(jìn)行解優(yōu)化，從而獲得HSize個高質(zhì)量解。在初始解集的優(yōu)化過程中，需保證Population中不能出現(xiàn)完全相同的解，且始終保持有序。通過該方法產(chǎn)生的初始解集能滿足分散搜索算法要求的“多樣性”和“高質(zhì)量”特性：“多樣性”體現(xiàn)為解的隨機(jī)產(chǎn)生過程，而“高質(zhì)量”是通過解的優(yōu)化操作實現(xiàn)。

（2）解優(yōu)化過程。本文采用Densham－Rushton算法［13］的全局優(yōu)化過程完成解的優(yōu)化工作。優(yōu)化操作是一個反復(fù)迭代的過程。首先，從當(dāng)前解中刪除一個設(shè)施點，使得刪除后目標(biāo)函數(shù)值增加最少。然后，從備選設(shè)施點中選擇一個未選上的設(shè)施點插入當(dāng)前解中，使得插入后的目標(biāo)函數(shù)值減少最多。最后，判斷該交換過程能否改進(jìn)當(dāng)前解：若能則實施交換，繼續(xù)進(jìn)行上述迭代過程；否則，優(yōu)化過程結(jié)束。

（3）參考集（RefSet）的構(gòu)建與更新。參考集的大小為RSize，其中包括RSize1個高質(zhì)量解和RSize2個多樣性解（RSize1＋RSize2＝RSize）。參考集的構(gòu)建以初始解集Population為基礎(chǔ)。首先，從初始解集中選擇RSize1個質(zhì)量最高的解插入?yún)⒖技?，并從初始解集中刪除這些解。然后，評估初始解集中剩余解與參考集中現(xiàn)有解之間的相異度，從初始解集中選擇相異度最高的解插入?yún)⒖技?，并從初始解集中刪除該解；反復(fù)執(zhí)行這一過程，直到參考集中解的數(shù)量為RSize時，構(gòu)建過程結(jié)束。參考集的更新以解組合過程產(chǎn)生的新解集合Pool為基礎(chǔ)，更新方法同上。

（4）子集（SubSet）產(chǎn)生方法。本文采用最常用的二元子集方法。為了避免重復(fù)產(chǎn)生相同的解，只有參考集中的新解能用于子集的產(chǎn)生。

（5）解組合過程。解組合的目的是產(chǎn)生新解（存放于Pool解集中），為后續(xù)參考集的更新提供基礎(chǔ)解集。本文選用“求并－減點”的策略實現(xiàn)解的組合過程。首先，對子集中的兩個解S1和S2進(jìn)行求并操作得到新解S，此時p≤｜S｜≤2p（p為中心點數(shù)），S可能為不可行解。然后，從S中刪除一個設(shè)施點，使得刪除該點后解的目標(biāo)函數(shù)值增加最少；反復(fù)執(zhí)行該刪除操作直到S中設(shè)施點的個數(shù)為p。從S中搜索待刪除點的時間復(fù)雜度為O（n），組合過程的時間復(fù)雜度為O（n＊p）。由此可見，解組合過程是一個非常耗時的過程。

1.3 分散搜索算法的并行化

為了提高分散搜索的效率，本文設(shè)計了一種并行分散搜索算法（PSSA）。PSSA采用一種粗粒度的并行策略，即將串行算法中部分反復(fù)執(zhí)行的操作分配給不同進(jìn)程并行執(zhí)行，從而提高算法的運行效率。在串行分散搜索算法中，初始解的優(yōu)化和解組合過程占用了大量的運行時間（分別達(dá)到總運行時間的73%和13%）。因此，對這兩個過程進(jìn)行并行化可以大幅提升算法的效率。PSSA采用主從模式：主進(jìn)程負(fù)責(zé)高質(zhì)量解的回收、初始解集的構(gòu)建、參考集的生成與更新以及少量的初始解優(yōu)化和解組合任務(wù)；從進(jìn)程主要負(fù)責(zé)初始解的優(yōu)化和解組合操作。PSSA的流程圖如圖2所示。PSSA的實現(xiàn)過程如下。

圖2 PSSA流程圖Fig.2 Flow diagram of PSSA

（1）構(gòu)建初始解集。在初始解集的構(gòu)建過程中，對部分解的優(yōu)化操作是相互獨立的，因此可以采用任務(wù)并行的策略對其進(jìn)行并行化。首先，在各進(jìn)程內(nèi)隨機(jī)產(chǎn)生HSize／np（np為進(jìn)程數(shù)）個解并進(jìn)行優(yōu)化處理；然后，各從進(jìn)程將優(yōu)化后的高質(zhì)量解發(fā)送至主進(jìn)程，由主進(jìn)程完成初始解集的構(gòu)建。為了保證求解質(zhì)量，當(dāng)HSize無法被np整除時，需調(diào)整各進(jìn)程內(nèi)產(chǎn)生高質(zhì)量解的個數(shù)。調(diào)整的原則是：各進(jìn)程產(chǎn)生高質(zhì)量解的個數(shù)相同（避免部分進(jìn)程閑置等待），且總數(shù)不小于HSize。通常，HSize的數(shù)目遠(yuǎn)小于PSize，因此，HSize的小幅增加不會影響初始解集的多樣性，反而能加快搜索的收斂速度。

（2）參考集的更新與同步。主進(jìn)程根據(jù)更新后的參考集是否發(fā)生變化決定算法是否終止：若參考集無變化，則算法結(jié)束；否則，主進(jìn)程需將參考集中新產(chǎn)生的解廣播給各從進(jìn)程。在廣播過程中，首先由主進(jìn)程向各從進(jìn)程廣播參考集中新解的個數(shù)，各從進(jìn)程收到消息后建立大小對應(yīng)的接收緩沖區(qū)；然后由主進(jìn)程向各從進(jìn)程廣播參考集中的新解。隨著算法迭代次數(shù)的增加，參考集中的新解個數(shù)會不斷降低。因此，該方法能有效地減少冗余通信。

（3）解組合過程。解組合過程中不同子集上的組合操作是相互獨立的，因此可以采用區(qū)域分解的策略對其進(jìn)行并行化。首先，將所有二元子集平均分配至各進(jìn)程，由各進(jìn)程分別對部分子集進(jìn)行合并操作；然后，各從進(jìn)程將合并產(chǎn)生的新解發(fā)送至主進(jìn)程，由主進(jìn)程進(jìn)行參考集的更新操作。由于二元子集的產(chǎn)生是一個計算量很小的過程，其計算時間遠(yuǎn)小于將其廣播至各從進(jìn)程的通信時間。因此，為了減少通信量，各進(jìn)程均執(zhí)行一次子集產(chǎn)生操作，而非由主進(jìn)程產(chǎn)生子集后分發(fā)給各從進(jìn)程。各進(jìn)程完成子集產(chǎn)生過程后，根據(jù)其進(jìn)程編號和總進(jìn)程數(shù)計算屬于該進(jìn)程的子集，對它們進(jìn)行解組合操作產(chǎn)生新解，然后將這些新解發(fā)回主進(jìn)程。

（4）結(jié)果輸出。計算結(jié)束后，由主進(jìn)程將最優(yōu)解以空間數(shù)據(jù)表的形式輸出至PostgreSQL數(shù)據(jù)庫。輸出結(jié)果包含一張點表和一張線表：點表含有p條記錄（p為中心點數(shù)），每條記錄為一個設(shè)施點，屬性數(shù)據(jù)包括分配到該設(shè)施點的所有用戶點的距離總和、用戶點個數(shù)等；線表含有n條記錄（n為用戶點個數(shù)），每條記錄為一個用戶點，屬性數(shù)據(jù)包括該用戶點所屬設(shè)施點的編號、服務(wù)距離等。

2 實驗

為了測試PSSA的運行效率和求解質(zhì)量，筆者在Visual Studio 2010環(huán)境下使用C?語言進(jìn)行PSSA的實現(xiàn)，并應(yīng)用模擬的路網(wǎng)數(shù)據(jù)進(jìn)行了相關(guān)實驗。實驗數(shù)據(jù)包括3個不同規(guī)模的數(shù)據(jù)集，如表1所示。并行環(huán)境為一臺雙核PC（CPU為Intel Core i3 530，內(nèi)存為3.24GB）和一臺四核PC（CPU為Intel Core i5－2400，內(nèi)存為3.24GB）組成的 Windows PC集群，消息傳遞接口采用MPICH2。

表1 測試數(shù)據(jù)集Table 1 Experimental data sets

實驗中分別應(yīng)用Densham－Rushton（DR）算法與PSSA算法（1～6進(jìn)程），在3個不同規(guī)模的數(shù)據(jù)集中，求解100個中心點的p－中心定位問題。其中，PSSA的元啟發(fā)參數(shù)為：PSize＝100，HSize＝5，RSize＝10，RSize1＝5，RSize2＝5。由于DR算法與PSSA的結(jié)果均依賴于初始解，每次得到的解會略有不同。因此，所有實驗結(jié)果（包括運行時間和解質(zhì)量）均為10次反復(fù)運行后的平均值。運行結(jié)果分析如下。

（1）運行效率。如表2所示，PSSA具有良好的并行效率。當(dāng)進(jìn)程數(shù)為1、2、3時，運行時間隨著進(jìn)程數(shù)的增加而減少；當(dāng)進(jìn)程數(shù)為5時運行時間最短，比串行分散搜索算法減少了近60%，已經(jīng)與DR算法相當(dāng)。但當(dāng)進(jìn)程數(shù)由3變?yōu)?和由5變?yōu)?時，運行時間沒有減少，反而出現(xiàn)增加的現(xiàn)象。其原因是：當(dāng)進(jìn)程數(shù)為3或4時，為了保證高質(zhì)量解的總數(shù)不小于HSize（實驗中HSize＝5），每個進(jìn)程分別生成2個高質(zhì)量解（總數(shù)分別為6和8）；此時，各進(jìn)程的運算量沒有減少，而通信量有所增加（通信時間增加），所以運行時間也會相應(yīng)增加。因此，當(dāng)HSize為np的整數(shù)倍時（np為進(jìn)程數(shù)，HSize為高質(zhì)量解個數(shù)），PSSA算法的并行效率最好。

表2 運行時間的對比Table 2 Comparison of running time

（2）解質(zhì)量。表3中目標(biāo)函數(shù)值為將用戶點按距離最近分配到各設(shè)施點后的距離總和。第一列為DR算法求得的目標(biāo)函數(shù)值，第二到七列分別為PSSA（1～6進(jìn)程）得到的結(jié)果較DR算法結(jié)果的改進(jìn)比例。由表中數(shù)據(jù)可以看出，PSSA得到的結(jié)果均優(yōu)于DR算法，將目標(biāo)函數(shù)值降低了0.4%～0.9%。

在數(shù)據(jù)集pmp＿5569＿7667中，PSSA得到的結(jié)果如圖3所示。該區(qū)域覆蓋東北及華北部分地區(qū)，中心點數(shù)為100。五角星表示最終解的設(shè)施點；所有用戶點用一條直線與其所屬設(shè)施點相連，便于分析人員定位。

表3 解質(zhì)量的對比Table 3 Comparison of results

圖3 PSSA計算結(jié)果（數(shù)據(jù)集：pmp＿5569＿7667）Fig.3 PSSA′s result on data set pmp＿5569＿7667

3 結(jié)論

本文基于分散搜索實現(xiàn)了高效的p－中心定位算法，并采用主從模式對串行算法中較耗時的解優(yōu)化和解組合過程進(jìn)行并行化，實現(xiàn)了解算p－中心定位問題的并行分散搜索算法（PSSA）。基于不同規(guī)模路網(wǎng)數(shù)據(jù)的實驗表明：1）PSSA具有良好的加速比，高質(zhì)量解個數(shù)為進(jìn)程數(shù)的整數(shù)倍時，并行效率最高；2）盡管PSSA算法的運行時間與DR算法相當(dāng)，但PSSA算法獲得了更高質(zhì)量的解（目標(biāo)函數(shù)值較DR算法降低0.4%～0.9%），兼顧了算法的高效率與解的高質(zhì)量。

［1］ 黎青松，楊偉，曾傳華.中心問題與中位問題的研究現(xiàn)狀［J］.系統(tǒng)工程，2005，23（5）：11－16.

［2］ HAKIMI S L.Optimum locations of switching centers and theabsolute centers and medians of a graph［J］.Operations Research，1964，12（3）：450－459.

［3］ GAREY M，JOHNSON D.Computers and Intractability：A Guide to the Theory of Np－completeness［M］.Freeman，1979.

［4］ 都志輝.高性能計算并行編程技術(shù)：MPI并行程序設(shè)計［M］.北京：清華大學(xué)出版社，2001.6－11.

［5］ MLADENOVIC N，BRIMBERG J，HANSEN P，et al.The pmedian problem：A survey of metaheuristic approaches［J］.European Journal of Operational Research，2007，179：927－939.

［6］ TSENG L Y，WU C S.The multistart drop－add－swap heuristic for the uncapacitated facility location problem［C］.The 6th International Conference on Informatics in Control，Automation and Robotics，Intelligent Control Systems and Optimization.INSTICC Press，2009.21－28.

［7］ 徐先瑞，李響，李小杰.改進(jìn)的求解約束P－Median問題的分散搜索算法［J］.計算機(jī)工程與應(yīng)用，2011，47（20）：28－30.

［8］ ALCARAZ J，LANDETE M，MONGE J F.Design and analysis of hybrid metaheuristics for the reliability p－median problem［J］.European Journal of Operational Research，2012，222（1）：54－64.

［9］ LANDA－TORRES I，SER J D，SALCEDO－SANZ S，et al.A comparative study of two hybrid grouping evolutionary techniques for the capacitated p－median problem［J］.Computers ＆Operations Research，2012，39（9）：2214－2222.

［10］ CADENAS J M，CANóS M J，GARRIDO M C，et al.Soft－computing based heuristics for location on networks：The p－median problem［J］.Applied Soft Computing，2011，11（2）：1540－1547.

［11］ GARCíA－LóPEZ F，MELIáN－BATISTA B，MORENO－PéREZ J A，et al.Parallelization of the scatter search for the p－median problem［J］.Parallel Computing，2003，29（5）：575－589.

［12］ RESENDE M G C，RIBEIRO C C，GLOVER F，et al.Scatter Search and Path－Relinking：Fundamentals，Advances，and Applications，in Handbook of Metaheuristics［M］.Springer，2010.87－107.

［13］ DENSHAM P J，RUSHTON G.A more efficient heuristic for solving large p－median problems［J］.Papers in Regional Science，1992，71（3）：307－329.