UMA HEURÍSTICA ILS PARA A RESOLUÇÃO DO PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM FROTA HETEROGÊNEA - Vieira, Naiara Helena; Cota, Fernanda dos Reis; Gomes Júnior, Aloisio de Castro; Gomes, Helton Cristiano; Fortes, Allexandre (Revista Latino-Americana de Inovação e Engenharia de Produção, 2022)
O problema de roteamento de veículos com frota heterogênea (PRVFH) é um problema de otimização combinatória que, devido à variação na capacidade dos veículos, ao número de restrições e ao número de clientes a serem visitados, apresenta elevada complexidade computacional. O objetivo principal do PRVFH é determinar o melhor conjunto de rotas possível que os veículos possam percorrer entre o depósito e os clientes, observando a capacidade de cada veículo. O presente trabalho apresenta uma abordagem utilizando a meta-heurística Iterated Iocal Search (ILS) para resolução do PRVFH. A solução inicial é obtida pelo procedimento de economias (Clarke-Wright). Como métodos de busca local, foram adotados os movimentos two-opt e two-point-move para melhorar as soluções. Os resultados, quando comparados a solução inicial obtida usando a heurística de Clarke-Wright, chegaram a melhorias de até 23%, com tempos computacionais abaixo de sete segundos. O método foi aplicado a 27 instâncias encontradas na literatura e adaptadas para o problema com variação de 32 a 80 clientes.