基于網(wǎng)絡(luò)Voronoi圖啟發(fā)式和群智能的最大覆蓋空間優(yōu)化

謝順平，馮學(xué)智，都金康

南京大學(xué)地理與海洋科學(xué)學(xué)院，江蘇南京210093

基于網(wǎng)絡(luò)Voronoi圖啟發(fā)式和群智能的最大覆蓋空間優(yōu)化

謝順平，馮學(xué)智，都金康

南京大學(xué)地理與海洋科學(xué)學(xué)院，江蘇南京210093

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

網(wǎng)絡(luò)Voronoi面域圖；空間優(yōu)化；最大覆蓋選址模型；Voronoi圖啟發(fā)式；粒子群算法

1 引 言

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

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

空間優(yōu)化問(wèn)題的精度、規(guī)模和復(fù)雜性要求優(yōu)化算法具有更高的啟發(fā)式性能，以克服優(yōu)化過(guò)程中的計(jì)算瓶頸。粒子群優(yōu)化算法具有獨(dú)特與簡(jiǎn)潔的仿生進(jìn)化機(jī)制和突出的尋優(yōu)能力，尤其對(duì)目標(biāo)函數(shù)及其約束條件的連續(xù)性和凸性具有較強(qiáng)的抗差性［13－14］，是極具空間優(yōu)化應(yīng)用潛力的群智能啟發(fā)式方法［15－17］。由于空間優(yōu)化基于空間位置分布評(píng)估的特點(diǎn)，需要模擬由位置產(chǎn)生的空間結(jié)構(gòu)參與分析和啟發(fā)。將網(wǎng)絡(luò)Voronoi圖啟發(fā)式和智能啟發(fā)式結(jié)合起來(lái)，充分發(fā)揮各自的優(yōu)勢(shì)和結(jié)合增強(qiáng)的優(yōu)化性能，是解決城市化區(qū)域復(fù)雜空間優(yōu)化問(wèn)題的一條值得探索的途徑。

2 最大覆蓋選址模型

2.1 最大覆蓋選址模型及其研究進(jìn)展

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

文獻(xiàn)［19］針對(duì)現(xiàn)有研究需求點(diǎn)狀分布與現(xiàn)實(shí)的不符，借助GIS用多邊形空間目標(biāo)表達(dá)需求分布，給出融合協(xié)同部分功能覆蓋的最大覆蓋模型。文獻(xiàn)［20］研究了基于區(qū)域內(nèi)分割面元的需求表達(dá)的覆蓋建模方法，并成功應(yīng)用于都柏林城市區(qū)域警報(bào)設(shè)施選址優(yōu)化。文獻(xiàn)［21—22］認(rèn)為設(shè)施對(duì)覆蓋半徑以外的需求仍有逐步衰減的功能覆蓋，并研究了可變半徑覆蓋、逐級(jí)覆蓋、協(xié)同覆蓋等的廣義覆蓋問(wèn)題。文獻(xiàn)［23］研究了通過(guò)適度完善道路網(wǎng)絡(luò)系統(tǒng)改善醫(yī)療服務(wù)設(shè)施對(duì)剛果偏遠(yuǎn)地區(qū)最大覆蓋的優(yōu)化模型。文獻(xiàn)［24］在基于時(shí)間滿意的網(wǎng)絡(luò)最大覆蓋選址問(wèn)題中，將覆蓋半徑的概念由從設(shè)施角度出發(fā)，轉(zhuǎn)變?yōu)橛呻x散需求點(diǎn)視角出發(fā)?？梢钥闯觯钚碌淖畲蟾采w空間優(yōu)化研究已開(kāi)始顧及需求的連續(xù)面狀分布、交通網(wǎng)絡(luò)影響和有限資源條件下的部分覆蓋策略等，但待優(yōu)化設(shè)施基本只能在網(wǎng)絡(luò)結(jié)點(diǎn)集或預(yù)定的一組候選點(diǎn)集上布設(shè)，缺乏基于道路網(wǎng)絡(luò)環(huán)境分析的最大覆蓋實(shí)用模型和空間分割圖形啟發(fā)式與智能啟發(fā)式結(jié)合的空間優(yōu)化方法。

2.2 基于網(wǎng)絡(luò)Voronoi圖的最大覆蓋模型

