莫漢培，陳秋良，張子臻

(1.東莞供電局,廣東 東莞 523000;2.中山大學(xué) 移動(dòng)信息工程學(xué)院,廣東 珠海 519000)

遺傳算法求解電力設(shè)施選址問(wèn)題

莫漢培1，陳秋良2，張子臻2

(1.東莞供電局,廣東 東莞 523000;2.中山大學(xué) 移動(dòng)信息工程學(xué)院,廣東 珠海 519000)

電力系統(tǒng)設(shè)施選址優(yōu)化問(wèn)題是電力系統(tǒng)規(guī)劃和設(shè)計(jì)中的一個(gè)基礎(chǔ)性問(wèn)題，可以抽象成約束型的p-中位(p-median)問(wèn)題，這是一個(gè)經(jīng)典的NP-hard問(wèn)題。該問(wèn)題可以描述為從一個(gè)點(diǎn)的集合中選擇p個(gè)有容量限制的中位點(diǎn)，讓它們?nèi)シ?wù)一些有需求的點(diǎn)(客戶)，要求每一個(gè)中位點(diǎn)都不超出容量，并且總花費(fèi)最小。文中針對(duì)這一優(yōu)化問(wèn)題，在經(jīng)典遺傳算法的基礎(chǔ)上，提出了一種改進(jìn)的遺傳算法，并混合使用局部搜索算法，進(jìn)行問(wèn)題的求解。該算法能夠利用遺傳算法的全局收斂性，并且有效克服遺傳算法的局部收斂和早熟問(wèn)題，從而得到更準(zhǔn)確的近似解。最后，使用網(wǎng)上的公開測(cè)試數(shù)據(jù)集以及經(jīng)地理信息平臺(tái)(GIS)收集的某供電局的坐標(biāo)信息進(jìn)行實(shí)驗(yàn)驗(yàn)證。結(jié)果表明，提出的算法能夠有效解決設(shè)施選址問(wèn)題，并且為企業(yè)提供切實(shí)可行的方案。

設(shè)施選址；遺傳算法；約束型p-中位問(wèn)題；GIS平臺(tái)

1 概 述

在電力系統(tǒng)的規(guī)劃和設(shè)計(jì)中，確定服務(wù)設(shè)施點(diǎn)比如變電站的位置是非?；A(chǔ)性的工作，這對(duì)于后期設(shè)備的維護(hù)、工作人員的調(diào)度都有很大影響。在實(shí)際的情形中，由于服務(wù)點(diǎn)數(shù)量龐大，地理位置信息相對(duì)復(fù)雜，以及人員容量等限制條件較多等原因?qū)е略搯?wèn)題求解困難。

設(shè)施選址問(wèn)題[1-2]是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，這個(gè)問(wèn)題可以描述為在一片區(qū)域內(nèi)有一些服務(wù)點(diǎn)，這些服務(wù)點(diǎn)都有一定的需求服務(wù)量，要從中選擇p個(gè)設(shè)施點(diǎn)來(lái)服務(wù)這些服務(wù)點(diǎn)，并且要求滿足一定的限制。文中所考慮的是約束型p-中位問(wèn)題，這個(gè)問(wèn)題是設(shè)施選址問(wèn)題的一種常見形式，在實(shí)際生產(chǎn)生活中應(yīng)用廣泛，并且在運(yùn)籌學(xué)、組合調(diào)度等領(lǐng)域都有研究。約束型p-中位問(wèn)題已經(jīng)被證明是一個(gè)NP-hard問(wèn)題，因此精確解無(wú)法在多項(xiàng)式時(shí)間內(nèi)得到，所以人們都傾向于使用現(xiàn)代啟發(fā)式算法或者一些近似算法以得到問(wèn)題的近似最優(yōu)解。

