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

• Processo: 16/08481-6
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de julho de 2016
• Data de Término da vigência: 19 de março de 2017
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação
• Pesquisador responsável: Luis Augusto Angelotti Meira
• Beneficiário: Rodrigo Rosatti Galvão
• Instituição Sede: Faculdade de Tecnologia (FT). Universidade Estadual de Campinas (UNICAMP). Limeira , SP, Brasil
• Assunto(s): Problemas de roteamento de veículos Problema do caixeiro viajante (PCV) Logística Otimização matemática
• Palavra(s)-Chave do Pesquisador: grafos | Logísitica | otimização | Roteamento | Vrp | Otimização Comnbinatória

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)