本文設(shè)計(jì)的最大覆蓋模型考慮需求在區(qū)域內(nèi)連續(xù)非均質(zhì)分布，規(guī)定覆蓋半徑由設(shè)施站點(diǎn)角度出發(fā)，設(shè)施功能對(duì)覆蓋半徑以?xún)?nèi)的需求完全覆蓋，對(duì)覆蓋半徑以外需求部分覆蓋，部分覆蓋強(qiáng)度隨距離逐步衰減。在限定資源條件下，追求設(shè)施功能的非重疊覆蓋是最大化覆蓋效率的前提。由于網(wǎng)絡(luò)Voronoi面域圖是對(duì)功能覆蓋的非重疊分割，優(yōu)化算法最大化這種分割所達(dá)到的設(shè)施功能覆蓋需求總和，必然會(huì)最小化重疊覆蓋，所以基于網(wǎng)絡(luò)Voronoi面域圖的最大覆蓋模型具有啟發(fā)最小化重疊覆蓋的性能。

網(wǎng)絡(luò)上的最大覆蓋問(wèn)題可分為連續(xù)最大覆蓋問(wèn)題和離散最大覆蓋問(wèn)題，其差別在于設(shè)施可以在整個(gè)網(wǎng)絡(luò)路段上布設(shè)，還是只能在網(wǎng)絡(luò)節(jié)點(diǎn)上布設(shè)。網(wǎng)絡(luò)連續(xù)最大覆蓋問(wèn)題是頗具挑戰(zhàn)性的空間優(yōu)化難題，但其實(shí)用意義卻是顯而易見(jiàn)的。根據(jù)最大覆蓋問(wèn)題的性質(zhì)，設(shè)施覆蓋域?yàn)橐愿采w半徑確定的網(wǎng)絡(luò)輻射緩沖區(qū)，考慮部分覆蓋時(shí)，還要顧及功能輻射呈逐步衰減的外延緩沖帶。追求重復(fù)覆蓋的最小化要求在最大覆蓋模型中不考慮重復(fù)覆蓋的需求統(tǒng)計(jì)，因此，網(wǎng)絡(luò)Voronoi圖是非常適合的功能覆蓋提取模型。為此，本文提出的基于網(wǎng)絡(luò)Voronoi圖的連續(xù)最大覆蓋問(wèn)題的數(shù)學(xué)模型描述如下

式中

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

3 粒子群空間優(yōu)化

粒子群優(yōu)化（PSO）是一種基于群體搜索的算法，它建立在模擬鳥(niǎo)群社會(huì)的基礎(chǔ)之上。文獻(xiàn)［14］對(duì)Heppner模型進(jìn)行了修正，模擬由眾多無(wú)質(zhì)量和體積的粒子組成的群體在搜索空間中以一定的矢量速度飛行，每個(gè)粒子在搜索時(shí)，考慮自己曾搜索到的最好解和鄰域或群體內(nèi)其他粒子搜索到的歷史最好解，并據(jù)此調(diào)整自身的飛行速度和位置，使粒子能夠飛向解空間，并在最優(yōu)解處積聚。自粒子群算法提出以來(lái)，引起相關(guān)領(lǐng)域?qū)W者的關(guān)注并成為優(yōu)化應(yīng)用研究熱點(diǎn)，針對(duì)具體應(yīng)用出現(xiàn)了各種改進(jìn)方法［13－14］。本研究在帶慣性權(quán)重的粒子群算法中集成了改善全局搜索性能的方法，融入遺傳交叉機(jī)制以使性能低劣的粒子得到進(jìn)化，從而提高整個(gè)群體的全局優(yōu)化搜索性能。

3.1 空間優(yōu)化粒子群算法模型

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

3.2 融入遺傳交叉機(jī)制

粒子群算法在每一次迭代對(duì)所有粒子的速度和位置更新前，先對(duì)所有粒子在其當(dāng)前位置處的適應(yīng)值按從優(yōu)到劣進(jìn)行排序，對(duì)前80%適應(yīng)值較好的粒子按標(biāo)準(zhǔn)粒子群算法速度和位置模型更新，對(duì)其余20%適應(yīng)值較差的粒子按遺傳交叉機(jī)制更新。算法在適應(yīng)值較好的粒子中隨機(jī)選擇出占群體總數(shù)20%的粒子，通過(guò)將它們隨機(jī)地兩兩交叉，產(chǎn)生的相同數(shù)量后代粒子取代群體中適應(yīng)值較差的粒子，以使這些粒子搜索能力得到進(jìn)化，同時(shí)增強(qiáng)整個(gè)粒子群體脫離局部最優(yōu)的能力。

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