近些年來(lái)，許多學(xué)者提出的一些解決方法都是基于啟發(fā)式算法思想的。文獻(xiàn)[3-5]提出了一種基于禁忌搜索的方法，主要是通過(guò)禁忌表的方法來(lái)改善局部搜索陷入局部最優(yōu)解的問(wèn)題；文獻(xiàn)[6-7]提出用模擬退火的方法解決p-median問(wèn)題，同樣也是用一種退火機(jī)制來(lái)跳出局部最優(yōu)解；文獻(xiàn)[8]采用雙層模擬退火算法，外層對(duì)設(shè)施選址決策進(jìn)行優(yōu)化,內(nèi)層則在上層確定的設(shè)施選址決策基礎(chǔ)上,進(jìn)行用戶需求分配的優(yōu)化；文獻(xiàn)[9-10]使用了蟻群算法來(lái)求解；文獻(xiàn)[11]使用了局部搜索的方法；文獻(xiàn)[12-14]使用了遺傳算法來(lái)求解。隨著研究的深入，越來(lái)越多的學(xué)者傾向于改進(jìn)傳統(tǒng)的啟發(fā)式算法并且混合使用多種方法來(lái)提高算法的性能或者減少時(shí)間復(fù)雜度。例如，文獻(xiàn)[15-16]使用禁忌搜索和遺傳算法混合求解這一類問(wèn)題，并得到了較好的結(jié)果。

禁忌搜索、模擬退火、遺傳算法等啟發(fā)式算法可能受到待求解問(wèn)題不同條件的影響，在時(shí)間、效率、精確度等方面表現(xiàn)出一些差異。在問(wèn)題規(guī)模比較大時(shí)，以遺傳算法為代表的進(jìn)化類算法以其優(yōu)良的自適應(yīng)性和學(xué)習(xí)性表現(xiàn)出比較好的性能。

文中針對(duì)約束型p中位問(wèn)題，在經(jīng)典遺傳算法的基礎(chǔ)上，提出了一種改進(jìn)的遺傳算法，并混合使用局部搜索算法，進(jìn)行問(wèn)題的求解。

2 問(wèn)題建模

文中所討論的電力系統(tǒng)設(shè)施選址問(wèn)題將優(yōu)化目標(biāo)抽象為距離的花費(fèi)，目標(biāo)是使得服務(wù)點(diǎn)到設(shè)施點(diǎn)的距離總和最小(當(dāng)然，這個(gè)目標(biāo)根據(jù)不同的問(wèn)題情境是可以進(jìn)行修改的)。將該電力設(shè)施選址問(wèn)題從現(xiàn)實(shí)世界中抽象出來(lái)，并用數(shù)學(xué)語(yǔ)言建模成約束型p-中位問(wèn)題(Capacitatedp-MedianProblem，CPMP)，具體描述如下：

假設(shè)有一個(gè)無(wú)向圖G={V,E}，V為頂點(diǎn)，E為無(wú)向邊。假設(shè)無(wú)向圖是全連通的，即每?jī)蓚€(gè)點(diǎn)之間都有一條邊。那么這個(gè)問(wèn)題可以描述為從無(wú)向圖的頂點(diǎn)集合V中尋找數(shù)量為p的子集，并且滿足以下約束：

(1)

s.t.

(2)

(3)

(4)

上面的模型中出現(xiàn)的數(shù)學(xué)符號(hào)的含義為：

V={1,2,…,n}是所有服務(wù)點(diǎn)集合，同時(shí)也是候選的設(shè)施點(diǎn)(medians)集合；

dij是服務(wù)點(diǎn)i到服務(wù)點(diǎn)j的距離；

xij表示分配與否，xij=1表示服務(wù)點(diǎn)i分配到設(shè)施點(diǎn)j，反之xij=0表示沒有分配；

xjj表示是否被選為設(shè)施點(diǎn)，xjj=1表示點(diǎn)j被選為設(shè)施點(diǎn)，反之xjj=0表示沒被選；

qj表示點(diǎn)j的需求量；

Qj表示設(shè)施點(diǎn)j的容量。

