Metodologia híbrida para resolução do problema dial-a-ride

Resumo

Este projeto consiste basicamente na continuação do projeto de mestrado em Computação Aplicada intitulado "Novas Heurísticas para o Problema de Escalonamento de Tripulações", financiado pela FAPESP (processo 03/04547-2), que está sendo desenvolvido no Instituto Nacional de Pesquisas Espaciais. Durante o desenvolvimento de tal projeto, foi apresentada uma nova metodologia, baseada na interação de um algoritmo evolutivo denominado Algoritmo de Treinamento Populacional (ATP) com o método de geração de colunas em Programação Linear. A idéia deste projeto é estudar e aprimorar tal metodologia. Para isso, será abordado um outro problema de otimização combinatória conhecido como Dial-a-Ride Problem - DARP (problema de roteamento com entregas e coletas). O DARP foi escolhido, pois trata-se de um problema atual, pouco explorado na literatura, e que pode ser modelado como um problema a ser resolvido por geração de colunas, onde o sub-problema gerador de colunas é um problema de fluxos em redes com capacidades (ou recursos). Além disso, como existem diversos outros problemas em que o sub-problema gerador de colunas pode ser classificados como problemas de fluxos em redes, a aplicação da ATP/PL ao DARP se torna uma ótima oportunidade para analisar o comportamento de tal metodologia de uma forma mais abrangente. (AU)