周繼恩　馮　興　馮　鑫

(中國銀聯(lián)股份有限公司　上海 201201)

0　引　言

隨著社會經(jīng)濟(jì)的不斷發(fā)展，自動取款機(jī)ATM已經(jīng)成為人們經(jīng)濟(jì)生活中不可或缺的重要基礎(chǔ)設(shè)施之一。對銀行而言，合理的ATM部署不僅能夠提升銀行客戶的用戶體驗(yàn)，而且能夠幫助銀行在激烈的行業(yè)競爭中發(fā)掘潛在客戶和提高市場份額。設(shè)施區(qū)位問題是關(guān)于設(shè)施在空間最優(yōu)化布局的區(qū)位分析問題?；镜脑O(shè)施區(qū)位問題考慮在離散空間中放置P個設(shè)施以服務(wù)D個需求點(diǎn)，并根據(jù)實(shí)際問題提出不同的優(yōu)化目標(biāo)獲得不同的模型，如P-Meidan[1]問題中的minisum模型考慮最小化需求點(diǎn)與其最近設(shè)施點(diǎn)的加權(quán)距離和，其中權(quán)重為該需求點(diǎn)的需求值。minimax模型[2]考慮最小化所有需求點(diǎn)與其最近設(shè)施點(diǎn)的距離的最大值。ATM選址可以被視為一種特定的設(shè)施區(qū)位問題，但由于ATM市場情況高度復(fù)雜，ATM的部署受到人口密度、商業(yè)因素、競爭因素和已部署機(jī)具等多方面影響。經(jīng)典的設(shè)施區(qū)位問題由于其數(shù)學(xué)模型的抽象性，無法適用于ATM選址問題。本文提出一種更加適用于ATM選址的P-Median問題的一種變形，設(shè)計(jì)了基于Voronoi圖和修改的K中心點(diǎn)聚類的求解算法，構(gòu)建了更加符合市場真實(shí)情況的ATM選址模型，并以深圳市某銀行為例，應(yīng)用模型獲得ATM的合理部署位置。

1　P-Median問題與ATM選址原則

P-Median問題是一個經(jīng)典的設(shè)施區(qū)位問題，由Hakimi[1]在其影響深遠(yuǎn)的工作中提出。P-Median問題考慮在離散空間中部署P個設(shè)施，使得空間中需求點(diǎn)與其距離最近的設(shè)施的加權(quán)距離和最小，需求點(diǎn)的權(quán)重為其需求值。從定性的角度來看，P-Median問題試圖使所放置的P個設(shè)施盡量靠近空間中的需求點(diǎn)。Kariv等[3]證明在一般的圖結(jié)構(gòu)中，P-Median問題是一個NP難的問題。因此P-Median問題的求解通常使用近似或啟發(fā)式算法[4]。P-Median問題是設(shè)施區(qū)位問題的核心，很多現(xiàn)實(shí)生活中的設(shè)施區(qū)位問題都可以轉(zhuǎn)化成為P-Median問題。

與P-Median問題相似，ATM選址的一個原則同樣是試圖讓ATM盡可能靠近用戶。但ATM選址問題難以直接轉(zhuǎn)化為P-Median問題，原因如下：

1) P-Median問題及其他經(jīng)典設(shè)施區(qū)位問題通常考慮在空白的空間中投放設(shè)施，即研究區(qū)域中無已部署設(shè)施。對于ATM選址而言，由于市場中已經(jīng)存在大量ATM且ATM的部署與裁撤具有較高的成本，空白區(qū)域假設(shè)不適用。

2) P-Median問題不考慮空間中同類設(shè)施的競爭影響，而ATM市場則是一個高度競爭的市場，ATM選址模型須考慮競爭因素。

3) 在P-Median問題及其他經(jīng)典設(shè)施區(qū)位問題中，空間中的需求點(diǎn)和其需求值大小通常為已知固定值。ATM選址問題中，用戶的位置與其需求值大小比較模糊，需要首先對需求點(diǎn)進(jìn)行篩選并評估需求值。

ATM選址是一個復(fù)雜的商業(yè)決策過程，影響ATM部署合理性的因素非常多，各個因素之間的相互關(guān)系也非常復(fù)雜。為了使問題更加清晰，本文遵循以下幾點(diǎn)假設(shè)：