式(1)是該選址問(wèn)題的目標(biāo)函數(shù)，即目標(biāo)為最小化所有服務(wù)點(diǎn)(也稱客戶點(diǎn)，下同)到它所分配的設(shè)施點(diǎn)(medians)的距離總和；式(2)要求每一個(gè)服務(wù)點(diǎn)都分配了惟一一個(gè)設(shè)施點(diǎn)；式(3)表示一共選取了p個(gè)設(shè)施點(diǎn)；式(4)表示每一個(gè)設(shè)施點(diǎn)都不能超過(guò)它的容量限制。

3 遺傳算法

遺傳算法(GeneticAlgorithm)是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法，它最初由美國(guó)J.Holland教授于1975年首先提出。利用遺傳算法求解優(yōu)化問(wèn)題的基本思想是：把需要求解的問(wèn)題模擬成一個(gè)生物進(jìn)化的過(guò)程，通過(guò)復(fù)制、交叉、突變等操作產(chǎn)生下一代的解，并逐步淘汰掉適應(yīng)度函數(shù)值低的解，增加適應(yīng)度函數(shù)值高的解。這樣進(jìn)化N代后就很有可能會(huì)進(jìn)化出適應(yīng)度函數(shù)值很高的個(gè)體，算法能夠保證求解時(shí)的收斂性。

運(yùn)用遺傳算法求解組合優(yōu)化問(wèn)題的主要步驟為：染色體編碼，適應(yīng)值計(jì)算，種群選擇，交叉，變異等。以下將結(jié)合電力設(shè)施選址問(wèn)題對(duì)遺傳算法進(jìn)行具體說(shuō)明。

3.1 染色體編碼

染色體編碼，就是要將待求解問(wèn)題的解表示成基因串的形式，這樣才能使用遺傳算法進(jìn)行求解。

在電力設(shè)施選址的問(wèn)題中，由于可供選址的設(shè)施點(diǎn)是空間離散分布的，所以采用p個(gè)設(shè)施點(diǎn)的索引(編號(hào))來(lái)進(jìn)行染色體的編碼。首先給所有可選擇的設(shè)施點(diǎn)編號(hào)(1,2,…,n)，在遺傳算法中每一條染色體有p個(gè)基因，每一個(gè)基因就是一個(gè)設(shè)施點(diǎn)的編號(hào)。因此，如果p=5，那么染色體gene可能表示成gene={index1，index2，…，index5}，其中index表示可供選擇的設(shè)施點(diǎn)的編號(hào)1,2,…,n。需要特別注意的是，這里的基因是沒有順序的，即染色體{1，3，2}和{1,2,3}是一樣的，這對(duì)于后面交叉操作時(shí)防止同一條染色體出現(xiàn)重復(fù)基因有很大作用。

3.2 適應(yīng)值計(jì)算

遺傳算法中使用適應(yīng)值來(lái)表示解得優(yōu)劣，并作為后續(xù)選擇操作的依據(jù)。在大多數(shù)情況下，人們通常將目標(biāo)函數(shù)映射成函數(shù)值非負(fù)的適應(yīng)值函數(shù)。得到一條染色體之后，定義染色體的適應(yīng)值為所有服務(wù)點(diǎn)到該點(diǎn)所分配的設(shè)施點(diǎn)的距離總和。首先，忽略地理環(huán)境的復(fù)雜信息，考慮兩點(diǎn)之間的歐氏距離。目標(biāo)是最小化距離總和D，如何給所有的服務(wù)點(diǎn)分配一個(gè)設(shè)施點(diǎn)分配以達(dá)到該目標(biāo)。這是一個(gè)廣義分配問(wèn)題(GeneralAssignmentProblem，GAP)，也是一個(gè)NP-hard問(wèn)題。長(zhǎng)期以來(lái)，有許多方法被用來(lái)解決這一問(wèn)題，例如經(jīng)典的貪心算法、基于“優(yōu)先級(jí)”的分配算法、拉格朗日松弛等等。

