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. / Att ha pålitliga elnät är essentiellt för ett välfungerande samhälle därav är underhållet av sådana system av stor vikt och i Sverige strikt reglerat. Dåligt planerade besiktningar leder till onödig körning inom nätet vilket bidrar till ökade utsläpp och kostnader. Underhållsplanering liknar problemet, CVRP, ett kombinatoriskt optimeringsproblem. Varje rutt har en ursprungsplats, i detta fall är besiktningsmannens kontor. Kontoret är start- och slutpunkten för varje rutt. Dessutom har villkor som sista besiktningsdatum en inverkan på hur komponenter i nätet prioriteras. Underhållsplaneringsproblemet är sannolikt NP-svårt. Mot bakgrund av ovanstående är syftet med denna studie att utveckla en algoritm som effektivt genererar dagliga besiktningsscheman på årsbasis. Det finns redan flera verktyg och algoritmer som har utvecklats för att lösa den här typen av problem, till exempel Googles OR-Tools, som beräknar optimala eller nästan optimala lösningar på VRP-problem. Tidskomplexiteten hos dessa verktyg gör dem opraktiska att använda vid planering av underhåll av elnät eftersom dessa kan innehålla många tusen komponenter, dvs noder. Huvudsyftet med denna studie är att utveckla en algoritm som ger en lösning som är tillräckligt bra jämfört med de lösningar som beräknas av de verktyg som finns idag men med en lägre tidskomplexitet.För att utveckla och testa algoritmen krävs elnätsdata. På grund av denna datas känsliga natur genereras ett simulerat nätverk istället för att använda riktiga data. Det simulerade nätet är baserat på markanvändningsdata från Uppsala, Sverige, och på den rumsliga distributionen av ett befintligt eldistributionsnät i Örebro, Sverige. Schemaläggnings- och ruttalgoritmen som utvecklats fungerar genom att dela upp kandidatnoder i delmängder. Uppdelningen görs genom att använda densitetsbaserad spatial klustring (DBSCAN). Klustringen görs genom att välja ut alla objekt som behöver besiktigas det året. Som ett efterbehandlingssteg läggs alla bruspunkter till det närmaste intilliggande klustret. Sedan beräknas en distansmatris för objekten inom varje kluster. En besiktningsrutt beräknas genom att inom varje kluster alltid starta på en slumpmässig vald ej besökt startnod. Därefter väljs den närmsta nod tills alla noder inom klustret har besökts. Detta upprepas sedan 100 gånger för varje kluster, och slutligen behålls den bästa iterationen. Antalet iterationer baseras på att utvärdera förbättringen per ytterligare iteration - som verkar vara logaritmisk. Det här innebär att algoritmen har en linjär tidskomplexitet efter att klustringen och beräkningen av distansmatrisen har genomförts. Algoritmen utvärderas genom att jämföra den totala körtiden för den beräknade rutten med rutterna för en modifierad Concorde TSP-lösning och lösningen från Googles VRP-solver. Resultaten visar att algoritmen presterar bättre i områden med kortare genomsnittligt avstånd mellan noderna och körtiden för besiktningsrutterna minskar med ett högre antal iterationer. Även om de existerande VRP-algoritmerna returnerar lösningar med besiktningsrutter som är cirka 25 % kortare än den föreslagna metoden, så är dessa inte realistiska att använda när antalet noder närmar sig de av ett riktigt elnät.Dessutom, medan den föreslagna metoden har en linjär tids-och rymdkomplexitet medan de existerande VRP-algoritmerna har en exponentiell tidskomplexitet. Slutligen är de VRP-baserade algoritmerna inte praktiska i verkligheten när besiktningar läggs till eller ändras eller när antalet noder är avsevärt större än de cirka 1 000 noder som används i utvärderingen. På grund av den känsliga karaktären hos elnätsdata kunde algoritmens prestanda inte jämföras med faktiska besiktningsscheman. Men med all sannolikhet borde de beräknade besiktningsschemana vara betydligt effektivare än manuellt planerade scheman.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-315862 |
| Date | January 2022 |
| Creators | Offenbacher, Carolina, Thornström, Ellen |
| Publisher | KTH, Geoinformatik |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-ABE-MBT ; 22590 |
Page generated in 0.003 seconds