Roteamento de veículos sem e com janelas temporais - Semedo, Arlindo Tavares (2014)
Neste trabalho abordamos o Problema de Roteamento de Veículos (PRV) e o Problema de Roteamento de Veículos com Janelas Temporais (PRVJT). O PRV, bem como a sua extensão PRVJT, são problemas combinatórios pertencentes à classe de problemas NP-Difíceis. Para ambos os problemas, apresentamos dois grupos de formulações em Programação Linear Inteira Mista: um grupo de formulações em que cada rota é associada a um veículo específico e outro grupo de formulações em que são determinadas as rotas sem as associar aos veículos. Usamos as formulações apresentadas para obter resultados computacionais para vários exemplos. Os exemplos que usamos têm 4, 7, 13 , 20, 25, 40, 50, 75 e 100 clientes, 1 depósito e até 27 veículos. Os resultados computacionais permitem-nos comparar, para estes exemplos, os valores da relaxação linear e os valores da melhor solução admissível encontrada. Esses resultados computacionais foram obtidos com as formulações usando o software Xpress.