一種基于進化算法的銀行網點選址求解方法

范人勝，杜紅濤，周丹，吳洪，陳俊，何勇

（1.廣東省農村信用社聯合社，廣州 510000；2.珠海市長陸工業自動控制系統股份有限公司，珠海 519090）

0 引言

選址問題是運籌學和管理科學中經典的決策問題，有著巨大的經濟和社會研究價值，其主要研究選擇設施的數目同和確定設施的最優位置，實現為用戶提供優質服務價值的目的。自1964年Hakimi提出選址問題[1]后，大大激發了選址問題的研究，許多學者投身到選址問題的理論研究中。Hedetniemi等人[2]在一個無權重的網絡中選擇一個設施點，并新設計了算法解決此類問題，文獻[3]提出可變領域搜索和禁忌搜索結合的算法求解離散選址問題。Goldman研究在樹狀網上選擇設施點的中值問題[4]，其方法為先任選網絡上的一個節點，計算該節點的權重是否超過所有節點權重的一半，是則選為中值點。Berman等人[5]利用最大覆蓋模型求解距離，并針對不同情形做了改進。在選址模型的應用中，大部分用于物流中心、醫院、消防站等公共服務領域，在銀行選址方面的應用研究相對較少[6]。

銀行網點作為一種服務類公共商業設施，其服務理念是“以客戶為中心”，銀行網點選址合理與否不僅影響到人民的生活質量，也關系到企業的戰略發展[7]，合理的銀行網點選址在給人民帶來生活便利的同時，也給企業帶來更大的收益。銀行選址作為一門重要的研究課題，學者們用不同的理論和方法對其做了探索和研究。文獻[8]設計了基于LBI的網點選址算法對網點進行部署。楊柳等人[9]提出用GIS技術確定ATM機的布局。文獻[10]利用復雜網絡方法，提出基于復雜網絡的網點選址優化模型。Richard[11]利用GIS空間交互模型進行網點選址研究。Philip等人[12]采用了Huff模型構建銀行網點選址模型。目前大多數銀行選址研究都是基于離散型的，即在給定的網絡節點上選取銀行網點的部署位置；而連續型選址研究較少，其是指在給定的整個備選區域選取最優的位置。連續型選址相對于離散型選址來說，位置的選取是全局范圍內尋找，對于環境的適應性更強，求解的難度更大[13]，連續型選址屬于NP難問題。本文研究的銀行網點選址是基于連續型的，考慮到經濟實用性以及成本問題,以銀行網點到居民點的路徑長度最小作為優化目標。

差分進化（DE）算法是一種啟發式優化算法，具有受控參數少、魯棒性強等特點，在約束優化、聚類優化和神經網絡優化等方面得到了廣泛應用[14-16]。該算法在變異方面使用了差分策略，提高算法的搜索效率，避免了變異方式的不足，其具備全局并行和高效搜索的特性[17-18]，適合解決連續優化問題。但初始種群的個體分布會影響到算法的全局收斂能力[19]，為此本文找尋了可以縮小網絡覆蓋半徑的均值點，作為差分進化算法的初始位置，從而提出解決連續K中心網點選址問題的均值點差分進化（Mean Points DE，MDE）算法。

1 銀行網點選址模型

本文采用幾何方式，將網點選址問題轉化為圖論問題。網點位置選取的不同，將對居民的生活便利產生影響。如圖1-（A）所示，四節點構成的網絡圖G1，假定無向邊的長度都是2。圖1-（B）在節點v3設定網點位置，網點S到最遠居民點v4的距離為2；圖1-（C）將v2選定為網點S的部署位置，網點S到最遠居民點v4的距離為 4，對比圖 1-（B）和 1-（C）可知，網點位置選取的不同，其到各居民點的距離將產生差異，進而影響居民的生活質量。銀行網點選址問題的主要目標就是通過調整網點位置，最大限度地提高網點對居民的服務質量。

圖1 銀行網點選址問題