考慮到計(jì)算的復(fù)雜性和時(shí)間性能，文中采用基于優(yōu)先級(jí)的貪心分配策略，它的時(shí)間復(fù)雜度不高而且效果較理想，能夠較好地解決這一問(wèn)題。該算法的具體流程描述如下：

對(duì)于一個(gè)服務(wù)點(diǎn)c，計(jì)算它到所選取的每一個(gè)設(shè)施點(diǎn)的距離，然后對(duì)得到的距離值進(jìn)行排序。記服務(wù)點(diǎn)到最近的設(shè)施點(diǎn)的距離為d1，到次近的設(shè)施點(diǎn)的距離為d2，那么服務(wù)點(diǎn)c的優(yōu)先級(jí)為：

Priority(c)=d2-d1

首先算出所有服務(wù)點(diǎn)的優(yōu)先級(jí)，然后按照優(yōu)先級(jí)從高到低進(jìn)行分配，優(yōu)先級(jí)越高的優(yōu)先分配設(shè)施點(diǎn)給它。對(duì)此，可以這樣理解，優(yōu)先級(jí)越高的服務(wù)點(diǎn)，說(shuō)明離它最近的設(shè)施點(diǎn)和次近的服務(wù)點(diǎn)相差越大，如果到后面給它分配，一旦離它最近的設(shè)施點(diǎn)的容量已經(jīng)滿了，那么就會(huì)增加很大的花費(fèi)，這是不符合需求的。因此基于這種優(yōu)先級(jí)的貪心方法，可以較好地解決這個(gè)分配問(wèn)題。

3.3 選 擇

選擇是遺傳算法中非常重要的一步，選擇的目的是把優(yōu)化的個(gè)體(或解)直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的。計(jì)算出每條染色體的適應(yīng)值之后，就可以采取一定的選擇策略來(lái)對(duì)種群進(jìn)行選擇。

常用的選擇策略有輪盤賭選擇、錦標(biāo)賽選擇等等，這些選擇方法都有一定的優(yōu)缺點(diǎn)。為了防止種群過(guò)早陷入局部收斂，同時(shí)避免種群的退化，沒有采用輪盤賭的選擇方法，因?yàn)檩啽P賭選擇很快就會(huì)出現(xiàn)大量相同的染色體，從而陷入局部解。

文中采取了一種根據(jù)適應(yīng)值排序的混合選擇策略：首先，計(jì)算每一條染色體的適應(yīng)值，并且按照適應(yīng)值從高到低進(jìn)行排序；然后，按照適應(yīng)值進(jìn)行選擇，適應(yīng)值高的選擇保留到后代，在這個(gè)過(guò)程中需要保證不出現(xiàn)重復(fù)的染色體。同時(shí)，保留很小比例的最差解，有利于防止局部收斂。

3.4 交 叉

類似于自然界生物進(jìn)化過(guò)程，基因的交叉互換和重組能夠產(chǎn)生新的個(gè)體，在遺傳算法中，通過(guò)交叉操作，將大大提高遺傳算法的搜索能力，加速求解過(guò)程，并期望優(yōu)秀的基因結(jié)合在一起，從而得到更優(yōu)解。

例如，c={1,2,3,4,5,6}是最優(yōu)解，而已經(jīng)得到c1={8,9,3,4,5,6}和c2={1,2,6,7,10,11}，那么按照如下的交叉方式進(jìn)行基因重組：

具體來(lái)說(shuō)，根據(jù)前面所述的染色體編碼方法，將采用如下的交叉算法：

(1)預(yù)處理。因?yàn)槊總€(gè)設(shè)施點(diǎn)只能出現(xiàn)一次，所以要保證在經(jīng)過(guò)交叉之后一條染色體中不會(huì)出現(xiàn)兩個(gè)相同的基因。預(yù)處理的方法是：對(duì)于參與交叉的兩條染色體，計(jì)算出染色體相同的部分移到染色體的右邊，并將不同的部分移到左邊。

(2)當(dāng)兩條染色體不完全相同的時(shí)候，進(jìn)行交叉運(yùn)算，可以采用經(jīng)典的單點(diǎn)交叉。

