• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.3.2007.tde-01082007-175300
Documento
Autor
Nome completo
Luciele Wu
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2007
Orientador
Banca examinadora
Cunha, Cláudio Barbieri da (Presidente)
Brinati, Marco Antônio
Lorena, Luiz Antonio Nogueira
Título em português
O problema de roteirização periódica de veículos.
Palavras-chave em português
Heurística
Logística (administração de materiais)
Roteirização periódica
Transportes
Resumo em português
O problema de roteirização periódica de veículos pode ser considerado como uma generalização do problema clássico de roteirização devido a duas características próprias: um período de planejamento maior que um dia, em que os veículos fazem diversas viagens, e freqüências de visitas associadas a pontos a serem servidos. Esse tipo de problema pode ter muitas aplicações práticas. Atualmente, algumas indústrias automobilísticas brasileiras já utilizam um sistema de coleta que se baseia na idéia de roteirização periódica, com a finalidade de reduzir o estoque de peças. Assim como os problemas originais de roteirização de veículos, o problema aqui tratado é também difícil de ser resolvido, sendo impossível o uso de algoritmos exatos para a obtenção de uma solução ótima para o tamanho de problemas encontrados na prática. Isso motivou o estudo, que direcionou seus esforços na exploração de novas estratégias de solução para esse problema através de novas abordagens, de modo que houvesse um aumento na qualidade de soluções e uma diminuição do tempo de processamento computacional. Dois procedimentos diferentes foram propostos para a alocação dos clientes aos dias de visitas: uma heurística de inserção seqüencial que visa equilibrar os esforços dos diferentes dias do período de planejamento, e uma heurística baseada em algoritmos genéticos. As rotas diárias são construídas através da utilização do algoritmo de economias de Clarke e Wright, que permite a obtenção de boas soluções em tempos de processamento curtos. Experimentos computacionais são realizados para a avaliação da eficiência de cada uma das heurísticas propostas através da utilização de benchmarks retirados da literatura e problemas-teste gerados aleatoriamente, e os resultados são também comparados aos anteriormente mostrados na literatura.
Título em inglês
The period vehicle routing problem.
Palavras-chave em inglês
Heuristic
Logistics (supply chain)
Period routing
Transportation
Resumo em inglês
The period vehicle routing problem can be viewed as a generalization of the classic vehicle routing problem due to two singular features: a planning period longer than one day in which vehicles make several trips and frequencies of visit associated to points to be serviced. This type of problem may arise in different practical applications. Nowadays, some Brazilian automaker industries are already utilizing a collect system based on the idea of the period routing in order to reduce parts inventory. Similarly to the original vehicle routing problem, the period vehicle routing problem is also hard to solve, making it impossible to use exact in order to obtain an optimal solution for problem sizes found in practice. This motivated this research study, which directed its efforts to the exploration of new strategies of solution through new reasoning, leading to an increase in the quality of the solution and a decrease in the computational processing time. The proposed heuristics are composed of three consecutive stages: (i) assigning customers to days of visit while respecting their given frequencies, (ii) building routes that serve all customers assigned to each day of the planning horizon, and (iii) improving the obtained solution. Despite the distinction between the stages, we managed to take into consideration the integration among the three decisions. Two different procedures were proposed to the assignment of customers to days of visit: a sequential insertion heuristic that aims to balance the workload among different days in the time horizon, and a heuristic based on genetic algorithms. The daily routes are then constructed by using the Clarke and Wright's savings algorithm, which allows good solutions to be obtained in short processing times. Computational experiments are made in order to evaluate the efficiency of each proposed heuristic using both benchmark problem sets from the literature and randomly generated problems as well, and the results are compared to the previously reported in the literature.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
DissertacaoEdRevLWu.pdf (757.57 Kbytes)
Data de Publicação
2007-08-29
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2018. Todos os direitos reservados.