Busca tabu para o problema de roteamento dinamico de veiculos com janelas de tempo

Resumo: O problema de roteamento dinâmico de veículos com janelas de tempo (PRDVJT) decorre do problema de roteamento estático de veículos com janelas de tempo (PRVJT). No problema estático, o objetivo é atender todos os clientes dentro de intervalos de tempo previamente estipulados, respeitando as restrições de capacidade dos veículos e minimizando o número de veículos e a distância percorrida. Neste problema, todos os dados necessários para a definição das rotas são conhecidos a priori. No PRDVJT, algumas informações, por exemplo, a localização e a demanda de alguns clientes, são reveladas dinamicamente ao tomador de decisão, ao mesmo tempo em que os motoristas percorrem seus roteiros. Este trabalho estuda e desenvolve métodos para os problemas PRVJT e PRDVJT. Para o PRVJT são testadas heurísticas construtivas, incluindo a proposta de uma heurística focada na redução do número de rotas, e métodos de busca local e tabu baseados na vizinhança granular. Posteriormente, as heurísticas são adaptadas e aplicadas ao PRDVJT, avaliando-se os benefícios de desvio do destino planejado e de inclusão de estratégias de espera e de posicionamento de veículos. Os testes computacionais do PRDVJT são executados num ambiente de simulação baseado em características práticas levantadas numa pesquisa a campo com empresas de transportes da região de Campinas e São PauloAbstract: The dynamic vehicle routing problem with time windows (DVRPTW) originates from the static vehicle routing problem with time windows (VRPTW). The objective of the static problem is to serve a given set of clients within their time window constraints, subject to each vehicle capacity, minimizing the number of vehicles and the distance traveled. In this problem, all data needed to create routes is previously known. In the DVRPTW, some information, for instance, the positioning and demand of some clients, is dynamic revealed for the decision maker at the same time in which the drivers are executing their routes. This work studies and develops methods for the VRPTW and DVRPTW. Constructive heuristics, as well as a suggestion of an heuristic focused on route minimization, are discussed for the VRPTW. Also for the same problem, local and tabu search methods based on the granular neighborhood are tested. Afterward, these heuristics are adapted and applied for the DVRPTW, evaluating the benefits of diversion and waiting and positioning strategies. Computational experiments for the DVRPTW are performed with a simulation environment founded on practical attributes collected during interviews with transportation companies of the Campinas and São Paulo regio