而經(jīng)過(guò)預(yù)處理，兩條染色體變?yōu)椋?/p>

經(jīng)過(guò)交叉互換得到的新的染色體符合要求。

(3)如果兩條染色體完全相同，為了防止陷入局部最優(yōu)解，采用的方法是引入新的染色體，即隨機(jī)生成一條新的染色體，并與之另一條進(jìn)行交換。

3.5 變 異

變異操作是模擬自然界遺傳過(guò)程中的基因突變，需要注意的是，基于突變是隨機(jī)發(fā)生的，而且概率較低。

遺傳算法引入變異操作的主要作用有兩個(gè)：一是使遺傳算法具有局部的隨機(jī)搜索能力。當(dāng)遺傳算法通過(guò)交叉算子已接近最優(yōu)解鄰域時(shí)，利用變異操作的這種局部隨機(jī)搜索能力可以加速向最優(yōu)解收斂。顯然，此種情況下的變異概率應(yīng)取很小的值，否則接近最優(yōu)解的狀態(tài)會(huì)因變異而遭到破壞。二是使遺傳算法可維持群體多樣性，以防止程序出現(xiàn)早熟收斂現(xiàn)象，得不到理想的近似解。

在變異操作中，隨機(jī)地對(duì)染色體的某一個(gè)基因進(jìn)行變異，把這個(gè)基因隨機(jī)替換成另外一個(gè)沒有出現(xiàn)在染色體中的基因，即服務(wù)點(diǎn)的編號(hào)。在這個(gè)過(guò)程中，可以保證一條染色體中不會(huì)出現(xiàn)兩個(gè)相同的基因。比如將c1={2 8 1 4 5 7}進(jìn)行變異操作，可能得到的結(jié)果為：

其中，c1染色體的第5個(gè)基因從5變異為3。

3.6 局部搜索

樸素的遺傳算法在求解時(shí)，需要非常多的迭代次數(shù)，才能得到比較好的近似解。為了提高遺傳算法的搜索能力，加快收斂速度，減少程序的運(yùn)行時(shí)間復(fù)雜度，引入了局部搜索策略。

在完成交叉和變異之后，以一定的比例選取部分染色體進(jìn)行局部搜索，尋找在這個(gè)解得鄰域中的更優(yōu)解。具體的算法流程如下：

首先，對(duì)于所選中的染色體的每一個(gè)基因c，搜索距離它最近的k個(gè)服務(wù)點(diǎn)。其中k是一個(gè)經(jīng)驗(yàn)值，k越大，時(shí)間復(fù)雜度越高，但是k越小，搜索的范圍小，優(yōu)化效果可能也比較小。因?yàn)檫@里是需要做一些局部的優(yōu)化，所以k盡量選擇較小一些，在實(shí)驗(yàn)過(guò)程中需要調(diào)節(jié)k值。

然后，把c替換成它鄰近的服務(wù)點(diǎn)，如果能夠得到更優(yōu)的適應(yīng)值，則替換它。同樣的，這里也需要保證染色體中不出現(xiàn)相同的基因。

經(jīng)過(guò)局部搜索，可以讓部分解加速向最優(yōu)解靠攏，從而加快算法的收斂速度。

4 實(shí)驗(yàn)分析

文中利用C++實(shí)現(xiàn)了前面描述的算法并進(jìn)行了實(shí)驗(yàn)分析。實(shí)驗(yàn)機(jī)器的配置為：CPUInteli5 主頻2.3GHz，內(nèi)存8G。

