基于網絡Voronoi圖啟發式和群智能的最大覆蓋空間優化

謝順平，馮學智，都金康

南京大學地理與海洋科學學院，江蘇南京210093

基于網絡Voronoi圖啟發式和群智能的最大覆蓋空間優化

謝順平，馮學智，都金康

南京大學地理與海洋科學學院，江蘇南京210093

提出一種基于網絡Voronoi面域圖的最大覆蓋選址模型及相應的粒子群優化方法，為城市化區域響應敏感型公共服務設施的空間優化提供技術方法?？紤]設施功能沿交通網絡傳導以及需求非均勻連續分布情形，對設施在網絡連續空間上進行布局優化，選址模型采用網絡Voronoi面域圖劃分布局設施的功能輻射域，以啟發空間優化最小化重疊覆蓋。模型最大化設施利用效率，設施功能對覆蓋半徑以內的需求完全覆蓋，對覆蓋半徑以外的需求部分覆蓋。提出一種集成遺傳機制和廣義Voronoi圖的改進粒子群算法，以提高連續網絡空間內的空間優化性能。對南京市消防站最大覆蓋選址優化的試驗表明，該研究取得較為理想的結果。

網絡Voronoi面域圖；空間優化；最大覆蓋選址模型；Voronoi圖啟發式；粒子群算法

1 引 言

空間優化作為GIS實現空間決策的一項關鍵技術，已成為相關領域研究熱點，隨著計算機科學、人工智能、地理空間分析技術的發展，使得有效解決城市化區域復雜的空間優化問題成為可能。Voronoi圖空間分析模型在位置問題描述、模擬位置產生的空間結構、選址模型構建、圖啟發式等方面具有獨特功能和應用潛力，一些學者研究了Voronoi圖在空間優化分析中的理論和方法。文獻［1］較早提出解決p－中心問題的Voronoi圖啟發式方法，即初始在區域內隨機產生p個中心位置，構建相應的Voronoi圖，將p個中心再移位到對應Voronoi多邊形的1－中心解上，如果最大中心位移小于預設容限，則問題獲解。否則，繼續構建Voronoi圖迭代。文獻［2］就可通過Voronoi圖啟發式求解的一類連續位置優化問題進行了深入討論，并給出用Voronoi圖參與描述的連續p－中值問題選址模型和相稱問題選址模型。文獻［3］認為設施布局選址的純解析計算可變換為圖論與解析計算相結合問題，并將全局范圍內的p－中值選址轉化為基于Voronoi圖的分區p－中值選址。文獻［4—5］提出了一種啟發式Voronoi圖算法，以解決限制空間中離散需求點p－中心問題和覆蓋問題。文獻［6］發展了一種確定有限數目相同傳感器位置的Voronoi圖啟發式方法，使用Voronoi圖評估非檢測概率并引導搜索方向。此外，Voronoi圖還被應用于空間競爭分析模型［7］。

近年來，隨著城市交通網絡體系的完善，可達性和距離的時間效應改變了人們的擇近視角。交通網絡對城市公共服務設施服務范圍的影響日趨明顯，常規Voronoi圖分析應用于城市化區域的局限性和缺陷逐漸顯現。這種基于平面歐氏距離的空間分割方法由于未能體現城市空間傳導和阻隔機制，因而不能準確表達城市化區域服務域的空間形態［8］。作為其適應道路網絡環境的擴展模型，網絡Voronoi面域圖是一種基于網絡路徑代價（長度、時間、費用、效率等）距離度量的空間劃分模型。它通過最短路徑分析分別對網絡空間中的結點和弧段進行鄰近最近發生元的分割，進而采用面線鄰近分析對平面空間進行劃分而成，可模擬城市各類功能輻射與吸引的網絡傳導機制和服務覆蓋格局，更適用于城市化區域的空間分析［8－12］。文獻［8—9］在評估城市零售商業需求分布中用路徑時間代替路徑距離，并認為網絡Voronoi圖是劃分城市化區域功能服務域較為精確的方法，國內學者也開始研究網絡Voronoi面域圖的構建算法及其在城市商業設施服務域分析中的應用［10－12］。隨著網絡Voronoi圖模型及其構建算法的成熟，這一模型參與城市空間分析和空間優化將成為趨勢。

