Randomized heuristic scheduling of electrical distribution network maintenance in spatially clustered balanced zones

Abstract: Reliable electricity distribution systems are crucial; hence, the maintenance of such systems is highly important, and in Sweden strictly regulated. Poorly planned maintenance scheduling leads unnecessary driving which contributes to increased emissions and costs.  Maintenance planning is similar to the capacitated vehicle routing problem, CVRP, a combinatorial optimization problem. Each route has an origin location, in this case is the office of the maintenance worker. The origin is the starting and ending point of each route. In addition, conditions such as due date for inspection has an impact on how components in the network are prioritized. The maintenance planning problem is likely NP-hard.  Given the above, the aim for this study is to develop a heuristic algorithm that efficiently generates daily inspection schedules on a yearly basis. There are multiple tools and algorithms already developed to solve these kinds of problems, for example the Google’s OR-Tools library, which provide optimal or near optimal solutions to VRP problems. The time complexity of those tools makes them impractical to use when planning maintenance of electrical networks since they can contain many thousands of components i.e., nodes. The main aim of this study is to develop an algorithm that provides a solution good enough compared to the solutions computed by the tools mentioned above but with a lower time complexity.  In order to develop and test the algorithm an electrical distribution network data is required. Due to the sensitive nature of this data, a simulated network is generated in place of using real data. The simulated network is based on land use data from the city of Uppsala, Sweden, and is based on the spatial distribution of an existing electrical distribution network in Örebro, Sweden. The scheduling and routing algorithm developed works by dividing candidate nodes into subsets. The division is done by using Density-based spatial clustering of applications with noise (DBSCAN). The clustering is made by querying all objects that requires an inspection to be performed that year. As a post-processing step all noise points are appended to the closest neighboring cluster. Then a distance map is computed for the objects within each cluster. An inspection day route is computed by applying a greedy forward selection in each cluster, always selecting a random unvisited starting node until all nodes within the cluster has been visited. This is then repeated 100 times for each cluster, finally keeping the best iteration. The number of iterations is based on evaluating the gain per additional iteration which appear to be logarithmic. The greedy forward selection means that the algorithm has a linear time complexity after the clustering and distance map computation is done.  The algorithm is evaluated by comparing the total driving time for the computed route to the output routes of a modified Concorde TSP solution and the solution of Google’s VRP solver.  The results show that the algorithm performs better in areas with shorter average neighborhood distance and driving time of the output route decrease with higher number of iterations. Although the VRP based baselines methods return solutions with inspection routes that are roughly 25% shorter than the proposed method, for realistic problem sizes the proposed method uses less compute resources i.e., time and memory. Furthermore, while the proposed method has a linear time and space complexity whereas the baselines have exponential time complexity. Finally, the VRP based back-optimization solutions are not practical in real settings when inspection tasks are added / changed daily due to service tasks and unfinished routes or when the number of nodes is substantially larger than the roughly 1 000 nodes used in the evaluation.Due to the sensitive nature of electrical distribution data the performance of the algorithm could not be compared to actual maintenance schedules. But with all likelihood the computed schedules should be significantly more efficient than manually planned schedules.