Aplicação de Metaheurísticas para o problema de roteamento de veículos dinâmico para transporte reativo a demanda
Ano de defesa: | 2012 |
---|---|
Autor(a) principal: | |
Orientador(a): | |
Banca de defesa: | |
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. |