式中，ri～（U（0，1）。經(jīng)過(guò)交叉操作，由兩個(gè)父代粒子的位置按隨機(jī)的遺傳比例產(chǎn)生了兩個(gè)子代粒子的位置，速率交叉只有方向受到影響，數(shù)量沒(méi)有變化。

3.3 粒子位置分量飛行空間的設(shè)計(jì)

網(wǎng)絡(luò)連續(xù)型最大覆蓋模型中的所有待優(yōu)化設(shè)施可以布設(shè)在網(wǎng)絡(luò)路段上的任意位置。在粒子群算法中，直接在連續(xù)的網(wǎng)絡(luò)路段軌跡空間中設(shè)計(jì)設(shè)施位置的飛行操作非常困難?？紤]到網(wǎng)絡(luò)上布局的設(shè)施與周?chē)枨蠓植紡?qiáng)度的空間關(guān)聯(lián)性，即二維空間分布的需求強(qiáng)度對(duì)布設(shè)設(shè)施具有引力，為了使粒子群優(yōu)化算法的飛行導(dǎo)向啟發(fā)機(jī)制與尋優(yōu)性能得以保持和發(fā)揮，本文預(yù)先建立道路網(wǎng)絡(luò)空間與二維平面空間之間映射關(guān)系，通過(guò)構(gòu)建道路路段的廣義Voronoi圖實(shí)現(xiàn)這種映射。優(yōu)化算法讓粒子個(gè)體的每個(gè)設(shè)施位置分量在二維空間飛行，當(dāng)某個(gè)設(shè)施位置飛入到某條路段的Voronoi多邊形內(nèi)部時(shí)，該條路段上的最近點(diǎn)即為該設(shè)施對(duì)應(yīng)的當(dāng)前網(wǎng)絡(luò)空間飛行位置。這種轉(zhuǎn)換機(jī)制確保了在高維空間飛行粒子的各個(gè)設(shè)施位置在網(wǎng)絡(luò)空間連續(xù)飛行，配合粒子群算法使優(yōu)化進(jìn)程朝正確的方向拓展，從而實(shí)現(xiàn)網(wǎng)絡(luò)上的連續(xù)空間優(yōu)化。

4 空間優(yōu)化計(jì)算與結(jié)果分析

4.1 試驗(yàn)數(shù)據(jù)與優(yōu)化參數(shù)

本試驗(yàn)對(duì)南京市主城區(qū)14個(gè)消防設(shè)施的位置使用最大覆蓋模型進(jìn)行空間優(yōu)化，優(yōu)化目標(biāo)為覆蓋盡可能多的城區(qū)人口和最小化重疊覆蓋，即在限定資源前提下最大限度提高公共安全設(shè)施的配置與利用效率。由于獲取更詳細(xì)人口分布資料的限制，本試驗(yàn)以南京市主城各行政區(qū)屬街道區(qū)域?yàn)槿丝诘淖钚〗y(tǒng)計(jì)單位，行政街道區(qū)域單元內(nèi)的人口密度視為均勻分布，以此作為空間優(yōu)化試驗(yàn)區(qū)內(nèi)需求強(qiáng)度非均勻分布的依據(jù)。本試驗(yàn)的網(wǎng)絡(luò)分析采用路徑長(zhǎng)度距離作為連接代價(jià)，消防設(shè)施完全覆蓋區(qū)域設(shè)置為網(wǎng)絡(luò)路徑距離2.5km以?xún)?nèi)，超過(guò)該距離設(shè)施功能呈逐步衰減的部分覆蓋。優(yōu)化算法的群體規(guī)模設(shè)置為50，最大迭代次數(shù)為1 500次，速度慣性權(quán)重初值1.0、終值0.5。對(duì)迭代中每個(gè)粒子表示的14個(gè)設(shè)施的一種布局試探方案，通過(guò)計(jì)算相應(yīng)的網(wǎng)絡(luò)Voronoi面域圖，獲取各設(shè)施覆蓋的需求信息，通過(guò)模型計(jì)算其適應(yīng)值，當(dāng)一輪迭代所有粒子的適應(yīng)值獲得后，按照改進(jìn)的粒子群算法粒子更迭機(jī)制進(jìn)化整個(gè)粒子種群。在空間優(yōu)化計(jì)算的迭代過(guò)程中，為評(píng)估所有產(chǎn)生的粒子所表示的各種設(shè)施布局方案性能，共需計(jì)算生成75 000幅網(wǎng)絡(luò)Voronoi面域圖。

4.2 優(yōu)化結(jié)果分析

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

