基于仿射傳播聚類的大規(guī)模選址布局問(wèn)題求解

摘 要:選址布局問(wèn)題是一個(gè)廣泛研究的運(yùn)籌學(xué)問(wèn)題。通過(guò)將選址布局問(wèn)題看做聚類問(wèn)題，結(jié)合仿射傳播聚類算法并且將候選地址的信息映射為特征向量，提出了兩種求解選址布局問(wèn)題的方法:基于塊劃分的選址布局方法和基于道路網(wǎng)絡(luò)的選址布局方法。使用模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集來(lái)評(píng)估兩種方法，實(shí)驗(yàn)結(jié)果表明兩種方法都能夠求解設(shè)施資源受限和不受限情況下的選址布局問(wèn)題，而且可以很好地解決大規(guī)模的選址布局問(wèn)題。

關(guān)鍵詞:仿射傳播聚類; 選址布局問(wèn)題; 道路網(wǎng)絡(luò); 運(yùn)籌學(xué)

中圖分類號(hào):TP391 文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2010)03-0841-04

doi:10.3969/j.issn.1001-3695.2010.03.009

Solving large scale location problem using affinity propagation clustering

TANG Dong-ming， ZHU Qing-xin， YANG Fan， BAI Yong

(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:Location problem is a well-studied problem in operations research. By treating location problem as clustering problem， integrating affinity propagation clustering algorithm andmapping information of candidate into feature vector， this paper presented two methods to select suitably situation from candidate situation:location method based on region division and location method based on road network. It evaluated two methods using synthetic data sets as well as real-world data sets. The experimental results show that two methods can solve location problem with fixed number facilities and location problem with unfixed number facilities， and can solve large location problems and provide good solutions.

Key words:affinity propagation clustering; location problem; road network; operations research

0 引言

如何選擇合適的地址布局消防站、商店、急救中心、公共安全服務(wù)機(jī)構(gòu)、工廠、倉(cāng)庫(kù)、物流中心、通信基站等設(shè)施和機(jī)構(gòu)，讓它們?cè)谫Y源有限的條件下發(fā)揮最大的功能是選址布局規(guī)劃部門的一個(gè)重要任務(wù)。選址布局問(wèn)題的數(shù)學(xué)模型取決于兩個(gè)方面的條件:可供選址的范圍、條件;怎樣判定選址的質(zhì)量。根據(jù)設(shè)施所能選擇的空間選址布局問(wèn)題可分為離散選址、連續(xù)選址和網(wǎng)絡(luò)選址。在數(shù)學(xué)模型上，一般將選址布局問(wèn)題歸納為多目標(biāo)規(guī)劃問(wèn)題，即在資源受限的條件下以最小化的代價(jià)來(lái)滿足多個(gè)目標(biāo)。目前已經(jīng)有眾多的學(xué)者提出了多種數(shù)學(xué)方法來(lái)求解此類問(wèn)題[1~5]。文獻(xiàn)[1]描述了一種基于整數(shù)目標(biāo)規(guī)劃的多目標(biāo)消防站選址布局方法;文獻(xiàn)[2]采用模糊多目標(biāo)規(guī)劃方法，文獻(xiàn)[3]采用求解p-中值問(wèn)題的方法來(lái)解決可變網(wǎng)絡(luò)的布局問(wèn)題;文獻(xiàn)[4]提出了用求解p-中值問(wèn)題的方法來(lái)解決不可靠設(shè)施布局問(wèn)題;文獻(xiàn)[5]采用聚類方法來(lái)解決CDMA基站的規(guī)劃問(wèn)題。

