Algoritmos para o problema de roteamento de veículos com coleta e entrega simultâneas
AUTOR(ES)
Luciana Pereira de Assis
DATA DE PUBLICAÇÃO
2007
RESUMO
Neste trabalho é abordado o Problema de Roteamento de Veículos com Coleta e Entrega Simultâneas (VRPSPD) que é um problema básico de logística reversa, definido como: Dados uma rede de transporte com $n$ consumidores e um depósito, na qual cada consumidor possui uma demanda de coleta e/ou uma demanda de entrega, e um conjunto de veículos com capacidade limitada, o VRPSPD consiste em definir rotas otimizadas que satisfaçam todas as demandas dos clientes, respeitando a capacidade dos veículos. Devido à complexidade computacional do VRPSPD, o desenvolvimento e análise de heurísticas construtivas é de extrema importância. Este trabalho compara cinco heurísticas construtivas conhecidas da literatura e propõe três novas heurísticas. Os resultados mostram que as heurísticas propostas são melhores em 90% das instâncias testadas considerando a redução da distância trafegada pelos veículos. A heurística com os melhores resultados da literatura (Heurística Baseada em Inserção) é estendida em duas direções. Na primeira pela introdução de alternativas permitindo que as rotas sejam finalizadas mais cedo e, na segunda direção, pelo uso de ferramentas de apoio a decisão multicritério para escolher o vértice a ser inserido na rota a cada passo da heurística. Os resultados também apresentaram uma melhora significativa da distância trafegada em 92% das instâncias. As 4 melhores heurísticas analisadas neste trabalho foram utilizadas na fase de construção da heurística baseada no GRASP. Na fase de busca local foram aplicados movimentos de intercâmbio, realocação, eliminação de rotas, cruzamento e 2Opt. Os resultados obtidos foram comparados aos melhores resultados da literatura. Em 64% das instâncias analisadas, as soluções apresentadas pela heurística proposta reduziram a distância trafegada total significativamente. Os resultados também comprovaram que a utilização de uma boa heurística nesta fase melhora a qualidade dos resultados finais da heurística baseada no GRASP.
ASSUNTO(S)
computação teses. logística teses. transporte rodoviário controle automático teses. algoritmos de computador teses. otimização matemática teses. transporte rodoviário processamento de dados teses.
ACESSO AO ARTIGO
http://hdl.handle.net/1843/RVMR-79SPKKDocumentos Relacionados
- Heurísticas e algoritmo exato para o problema de roteamento de veículos com coleta e entrega simultâneas
- Algoritmos para a resolução do problema de estoque e roteamento de veiculos
- A tabu search for the vehicle routing problem with pickup and delivery
- Heuristicas para o problema de estoque e roteamento de veiculos
- Modelagem para o Problema de Roteamento de Veículos Fretados