Algoritmos de otimização para o problema de roteamento de veículos

Resumo

O objetivo deste projeto é desenvolver algoritmos eficientes para o problema de roteamento de veículos numa malha viária. Quando um veículo recebe um conjunto de pontos de entrega, ele deve utilizar uma rota otimizada, minimizando a distância percorrida ou o tempo total. Trata-se do clássico problema do Caixeiro Viajante (TSP). Entretanto, havendo mais de um veículo, o problema passa a ter duas etapas: (I) particionar os pontos de entrega e (II) para cada conjunto resolver um caixeiro viajante. O objetivo é encontrar um mínimo global em relação às duas etapas. Esta generalização do TSP pode receber requisitos adicionais como capacidade do veículo ou janelas temporais de entrega. Temos assim o Problema de Roteamento de Veículos (VRP). Esta iniciação científica será dedicada ao projeto de algoritmos de otimização para o VRP. O aluno utilizará diversas técnicas de otimização com a finalidade de encontrar soluções de boa qualidade em tempo computacional adequado. Ao final desta iniciação científica, espera-se que aluno tenha formado sólidos conhecimentos nas áreas de programação matemática, otimização e problemas roteamento de veículos. (AU)