選址布局問(wèn)題本身是一個(gè)NP難問(wèn)題，目前求解這個(gè)問(wèn)題面臨著兩個(gè)難題:如何在用戶可容忍的時(shí)間內(nèi)進(jìn)行大規(guī)模的選址布局分析;如何獲得全局的優(yōu)化解。聚類分析作為一種有效的數(shù)據(jù)分析工具，被廣泛應(yīng)用于模式識(shí)別、數(shù)據(jù)挖掘、文本處理、語(yǔ)音處理、生物信息處理、圖像處理等領(lǐng)域。2007年J.F. Brendan等人[6]提出了一種新的聚類算法，即仿射傳播聚類算法(affinity propagation clustering，AP)。本文在研究仿射傳播聚類算法的基礎(chǔ)上提出了兩種適用于求解大規(guī)模選址布局問(wèn)題的方法，并以消防站選址為例進(jìn)行了詳細(xì)的闡述，最后進(jìn)行了相關(guān)的仿真實(shí)驗(yàn)。本文提出的算法能夠快速地求解大規(guī)模的選址布局問(wèn)題;在未給定目標(biāo)選址個(gè)數(shù)的時(shí)候算法能夠自動(dòng)決定合適的設(shè)施個(gè)數(shù);在給定目標(biāo)地址的時(shí)候算法能夠提供設(shè)施的覆蓋候選區(qū)域;算法提供的信息可以作為決策的依據(jù)。

1 仿射傳播聚類

設(shè)給定的N個(gè)數(shù)據(jù)點(diǎn)為x1，x2，…，xN，為了劃分這N個(gè)數(shù)據(jù)點(diǎn)為不同的類別，AP算法引入了類代表(exemplars)的概念，即一類數(shù)據(jù)中的代表點(diǎn)。算法在初始時(shí)將所有數(shù)據(jù)點(diǎn)都看做潛在的類代表點(diǎn)。AP算法將每個(gè)數(shù)據(jù)點(diǎn)看做網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，通過(guò)節(jié)點(diǎn)之間不斷迭代傳送更新的真實(shí)數(shù)據(jù)消息來(lái)產(chǎn)生類代表點(diǎn)及相應(yīng)的附屬點(diǎn)，在消息傳遞的過(guò)程中就完成了數(shù)據(jù)的分簇。算法的初始輸入條件為N個(gè)數(shù)據(jù)點(diǎn)之間的相似度組成的N×N相似度矩陣s，s(i，k)表示數(shù)據(jù)點(diǎn)k作為數(shù)據(jù)點(diǎn)i的類代表的適合度。當(dāng)采用歐式距離來(lái)表示數(shù)據(jù)點(diǎn)之間的相似度時(shí)，s(i，k)可以用式(1)來(lái)表示。

s(i，k)=-‖xi-xk‖2(1)

AP算法與傳統(tǒng)的K-均值聚類算法不同，它無(wú)須預(yù)先知曉聚類的個(gè)數(shù)，通過(guò)調(diào)節(jié)s(k，k)的值可以改變聚類的個(gè)數(shù)，s(k，k)值越大則點(diǎn)k越可能被選為類代表點(diǎn)。s(k，k)被稱為preferences，即偏度，如果預(yù)先并不知曉哪些數(shù)據(jù)點(diǎn)適合作為類代表點(diǎn)，則可以為s(k，k)設(shè)置一個(gè)相同的值。 迭代計(jì)算的過(guò)程中，有兩類消息在數(shù)據(jù)點(diǎn)之間傳遞，這兩類消息反映了數(shù)據(jù)點(diǎn)之間的競(jìng)爭(zhēng)，同時(shí)也是一個(gè)證據(jù)收集與累加的過(guò)程。數(shù)據(jù)點(diǎn)k為了成為類代表點(diǎn)需要從每個(gè)數(shù)據(jù)點(diǎn)i收集證據(jù)r(i，k)，它表示數(shù)據(jù)點(diǎn)k對(duì)點(diǎn)i的responsibility，用來(lái)度量數(shù)據(jù)點(diǎn)k適合作為數(shù)據(jù)點(diǎn)i的類代表的程度，即點(diǎn)k對(duì)點(diǎn)i的吸引度。數(shù)據(jù)點(diǎn)i從候選的類代表點(diǎn)k收集證據(jù)a(i，k)，表示數(shù)據(jù)點(diǎn)i對(duì)點(diǎn)k的availability，用來(lái)度量數(shù)據(jù)點(diǎn)i選擇點(diǎn)k作為它的類代表點(diǎn)的適合程度，即點(diǎn)i對(duì)點(diǎn)k的歸屬度。

每一次消息迭代傳遞過(guò)程都包含三個(gè)部分，即更新吸引度以給出適應(yīng)度、更新所有點(diǎn)的適應(yīng)度以給出吸引度、給出吸引度和適應(yīng)度監(jiān)控類代表的決策并當(dāng)決策n次迭代都沒(méi)有變化的情況下終止算法。

