A Meta Heuristic Genetic Algorithm for Multi-Depot Routing in Autonomous Bridge Inspection

Abstract

We attack the problem of routing autonomous climbing robots for steel truss bridge inspection using a metaheuristic genetic algorithm. These robots, deployed from four depots at the four corners of the bridge, must traverse every member of the bridge truss while minimizing distance traveled and balancing tours among robots. This problem maps to the well known NP-Hard Min-Max Multi-Depot k (robot) Chinese Postman Problem. We constructed 20 benchmark bridge instances of four different types of truss configurations using realistic dimensions as a testbed for comparison. Compared to the best known direct encoded genetic algorithm approach, our metaheuristic genetic algorithm produces routes that are on average 25% better quality, and does so 22<tex>$x$</tex> faster. On the four depot version of the problem, the MetaGA on average performs 42% better. These results on our benchmarks show evidence our metaheuristic genetic algorithm provides high-quality tours in realistic time for real-world robot bridge inspection scenarios and has the potential to generalize to vehicle routing and the broader class of arc-routing problems.