網點選址對應的網絡拓撲圖用G(V,E)表示，其中V(G)={v1,v1,···,vn}，V(G)是指n個網絡節點構成的集合。lij為節點vi和vj的歐幾里得距離，對于任意兩節點vi和vj間的距離小于等于給定的半徑r時（即lij≤r），稱兩節點互為鄰接節點，且兩節點之間有邊相連，鄰接節點間的所有邊構成集合E(G)。

在銀行網點選址中，需要設置網點為居民點提供服務，居民點會以距離其最小的銀行網點作為其服務節點。假設給定網絡G的規模為n，設置服務網點數量為K個，是網絡G的鄰接矩陣，如果e(vi,vj)∈E(G)，則eij=1，否則eij=0。最短距離矩陣為表示網絡G中節點vi到vj的最短路徑距離，最短距離矩陣可由Floyd算法求得。如果d(vi,uj)≤d(vi,ul),j,l≤k,l≠j，則節點vi選擇uj為其服務網點，此時網點uj的服務集Uj包含vi，即vi∈Uj。uj與服務集Uj中節點間最大的最短路徑距離為，稱為網點uj的覆蓋半徑。所有網點中的最大覆蓋半徑稱為網點集的覆蓋半徑，也稱為客戶節點到網點集的路徑長度。

服務網點集的覆蓋半徑是網點選址好壞的重要評價指標，覆蓋半徑越小，居民獲得銀行服務越便利。因此，銀行網點選址問題的優化目標為網點集的覆蓋半徑最小，即路徑長度最小，其模型為式：

其中，R2為圖G所在的二維平面。

根據網點設置位置不同，銀行網點選址問題又分為離散K中心網點選址問題和連續K中心網點選址問題。離散K中心網點選址問題是在節點集V(G)中選取K個位置作為網點。而連續K中心網點選址問題是指在有界平面R2中無約束地選取K個位置并設置為網點，網點設置方式靈活高效。連續K中心網點選址相比于離散K中心網點選址，能夠獲得更小的覆蓋半徑。

圖2 4客戶節點網點部署示意圖

同樣以如圖1-（A）的網絡圖為例。圖2-（A）為離散K中心網點選址問題的選取方法，在V(G)中選擇v2節點作為網點部署位置，全局最優的覆蓋半徑為4，圖2-（B）為連續K中心網點選址問題的選取方法，在平面R2中選取一個合適的位置設置網點，覆蓋半徑降低為3，優于離散K中心網點選址問題的覆蓋半徑。連續K中心網點選址問題是指在整個網絡平面范圍內，選擇任意K個位置來設置銀行網點，因此連續K中心網點選址問題是NP難問題，難以通過經典數學方式進行精確求解。對于連續優化問題，進化算法有較好的求解效果。

2 基于改進差分進化算法的銀行網點選址

差分進化（DE）算法是一種基于群體差異的隨機搜索算法，該算法具有較強的搜索能力和魯棒性，適合求解連續空間優化問題。針對連續K中心網點選址問題，初始種群的個體分布會影響算法的全局收斂能力，優化種群的初始位置，可提高算法的收斂效果。為此，本文引入了基于均值點的初始種群生成方法，提出了一種均值點的差分進化（MDE）算法。

2.1 MDE算法的初始化

在連續K中心網點選址的網絡拓撲圖中，規定兩節點的距離lij≤r時，兩節點之間有邊相連，節點vi的覆蓋范圍是一個半徑為r的球形鄰域：Bi=如圖3（A）所示的三節點網絡圖，其中r＜l(v1,v2)≤2r。如圖 3（B）所示，陰影區D=B1?B2。若在雙節點的陰影區D上部署網點節點，可以連通節點v1和v2，而v1和v2的中點c位陰影區內，在中點c處部署網點可以有效連接節點v1、v2和v3。中點c具有較好的連通性，可以有效縮短覆蓋半徑。因此，在平面R2上距離滿足r＜lij≤2r的雙節點具有重要意義，同理推廣到任意雙節點的情況。