AP算法無(wú)須提前給出聚類的個(gè)數(shù)，從消息的傳遞過(guò)程中依賴輸入的偏度來(lái)產(chǎn)生適當(dāng)?shù)木垲悢?shù)，這樣就能夠基于一個(gè)先決適當(dāng)條件來(lái)進(jìn)行自動(dòng)的模型選擇，通過(guò)調(diào)節(jié)偏度就能調(diào)節(jié)節(jié)點(diǎn)作為類代表的度。AP算法可以看做是一種搜索最小能量函數(shù)的方法，用c1，c2，…，cN表示相應(yīng)的N個(gè)數(shù)據(jù)點(diǎn)的類代表，則s(i，ci)就是數(shù)據(jù)點(diǎn)i到它的類代表點(diǎn)的相似度。因此相應(yīng)的能量函數(shù)為E(C)=∑Ni=1s(i，ci)。實(shí)際上計(jì)算最小能量是很難的，是一個(gè)NP難度k中值問(wèn)題。但是AP算法的更新迭代規(guī)則協(xié)調(diào)了固定點(diǎn)的遞歸來(lái)最小化為一個(gè)近似Bethe自由能量。

選址布局問(wèn)題從本質(zhì)上來(lái)說(shuō)是一個(gè)p-中值問(wèn)題，在各種約束條件下尋找某種最小的成本，以使全部或平均性能最優(yōu)，因此傳統(tǒng)的方法無(wú)法解決大規(guī)模的選址問(wèn)題。通過(guò)前面的敘述可知，可以將選址問(wèn)題中的候選點(diǎn)轉(zhuǎn)換為AP算法中的數(shù)據(jù)點(diǎn)，候選點(diǎn)之間的關(guān)系可以轉(zhuǎn)換為相似度，可以將選址前的一些先驗(yàn)信息轉(zhuǎn)換為偏度。

2 基本模型和問(wèn)題定義

一般的選址布局問(wèn)題可以描述為:在N個(gè)候選地址中選擇適當(dāng)?shù)牡刂方ㄔO(shè)設(shè)施或機(jī)構(gòu)。下面給出一些基本的符號(hào)定義:X為候選點(diǎn)描述，X=(x1，x2，…，xn)，每個(gè)xi(i=1，…，n)分別描述候選點(diǎn)的某一個(gè)特征;CA為候選地址集合，CA={X1，X2，…，XN}，該集合中可以包含已經(jīng)存在的站點(diǎn)，在此候選地址也可理解為測(cè)試地址;C為選中的地址集合，C={C1，C2，…，Ci};c為每個(gè)候選地址所隸屬的選中地址，c={c1，c2，…，cN}，ci∈C;s(i，j)為候選地址i與j之間的關(guān)系。

由以上描述可知，為了采用AP算法求解選址布局問(wèn)題，就需要將候選地址的特征采用數(shù)學(xué)形式進(jìn)行描述，并將候選地址之間的約束和關(guān)聯(lián)關(guān)系轉(zhuǎn)換為相似度信息，最后最小化能量函數(shù)。迭代運(yùn)算找出的類代表點(diǎn)即為選中的地址。下面將以消防站的選址布局問(wèn)題為例詳細(xì)闡述如何采用AP算法求解。

3 基于塊劃分的選址布局方法

城市消防規(guī)劃在城市建設(shè)和發(fā)展中具有重要意義， 在選址布局消防站時(shí)一般受以下幾個(gè)因素的影響[2]:a)最大化的服務(wù)能力，即輻射區(qū)域要廣;b)最小化的平均服務(wù)距離，即消防站到事故發(fā)生地的距離要短;c)最小化平均到達(dá)時(shí)間，即消防站到轄區(qū)的事故發(fā)生地平均響應(yīng)時(shí)間要短;d)修建合理數(shù)量的消防站來(lái)滿足需求;e)高危險(xiǎn)地區(qū)盡量靠近消防站;f)要考慮人口密集度。

文獻(xiàn)[2]提出將一個(gè)大的規(guī)劃區(qū)域劃分成多個(gè)等面積的小區(qū)域，并給每個(gè)小區(qū)域賦予不同的風(fēng)險(xiǎn)類型值的方法。圖1為文獻(xiàn)[2]中將英國(guó)Derbyshire 地區(qū)劃分為186×116個(gè)小區(qū)塊的一部分。區(qū)塊中的數(shù)字代表該區(qū)塊的風(fēng)險(xiǎn)等級(jí)。