1) ATM市場為競爭市場，即市場中包含多家銀行的ATM。

2) 用戶優(yōu)先考慮使用與自身距離最近及與其持有銀行卡相同開戶行名稱的ATM，否則跨行取款需付手續(xù)費(fèi)。

3) 各個銀行的持卡人均勻分布于市場中，即在空間中每一個子區(qū)域內(nèi)各銀行的持卡人數(shù)比例與空間整體各銀行的持卡人數(shù)比例相同。

2　ATM選址模型定義

本文提出一種基于P-Median問題的ATM選址模型，模型具有一個研究主體B銀行(如無特殊說明，后文使用B銀行代表模型研究主體)。為符合市場實(shí)際情況，模型加入多銀行競爭因素并在已有ATM的基礎(chǔ)上在空間中選取P個B銀行ATM部署地點(diǎn)，使得空間中的需求點(diǎn)與其距離最近的B銀行ATM加權(quán)距離和最小，其中權(quán)重為需求值。

2.1　需求與競爭因素評估

影響ATM選址的因素很多，包括研究區(qū)域的GDP、人口密度、公共設(shè)施分布、商圈分布等[5]。建立ATM選址模型需要首先對研究區(qū)域從空間因素和經(jīng)濟(jì)因素等方面進(jìn)行考察[6]，篩選需求點(diǎn)，評估需求值。一般而言，ATM的交易量與其地理位置的人流量成正比，因?yàn)橛脩敉ǔＴ诔鲂型局惺褂肁TM。基于此，本文選取需求點(diǎn)類型包括：小區(qū)、寫字樓、商圈、科技工業(yè)園區(qū)、機(jī)場、火車站、地鐵站。不同的需求點(diǎn)通常具有不同的需求值，基于模糊綜合評判方法[7]，本文使用需求點(diǎn)的類型因子和規(guī)模因子對需求值進(jìn)行評估。類型因子即需求點(diǎn)所屬類型的權(quán)重值，規(guī)模因子即評價同類需求點(diǎn)的規(guī)模大小因子值，類型因子與規(guī)模因子的乘積為需求點(diǎn)最終的需求值。各個需求點(diǎn)的類型因子和規(guī)模因子通過分析ATM的交易數(shù)據(jù)獲得，結(jié)果如表1所示。

表1　ATM選址需求點(diǎn)需求值評估

由于城市的小區(qū)、地鐵站等通常較多，易導(dǎo)致研究區(qū)域需求點(diǎn)過于密集，為了提高模型的計(jì)算效率，在實(shí)際的模型計(jì)算中首先對選取的需求點(diǎn)進(jìn)行合并。由于不同的需求點(diǎn)類型權(quán)重不同，本文對距離500米以內(nèi)的同類型需求點(diǎn)進(jìn)行合并。

基于假設(shè)1，在建立ATM選址模型時須考慮競爭因素。由于市場中通常有多家銀行，為使問題清晰，除研究主體B銀行外，市場中其他銀行的ATM均視為競爭點(diǎn)。通常，各個銀行的發(fā)卡量不同，基于假設(shè)2，不同銀行在市場中競爭影響大小并不相同?；诩僭O(shè)3，為對不同銀行的ATM競爭影響進(jìn)行評估，本文使用研究區(qū)域內(nèi)某一銀行在中國銀聯(lián)跨行轉(zhuǎn)接交易中的銀行卡交易活躍程度作為該銀行ATM的競爭影響權(quán)重。

2.2　Voronoi圖與空間劃分

本文使用2維的Voronoi圖[8]，以B銀行ATM為生成元構(gòu)建ATM實(shí)施部署的拓?fù)浣Y(jié)構(gòu)平面圖，并為需求點(diǎn)和競爭點(diǎn)快速確認(rèn)距離其最近的B銀行ATM。Voronoi圖是一種平面分割方法，其使用N個生成元將平面劃分為N個區(qū)域，每個區(qū)域僅存在1個生成元，并使得每個區(qū)域中的點(diǎn)到該區(qū)域中生成元的距離比到其他生成元距離更近。Voronoi圖的示例見圖1，其數(shù)學(xué)定義如公式所示：

