Ciência da Computação
URI permanente para esta coleçãohttps://locus.ufv.br/handle/123456789/197
Navegar
Item Modelagem e heurísticas para problemas de roteamento de veículos com atendimento suficientemente próximo(Universidade Federal de Viçosa, 2018-09-28) Aparecido, Willian Gonçalves; Santos, André Gustavo dos; http://lattes.cnpq.br/0932554963961248Neste trabalho, foram abordados dois problemas de roteamento para atendimento de arcos suficientemente próximo. O primeiro é o Problema de Roteamento de Veículos com Atendimento Suficientemente Próximo (PRVASP), onde as restrições de atendimento dos consumidores e tamanho das rotas devem ser respeitadas e, em paralelo, objetiva a busca por trajetos de menor custo. Uma aplicação interessante deste problema é a leitura de medidores de água, luz ou gás por rádio frequência através de dispositivos automáticos de leitura, em que veículos equipados com estes dispositivos podem realizar a leitura à distância, e assim, devem passar próximos o suficiente para que os dispositivos coletem as informações de cada consumidor. Para resolver este problema, foi proposto um modelo matemático de programação linear inteira e, também, uma meta-heurística híbrida com Iterated Greedy e Variable Neighborhood Descent (que utiliza quatro estruturas de vizinhanças). O segundo problema analisado é o Problema de Roteamento de Veículos com Máximo Atendimento Suficientemente Próximo (PRVMASP), onde a restrição que força o atendimento de todos os consumidores do PRVASP passa a ser o objetivo, isto é, deve-se atender o maior número de consumidores. Esta é uma variação que condiz com casos práticos, pois nem sempre é possível realizar o atendimento de todos os consumidores, seja por falta de veículos, pela quantidade insuficiente de funci- onários responsáveis pela leitura, pela redução de jornada de trabalho, ou ainda, pelo aumento do número de consumidores que devem ser atendidos. Para a resolução do PRVMASP, baseado nos métodos utilizados no PRVASP, foi formulado um modelo de programação linear inteira e foi adicionada à meta-heurística híbrida proposta uma nova estrutura de vizinhança. Tanto para o PRVASP quanto para o PRVMASP, foram realizados vários testes computacionais com instâncias presentes na literatura, sendo possível comprovar que a meta-heurística desenvolvida IG + VND obteve resultados parecidos com os modelos, validando seu uso em problemas de atendimento de arcos suficientemente próximo e tendo como vantagem o baixo tempo de execução utilizado.