為了規(guī)劃選址消防站可以將要規(guī)劃布局的整體區(qū)域劃分成多個(gè)等面積的小區(qū)域，劃分出的小區(qū)域可以是方形也可以是多邊形(六邊形)，在每個(gè)小區(qū)域中選取一定數(shù)量的地點(diǎn)作為候選地址。候選點(diǎn)按以下特征進(jìn)行描述:

候選點(diǎn)X=(x1，x2，x3，x4，x5)。其中:x1表示候選點(diǎn)的水平方向上的坐標(biāo);x2表示候選點(diǎn)縱軸方向上的坐標(biāo);x3表示候選點(diǎn)所在小區(qū)域的風(fēng)險(xiǎn)等級(jí)(取值為1，…，4，數(shù)值越大表示危險(xiǎn)系數(shù)越高);x4表示小區(qū)域的人口總數(shù)占整個(gè)大區(qū)域的人口總數(shù)的比例;x5表示是否是已存在的消防站(取值為0、1，1表示已經(jīng)存在)。可以增加特征維數(shù)來(lái)描述一些特定的約束條件。兩個(gè)候選點(diǎn)之間的空間距離采用歐式距離來(lái)度量，用式(2)描述:

D(i，j)=(Xi1-Xj1)2+(Xi2-Xj2)2(2)

設(shè)一個(gè)消防站的最遠(yuǎn)服務(wù)距離為L(zhǎng)，同時(shí)設(shè)定一個(gè)大的正值T，則兩個(gè)候選點(diǎn)之間的相似度計(jì)算如式(3)所示。在候選點(diǎn)比較多的時(shí)候(候選點(diǎn)高于2 000)，對(duì)兩點(diǎn)之間相似度很小的s(i，j)數(shù)據(jù)可以拋棄，這樣就可以形成一個(gè)稀疏矩陣，由前面的敘述可知AP算法能夠處理這種情況。

s(i，j)=-D(i，j)if(D(i，j)

每個(gè)候選點(diǎn)的偏度按式(4)進(jìn)行計(jì)算，M為一個(gè)負(fù)值，通常取所有相似度的中值，但是為了得到特定數(shù)量的分類個(gè)數(shù)可以調(diào)節(jié)該值以滿足設(shè)施總數(shù)的約束條件;θ為一個(gè)正的小值;wj為相應(yīng)特征分量的權(quán)值。為了防止某個(gè)點(diǎn)的偏度過(guò)高，設(shè)定了一個(gè)閾值θ，每個(gè)候選點(diǎn)的特征分量和相應(yīng)的權(quán)值進(jìn)行加權(quán)運(yùn)算后就能夠反映一個(gè)點(diǎn)在多大程度上能夠當(dāng)選類代表。從式(4)中可以看出，只要給出合適的權(quán)值就能夠?qū)⒑蜻x點(diǎn)的特征反映到偏度中，這樣高危險(xiǎn)的點(diǎn)就可能當(dāng)選為類代表。

pi=min-θ，M×(1-e1/∑5j=3wj×xj)(4)

4 基于道路網(wǎng)絡(luò)的選址布局方法

在描述道路網(wǎng)絡(luò)的選址布局方法前先給出空間道路網(wǎng)絡(luò)的一些基本定義[7~9]。

定義1 圖是指某類具體事務(wù)和這些事務(wù)之間的聯(lián)系。一個(gè)圖G定義為一個(gè)有序?qū)?V，E，W)，記為G=(V，E，W)。其中:V是一個(gè)非空集合，稱為定點(diǎn)集合;E是由V中的點(diǎn)組成的無(wú)序點(diǎn)對(duì)構(gòu)成的集合，稱為邊集;W為邊上的權(quán)值。一個(gè)對(duì)象位于且僅位于一條網(wǎng)絡(luò)邊上，該對(duì)象在本文中即表示候選點(diǎn)。對(duì)于一個(gè)道路網(wǎng)絡(luò)，為了降低其復(fù)雜性，可以將道路網(wǎng)絡(luò)的交叉口建模為網(wǎng)絡(luò)圖的節(jié)點(diǎn)，而將交叉口之間的路段建模為網(wǎng)絡(luò)圖的邊[7]。