空間優化問題的精度、規模和復雜性要求優化算法具有更高的啟發式性能，以克服優化過程中的計算瓶頸。粒子群優化算法具有獨特與簡潔的仿生進化機制和突出的尋優能力，尤其對目標函數及其約束條件的連續性和凸性具有較強的抗差性［13－14］，是極具空間優化應用潛力的群智能啟發式方法［15－17］。由于空間優化基于空間位置分布評估的特點，需要模擬由位置產生的空間結構參與分析和啟發。將網絡Voronoi圖啟發式和智能啟發式結合起來，充分發揮各自的優勢和結合增強的優化性能，是解決城市化區域復雜空間優化問題的一條值得探索的途徑。

2 最大覆蓋選址模型

2.1 最大覆蓋選址模型及其研究進展

現實中有一類設施的功能或提供的服務受時間和距離制約，如消防站、急救中心、救援中心等一些應急服務設施，這類設施提供的服務具有較強的時效性，它們必須在規定的時間內響應服務請求并實現服務。因此，這類設施必須布設在與潛在需求分布特定的距離以內，才有可能提供有效的服務，確定這類設施的優化位置屬于覆蓋問題范疇［18］。有集合覆蓋與最大覆蓋兩類覆蓋問題。集合覆蓋問題模型的目標是用最少的設施配置用去覆蓋所有需求。通常，滿足覆蓋全部需求的設施建設成本難以承受，并會導致設施利用率降低。如果在限定設施數目條件下，確定它們的位置使得覆蓋盡可能多的需求量，這就是最大覆蓋問題（maximal covering location problem，MCLP）。由于最大覆蓋問題的實用意義較為突出，已成為相當一段時期該領域的研究熱點［18－24］。

文獻［19］針對現有研究需求點狀分布與現實的不符，借助GIS用多邊形空間目標表達需求分布，給出融合協同部分功能覆蓋的最大覆蓋模型。文獻［20］研究了基于區域內分割面元的需求表達的覆蓋建模方法，并成功應用于都柏林城市區域警報設施選址優化。文獻［21—22］認為設施對覆蓋半徑以外的需求仍有逐步衰減的功能覆蓋，并研究了可變半徑覆蓋、逐級覆蓋、協同覆蓋等的廣義覆蓋問題。文獻［23］研究了通過適度完善道路網絡系統改善醫療服務設施對剛果偏遠地區最大覆蓋的優化模型。文獻［24］在基于時間滿意的網絡最大覆蓋選址問題中，將覆蓋半徑的概念由從設施角度出發，轉變為由離散需求點視角出發?？梢钥闯?，最新的最大覆蓋空間優化研究已開始顧及需求的連續面狀分布、交通網絡影響和有限資源條件下的部分覆蓋策略等，但待優化設施基本只能在網絡結點集或預定的一組候選點集上布設，缺乏基于道路網絡環境分析的最大覆蓋實用模型和空間分割圖形啟發式與智能啟發式結合的空間優化方法。

2.2 基于網絡Voronoi圖的最大覆蓋模型

本文設計的最大覆蓋模型考慮需求在區域內連續非均質分布，規定覆蓋半徑由設施站點角度出發，設施功能對覆蓋半徑以內的需求完全覆蓋，對覆蓋半徑以外需求部分覆蓋，部分覆蓋強度隨距離逐步衰減。在限定資源條件下，追求設施功能的非重疊覆蓋是最大化覆蓋效率的前提。由于網絡Voronoi面域圖是對功能覆蓋的非重疊分割，優化算法最大化這種分割所達到的設施功能覆蓋需求總和，必然會最小化重疊覆蓋，所以基于網絡Voronoi面域圖的最大覆蓋模型具有啟發最小化重疊覆蓋的性能。

