Focusing on the issues that the number, location, and coverage of multi-regional logistics centers of distribution centers are unknown, an improved k-means clustering algorithm is proposed. Based on the urban economic gravity model, this algorithm combines the urban transportation distance with the indicators of household consumption capacity, redefines the distance factor of the similarity measure between objects. The idea of density is introduced into the k-means algorithm, and the concept of intra-class difference mean is raised to determine the optimal number of clusters. After the partition is implemented, the centroid method is used to determine the final distribution center in these areas. Finally, in case study, we analyze the location process of constructing logistics distribution centers in 37 cities in the western region, and compares them with the traditional k-means clustering results. The comparing result shows that the improved algorithm not only saves the delivery time, but also greatly reduces the transportation cost and has sound economic value.