在距離空間(X，d)中有n個點(diǎn)s1，s2，…，sn， 將X劃分為n個區(qū)域使得：

Si={x∈X|d(x,si)

(1)

圖1　Voronoi圖示例

2.3　ATM選址數(shù)學(xué)模型

假定在空間中已有B銀行的T個ATM部署點(diǎn)，添加P個ATM部署點(diǎn)，則空間中B銀行共有T+P個ATM部署點(diǎn)s1，s2，…，st+p。以B銀行ATM為生成元對空間建立Voronoi圖，每個Voronoi圖區(qū)域內(nèi)有M個需求點(diǎn)c1，c2，…，cm，對應(yīng)的需求值分別為w1，w2，…，wm，N個競爭點(diǎn)競爭值分別為b1，b2，…，bn。ATM選址數(shù)學(xué)模型如公式所示：

(2)

對每一個Voronoi區(qū)域，如果該區(qū)域的競爭值之和越大，即式(2)中的分母越大，那么該區(qū)域的用戶將更有可能被競爭點(diǎn)分流，該區(qū)域的需求點(diǎn)的權(quán)重將更小，模型優(yōu)化過程中將避免在此類區(qū)域添加ATM。

3　算　法

3.1　K中心點(diǎn)聚類與勞埃德算法

K中心點(diǎn)聚類是K均值聚類算法的一種變體。K中心點(diǎn)聚類考慮將N個數(shù)據(jù)點(diǎn)分為K個組，使得每個組內(nèi)的數(shù)據(jù)點(diǎn)之間的距離較小，而不同組數(shù)據(jù)點(diǎn)之間的距離較大。與K均值聚類不同，K中心點(diǎn)聚類僅以數(shù)據(jù)點(diǎn)本身為簇中心，以減小對異常數(shù)據(jù)的敏感性。勞埃德算法[9]是一種常見的K中心點(diǎn)聚類算法，算法步驟如下：

輸入：N個數(shù)據(jù)點(diǎn)和簇數(shù)目K

輸出：K個簇

1. 從N個數(shù)據(jù)點(diǎn)中隨機(jī)選擇K個點(diǎn)作為初始簇中心點(diǎn)；

2. 計(jì)算每個數(shù)據(jù)點(diǎn)到K個簇中心點(diǎn)的距離，將數(shù)據(jù)點(diǎn)分配到距離其最近的簇中心點(diǎn)形成K個簇；

3. 在每個簇中，選取一個新的簇中心點(diǎn)使得簇中其他點(diǎn)到簇中心點(diǎn)的距離和最?。?/p>

4. 如果數(shù)據(jù)點(diǎn)到其所屬簇中心的距離和的變化在預(yù)設(shè)精度內(nèi)，則算法停止，否則回到步驟2。

3.2　K中心點(diǎn)聚類與ATM選址

在一般的圖結(jié)構(gòu)中，P-Median問題的計(jì)算復(fù)雜性是NP難題，但Hakimi[3]證明P-Median問題中總有一組最優(yōu)解使得P個設(shè)施的部署位置位于空間中的需求點(diǎn)上，這個結(jié)論被稱為Hakimi性質(zhì)?；贖akimi性質(zhì)，本文使用一種修改的勞埃德算法將新添加的ATM部署點(diǎn)置于空間中的需求點(diǎn)上。經(jīng)典的勞埃德算法在迭代過程中所有的簇中心均發(fā)生更新，本文提出的ATM選址模型系基于空間中已有的ATM，因此在算法迭代過程中將以B銀行已有ATM為固定簇中心不進(jìn)行更新。本文首先在B銀行已有ATM所在位置添加一個需求值為無窮大的需求點(diǎn)以保證已有ATM為固定簇中心在迭代過程中保持不變，算法步驟如下：

輸入：N個需求點(diǎn)與競爭點(diǎn)，K個已有B銀行ATM部署點(diǎn)，新增ATM部署點(diǎn)數(shù)目P

輸出：K+P個ATM部署點(diǎn)

1. 計(jì)算空間中每個需求點(diǎn)的需求值與每個競爭點(diǎn)的競爭值；

2. 在B銀行已有K個ATM處添加需求值為無窮大的需求點(diǎn)；

3. 在空間中隨機(jī)選擇P個點(diǎn)為新ATM部署點(diǎn)；

4. 基于B銀行所有K+P個ATM部署點(diǎn)對空間建立Voronoi圖；

5. 計(jì)算每個Voronoi圖區(qū)域內(nèi)的競爭值；

6. 在每個Voronoi圖區(qū)域內(nèi)選取需求點(diǎn)為新部署點(diǎn)使得區(qū)域中其他需求點(diǎn)到新部署點(diǎn)競爭值衰減的加權(quán)距離和最小；

7. 如果所有部署點(diǎn)的位置變化在預(yù)設(shè)經(jīng)度內(nèi)，算法停止，否則回到步驟4。

4　實(shí)驗(yàn)結(jié)果

本文以深圳市B銀行(某真實(shí)的商業(yè)銀行)為例，應(yīng)用ATM選址模型選取新的ATM部署地點(diǎn)。B銀行市場中已有的ATM部署地點(diǎn)有59個，以B銀行已有ATM部署點(diǎn)對深圳市建立Voronoi圖的結(jié)果見圖2，深圳市ATM需求點(diǎn)分布見圖3，B銀行ATM的競爭點(diǎn)分布見圖4。

圖2　B銀行已有ATM建立Voronoi圖

圖3　深圳市ATM需求點(diǎn)分布

選址數(shù)部署地點(diǎn)經(jīng)緯度需求點(diǎn)加權(quán)距離和0無530．191(113．83120°，22．72800°)513．252(113．86840°，22．56658°)(114．01290°，22．63699°)491．714(113．88510°，22．54974°)(114．03030°，22．61055°)(114．04010°，22．62283°)(114．00610°，22．64311°)467．56

應(yīng)用ATM選址模型為B銀行分別添加1、2、4個新ATM部署地點(diǎn)，結(jié)果見表2。計(jì)算和實(shí)驗(yàn)結(jié)果表明僅添加4個B銀行ATM部署點(diǎn)就可將所有需求點(diǎn)的加權(quán)距離和減小11.8%。

5　結(jié)　語

本文通過篩選與ATM選址相關(guān)的需求點(diǎn)，考慮多銀行ATM的競爭影響并基于市場中已有ATM，構(gòu)建一種更符合真實(shí)市場情況的ATM選址模型，并設(shè)計(jì)了一種基于Voronoi圖和K中心點(diǎn)聚類的模型求解算法。由于影響ATM選址的因素諸多且復(fù)雜，在模型設(shè)計(jì)過程中，描述了考慮加入哪些因素和如何確定各個因素的權(quán)重等棘手問題的解決方法。在模型中加入更多的因素通?？梢允鼓Ｐ透咏鎸?shí)情況，但同時也會增加模型的復(fù)雜度，使得模型求解難度增加。如何根據(jù)不同的應(yīng)用場景和求解目的，平衡模型的復(fù)雜度與求解難度，是一個具有應(yīng)用價值的研究方向。

