基于仿射传播聚类的大规模选址布局问题求解

Solving large scale location problem using affinity propagation clustering

选址布局问题是一个广泛研究的运筹学问题。通过将选址布局问题看做聚类问题,结合仿射传播聚类算法并且将候选地址的信息映射为特征向量,提出了两种求解选址布局问题的方法:基于块划分的选址布局方法和基于道路网络的选址布局方法。使用模拟数据集和真实数据集来评估两种方法,实验结果表明两种方法都能够求解设施资源受限和不受限情况下的选址布局问题,而且可以很好地解决大规模的选址布局问题。

Location problem is a well-studied problem in operations research. By treating location problem as clustering problem, integrating affinity propagation clustering algorithm and mapping information of candidate into feature vector, this paper presented two methods to select suitably situation from candidate situation：location method based on region division and location method based on road network. It evaluated two methods using synthetic data sets as well as real-world data sets. The experimental results show that two methods can solve location problem with fixed number facilities and location problem with unfixed number facilities, and can solve large location problems and provide good solutions.