Heurísticas para o problema de roteamento de veículos com atendimento suficientemente próximo

O problema de roteamento de veículos com atendimento suficientemente próximo, também conhecido como problema do caixeiro rural direcionado generalizado com restrição de distância, é um problema de roteamento que tem como objetivo encontrar trajetos de menor custo, respeitando as restrições de tamanho da rota e, principalmente, de atendimento de consumidores. Uma aplicação da vida real interessante é a leitura de medidores de água, luz ou gás por rádio frequência através de dispositivos automáticos de leitura, onde veículos equipados com estes dispositivos precisam passar em um subconjunto de ruas para coletar as informações de todos consumidores à distância. Neste artigo, propomos uma meta-heurística híbrida com Iterated Greedy e Variable Neighborhood Descent (que utiliza quatro estruturas de vizinhanças) que, com base nas várias instâncias testadas, foi capaz de apresentar resultados parecidos com os de modelos exatos presentes na literatura, tendo como vantagem o tempo de execução utilizado.