圖3 三節點網絡圖

在網絡圖G中，任意兩個節點vi和vj，如果兩節點之間的距離滿足：r＜lij≤2r，則有Dij=Bi?Bj≠?，稱Dij為雙節點vi和vj的公共覆蓋區域。在Dij內的任意節點可與vi,vj同時建立連接，則Dij具有較好的連通效果，具有降低網點覆蓋半徑的潛質。而vi和vj所在直線的中點，根據圓的相交定理可知，中點cij∈Dij。因此可通過一個確定的點cij來代表公共覆蓋區域，稱點cij為網絡圖G的均值點，在均值點處部署網點，可以增加周邊節點的連通性，達到降低網點覆蓋半徑的目的。

尋找到網絡圖G的全部均值點{cij}后，將均值點用于MDE算法的初始化。算法的初始化描述如下：隨機選擇均值點作為網點節點的位置，K個網點節點的位置坐標拼接成一個個體的初始位置。

2.2 MDE算法的編碼表示和動態方程

MDE算法的第i個個體表示為：xi=(xi1,xi2,…,xim)。在連續K中心網點選址問題的求解過程中，MDE算法的每個個體代表網點選址問題的一組解，編碼方式為K個網關在平面R2上的坐標位置的組合，網點選址的位置分別為：(a1,b1),(a2,b2),…,(aj,bj),…,(aK,bK)，其中aj=x2j-1;bj=x2j;m=2K。

MDE算法在迭代過程中，通過變異、交叉和選擇更新個體的位置，從而搜索得到更加優秀的解。在種群初始化后，MDE算法通過差分策略實現個體變異。變異策略是隨機選擇兩個不同的個體，將待變異個體與縮放后的向量差進行向量合成，產生一個變異向量。變異向量的計算見式（1）。

其中i≠r1≠r2≠r3，χ為縮放因子，vi(t+1)表示(t+1)時刻第i個變異向量。為了完善差分變異搜索策略，MDE算法使用了交叉操作。在(t+1)時刻，對種群中的目標個體與其變異向量進行個體間的交叉操作，如式（2）所示，其中CR為交叉概率，CR∈[0,1]，jrand為[1,2,3,···,2K]的隨機整數。xi,j(t)表示t時刻第i個個體的第j位元素。

通過交叉操作后，得到目標個體的試驗向量ui。交叉完成后，按照式（3）進行選擇操作。

其中f(xi)為個體xi對應的適值。如果試驗向量的目標函數值小于等于目標個體的函數值時，那么試驗向量就取代目標個體進入下一代；否則目標個體就會繼續保持到下一代中。通過比較每一個試驗向量和被它們繼承了參數的目標個體可以看出，MDE算法比其他進化算法更緊密地將交叉和選擇結合起來。

2.3 MDE算法適值函數設計

在連續K中心網點選址問題中，適值函數越小，個體就越優秀，適值函數為個體的覆蓋半徑。MDE算法的每個個體代表K網點坐標位置的組合，因為個體可以降落到平面的任意位置，所以計算個體到居民節點的距離比較困難，可以采用如下方法進行計算。

個體的第k個網關uk的位置為ok=(ak,bk)，其中1≤k≤K。節點vi到其最近網點的距離為。則個體 (o1,o2,···,oK)的覆蓋半徑即該個體的適值為

2.4 MDE算法在網點選址中的實現

MDE算法的種群是隨機產生的，每個個體代表網點選址的一組解，計算迭代過程中每個個體的適值，并記錄種群的最小適值，MDE算法求解連續K中心網點選址的步驟如下：

Step1：初始化數目為PopSize的種群，在網絡圖的均值點出初始化種群的位置，并計算每個目標向量的適值，即覆蓋半徑R。

Step2：設定參數，確定縮放因子χ和交叉概率CR值。

Step3：根據式（1）對種群中的個體進行變異操作，產生變異后的中間體變異向量。

