Um método para a roteirização de veículos em regiões com restrições de circulação

As restrições de tráfego de caminhões em centros urbanos estão sendo cada vez mais adotadas para tentar reduzir os níveis de congestionamentos. Com isso, empresas distribuidoras necessitam criar rotas otimizadas para atender a demanda dos seus clientes, mas respeitando as restrições de circulação de veículos. Este trabalho tem como objetivo propor um método para roteirização de veículos em regiões com restrições de circulação. Por se tratar de um problema NP-difícil, métodos exatos demandam tempos computacionais não aceitáveis em problemas envolvendo muitos clientes, i.e., problemas reais. Assim sendo, o método proposto utiliza, separadamente as meta-heurísticas Busca em Vizinhança Variável (VNS) e Procedimento de Busca Guloso, Aleatório e Adaptativo (GRASP) para encontrar rotas sub-ótimas, eventualmente ótimas para os veículos. Foram desenvolvidos e comparados quatro algoritmos, usando a meta-heurísticas VNS e GRASP; sendo ambas aplicadas uma vez com dependência de tempo e outra vez com clusterização. Como validação, este trabalho utilizou os dados de uma distribuidora real da cidade de São Paulo, a partir destes foram criadas 27 instâncias para a realização dos experimentos nas cidades de Fortaleza, Recife e São Paulo. Essas cidades foram escolhidas por possuírem restrições de circulação. Os resultados obtidos mostram que o método é capaz de lidar com diferentes cenários de roteirização, alcançando um bom resultado para as meta-heurísticas VNS e GRASP.