定義2 對(duì)象之間的距離是指兩者在空間道路網(wǎng)絡(luò)中的最短距離。

在實(shí)際的選址布局中，候選地址不只是局限于道路網(wǎng)絡(luò)的交叉口，更多的是在網(wǎng)絡(luò)的邊上。當(dāng)兩個(gè)候選點(diǎn)在同一條道路上時(shí)它們之間的最短距離即為它們之間的距離，不在同一條道路上時(shí)只需計(jì)算它們所在道路的兩個(gè)節(jié)點(diǎn)和另外一個(gè)候選點(diǎn)所在道路的兩個(gè)節(jié)點(diǎn)間的最短距離，加上候選點(diǎn)到所在道路節(jié)點(diǎn)之間的距離，和的最小值即為兩候選點(diǎn)間的最短距離。

道路網(wǎng)的規(guī)模一般都比較大，經(jīng)典的Dijkstra 最短路徑算法的時(shí)間復(fù)雜度為O(|V|log|V|)。其中V為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，很顯然當(dāng)節(jié)點(diǎn)數(shù)目比較大時(shí)使用經(jīng)典的Dijkstra算法將耗費(fèi)極大的時(shí)間和空間。為了加速計(jì)算空間道路網(wǎng)絡(luò)中的最短距離，目前已經(jīng)產(chǎn)生了很多技術(shù)。文獻(xiàn)[10，11]詳細(xì)闡述比較了三種用于空間道路網(wǎng)絡(luò)的快速計(jì)算最短路徑的算法，即兩隊(duì)列的圖增長(zhǎng)算法、近似桶原理的Dijkstra算法和雙桶Dijkstra算法。目前還有一些其他的算法[12，13]，由于最短路計(jì)算問(wèn)題并不是本文的研究重點(diǎn)，在此不再詳述。

為了選址消防站，可以在每條道路上選取一定數(shù)量的點(diǎn)作為候選點(diǎn)，同樣道路的節(jié)點(diǎn)也可以看做是候選點(diǎn)，候選點(diǎn)按以下特征進(jìn)行描述:候選點(diǎn)X=(x1，x2，x3，x4，x5，x6)。其中:x1、x2表示候選點(diǎn)所在道路邊的兩個(gè)節(jié)點(diǎn);x3表示候選點(diǎn)間的距離;x4表示候選點(diǎn)所在鄰近區(qū)域的風(fēng)險(xiǎn)等級(jí)(取值為1，…，4，數(shù)值越大表示危險(xiǎn)系數(shù)越高);x5表示道路所在街區(qū)人口占總?cè)丝跀?shù)的比例;x6表示是否是已存在的消防站(取值為0、1，1表示已經(jīng)存在)。

兩個(gè)候選點(diǎn)間的空間距離采用基于道路網(wǎng)絡(luò)的最短路徑距離來(lái)度量;候選點(diǎn)之間的相似度采用兩點(diǎn)之間的最短距離來(lái)度量，運(yùn)算方式如式(3)所示;候選點(diǎn)偏度的計(jì)算采用類似第3章的方法。

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)配置

實(shí)驗(yàn)用的數(shù)據(jù)集分為兩類，即模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集。模擬數(shù)據(jù)集采用算法隨機(jī)生成，真實(shí)數(shù)據(jù)集來(lái)源于文獻(xiàn)[9]和Florida State University的Li Fei-fei。

5.2 基于塊劃分的選址布局方法實(shí)驗(yàn)結(jié)果與分析

模擬數(shù)據(jù)集的生成采用如下方式:給定W×H的矩形區(qū)域，劃分成n×n個(gè)(W/n)×(H/n)大小的區(qū)域，每個(gè)區(qū)域隨機(jī)選擇一定數(shù)量的候選點(diǎn)。分兩種方式進(jìn)行實(shí)驗(yàn):a)所有候選點(diǎn)公平競(jìng)爭(zhēng)，即所有候選點(diǎn)具有相同的先決條件;b)非公平競(jìng)爭(zhēng)，即隨機(jī)賦予候選點(diǎn)一些先決條件。