Step4：根據式（2）對變異向量和父代中的目標個體進行交叉操作，產生交叉后的試驗向量ui。

Step5：計算交叉后的試驗向量與父代中目標個體的適應值，根據式（3）產生新的一代種群。當滿足F(ui)＜F(xi)時，ui取代目標個體原來的位置；否則，不取代。

Step6：當個體的適值收斂或達到了最大迭代次數時，算法結束運行；否則返回Step3。

算法的偽代碼描述為：

3 仿真分析

本節的仿真環境是：MATLAB 2015a，內存8GB，CPU主頻為2.5GHz的四核計算機。實驗分別采用50、100、150和200節點規模的隨機網絡仿真連續K中心網點選址問題，網絡圖是連通的，節點度介于1和11，4種規模的網絡拓撲如圖4所示。實驗以最小覆蓋半徑作為優化目標，將MDE算法與經典的PSO算法和GA算法進行實驗結果對比。

圖4 4種規模的網絡拓撲圖

3.1 算法在不同網絡規模下的優化效果

表1為MDE、PSO、GA這3種算法在50,100,150,200不同規模隨機網絡中的優化結果，設定服務網點數目為5。表1分別記錄了3種算法20次獨立試驗結果中，覆蓋半徑的最大值、最小值、平均值和標準差。

從表1對比3種算法的最小覆蓋半徑可知，MDE算法的各項指標要優于PSO算法和GA算法。MDE算法的標準差較小，穩定性較強。MDE算法與GA算法原理相同，都采用了變異、交叉和選擇機制，但MDE算法在變異方面使用了差分策略，即使用了差分向量對個體進行擾動，實現個體變異，可以有效利用群體分布的特性，提高算法的搜索效率，避免了變異方式的不足。MDE算法和PSO算法都適合解決連續空間優化問題，但PSO算法在搜索過程中，容易陷入局部最優，搜索結果的魯棒性較差，相比PSO算法，MDE算法的全局搜索能力強，搜索精度高，穩定性強。

表1 3種算法在不同節點規模下的覆蓋半徑結果

3.2 算法在不同網絡規模下的收斂性過程

圖5為MDE、PSO和GA算法在4種不同網絡規模下的迭代收斂過程，A-D的網絡規模分別為50,100,150,200節點。從圖中可以看出，各算法初始值與收斂值差異較大，收斂過程對比明顯。

圖5 3種算法收斂過程分析

對比3個算法的初始值可知，GA算法的初始值最大，MDE算法與PSO算法的初始值相似，但稍微優于PSO算法。對比3個算法的收斂過程可知，GA算法和PSO算法收斂最快，容易陷入局部最優解；MDE算法收斂最慢，MDE算法的差分進化策略保障了種群多樣性，收斂過程較慢，更易于收斂全局最優解。

3.3 算法在不同服務網點數目情況下的優化效果

表2為MDE、PSO、GA這3種算法在200網絡規模情況下，設定不同服務網點數目，獨立運行20次時，覆蓋半徑的最大值、最小值、平均值和標準差。

表2 3種算法在不同服務網點數目下的覆蓋半徑結果

從表2的實驗結果可知，在服務網點數目一定的情況下，MDE算法的覆蓋半徑要優于PSO算法和GA算法，各項指標表現更優秀。GA算法解決的是離散K中心選址問題，服務網點部署在網絡節點上，MDE算法和PSO算法解決的是連續K中心選址問題，服務網點部署在非鄰接節點的中心位置，能夠縮短其到周圍節點的路徑長度。

4 結語

針對銀行網點選址問題，本文提出采用全局搜索能力較強的MDE算法解決連續型網點選址問題，以網點集的覆蓋半徑最小為優化目標，找尋了可以縮小覆蓋半徑的種群初始位置，并設計了新的適值函數。通過對比PSO和GA算法的實驗結果，MDE算法收斂獲得更加優秀的可行解。本文采用MDE算法解決連續K中心銀行網點選址問題，為研究其他連續型設施選址問題提供了一種很好的解決方法。