A Comparison of Algorithms for the Spatial Clustering of Technological Assets
摘要
We compared in a GIS environment three algorithms for the spatial clustering of electrical panels, to optimize maintenance team routes and schedule their activities across quarters. The considered algorithms are the constrained K-means, an application of the traveling salesman problem and a third one which, despite being specifically developed, turned out to be less effective. This latter approach involves the discretization of the bounding polygon containing the panels using a vector grid, the subsequent identification of the cells on which the panels lie, and finally the aggregation into groups through statistical evaluations of the row and column coordinates of the grid cells. The processed samples consist of sets of panels in seven Italian cities, characterized by different sample sizes, distributions and densities. The algorithms’ effectiveness was established as the capability to get good clustering results in all the considered situations. The evaluation was conducted using both qualitative and quantitative methods. Qualitatively, clusters were inspected visually. Quantitatively, we calculated intra-cluster and inter-cluster distances, compactness and separation indices such as the Dunn’s and the Silhouette indices. The constrained K-means turned out to be the algorithm more suitable to our needs and so it has been implemented in a WebGIS application used as a decision support system by the electrical utility company Hera Luce srl1 in Italy. A further enhancement involves using distances over a real road network instead of Euclidean ones, but this assumes the availability of an updated network, which is not always granted.