一種基于市場(chǎng)真實(shí)情況的ATM選址模型的研究及應(yīng)用

周繼恩　馮　興　馮　鑫

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

0　引　言

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

1　P-Median問(wèn)題與ATM選址原則

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

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

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

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

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

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

1) ATM市場(chǎng)為競(jìng)爭(zhēng)市場(chǎng)，即市場(chǎng)中包含多家銀行的ATM。

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

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

2　ATM選址模型定義

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

2.1　需求與競(jìng)爭(zhēng)因素評(píng)估

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

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

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

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

2.2　Voronoi圖與空間劃分

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

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

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

(1)

圖1　Voronoi圖示例

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

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

(2)

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

3　算　法

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

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

輸入：N個(gè)數(shù)據(jù)點(diǎn)和簇?cái)?shù)目K

輸出：K個(gè)簇

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

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

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

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

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

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

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

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

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

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

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

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

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

6. 在每個(gè)Voronoi圖區(qū)域內(nèi)選取需求點(diǎn)為新部署點(diǎn)使得區(qū)域中其他需求點(diǎn)到新部署點(diǎn)競(jìng)爭(zhēng)值衰減的加權(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銀行市場(chǎng)中已有的ATM部署地點(diǎn)有59個(gè)，以B銀行已有ATM部署點(diǎn)對(duì)深圳市建立Voronoi圖的結(jié)果見圖2，深圳市ATM需求點(diǎn)分布見圖3，B銀行ATM的競(jìng)爭(zhēng)點(diǎn)分布見圖4。

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

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

選址數(shù)部署地點(diǎn)經(jīng)緯度需求點(diǎn)加權(quán)距離和0無(wú)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個(gè)新ATM部署地點(diǎn)，結(jié)果見表2。計(jì)算和實(shí)驗(yàn)結(jié)果表明僅添加4個(gè)B銀行ATM部署點(diǎn)就可將所有需求點(diǎn)的加權(quán)距離和減小11.8%。

5　結(jié)　語(yǔ)

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

[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空間分析與模糊綜合評(píng)判在銀行ATM網(wǎng)點(diǎn)選址中的應(yīng)用[J].測(cè)繪科學(xué),2008,33(1):229-231.

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

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

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