• 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
 
 
Disertación de Maestría
DOI
10.11606/D.3.2007.tde-01082007-175300
Documento
Autor
Nombre completo
Luciele Wu
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2007
Director
Tribunal
Cunha, Cláudio Barbieri da (Presidente)
Brinati, Marco Antônio
Lorena, Luiz Antonio Nogueira
Título en portugués
O problema de roteirização periódica de veículos.
Palabras clave en portugués
Heurística
Logística (administração de materiais)
Roteirização periódica
Transportes
Resumen en 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 en inglés
The period vehicle routing problem.
Palabras clave en inglés
Heuristic
Logistics (supply chain)
Period routing
Transportation
Resumen en 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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
DissertacaoEdRevLWu.pdf (757.57 Kbytes)
Fecha de Publicación
2007-08-29
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2022. Todos los derechos reservados.