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. / 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.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-01082007-175300 |
| Date | 10 May 2007 |
| Creators | Wu, Luciele |
| Contributors | Cunha, Cláudio Barbieri da |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0022 seconds