表1為設(shè)施資源總數(shù)無(wú)限制條件下針對(duì)不同的數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)的結(jié)果。表中第一列為數(shù)據(jù)集的標(biāo)號(hào);第二列為選址布局區(qū)域的大小;第三列為劃分的小區(qū)塊的大小;第四列為候選點(diǎn)的個(gè)數(shù);第五列為設(shè)施最遠(yuǎn)服務(wù)距離;第六列表示候選點(diǎn)是否公平競(jìng)爭(zhēng)，公平競(jìng)爭(zhēng)則表示所有候選點(diǎn)都有同等的機(jī)會(huì)競(jìng)爭(zhēng);第七列為已經(jīng)存在的設(shè)施個(gè)數(shù);第八列為計(jì)算選出的地址個(gè)數(shù);第九列為按式(5)計(jì)算出的平均距離，式中的分子表示所有候選點(diǎn)到其類代表點(diǎn)的距離總和，分母表示類代表點(diǎn)的個(gè)數(shù);第十列為按式(6)計(jì)算出的誤差，式中分子表示候選點(diǎn)到其類代表點(diǎn)的距離大于L的候選點(diǎn)的個(gè)數(shù)，分母為候選點(diǎn)的總數(shù)。表1中前三行的候選點(diǎn)都擁有相同的先決條件，后三行的數(shù)據(jù)被隨機(jī)賦予了不同的風(fēng)險(xiǎn)等級(jí)、人口比例、是否是已存在設(shè)施所在地址。

表1 區(qū)域劃分法在設(shè)施資源總數(shù)不受限條件下的仿真實(shí)驗(yàn)結(jié)果

序號(hào)區(qū)域大小分塊大小候選點(diǎn)個(gè)數(shù)最遠(yuǎn)服務(wù)距離L是否公平競(jìng)爭(zhēng)已存在設(shè)施個(gè)數(shù)類代表個(gè)數(shù)平均距離誤差

110 000×10 000250×2501 6002 000是013132 3750.006 875

210 000×10 000500×5001 2002 000是01488 2790.002 500

310 000×10 0001 000×1 0001002 000是0137 3030.000 000

410 000×10 000250×2501 6002 000否31976 6850.000 000

510 000×10 000500×5001 2002 000否21957 6460.000 833

610 000×10 0001 000×1 0001002 000否2156 1960.000 000

avrDis=∑Ni=1D(i，ci)cNum(5)

err=number(D(i，ci)>L)N(6)

圖2對(duì)比了相同的候選點(diǎn)在公平競(jìng)爭(zhēng)和非公平競(jìng)爭(zhēng)條件下的選址結(jié)果，圖中的黑點(diǎn)表示候選點(diǎn)所在的位置，候選點(diǎn)和其類代表點(diǎn)之間用直線相連;圖2(b)中的候選點(diǎn)被隨機(jī)賦予了風(fēng)險(xiǎn)等級(jí)、人口所占比例，并隨機(jī)選擇兩個(gè)點(diǎn)作為已存在的設(shè)施，(b)中帶圓圈的點(diǎn)即為已存在的設(shè)施所在位置。從圖中可以看出，已存在的點(diǎn)作為強(qiáng)力點(diǎn)明顯地影響了選址的結(jié)果。

從本文前面的敘述可知，最遠(yuǎn)服務(wù)距離L是人為設(shè)定的一個(gè)閾值，其值對(duì)產(chǎn)生類代表的數(shù)量有很大的影響。對(duì)表1中的編號(hào)為1的數(shù)據(jù)取不同的L值，測(cè)試對(duì)類代表數(shù)量的影響，圖3為測(cè)試的結(jié)果。從圖中可以看出隨著L值的增大，類代表的個(gè)數(shù)最開始下降非常快，最后趨于平穩(wěn)。

為了驗(yàn)證在設(shè)施資源總數(shù)有限的條件下選址布局，本文對(duì)表1中的數(shù)據(jù)在資源總數(shù)為10的條件下進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2所示。從表2中可以看出，限制可用資源總量導(dǎo)致平均距離和誤差明顯升高，候選點(diǎn)多的情況下影響尤為明顯。

表2 區(qū)域劃分法在設(shè)施資源總數(shù)受限條件下的仿真實(shí)驗(yàn)結(jié)果