為了驗(yàn)證算法的正確性和有效性，文中采用了兩個(gè)數(shù)據(jù)集進(jìn)行測(cè)試和驗(yàn)證。第一個(gè)數(shù)據(jù)集是來(lái)自網(wǎng)絡(luò)上著名的優(yōu)化問(wèn)題公開測(cè)試數(shù)據(jù)集—OR-Library(http://people.brunel.ac.uk/～mastjjb/jeb/info.html)。選取了OR-Library中的p-median-capacitated問(wèn)題的測(cè)試數(shù)據(jù)，測(cè)試程序選取其中的10個(gè)測(cè)試用例，其中5組服務(wù)點(diǎn)數(shù)量n為50，設(shè)施點(diǎn)數(shù)目p為5，另外5組服務(wù)點(diǎn)數(shù)量n為100，設(shè)施點(diǎn)數(shù)目p為10。

測(cè)試結(jié)果如表1所示。

表1 第一個(gè)數(shù)據(jù)集上的測(cè)試結(jié)果

分析測(cè)試結(jié)果發(fā)現(xiàn),使用文中改進(jìn)的遺傳算法可以有效解決約束型p中位問(wèn)題。隨著服務(wù)點(diǎn)和設(shè)施點(diǎn)數(shù)量的增加，運(yùn)行的時(shí)間也在增加。在運(yùn)行時(shí)間不超過(guò)30s的情況下，算法最好的結(jié)果誤差為2.6%，最壞的結(jié)果誤差為5.5%。

為了更直觀地顯示程序運(yùn)行的結(jié)果，將其中一組數(shù)據(jù)的服務(wù)點(diǎn)和經(jīng)過(guò)文中算法求解出的設(shè)施點(diǎn)畫在圖上，如圖1所示。

第二個(gè)數(shù)據(jù)集來(lái)源于GIS平臺(tái)收集的數(shù)據(jù)。該平臺(tái)是基于高德地圖針對(duì)某供電局的裝置設(shè)備坐標(biāo)定位而開發(fā)的。通過(guò)該平臺(tái)，獲得了這些客戶點(diǎn)的地理信息數(shù)據(jù)。針對(duì)這些數(shù)據(jù)，對(duì)電力設(shè)施進(jìn)行選址，對(duì)不同

圖1 表1中一組數(shù)據(jù)，設(shè)施點(diǎn)選擇和分配結(jié)果

的設(shè)施點(diǎn)數(shù)量p進(jìn)行實(shí)驗(yàn)，結(jié)果如表2所示。

表2 利用某供電局裝置數(shù)據(jù)測(cè)算結(jié)果

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

文中給出了利用改進(jìn)的遺傳算法解決電力系統(tǒng)設(shè)施選址問(wèn)題的一種實(shí)現(xiàn)方法，并且與網(wǎng)上公開測(cè)試數(shù)據(jù)集進(jìn)行對(duì)比，驗(yàn)證了算法的可行性；同時(shí)該算法也表現(xiàn)出了良好的時(shí)間性能。此外，通過(guò)GIS系統(tǒng)收集了某供電局的電力設(shè)施數(shù)據(jù)并使用該方法進(jìn)行求解，能得出較滿意的結(jié)果。

當(dāng)然，在實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn)，提出的算法處理約束型p中位問(wèn)題時(shí)，對(duì)于不同的問(wèn)題規(guī)模和數(shù)據(jù)表現(xiàn)出了一定的效果差異，這說(shuō)明對(duì)于算法在不同情況的性能的穩(wěn)定性方面還需更深入的工作，加以改進(jìn)和優(yōu)化。

[1] 王 非,徐 渝,李毅學(xué).離散設(shè)施選址問(wèn)題研究綜述[J].運(yùn)籌與管理,2006,15(5):64-69.

[2] 楊豐梅,華國(guó)偉,鄧 猛,等.選址問(wèn)題研究的若干進(jìn)展[J].運(yùn)籌與管理,2005,14(6):1-7.

[3]RollandE,SchillingDA,CurrentJR.Anefficienttabusearchprocedureforthep-medianproblem[J].EuropeanJournalofOperationalResearch,1997,96(2):329-342.

[4]GloverF.Tabusearch-partI[J].ORSAJournalonComputing,1989,1(3):190-206.

[5] 郭崇慧,覃華勤.一種改進(jìn)的禁忌搜索算法及其在選址問(wèn)題中的應(yīng)用[J].運(yùn)籌與管理,2008,17(1):18-23.

