Meta-heurísticas para o Problema do Carteiro rural Orientado com Lucros e Incompatibilidades

O presente trabalho aborda o Problema do Carteiro Rural Orientado com Lucros e Incompatibilidades (em ingles, Directed Profitable Rural Postman Problema with Incompatibility Constraints, ou seja, DPRPP-IC). Este generaliza o problema do carteiro rural, adicionando arcos lucrativos e incompatibilidades entre pares de nodos. O DPRPP-IC procura uma rota com início e fim no depósito, que maximize a diferença entre as receitas e os custos totais, que são compostos pelos custos de deslocação e penalizações pagas para eliminar incompatibilidades fracas, satisfazendo as restrições de incompatibilidade. O problema apresentado tem aplicação prática para empresas que partilham serviços de distribuição, transporte ou logística. Uma vez que o DPRPP-IC é um caso particular de um problema NP-difícil, é proposto um algoritmo Tabu Search para encontrar soluções de boa qualidade de forma eficiente. Tabu Search é uma meta-heurística de pesquisa local que procura escapar a ótimos locais usando uma lista tabu, que não permite movimentos para soluções recentes. Algumas instâncias de referência da literatura são utilizadas para avaliar a qualidade da meta-heurística proposta. Após uma análise aos parâmetros da meta-heurística e a fixação dos mesmos, os resultados analisados mostram que a meta-heurística proposta obtém soluções de fraca qualidade, mas em tempos computacionais bastante inferiores aos registados na literatura para obtenção da solução ótima por métodos exatos.