網絡上的最大覆蓋問題可分為連續最大覆蓋問題和離散最大覆蓋問題，其差別在于設施可以在整個網絡路段上布設，還是只能在網絡節點上布設。網絡連續最大覆蓋問題是頗具挑戰性的空間優化難題，但其實用意義卻是顯而易見的。根據最大覆蓋問題的性質，設施覆蓋域為以覆蓋半徑確定的網絡輻射緩沖區，考慮部分覆蓋時，還要顧及功能輻射呈逐步衰減的外延緩沖帶。追求重復覆蓋的最小化要求在最大覆蓋模型中不考慮重復覆蓋的需求統計，因此，網絡Voronoi圖是非常適合的功能覆蓋提取模型。為此，本文提出的基于網絡Voronoi圖的連續最大覆蓋問題的數學模型描述如下

式中

n為參與配置和優化的設施數，n個設施分別為s1，s2，…，sn，它們的位置由粒子群優化過程中產生的代表一種設施布局方案的一個粒子坐標提供；p為需求點；vi為設施si的網絡Voronoi多邊形覆蓋區域，vi內分布的需求p到設施的距離由兩部分組成，其中dE（p，pm）為vi內需求p點到最近道路的直線路徑代價距離，dN（pm，si）為需求點p鄰近道路上的最近點pm到網絡上最近設施si的網絡路徑代價距離，當采用路徑長度代價時，dE（p，pm）與等長度的道路路徑代價相同，當采用路徑時間代價時，dE（p，pm）與等長度最低等級道路路徑時間代價相同；f為點p處的需求密度；dp為p點處的面積微元；k（d）為距離衰減函數；R為覆蓋半徑；C為大于1的常數，如果距離d從R到2R，k（d）從1.0衰減到0.1，則C取值為101／R，當然，k（d）亦可采用線性衰減方式。最大覆蓋模型目標函數的計算可由集成到網絡Voronoi面域圖模型中的信息獲取與分析計算功能實現［10］，通過與預先空間柵格離散化的區域需求疊加處理，提取各個網絡Voronoi多邊形區域內的需求信息，并進行目標函數的計算。顯然，上述模型追求布局設施通過道路網絡去覆蓋最大的區域需求總量。

3 粒子群空間優化

粒子群優化（PSO）是一種基于群體搜索的算法，它建立在模擬鳥群社會的基礎之上。文獻［14］對Heppner模型進行了修正，模擬由眾多無質量和體積的粒子組成的群體在搜索空間中以一定的矢量速度飛行，每個粒子在搜索時，考慮自己曾搜索到的最好解和鄰域或群體內其他粒子搜索到的歷史最好解，并據此調整自身的飛行速度和位置，使粒子能夠飛向解空間，并在最優解處積聚。自粒子群算法提出以來，引起相關領域學者的關注并成為優化應用研究熱點，針對具體應用出現了各種改進方法［13－14］。本研究在帶慣性權重的粒子群算法中集成了改善全局搜索性能的方法，融入遺傳交叉機制以使性能低劣的粒子得到進化，從而提高整個群體的全局優化搜索性能。

3.1 空間優化粒子群算法模型

一個設施k的位置可表示為（xk，yk），對優化的n個設施空間位置問題，粒子群中一個粒子個體表示了對n個設施的一種空間布局試探方案，每個粒子具有n個設施位置分量，粒子位置可表示為（s1，s2，…，sn），其中sk為設施k的坐標點。由于每個點又有x和y兩個坐標分量，所以每個粒子的坐標分量有2n個，算法優化時粒子在2n維空間飛行，粒子的位置向量可表示為（x1，y1，x2，y2，…，xn，yn）。如果考慮不同的粒子個體，則粒子i的位置向量表示為（xi1，yi1，xi2，yi2，…，xin，yin），粒子i的速度向量可表示為粒子i的歷史最好位置表示為（pi1，pi2，…，pin），整個群體或鄰域子群的歷史最好位置表示為（pg1，pg2，…，pgn）。由此對帶慣性權重的粒子群優化算法的速度迭代模型和位置迭代模型調整如下

3.2 融入遺傳交叉機制

