周继恩　冯　兴　冯　鑫

(中国银联股份有限公司　上海 201201)

0　引　言

随着社会经济的不断发展，自动取款机ATM已经成为人们经济生活中不可或缺的重要基础设施之一。对银行而言，合理的ATM部署不仅能够提升银行客户的用户体验，而且能够帮助银行在激烈的行业竞争中发掘潜在客户和提高市场份额。设施区位问题是关于设施在空间最优化布局的区位分析问题。基本的设施区位问题考虑在离散空间中放置P个设施以服务D个需求点，并根据实际问题提出不同的优化目标获得不同的模型，如P-Meidan[1]问题中的minisum模型考虑最小化需求点与其最近设施点的加权距离和，其中权重为该需求点的需求值。minimax模型[2]考虑最小化所有需求点与其最近设施点的距离的最大值。ATM选址可以被视为一种特定的设施区位问题，但由于ATM市场情况高度复杂，ATM的部署受到人口密度、商业因素、竞争因素和已部署机具等多方面影响。经典的设施区位问题由于其数学模型的抽象性，无法适用于ATM选址问题。本文提出一种更加适用于ATM选址的P-Median问题的一种变形，设计了基于Voronoi图和修改的K中心点聚类的求解算法，构建了更加符合市场真实情况的ATM选址模型，并以深圳市某银行为例，应用模型获得ATM的合理部署位置。

1　P-Median问题与ATM选址原则

P-Median问题是一个经典的设施区位问题，由Hakimi[1]在其影响深远的工作中提出。P-Median问题考虑在离散空间中部署P个设施，使得空间中需求点与其距离最近的设施的加权距离和最小，需求点的权重为其需求值。……