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

周繼恩　馮　興　馮　鑫

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

0　引　言

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

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

P-Median問題是一個經(jīng)典的設(shè)施區(qū)位問題，由Hakimi[1]在其影響深遠的工作中提出。P-Median問題考慮在離散空間中部署P個設(shè)施，使得空間中需求點與其距離最近的設(shè)施的加權(quán)距離和最小，需求點的權(quán)重為其需求值。從定性的角度來看，P-Median問題試圖使所放置的P個設(shè)施盡量靠近空間中的需求點。Kariv等[3]證明在一般的圖結(jié)構(gòu)中，P-Median問題是一個NP難的問題。因此P-Median問題的求解通常使用近似或啟發(fā)式算法[4]。P-Median問題是設(shè)施區(qū)位問題的核心，很多現(xiàn)實生活中的設(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ū)位問題中，空間中的需求點和其需求值大小通常為已知固定值。ATM選址問題中，用戶的位置與其需求值大小比較模糊，需要首先對需求點進行篩選并評估需求值。

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

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

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

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

2　ATM選址模型定義

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

2.1　需求與競爭因素評估

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

表1　ATM選址需求點需求值評估

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

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

2.2　Voronoi圖與空間劃分

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

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

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

(1)

圖1　Voronoi圖示例

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

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

(2)

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

3　算　法

3.1　K中心點聚類與勞埃德算法

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

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

輸出：K個簇

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

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

3. 在每個簇中，選取一個新的簇中心點使得簇中其他點到簇中心點的距離和最??；

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

3.2　K中心點聚類與ATM選址

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

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

輸出：K+P個ATM部署點

1. 計算空間中每個需求點的需求值與每個競爭點的競爭值；

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

3. 在空間中隨機選擇P個點為新ATM部署點；

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

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

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

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

4　實驗結(jié)果

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

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

圖3　深圳市ATM需求點分布

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

5　結(jié)　語

本文通過篩選與ATM選址相關(guān)的需求點，考慮多銀行ATM的競爭影響并基于市場中已有ATM，構(gòu)建一種更符合真實市場情況的ATM選址模型，并設(shè)計了一種基于Voronoi圖和K中心點聚類的模型求解算法。由于影響ATM選址的因素諸多且復(fù)雜，在模型設(shè)計過程中，描述了考慮加入哪些因素和如何確定各個因素的權(quán)重等棘手問題的解決方法。在模型中加入更多的因素通常可以使模型更接近真實情況，但同時也會增加模型的復(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)點選址中的應(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.