粒子群算法在每一次迭代對所有粒子的速度和位置更新前，先對所有粒子在其當前位置處的適應值按從優到劣進行排序，對前80%適應值較好的粒子按標準粒子群算法速度和位置模型更新，對其余20%適應值較差的粒子按遺傳交叉機制更新。算法在適應值較好的粒子中隨機選擇出占群體總數20%的粒子，通過將它們隨機地兩兩交叉，產生的相同數量后代粒子取代群體中適應值較差的粒子，以使這些粒子搜索能力得到進化，同時增強整個粒子群體脫離局部最優的能力。

用a和b表示被選擇的兩個參與交叉的個體指針，通過交叉算法由兩個父代個體產生子代個體位置和飛行矢量的計算公式表示如下［14］

式中，ri～（U（0，1）。經過交叉操作，由兩個父代粒子的位置按隨機的遺傳比例產生了兩個子代粒子的位置，速率交叉只有方向受到影響，數量沒有變化。

3.3 粒子位置分量飛行空間的設計

網絡連續型最大覆蓋模型中的所有待優化設施可以布設在網絡路段上的任意位置。在粒子群算法中，直接在連續的網絡路段軌跡空間中設計設施位置的飛行操作非常困難?？紤]到網絡上布局的設施與周圍需求分布強度的空間關聯性，即二維空間分布的需求強度對布設設施具有引力，為了使粒子群優化算法的飛行導向啟發機制與尋優性能得以保持和發揮，本文預先建立道路網絡空間與二維平面空間之間映射關系，通過構建道路路段的廣義Voronoi圖實現這種映射。優化算法讓粒子個體的每個設施位置分量在二維空間飛行，當某個設施位置飛入到某條路段的Voronoi多邊形內部時，該條路段上的最近點即為該設施對應的當前網絡空間飛行位置。這種轉換機制確保了在高維空間飛行粒子的各個設施位置在網絡空間連續飛行，配合粒子群算法使優化進程朝正確的方向拓展，從而實現網絡上的連續空間優化。

4 空間優化計算與結果分析

4.1 試驗數據與優化參數

本試驗對南京市主城區14個消防設施的位置使用最大覆蓋模型進行空間優化，優化目標為覆蓋盡可能多的城區人口和最小化重疊覆蓋，即在限定資源前提下最大限度提高公共安全設施的配置與利用效率。由于獲取更詳細人口分布資料的限制，本試驗以南京市主城各行政區屬街道區域為人口的最小統計單位，行政街道區域單元內的人口密度視為均勻分布，以此作為空間優化試驗區內需求強度非均勻分布的依據。本試驗的網絡分析采用路徑長度距離作為連接代價，消防設施完全覆蓋區域設置為網絡路徑距離2.5km以內，超過該距離設施功能呈逐步衰減的部分覆蓋。優化算法的群體規模設置為50，最大迭代次數為1 500次，速度慣性權重初值1.0、終值0.5。對迭代中每個粒子表示的14個設施的一種布局試探方案，通過計算相應的網絡Voronoi面域圖，獲取各設施覆蓋的需求信息，通過模型計算其適應值，當一輪迭代所有粒子的適應值獲得后，按照改進的粒子群算法粒子更迭機制進化整個粒子種群。在空間優化計算的迭代過程中，為評估所有產生的粒子所表示的各種設施布局方案性能，共需計算生成75 000幅網絡Voronoi面域圖。

4.2 優化結果分析

圖1分別給出了為采用網絡Voronoi面域圖分析的優化前后設施的最大覆蓋區域。從分圖（a）可以看出，現有設施布局功能重疊覆蓋嚴重，同時又存在較大面積未被消防功能完全覆蓋的區域。從分圖（b）和分圖（c）中可以看出，優化布局后的設施主要布設在人口稠密區域，人口密度較低地區和風景區基本未被空間優化出的設施功能覆蓋。存在其他未被覆蓋的區域主要反映出優化設施趨向于布設在路網和人口密度均比較高的區域，以獲得最大的覆蓋效率，同時也反映出現有消防站數量不能滿足對主城區人口的完全功能覆蓋。