序號(hào)區(qū)域大小分塊大小候選點(diǎn)個(gè)數(shù)最遠(yuǎn)服務(wù)距離L是否公平競(jìng)爭(zhēng)已存在設(shè)施個(gè)數(shù)類代表個(gè)數(shù)平均距離誤差

110 000×10 000250×2501 6002 000是010196 9750.053 125

210 000×10 000500×5001 2002 000是010147 1760.040 000

310 000×10 0001 000×1 0001002 000是01011 4740.030 000

410 000×10 000250×2501 6002 000否310199 2350.063 750

510 000×10 000500×5001 2002 000否210148 8390.062 500

610 000×10 0001 000×1 0001002 000否21012 5970.130 000

5.3 基于道路網(wǎng)絡(luò)的選址布局方法實(shí)驗(yàn)結(jié)果與分析

文獻(xiàn)[9]給出的真實(shí)道路網(wǎng)絡(luò)數(shù)據(jù)并不包含道路的長(zhǎng)度，因此結(jié)合Li Fei-fei的數(shù)據(jù)，結(jié)合兩者的數(shù)據(jù)后將數(shù)據(jù)轉(zhuǎn)換為網(wǎng)絡(luò)圖模型的數(shù)據(jù)。下面采用Oldenburg市的道路網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)。

采用隨機(jī)算法在Oldenburg市道路網(wǎng)絡(luò)上生成不同數(shù)量的候選點(diǎn)，并且保證每條道路上最多出現(xiàn)一個(gè)候選點(diǎn)，以此生成的數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)。Oldenburg市共有7 035條道路，6 105個(gè)節(jié)點(diǎn)，表3為在設(shè)施資源不受限制條件下的仿真實(shí)驗(yàn)結(jié)果。表中的前三行候選點(diǎn)都擁有相同的先決條件，后三行的數(shù)據(jù)被隨機(jī)賦予了不同的風(fēng)險(xiǎn)等級(jí)、人口比例、是否是已存在設(shè)施所在地址。從表中數(shù)據(jù)可以看出，候選點(diǎn)被賦予不同的先決條件后對(duì)比公平競(jìng)爭(zhēng)時(shí)運(yùn)算結(jié)果有了很大的變化，選出的類代表的個(gè)數(shù)明顯增加，候選點(diǎn)數(shù)量比較多時(shí)類代表個(gè)數(shù)增加的尤為明顯。表4為設(shè)施資源總數(shù)為13的條件下的仿真實(shí)驗(yàn)結(jié)果，對(duì)比表3可以發(fā)現(xiàn)平均距離和誤差變化非常大。

表3 道路網(wǎng)絡(luò)法在設(shè)施資源總數(shù)不受限條件下的仿真實(shí)驗(yàn)結(jié)果

序號(hào)區(qū)域大小分塊大小候選點(diǎn)個(gè)數(shù)最遠(yuǎn)服務(wù)距離L是否公平競(jìng)爭(zhēng)已存在設(shè)施個(gè)數(shù)類代表個(gè)數(shù)平均距離誤差

16 1057 0351002 000是0127 0430.050 000

26 1057 0351 6002 000是01598 1120.030 000

36 1057 0352 5002 000是019108 2800.015 200

46 1057 0351002 000否1145 8210.030 000

56 1057 0351 6002 000否32258 0100.021 250

66 1057 0352 5002 000否42765 3470.009 600

表4 道路網(wǎng)絡(luò)法在設(shè)施資源總數(shù)受限條件下的仿真實(shí)驗(yàn)結(jié)果

序號(hào)區(qū)域大小分塊大小候選點(diǎn)個(gè)數(shù)最遠(yuǎn)服務(wù)距離L是否公平競(jìng)爭(zhēng)已存在設(shè)施個(gè)數(shù)類代表個(gè)數(shù)平均距離誤差

16 1057 0351002 000是0136 1810.040 000

26 1057 0351 6002 000是013122 5820.043 750

36 1057 0352 5002 000是013188 5770.039 600

46 1057 0351002 000否1136 5270.040 000

56 1057 0351 6002 000否313126 1980.056 875

66 1057 0352 5002 000否413197 5100.069 200

