Multi-Agent Inspection Path Planning with Large-Scale Vehicle Routing Problem

A path planning problem involving multiple vehicles for a large and complex structure inspection is challenging owing to its high computational complexity. This occurs from the large and sparse nature of the inspection graph as it requires heavy computation for both preprocessing the graph and solving the problem. However, there have been fewer research efforts that focus on the computation inefficiency occurring from graph preprocessing, which is an important issue that needs to be addressed for practical application. This research proposes an algorithm that fuses a graph clustering algorithm with an ant colony system algorithm. It effectively reduces the computation required for preprocessing the graph and accelerates the vehicle routing problem (VRP) solving process by narrowing down a search space. A series of numerical experiments has shown that the proposed algorithm is capable of handling a large and sparsely connected graph VRP within a significantly reduced computation time. In addition, the algorithm yields a superior solution quality as compared to that of the conventional algorithm.