Estudo, implementação e análise de algoritmos de caminho mínimo em malhas viárias reais

• Processo: 99/01496-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de maio de 1999
• Data de Término da vigência: 30 de setembro de 1999
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Vitória Maria Miranda Pureza
• Beneficiário: Carlos Henrique de Oliveira Nunes
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Assunto(s): Logística Problemas de roteamento de veículos Algoritmos
• Palavra(s)-Chave do Pesquisador: Caminhos Minimos | Gis | Logistica | Roteamento De Veiculos

Resumo

Estudo, implementação e análise do desempenho de três algoritmos utilizados no cálculo de caminhos mínimos (shortest paths). O cálculo do caminho mínimo é uma etapa crítica em operações logísticas onde a definição de rotas em malhas viárias precisa ser realizada em um curto espaço de tempo. Por esta razão, existe um grande interesse na escolha do algoritmo mais adequado, em especial por parte das empresas que desenvolvem pacotes comerciais de roteamento. Apesar da literatura apontar vários estudos empíricos acerca do desempenho de algoritmos, só mais recentemente surgiu a preocupação em se definir aqueles que resultam em respostas mais rápidas em malhas viárias reais. Os objetos de estudo deste projeto consistem no algoritmo de Crescimento de Grafos, o algoritmo de Dijkstra implementado com buckets aproximados e o algoritmo de Dijkstra implementado com buckets duplos. O projeto contará com a participação e apoio da empresa GFMI software, localizada em Ribeirão Preto - SP, especializada no desenvolvimento de sistemas comerciais. (AU)