Aplicação de Metaheurísticas para o problema de roteamento de veículos dinâmico para transporte reativo a demanda

Detalhes bibliográficos
Ano de defesa: 2012
Autor(a) principal: Miranda, Dângelo Silva
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal de Viçosa
BR
Metodologias e técnicas da Computação; Sistemas de Computação
Mestrado em Ciência da Computação
UFV
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://locus.ufv.br/handle/123456789/2643
Resumo: Os problemas de roteamento de veículos são de grande importância na pesquisa operacional, uma vez que envolvem problemas relacionados a logística de distribuição de mercadoria e/ou transportes de pessoas e possuem aplicabilidade em diversas áreas da economia. Este trabalho aborda o problema de roteamento de veículos estático e dinâmico para transporte reativo a demanda. Por ser um transporte sob demanda, as necessidades dos passageiros devem ser consideradas também durante a determinação das rotas dos veículos a fim de garantir a qualidade do serviço prestado, flexibilidade das rotas e eficiência na utilização do veículo com um mínimo de adição de ônus para o prestador. Visto que o problema possui características combinatórias, foi proposta para o caso estático uma heurística GRASP Reativo onde o parâmetro de aleatoriedade utilizado durante a construção da solução tem sua probabilidade de escolha autocalibrada. Foram propostas e testadas combinações de estratégias e movimentos a fim de determinar a escolha mais adequada para solução de instâncias do problema. Além disso, foi proposto um algoritmo híbrido substituindo-se a Busca Local do GRASP Reativo pelo método Busca Tabu. Por fim, foram propostos e testados algoritmos de replanejamento para o caso dinâmico. Os resultados obtidos pelos algoritmos propostos são comparados entre si e com resultados gerados por algoritmos da literatura. A análise e discussão dos resultados mostram que os métodos propostos alcançaram resultados satisfatórios, visto que as metaheurísticas obtiveram em média resultados pelo menos 10,27% melhores que algoritmos da literatura no caso estático, e os métodos de replanejamento conseguem melhorar ainda mais estes resultados.