Heurística Relax-and-Fix Aplicada ao Problema de Roteamento em Arcos Capacitado e Priódico

Abstract

O presente trabalho trata do problema de roteamento em arco capacitado e periódico (PCARP). Considera-se o caso especial onde os veículos não têm a necessidade de voltar ao depósito no final de um dia e, ainda têm a possibilidade de folgar em qualquer dia do horizonte de tempo. O PCARP é um problema pouco explorado na literatura e é um problema NP-hard, sendo comumente aplicado em coleta de lixo urbano, inspeção de linhas de força despejo de sal em vias com neves, entrega de correspondência entre outros. Nesse trabalho, desenvolvemos métodos de solução do tipo relax-and-fix, propomos 4 estratégias diferentes e avaliamos o seu desempenho para determinar soluções para o PCARP. Os testes computacionais realizados mostraram que a heurística proposta pode ser um método rápido para determinar soluções iniciais para o problema.