文章基本信息

标题：Um Algoritmo Híbrido para a Resoluςão do Problema de Roteamento de Veículos com Janelas de Tempo
本地全文：下载
作者：Sabir Ribas ; Anand Subramanian ; Igor Machado Coelho 等
期刊名称：Mecánica Computacional
印刷版ISSN：2591-3522
出版年度：2010
卷号：XXIX
期号：96
出版社：CIMEC-INTEC-CONICET-UNL
摘要：Este trabalho trata do Problema de Roteamento de Veículos com Janelas de Tempo. Tal problema consiste em uma variante do roteamento de veículos clássico, em que a demanda de cada cliente deve ser atendida durante um intervalo temporal pré-estabelecido. Dado o caráter altamente combinatório do problema, que pertence à classe NP-Difícil, sua resolução por abordagens puramente exatas é, em muitos casos, computacionalmente impraticável. Este fato motiva o desenvolvimento de algoritmos heurísticos para sua resolução, que são mais rápidos, porém não garantem a obtenção da melhor solução para o problema. Neste trabalho é proposto um algoritmo heurístico híbrido, que combina os métodos Iterated Local Search, Variable Neighborhood Descent e um procedimento exato de particionamento de conjunto. Esse procedimento de programação matemática é acionado periodicamente com vistas a combinar da melhor forma as rotas geradas ao longo do algoritmo. Os resultados computacionais obtidos mostram que o algoritmo é promissor, visto que ele obteve soluções melhores ou iguais aos da literatura em quarenta e dois dos cinquenta e seis problemas-teste analisados. Além disso, o algoritmo melhorou os resultados da literatura em 21,4% dos problemas tratados.