František Nekovář presents Multi-tour Set Traveling Salesman Problem in Planning Power Transmission Line Inspection

On 2021-10-19 11:00:00 at E112, Karlovo náměstí 13, Praha 2
During the seminar, we will describe our novel generalization of Traveling
Salesman Problem. We will compare several methods of finding a solution for
generazation, and explore its application in planning for aerial vehicles in
visual inspection of power transmission lines.

This paper 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
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
Therefore, the computational requirements are addressed by the combinatorial
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.

Short seminar length - 20 min talk, 10 min discussion.

Link to paper:
Responsible person: Petr Pošík