Simulated Annealing aplicado ? resolu??o do problema de roteamento de ve?culos com janela de tempo.

Este trabalho apresenta um algoritmo eficiente, baseado na metaheur?stica Simulated Annealing (SA), para resolver o Problema de Roteamento de Ve?culos com Janela de Tempo. Esse problema tem como objetivo determinar as rotas de custo m?nimo para uma frota de ve?culos de mesma capacidade, atendendo ? demanda de um conjunto de clientes, para os quais o atendimento somente ? poss?vel dentro de um intervalo de tempo determinado, chamado ja -nela de tempo. A metodologia proposta, denominada SA-RAI, incorpora ao algoritmo Simulated Annealing cl?ssico, mecanismos auto-adaptativos para determina??o da temperatura inicial e n?mero de itera??es em uma mesma temperatura. Nesta metodologia, quando a temperatura atinge um valor limiar, a mesma ? reaquecida um certo n?mero de vezes, possibilitando escapar de ?timos locais. Al?m disso, ela conta com uma fase de intensifica??o. Sempre que uma melhor solu??o ? encontrada, ela ? submetida a um procedimento de refinamento, visando ao seu melhoramento. A metodologia foi aplicada a 168 problemas-teste da literatura e 13 novos melhores resultados foram encontrados.This work presents an efficient algorithm based on Simulated Annealing metaheuristic (SA) for solving the Vehicle Routing Problem with Time Windows. The goal of this problem is to find a set of routes with minimum cost (in terms of traveled distance) for a fleet of identical vehicles based at the depot, obeying the capacity of the vehicles and the demand of a set of costumers and its predefined time windows. The proposed method, named SA-RAI, uses auto-adaptive mechanisms to determine the initial temperature and number of iterations in a same temperature. When the temperature is close to zero, there is a reheating in order to escape local optimums. In addition, SA-RAI uses a refinement phase when a new best solution is found. The proposed method was applied to 168 benchmarks and 13 new best solutions were found