表1列出了優化前后按完全覆蓋人口排序的南京市主城區14個消防設施功能的完全覆蓋面積、完全覆蓋人口、綜合覆蓋人口（含部分覆蓋）、網絡Voronoi圖輻射域人口，圖2反映現有設施和優化設施完全覆蓋人口對比?？梢钥闯?，大部分優化后的設施比現有設施覆蓋更多人口，優化后的設施合計完全覆蓋人口185.74萬，占主城區人口的79.17%，比現有設施完全覆蓋人口提高32.18萬，增幅達21%；綜合覆蓋人口由優化前的186.68萬提高到優化后的213.72萬，增幅達14.5%。圖3為本次優化試驗過程模型目標函數值變化曲線。

圖1 網絡Voronoi面域圖分析的現有設施和優化設施的完全覆蓋域Fig.1 Fully covering areas of present facilities and optimized facilities analyzed by NVAD

表1 南京市現有設施和優化設施覆蓋信息Tab.1 Covering information of present facilities and optimized facilities in Nanjing

為比較網絡Voronoi面域圖啟發式、常規Voronoi圖啟發式和圓形緩沖區需求分析對最大覆蓋空間優化效果的影響，本文分別對基于后兩種情形的最大覆蓋模型也進行了空間優化試驗，并統一采用能夠真實反映城市化區域設施需求覆蓋效果的網絡Voronoi面域圖對三種優化獲得的設施布局進行評估（表2）?？梢钥闯?，基于網絡Voronoi面域圖啟發式優化獲得了功能對需求最高的完全覆蓋和綜合覆蓋，常規Voronoi圖啟發式優化因未考慮道路對功能覆蓋的影響，使得優化得到的設施布局實際覆蓋的需求低于前者和常規Voronoi圖評估結果，同樣，通過圓形緩沖區分析的優化既忽略道路影響，又可能包含重疊覆蓋統計，對其優化的設施布局進行基于網絡環境的評估自然不夠理想。

圖2 優化前后設施完全覆蓋人口對比Fig.2 Contrast of fully covering population of present facilities and optimized facilities

圖3 粒子群優化過程目標函數變化曲線Fig.3 Change of object function in particle swarm optimization process

表2 網絡Voronoi面域圖評估的不同最大覆蓋模型優化結果比較Tab.2 Comparison of spatial optimization results based on different maximal covering location models estimated by NVAD

5 結 論

城市化區域多設施最大覆蓋科學選址是復雜的空間優化問題，需要對城市空間作用機制的真實模擬和更強的啟發式性能，新型空間分析模型、空間選址模型和計算智能方法的結合將成為趨勢。城市公共服務設施使用效率的最大化對優化公共資源配置、追求公共服務公平性具有重要的實現意義。本文提出了基于網絡Voronoi面域圖啟發式的最大覆蓋選址模型，并結合改進粒子群空間優化方法進行了較為深入的研究，獲得如下結論：

（1）基于網絡Voronoi面域圖的最大覆蓋模型具有啟發最小化重疊覆蓋、最大化覆蓋需求的功能，模型顧及完全覆蓋和部分覆蓋，可以在有限資源條件下，充分發揮城市化區域設施的配置與利用效率。

（2）網絡Voronoi圖啟發式與群智能啟發式相結合，可形成兩種啟發式功能優勢互補的技術集成，為產生更強的啟發式創造了條件，有益于增強解決復雜的空間優化問題的能力。

（3）將遺傳進化機制引入粒子群算法，可以提高算法的全局優化性能，廣義Voronoi圖能夠實現布局設施位置飛行由二維空間到網絡空間的轉換，為解決復雜的網絡連續空間優化提供支持。

（4）試驗區現有消防站空間布局不盡合理，功能重疊覆蓋嚴重且存在較大服務盲區，消防站數量不足，通過空間優化，可大幅提高現有消防設施的利用效率。

本研究提出的最大覆蓋模型和改進粒子群優化算法可應用于支持城市化區域公共安全和應急救護等服務設施的最大覆蓋空間優化決策。當然，本研究還存在一些不足和需要改進的方面，如采用地統計與空間分析結合的方法獲得更詳細的需求分布數據；根據某些設施的特點，可以考慮采用基于需求出發的網絡Voronoi功能吸引域分析與啟發的最大覆蓋模型；優化過程需要的計算開銷較大，仍需進一步改進和提高圖形計算和優化計算的效率；進一步開展基于網絡路徑時間代價分析的空間優化研究。