表1列出了優(yōu)化前后按完全覆蓋人口排序的南京市主城區(qū)14個(gè)消防設(shè)施功能的完全覆蓋面積、完全覆蓋人口、綜合覆蓋人口（含部分覆蓋）、網(wǎng)絡(luò)Voronoi圖輻射域人口，圖2反映現(xiàn)有設(shè)施和優(yōu)化設(shè)施完全覆蓋人口對(duì)比?？梢钥闯?，大部分優(yōu)化后的設(shè)施比現(xiàn)有設(shè)施覆蓋更多人口，優(yōu)化后的設(shè)施合計(jì)完全覆蓋人口185.74萬(wàn)，占主城區(qū)人口的79.17%，比現(xiàn)有設(shè)施完全覆蓋人口提高32.18萬(wàn)，增幅達(dá)21%；綜合覆蓋人口由優(yōu)化前的186.68萬(wàn)提高到優(yōu)化后的213.72萬(wàn)，增幅達(dá)14.5%。圖3為本次優(yōu)化試驗(yàn)過(guò)程模型目標(biāo)函數(shù)值變化曲線。

圖1 網(wǎng)絡(luò)Voronoi面域圖分析的現(xiàn)有設(shè)施和優(yōu)化設(shè)施的完全覆蓋域Fig.1 Fully covering areas of present facilities and optimized facilities analyzed by NVAD

表1 南京市現(xiàn)有設(shè)施和優(yōu)化設(shè)施覆蓋信息Tab.1 Covering information of present facilities and optimized facilities in Nanjing

為比較網(wǎng)絡(luò)Voronoi面域圖啟發(fā)式、常規(guī)Voronoi圖啟發(fā)式和圓形緩沖區(qū)需求分析對(duì)最大覆蓋空間優(yōu)化效果的影響，本文分別對(duì)基于后兩種情形的最大覆蓋模型也進(jìn)行了空間優(yōu)化試驗(yàn)，并統(tǒng)一采用能夠真實(shí)反映城市化區(qū)域設(shè)施需求覆蓋效果的網(wǎng)絡(luò)Voronoi面域圖對(duì)三種優(yōu)化獲得的設(shè)施布局進(jìn)行評(píng)估（表2）?？梢钥闯觯诰W(wǎng)絡(luò)Voronoi面域圖啟發(fā)式優(yōu)化獲得了功能對(duì)需求最高的完全覆蓋和綜合覆蓋，常規(guī)Voronoi圖啟發(fā)式優(yōu)化因未考慮道路對(duì)功能覆蓋的影響，使得優(yōu)化得到的設(shè)施布局實(shí)際覆蓋的需求低于前者和常規(guī)Voronoi圖評(píng)估結(jié)果，同樣，通過(guò)圓形緩沖區(qū)分析的優(yōu)化既忽略道路影響，又可能包含重疊覆蓋統(tǒng)計(jì)，對(duì)其優(yōu)化的設(shè)施布局進(jìn)行基于網(wǎng)絡(luò)環(huán)境的評(píng)估自然不夠理想。

圖2 優(yōu)化前后設(shè)施完全覆蓋人口對(duì)比Fig.2 Contrast of fully covering population of present facilities and optimized facilities

圖3 粒子群優(yōu)化過(guò)程目標(biāo)函數(shù)變化曲線Fig.3 Change of object function in particle swarm optimization process

表2 網(wǎng)絡(luò)Voronoi面域圖評(píng)估的不同最大覆蓋模型優(yōu)化結(jié)果比較Tab.2 Comparison of spatial optimization results based on different maximal covering location models estimated by NVAD

5 結(jié) 論

城市化區(qū)域多設(shè)施最大覆蓋科學(xué)選址是復(fù)雜的空間優(yōu)化問(wèn)題，需要對(duì)城市空間作用機(jī)制的真實(shí)模擬和更強(qiáng)的啟發(fā)式性能，新型空間分析模型、空間選址模型和計(jì)算智能方法的結(jié)合將成為趨勢(shì)。城市公共服務(wù)設(shè)施使用效率的最大化對(duì)優(yōu)化公共資源配置、追求公共服務(wù)公平性具有重要的實(shí)現(xiàn)意義。本文提出了基于網(wǎng)絡(luò)Voronoi面域圖啟發(fā)式的最大覆蓋選址模型，并結(jié)合改進(jìn)粒子群空間優(yōu)化方法進(jìn)行了較為深入的研究，獲得如下結(jié)論：

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

