改进的K-means算法在校车站点布局中的应用

Application of Improved K-means Algorithm in School Bus Stop Location

校车站点布局问题是一种典型的设施选址问题。大多数设施选址问题均属于区域选址,将设施选址限定在一定空间范围内,其方法并不适用于需要将位置固定在道路上的校车站点布局问题。因此,为保证生成的站点分布在路网上,且学生到站点的步行距离较短,提出了一种改进的K-means聚类算法,以一定范围内密度最大的点为初始类中心,在逐次迭代中将类中心投影到路网上,进而聚类得到校车站点。与传统的利用最大最小距离法的改进方式进行对比发现,在相同的站点间最小间距下,基于密度法改进初始类中心的K-means算法使得学生到车站总步行距离较短,且迭代次数明显减少。该方法还可适用于超市班车站点选址、物流配送点选址等问题。

School bus stop location is a kind of facility location problem which can be applied in many fields.Most of researches about facility location problem usually locate facilities in several hundred square meter region which is not suit for school bus stop location problem.Therefore,in this paper,we solved this problem with improved K-means clustering algorithm which selected initial cluster center by density method and projected cluster centers to road network with successive iteration,to make school bus stops on the road and students have a shorter walking distance to the stations.Furthermore,we compared the results with the algorithm improved by maxi-min distance method.The results show that the algorithm improved by density method can make the total walking distance to the station shorter for students.