［1］ SUZUKI A，DREZNER Z.The p－center Location Problem in an Area［J］.Location Science，1996（4）：69－82.

［2］ OKABLE A，SUZUKI A.Locational Optimization Problems Solving through Voronoi Diagrams［J］.Europe Journal Operation Research，1997（98）：445－456.

［3］ CHEN Jun，ZHAO Renliang，QIAO Chaofei.Voronoi Diagram－based GIS Spatial Analysis［J］.Geomatics and Information Science of Wuhan University，2003，28（Special Issue）：32－37.（陳軍，趙仁亮，喬朝飛.基于Voronoi圖的GIS空間分析研究［J］.武漢大學學報：信息科學版，2003，28（特刊）：32－37.）

［4］ DAVOODI M，MOHADES A，REZAEI J.Solving the Constrained p－center Problem Using Heuristic Algorithms［J］.Applied Soft Computing，2011（11）：3321－3328.

［5］ DAVOODI M，MOHADES A.Solving the Constrained Coverage Problem［J］.Applied Soft Computing，2011（11）：963－969.

［6］ CAVALIER T M，CONNER W A，DE CASTILLO E，et al.A Heuristic Algorithm for Minimax Sensor Location in the Plane［J］.European Journal of Operational Research，2007（183）：42－55.

［7］ ZHU Weining，MA Jingsong，HUANG Xingyuan，et al.A Study of GIS Spatial Competition Analysis Model Based on Projective Weighted Voronoi Diagrams［J］.Acta Geodaetica et Cartographica Sinica，2004，33（2）：146－150.（朱渭寧，馬勁松，黃杏元，等.基于投影加權Voronoi圖的GIS空間競爭分析模型研究［J］.測繪學報，2004，33（2）：146－150.）

［8］ OKABLE A，SATOH T，FURUTA T，et al.Generalized Network Voronoi Diagrams：Concepts，Computational Methods and Applications［J］.International Journal of Geographical Information Science，2008，22（9），965－994.

［9］ OKABLE A，OKUNUKI K.A Computational Method for Estimating the Demand of Retail Stores on a Street Network and Its Implementation in GIS［J］.Transactions in GIS，2001，5（3）：209－220.

［10］ WANG Xinsheng，YU Ruilin，JIANG Youhua.Delimitating the Store Market Field Based on the Metric of the Cityblock Distance［J］.Geographical Research，2008，27（1）：85－92.（王新生，余瑞林，姜友華.基于道路網絡的商業網點市場域分析［J］.地理研究，2008，27（1）：85－92.）

［11］ XIE Shunping，FENG Xuezhi，LU Wei.Algorithm for Constructing Voronoi Area Diagram Based on Road Network Analysis［J］.Acta Geodaetica et Cartographica Sinica，2010，39（1）：88－94.（謝順平，馮學智，魯偉.基于道路網絡分析的Voronoi面域圖構建算法［J］.測繪學報，2010，39（1）：88－94.）

［12］ XIE Shunping，FENG Xuezhi，WANG Jiechen，et al.Research for Radiation Domain of Commercial Centers in Nanjing Based on Analysis of Road Network Weighted Voronoi Diagram［J］.Acta Geographica Sinica，2009，64（1）：1467－1476.（謝順平，馮學智，王結臣，等.基于道路網絡加權Voronoi圖分析的南京市商業中心輻射域研究［J］.地理學報，2009，64（12）：1467－1476.）

［13］ KENNEDY J，EBERHART R C.Particle Swarm Optimization［C］∥Proc of IEEE International Conference on Neural Networks.Perth：IEEE，l995：1942－1948.

［14］ ZENG Jianchao，JIE Jing，CUI Zhihua.Particle Swarm Optimization［M］.Beijing：Science Press，2004.（曾建潮，介婧，崔志華.微粒群算法［M］.北京：科學出版社，2004.）

