電力送電線点検計画におけるマルチツアー集合巡回セールスマン問題
Multi-Tour Set Traveling Salesman Problem in Planning Power Transmission Line Inspection
限られた走行予算の点検車両で電力線を完全にカバーするため、複数回の走行からなる最適経路を整数線形計画法とメタヒューリスティックで解く手法を提案し、実世界の変電所で実証した。
著者: František Nekovář, Jan Faigl, Martin Saska
分類: cs.RO, cs.AI
原文アブストラクト
This letter concerns optimal power transmission line inspection formulated as a proposed generalization of the traveling salesman problem for a multi-route one-depot scenario. The problem is formulated for an inspection vehicle with a limited travel budget. Therefore, the solution can be composed of multiple runs to provide full coverage of the given power lines. Besides, the solution indicates how many vehicles can perform the inspection in a single run. The optimal solution of the problem is solved by the proposed Integer Linear Programming (ILP) formulation, which is, however, very computationally demanding. Therefore, the computational requirements are addressed by the combinatorial metaheuristic. The employed greedy randomized adaptive search procedure is significantly less demanding while providing competitive solutions and scales better with the problem size than the ILP-based approach. The proposed formulation and algorithms are demonstrated in a real-world scenario to inspect power line segments at the electrical substation.