[1] Hakimi S L.Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems[J].Operations Research,1965,13(3):462-475.

[2] Hakimi S L.Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph[J].INFORMS,1964,12(3):450-459.

[3] Kariv O,Hakimi S L.An Algorithmic Approach to Network Location Problems.II:The p-Medians[J].Siam Journal on Applied Mathematics,1979,37(3):539-560.

[4] Nenad Mladenovic,Brimbergb J,Hansenc P,et al.The p-median problem:A survey of metaheuristic approaches[J].European Journal of Operational Research,2007,179(3):927-939.

[5] Zineldin M.Bank strategic positioning and some determinants of bank selection[J].International Journal of Bank Marketing,1996,14(6):12-22.

[6] 黎雯,周廷剛,張偉.GIS空間分析與模糊綜合評判在銀行ATM網(wǎng)點(diǎn)選址中的應(yīng)用[J].測繪科學(xué),2008,33(1):229-231.

[7] 戴曉愛,李麗.GIS與模糊綜合評判方法在垃圾填埋場選址中的應(yīng)用[J].測繪科學(xué),2011,36(5):128-130.

[8] 陳軍.Voronoi動態(tài)空間數(shù)據(jù)模型[M].北京:測繪出版社,2002.

[9] Lloyd S P.Least squares quantization in PCM[J].IEEE Transactions on Information Theory,1982,28(2):129-137.