[6]MurrayAT,ChurchRL.Applyingsimulatedannealingtolocation-planningmodels[J].JournalofHeuristics,1996,2(1):31-53.

[7]ChiyoshiF,Galv?oRD.Astatisticalanalysisofsimulatedannealingappliedtothep-medianproblem[J].AnnalsofOperationsResearch,2000,96(1-4):61-74.

[8] 秦 進(jìn),史 峰.物流設(shè)施選址問(wèn)題的雙層模擬退火算法[J].系統(tǒng)工程,2007,25(2):36-40.

[9] 許 婷,盛 明,婁彩榮.基于GIS和蟻群算法的物流配送中心選址研究[J].測(cè)繪科學(xué),2010,35(6):206-208.

[10] 李有梅,陳 曄.一種新的求解約束P-中位問(wèn)題的啟發(fā)式算法[J].計(jì)算機(jī)工程,2005,31(19):162-164.

[11]LorenaLAN,SenneELF.Localsearchheuristicsforcapacitatedp-medianproblems[J].NetworksandSpatialEconomics,2003,3(4):407-419.

[12]Estivill-CastroV,Torres-VelázquezR.Hybridgeneticalgorithmforsolvingthep-medianproblem[M]//Simulatedevolutionandlearning.Berlin:Springer,1999:18-25.

[13]AlpO,ErkutE,DreznerZ.Anefficientgeneticalgorithmforthep-medianproblem[J].AnnalsofOperationsResearch,2003,122(1-4):21-42.

[14]GhoseiriK,GhannadpourSF.Solvingcapacitatedp-medianproblemusinggeneticalgorithm[C]//ProcofIEEEinternationalconferenceonindustrialengineeringandengineeringmanagement.[s.l.]:IEEE,2007:885-889.

[15]GloverF,KellyJP,LagunaM.Geneticalgorithmsandtabusearch:hybridsforoptimization[J].Computers&OperationsResearch,1995,22(93):111-134.

[16] 李大衛(wèi),王 莉,王夢(mèng)光.遺傳算法與禁忌搜索算法的混合策略[J].系統(tǒng)工程學(xué)報(bào),1998,13(3):28-34.

Solving Grid System Facility Location Problem Based on Improved Genetic Algorithm

MO Han-pei1，CHEN Qiu-liang2，ZHANG Zi-zhen2

(1.Power Grid Co.,Guangdong Dongguan Power Supply Bureau,Dongguan 523000,China;2.School of Mobile Information Engineering,Sun Yat-Sen University,Zhuhai 519000,China)

Grid system facility location,as a basic problem in grid system plan and design,can be modeled as a capacitatedp-medianproblem,whichisaclassicalNP-hardproblem.Itcanbedescribedasselectingp-capacitatedmediansfromaverticessetinordertoserveasetofdemandvertices(customers),sothatthetotalassigneddemandtoeachofthecandidatemediandoesnotexceeditscapacity,andthecostisminimum.Tosolvethisproblem,animprovedgeneticalgorithmincorporatedwithalocalsearchprocedureisproposedbasedonclassicalgeneticalgorithm.Itcanusetheglobalconvergenceandavoidthelocalconvergenceandprematureingeneticalgorithmtoobtainthemoreaccurateapproximatedsolution.Thealgorithmhasbeentestedusingstandardtestingdataandtherealdatacollectedbyageographicinformationsystem.Theresultsshowthatthismethodcanprovideafeasibleandpromisingsolutionfortheindustry.

facility location;genetic algorithm;capacitatedp-medianproblem;NP-hard;GISplatform

2015-01-06

2015-04-10

時(shí)間：2016-02-18

中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金(15lgpy37)

莫漢培(1967-)，男，助理工程師，主要從事電力系統(tǒng)管理工作。

http://www.cnki.net/kcms/detail/61.1450.TP.20160218.1619.014.html

TP

A

1673-629X(2016)03-0197-05

10.3969/j.issn.1673-629X.2016.03.046