Apesar de serem utilizados com sucesso em problemas de roteirização clássicos como o do caixeiro-viajante e o de roteirização de veículos com janelas de tempo, os algoritmos genéticos não apresentavam bons resultados nos problemas de roteirização de veículos sem janelas de tempo. Utilizando-se de uma tendência recente de hibridização de algoritmos genéticos, Prins (2004) elaborou um algoritmo para o problema de roteirização de veículos sem janelas de tempo, monoperíodo, e que obrigatoriamente atenda a todos os clientes cujos resultados, quando aplicado a instâncias de Christofides et al. (1979) e de Golden et al. (1998), são comparáveis aos melhores códigos elaborados com base na busca tabu. Diferentemente da maioria dos algoritmos genéticos apresentados para solução de problemas de roteirização de veículos, no método desenvolvido por Prins (2004) o cromossomo é composto apenas pelos pontos a serem atendidos, não contendo delimitadores de rotas. Estas são definidas a partir de um método de particionamento do cromossomo. Este trabalho implementa o algoritmo descrito por Prins (2004) e propõe a este melhorias em diversas de suas etapas, como inicialização, operação de crossover, operação de mutação, reinicialização e particionamento do cromossomo. As alterações implantadas são aplicadas às instâncias de Christofides et al. (1979) e comparadas com o algoritmo inicial em termos de qualidade de solução e tempo de processamento. Finalmente, é elaborado um algoritmo genético que contempla as alterações que obtiveram resultados positivos. / In the Vehicle Routing Problem (VRP) we seek for a set of minimum-cost vehicle routes for a fleet of identical vehicles, each starting and ending at a depot, such that each customer is visited exactly once and the total demand of any route does not exceed the vehicle capacity. Several families of heuristics have been proposed for the VRP. They can be broadly classified into two main classes: classical heuristics developed between 1960 and 1990, and, more recently, metaheuristics. Among them, tabu search plays an key role, being acknowledged by most authors as the most successful approach for the VRP. In the literature some successful implementations of metaheuristic Genetic Algorithm (GA) can be found for classic routing problems such as the traveling salesman and vehicle routing problems with time windows. However, until recently, the same did not apply for the VRP. In this thesis we develop a genetic algorithm without trip delimiters, and hybridized with a local search procedure, for the solving the VRP, which is based on the work of Prins (2004). At any time, a chromosome can be converted into an optimal VRP solution (subject to chromosome sequence) by means of a splitting procedure, in which the chromosome sequence, representing a giant tour, is partitioned into feasible routes in terms of vehicle capacities. Starting with the procedure originally proposed Prins (2004), we then introduce new improvements in terms of the different components of the GA, aiming to obtain improved solutions. These include how we determine the initial population, different partitioning approaches, alternative reproduction (crossover) processes, a granular tabu mechanism similar to the one proposed by Toth and Vigo (2003 and, finally, in changes in the reinitialization process, aiming to reestablish diversity. Computational experiments are presented, based on the 14 classical Christofides instances for the VRP. The results show that the proposed improved versions of the GA allow us to obtain better solutions when compared to the original approach by Prins (2004).
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-28032008-161354 |
| Date | 07 December 2007 |
| Creators | Araújo, Carlos Eduardo Di Giacomo |
| 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 | English |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0014 seconds