（2）網(wǎng)絡(luò)Voronoi圖啟發(fā)式與群智能啟發(fā)式相結(jié)合，可形成兩種啟發(fā)式功能優(yōu)勢(shì)互補(bǔ)的技術(shù)集成，為產(chǎn)生更強(qiáng)的啟發(fā)式創(chuàng)造了條件，有益于增強(qiáng)解決復(fù)雜的空間優(yōu)化問(wèn)題的能力。

（3）將遺傳進(jìn)化機(jī)制引入粒子群算法，可以提高算法的全局優(yōu)化性能，廣義Voronoi圖能夠?qū)崿F(xiàn)布局設(shè)施位置飛行由二維空間到網(wǎng)絡(luò)空間的轉(zhuǎn)換，為解決復(fù)雜的網(wǎng)絡(luò)連續(xù)空間優(yōu)化提供支持。

（4）試驗(yàn)區(qū)現(xiàn)有消防站空間布局不盡合理，功能重疊覆蓋嚴(yán)重且存在較大服務(wù)盲區(qū)，消防站數(shù)量不足，通過(guò)空間優(yōu)化，可大幅提高現(xiàn)有消防設(shè)施的利用效率。

本研究提出的最大覆蓋模型和改進(jìn)粒子群優(yōu)化算法可應(yīng)用于支持城市化區(qū)域公共安全和應(yīng)急救護(hù)等服務(wù)設(shè)施的最大覆蓋空間優(yōu)化決策。當(dāng)然，本研究還存在一些不足和需要改進(jìn)的方面，如采用地統(tǒng)計(jì)與空間分析結(jié)合的方法獲得更詳細(xì)的需求分布數(shù)據(jù)；根據(jù)某些設(shè)施的特點(diǎn)，可以考慮采用基于需求出發(fā)的網(wǎng)絡(luò)Voronoi功能吸引域分析與啟發(fā)的最大覆蓋模型；優(yōu)化過(guò)程需要的計(jì)算開(kāi)銷(xiāo)較大，仍需進(jìn)一步改進(jìn)和提高圖形計(jì)算和優(yōu)化計(jì)算的效率；進(jìn)一步開(kāi)展基于網(wǎng)絡(luò)路徑時(shí)間代價(jià)分析的空間優(yōu)化研究。

［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］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，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.（朱渭寧，馬勁松，黃杏元，等.基于投影加權(quán)Voronoi圖的GIS空間競(jìng)爭(zhēng)分析模型研究［J］.測(cè)繪學(xué)報(bào)，2004，33（2）：146－150.）

［8］ OKABLE A，SATOH T，F(xiàn)URUTA 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.（王新生，余瑞林，姜友華.基于道路網(wǎng)絡(luò)的商業(yè)網(wǎng)點(diǎn)市場(chǎng)域分析［J］.地理研究，2008，27（1）：85－92.）

［11］ XIE Shunping，F(xiàn)ENG 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.（謝順平，馮學(xué)智，魯偉.基于道路網(wǎng)絡(luò)分析的Voronoi面域圖構(gòu)建算法［J］.測(cè)繪學(xué)報(bào)，2010，39（1）：88－94.）

［12］ XIE Shunping，F(xiàn)ENG 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.（謝順平，馮學(xué)智，王結(jié)臣，等.基于道路網(wǎng)絡(luò)加權(quán)Voronoi圖分析的南京市商業(yè)中心輻射域研究［J］.地理學(xué)報(bào)，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］.北京：科學(xué)出版社，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.（杜國(guó)明，陳曉翔，黎夏.基于粒子群優(yōu)化算法的空間優(yōu)化決策［J］.地理學(xué)報(bào)，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.（黎海波，黎夏，劉小平，等.多目標(biāo)粒子群算法與選址中的形狀優(yōu)化［J］.遙感學(xué)報(bào)，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.（馬云峰，楊超，張敏，等.基于時(shí)間滿意的最大覆蓋選址問(wèn)題［J］.中國(guó)管理科學(xué)，2006，14（2）：45－51.）

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

XIE Shunping，F(xiàn)ENG 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

國(guó)家863計(jì)劃（2008AA12Z106）

叢樹(shù)平）

2011－03－11

2011－09－20

謝順平（1957—），男，博士，高級(jí)工程師，研究方向?yàn)榈乩硇畔⑾到y(tǒng)理論與應(yīng)用、空間分析與智能空間優(yōu)化。

E－mail：xiesp＠nju.edu.cn