Otimização de rotas com procuras nos arcos: uma heurística

Trata-se de um problema de otimização de rotas nos arcos definido num grafo misto, conhecido pela designação de MCARP (Mixed Capacitated Arc Routing Problem) e é comprovadamente NP-difícil. Com o objetivo de determinar soluções admissíveis, apresenta-se uma matheurística em que se alia a resolução de dois modelos compactos a regras heurísticas para a fixação de serviços.O desempenho da matheurística foi avaliado com um conjunto de instâncias habitualmente utilizado para testar heurísticas para o MCARP. Os resultados não foram os mais animadores, pois as instâncias de maior dimensão que simulam casos reais permanecem com um tempo computacional elevado.