A Metaheuristic Genetic Algorithm for Routing Bridge Inspection Robots
Loading...
Authors
Dedeurwaerder, Bryan
Issue Date
2023
Type
Thesis
Language
Keywords
Algorithm , Bridge , Genetic , Inspection , Metaheuristic , Route
Alternative Title
Abstract
The safety and integrity of transportation infrastructure relies heavily on bridge inspections which can be expensive and hazardous for inspectors. Recent advancements in robotics and autonomy has resulted in steel truss climbing robots for bridge inspection that can reduce these costs and improve safety. However, optimally routing multiple robots to traverse and inspect each member of a truss bridge remains a challenging NP-hard problem which we represent by the Min-Max k-Chinese Postman Problem. In this thesis we attack this problem by constructing routes with a Metaheuristic Genetic Algorithm. The results demonstrate that this approach provides high quality solutions in reasonable time. Specifically, on standard benchmarks from literature we reveal that the quality of solutions are statistically indistinguishable compared to a prior state-of-the-art Tabu Search method. Furthermore, our Metaheuristic Genetic Algorithm surpasses the prior best Direct Encoded Genetic Algorithm by producing routes that are on average 15.24% better quality in a fraction (0.05) of the time on 20 new benchmark problems representing four well-known bridge truss structures. We also investigate the impact of multiple robot starting points on the total inspection time in the multi-depot variant of the Min-Max k-Chinese Postman Problem. The Metaheuristic Genetic Algorithm multi-depot solutions outperforms the previous best Genetic Algorithm multi-depot solutions that are on average 41.72% better quality and 22 times faster with three different postman configurations on the 20 new benchmark problems. This thesis therefore indicates that Metaheuristic Genetic Algorithms are a viable approach to the Min-Max k-Chinese Postman Problem and thus for routing autonomous inspection robots for safer, most cost effective bridge inspection. More generally, Metaheuristic Genetic Algorithms may show promise for attacking other similar Arc Routing Problems.