Heurísticas para otimização de rotas de inspeção aérea de linhas de alta e média tensão

A inspeção de linhas de alta e média tensão é um procedimento de alta importância na manutenção e bom funcionamento da rede elétrica. O planeamento eficiente desta inspeção permite não só a poupança de recursos, como também a diminuição dos custos desta operação. Tal planeamento pode ser conseguido estudando o problema como um Problema de Roteamento nos Arcos com Capacidades cuja solução ótima pode ser obtida através de modelos de Programação Linear Inteira Mista (PLIM). Neste trabalho, foram desenvolvidos dois modelos de PLIM. Contudo, a aplicação desses modelos a instâncias de média/grande dimensão revelou-se como um processo moroso. De forma a contornar esta adversidade, foram implementadas duas heurísticas construtivas para obter soluções admissíveis rapidamente. Seguidamente, foram também desenvolvidas quatro heurísticas melhorativas que permitem o refinamento das soluções obtidas, de forma a diminuir o seu valor. Estas heurísticas recorrem a várias abordagens de perturbação e reordenação dos arcos dentro de rotas e entre rotas, bem como a troca de bases aéreas, de forma a explorar novas regiões do espaço de soluções. Os resultados obtidos pelas heurísticas melhorativas revelaram melhoramentos substanciais nas soluções geradas pela melhor heurística construtiva, cujo valor se encontra já bastante próximo do ótimo.