［15］ DU Guoming，CHEN Xiaoxiang，LI Xia.Spatial Optimal Search Based on Particle Swarm Optimization［J］.Acta Geographica Sinica，2006，61（12）：1290－1298.（杜國明，陳曉翔，黎夏.基于粒子群優化算法的空間優化決策［J］.地理學報，2006，61（12）：1290－1298.）

［16］ LI Haibo，LI Xia，LIU Xiaoping，et al.Particle－swarm Optimization for Site Selection with Contiguity Constraints［J］.Journal of Remote Sensing，2008，12（5）：724－733.（黎海波，黎夏，劉小平，等.多目標粒子群算法與選址中的形狀優化［J］.遙感學報，2008，12（5）：724－733.）

［17］ YAPICIOGLU H，SMITH A E，DOZIER G.Solving the Semi－desirable Facility Location Problem Using Bi－objective Particle Swarm［J］.European Journal of Operational Research，2007（177）：733－749.

［18］ CHURCH R L，REVELLE C S.The Maximal Covering Location Problem［J］.Papers of the Regional Science Association，1974（32）：101－118.

［19］ ALEXANDRIS G，GIANNIKOS I.A New Model for Maximal Coverage Exploiting GIS Capabilities［J］.European Journal of Operational Research，2010（202）：328－338.

［20］ MURRAY A T，O’KELLY M E，CHURCH R L.Regional Service Coverage Modeling［J］.Computers ＆Operations Research，2008（35）：339－355.

［21］ BERMAN O，DREZNER Z，KRASS D，et al.The Variable Radius Covering Problem［J］.European Journal of Operational Research，2009（196）：516－525.

［22］ BERMAN O，DREZNER Z，KRASS D.Generalized Coverage：New Developments in Covering Location Models［J］.Computers ＆Operations Research，2010（37）：1675－1687.

［23］ MURAWSKI L，CHURCH R L.Improving Accessibility to Rural Health Services：The Maximal Covering Network Improvement Problem［J］.Socio－economic Planning Sciences，2008（43）：102－110.

［24］ MA Yunfeng，YANG Chao，ZHANG Min，et al.Timesatisfaction－based Maximal Covering Location Problem［J］.Chinese Journal of Management Science，2006，14（2）：45－51.（馬云峰，楊超，張敏，等.基于時間滿意的最大覆蓋選址問題［J］.中國管理科學，2006，14（2）：45－51.）

Maximal Covering Spatial Optimization Based on Network Voronoi Diagrams Heuristic and Swarm Intelligence

XIE Shunping，FENG Xuezhi，DU Jinkang
School of Geographic and Oceanographic Scienses，Nanjing University，Nanjing210093，China

A maximal covering location model based on network Voronoi area diagrams and particle swam optimization is proposed to provide the spatial optimization means for response sensitive public service facilities in urbanized area.It is taken into account that facilities function conducts along traffic network and variable demands distribute continuously，the facilities optimized can be located in continuous network space.The network Voronoi area diagrams are used to simulate the service areas of facilities in the maximal covering location model，which has heuristic to minimize overlap coverage in spatial optimization.The proposed model maximizes utilization of facilities，the demands within coverage radius are covered completely and the demands beyond coverage radius are covered partially by facilities function.An improved particle swam optimization algorithm integrated with genetic mechanism and generalized Voronoi diagram is proposed to enhance the optimization performance in continuous network space.The computational experiment for location optimization of fire stations in Nanjing shows that the proposed model and optimization algorithm have achieved desired results.

network Voronoi area diagram；spatial optimization；maximal covering location model；Voronoi diagrams heuristic；particle swarm optimization

XIE Shunping（1957—），male，PhD，senior engineer，majors in theory and application of GIS，spatial analysis and intelligent spatial optimization.

1001－1595（2011）06－0778－07

P208

A

國家863計劃（2008AA12Z106）

叢樹平）

2011－03－11

2011－09－20

謝順平（1957—），男，博士，高級工程師，研究方向為地理信息系統理論與應用、空間分析與智能空間優化。

E－mail：xiesp＠nju.edu.cn