基于塊劃分的選址布局方法是一種比較粗略的選址布局方法，候選點(diǎn)之間的相似程度采用直接的空間直線距離來(lái)描述，并不能完全反映候選點(diǎn)之間的真實(shí)情況。在現(xiàn)實(shí)環(huán)境中，候選點(diǎn)之間的相似距離更多地取決于物理的道路網(wǎng)絡(luò)和交通狀況，因此基于道路網(wǎng)絡(luò)的選址布局方法更能反映真實(shí)情況，作出更加精確的決策。但是在道路網(wǎng)絡(luò)比較復(fù)雜、節(jié)點(diǎn)數(shù)比較多的情況下，候選點(diǎn)之間的相似度計(jì)算對(duì)時(shí)間和空間的消耗都較大。

對(duì)兩種方法進(jìn)行仿真實(shí)驗(yàn)并對(duì)比后可知，基于塊劃分的選址布局方法比較適宜對(duì)大片區(qū)域，如森林防火、新建城市和片區(qū)的規(guī)劃布局，基于道路網(wǎng)絡(luò)的選址布局方法比較適宜城市精確選址布局設(shè)施、商業(yè)網(wǎng)點(diǎn)等。

6 結(jié)束語(yǔ)

本文在研究了AP算法后提出了兩種求解選址布局問(wèn)題的方法，將問(wèn)題中候選點(diǎn)之間的距離轉(zhuǎn)換為AP算法中的相似度，并且將候選點(diǎn)的信息映射為特征，以特征加權(quán)后的值的和來(lái)決定候選點(diǎn)偏度。這種方法很好地結(jié)合了AP算法和求解選址布局問(wèn)題的特點(diǎn)。方法的求解結(jié)果可以為決策提供依據(jù)信息，并且在預(yù)先不知道多少設(shè)施可以滿足要求的情況下，算法能夠自動(dòng)提供合適的設(shè)施個(gè)數(shù)。實(shí)驗(yàn)證明本文提出的方法是有效可靠的，特別適用于大規(guī)模的精細(xì)選址。

參考文獻(xiàn):

[1]BADRI M A，MORTAGY A K，ALSAYED C A. Multi-objective mo-del for locating fire stations[J]. European Journal of Operational Research， 1998，110(2):243-260.

[2]YANG Li-li， BRYAN F J， YANG Shuang-hua. A fuzzy multi-objective programming for optimization of fire station locations through genetic algorithms[J]. European Journal of Operational Research， 2007， 181(2):903-915.

[3]DANIEL S， VLADIMIR M. The p-median problem in a changing network: the case of Barcelona[J]. Location Science， 1998，6(2):383-394.

[4]LEE S D. On solving unreliable planar location problems[J]. Computers and Operations Research， 2001，28(4): 329-344.

[5]張宏遠(yuǎn)， 谷寒雨， 席裕庚. 基于聚類分解的WCDMA基站布局規(guī)劃算法[J]. 控制與決策， 2006，21(2): 213-216.

[6]BRENDAN J F， DELBERT D. Clustering by passing messages between data points[J]. Science， 2007，315(5814): 972-976.

[7]陳繼東， 孟小峰，賴彩鳳. 基于道路網(wǎng)絡(luò)的對(duì)象聚類[J]. 軟件學(xué)報(bào)， 2007，18(2): 332-344.

[8]MAN L Y， NIKOS M. Clustering objects on a spatial network[C]//Proc of the ACM SIGMOD International Conference on Management of Data. New York:ACM Press， 2004:443-454.

[9]THOMAS B. A framework for generating network-based moving objects[J]. GeoInformatica， 2002，6(2):153-180.

[10]ZHAN F B. Three fastest shortest path algorithms on real road networks:data structures and procedures[J]. Journal of Geographic Information and Decision Analysis， 1997，1(1): 69-82.

[11]ZHAN F B， NOON C E. Shortest path algorithms: an evaluation using real road networks[J]. Transportation Science， 1998，32(1):65-73.

[12]MANOLIS T， SPIRIDON B， DIMITRIS P，et al. Constrained shortest path computation[C]//Lecture Notes in Computer Science. Berlin:Springer， 2005:181-199.

[13]MAN L Y， DIMITRIS P， PAPADIAS D， et al. Reverse nearest neighbors in large graphs[J]. IEEE Trans on Knowledge and Data Engineering， 2006，18(4):540-559.