Metaheurı́sticas para o Roteamento de Veı́culos com Frota Heterogênea e Coleta e Entrega Simultânea

Neste trabalho é abordado o problema de localização de concentradores incapacitado com alocação múltipla. Para sua solução, propõe-se o uso de duas matheurísticas: Relaxation Enforced Neighborhood Search (RENS) e Variable Neighborhood Descent Branching (VNDB). Para gerar a solução inicial é aplicado o método construtivo RENS que resolve a versão relaxada do problema, fixa as variáveis que assumiram valores inteiros e resolve o subproblema com as variáveis restantes. Depois é aplicado o método de refinamento VNDB que explora o espaço de soluções por meio de trocas exaustivas de estruturas de vizinhança. Os experimentos foram aplicados a um conjunto de instâncias baseado no tráfego de um serviço postal australiano. Os resultados são comparados com as soluções encontradas por um método exato de um aplicativo comercial de propósito geral. Os experimentos computacionais mostram que as mataheurísticas encontram soluções próximas dos resultados do aplicativo comercial de propósito geral em tempo hábil.