Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/2643
Tipo: Dissertação
Título: Aplicação de Metaheurísticas para o problema de roteamento de veículos dinâmico para transporte reativo a demanda
Título(s) alternativo(s): Metaheuristics application to the dynamic vehicle routing for demand responsive transportation problem
Autor(es): Miranda, Dângelo Silva
Primeiro Orientador: Santos, André Gustavo dos
Primeiro coorientador: Arroyo, José Elias Cláudio
Primeiro avaliador: Raggi, Luiz Aurélio
Abstract: 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.
Vehicle routing problems have great interest in operations research, as they are logistics problems related to the delivery of goods and people transportation, and because they have applications in several fields of economy. This work deals with static and dynamic vehicle routing problem for demand responsive transportation. Being a responsive transportation, passengers' needs must be considered also along the route planning, in order to assure the quality or service, route flexibility and vehicle usage effectiveness, with minimum impact in the costs for the company. Since the problem has combinatorial characteristics, a Reactive GRASP heuristic is proposed for the static case. The randomness parameter used in construction phase has its probability self-adjusted. To find the approach best suited for the set of instances, different combinations of strategies and neighborhoods are proposed and tested. Besides that, it is proposed an hybrid algorithm, substituting the local search of the Reactive GRASP by an Tabu Search method. Furthermore, dynamic replanning algorithms were proposed and tested for the dynamic scenario. The results of the proposed methods are compared one to each other and to results of algorithms from the literature. The experimental analisys shows that the proposed methods give satisfactory results, as the metaheuristics obtained in average solutions 10,27% better than those from the literature in the static scenario, and the dynamic replanning methods improve the results even further.
Palavras-chave: Roteamento de veículos
Estático
Dinâmico
Transporte reativo a demanda
Metaheurísticas
Vehicle routing
Static
Dynamic
Demand responsive transportation
Metaheuristics
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: BR
Editor: Universidade Federal de Viçosa
Sigla da Instituição: UFV
Departamento: Metodologias e técnicas da Computação; Sistemas de Computação
Citação: MIRANDA, Dângelo Silva. Metaheuristics application to the dynamic vehicle routing for demand responsive transportation problem. 2012. 92 f. Dissertação (Mestrado em Metodologias e técnicas da Computação; Sistemas de Computação) - Universidade Federal de Viçosa, Viçosa, 2012.
Tipo de Acesso: Acesso Aberto
URI: http://locus.ufv.br/handle/123456789/2643
Data do documento: 9-Ago-2012
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
texto completo.pdf893,71 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.