Análise de algoritmos heurísticos para problemas ricos de roteamento de veículos

• Processo: 07/06864-6
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2008
• Data de Término da vigência: 28 de fevereiro de 2010
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Peterson Katagiri Zilli
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Vinculado ao auxílio: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas, AP.PRNX.TEM
• Assunto(s): Otimização combinatória Problemas de roteamento de veículos Heurística Pesquisa Tabu
• Palavra(s)-Chave do Pesquisador: Busca Tabu | Grasp | heuristicas | Otimização Combinatória | roteamento de veículos | Otimização Combinatória

Resumo

O Problema de Roteamento de Veículos (VRP, em inglês) foi proposto por Dantzig e Ramser em 1959 e desde então centenas de artigos foram dedicados à solução de suas variantes. O problema consiste em determinar rotas otimais que serão usadas por veículos para servirem a um conjunto de clientes. Nesse trabalho vamos estudar o problema com foco nos modelos chamados de "ricos" na literatura os quais englobam variantes bastante complexas do VRP onde são representadas situações mais próximas dos problemas logísticos encontrados em sistemas de distribuição reais. A principal motivação para esta pesquisa é uma aplicação prática referente ao problema do roteamento dos ônibus fretados pela UNICAMP para o transporte de seus funcionários, que caracteriza-se como um modelo "rico". O objetivo final é a otimização de tal processo através da minimização da distância total percorrida e/ou do número de veículos empregados, com a conseqüente redução dos gastos incorridos pela Universidade. Portanto, além do seu aspecto científico, espera-se que este projeto produza resultados com chances reais de trazer benefícios à administração de uma instituição pública de ensino. Para que isto venha a ocorrer, prevê-se ainda a inserção das heurísticas desenvolvidas em um sistema de informações geográficas comercial que é usado pela Universidade. Deste modo, este trabalho dá continuidade ao projeto de Iniciação Científica deste aluno que foi apoiado pela FAPESP (processo 04/15019-0) e no qual desenvolveu-se um primeiro estudo nesta direção. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

ZILLI, Peterson Katagiri. Análise de algoritmos heurísticos para problemas ricos'' de roteamento de veículos. 2011. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.