Otimização do problema de roteamento de veículos capacitado usando algoritmos genéticos com heurísticas e representações cromossômicas alternativas

Detalhes bibliográficos
Ano de defesa: 2015
Autor(a) principal: Lima, Stanley Jefferson De Araujo lattes
Orientador(a): Araújo, Sidnei Alves de lattes
Banca de defesa: Schimit , Pedro Henrique Triguis lattes, Pereira, Fabio Henrique lattes, Junqueira, Leonardo lattes, Silva Filho, Oscar Salviano lattes
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Nove de Julho
Programa de Pós-Graduação: Programa de Pós-Graduação de Mestrado e Doutorado em Engenharia de Produção
Departamento: Engenharia
País: Brasil
Palavras-chave em Português:
Palavras-chave em Inglês:
Área do conhecimento CNPq:
Link de acesso: http://bibliotecatede.uninove.br/handle/tede/1124
Resumo: In recent years, the Vehicle Routing Problem (VRP) has attracted an increasing attention from researchers due to the great difficulty of its solution and its presence in various practical situations. As consequence, there has been great effort to develop more robust, agile and flexible algorithms that can be modeled according to the scenario that describes the problem. The Capacitated Vehicle Routing Problem (CVRP) is a version of VRP and consists in determining a set of routes to be followed by a fleet of homogeneous vehicles, which must serve a set of customers. The objective is to minimize the total cost of the routes subject to the following restrictions: i) routes must start and end in the same distribution center; ii) each customer must be visited once and its demand must be met in full by only one vehicle and iii) the sum of customers' demands included in a route cannot exceed the vehicle capacity. The CVRP belongs to the class of NP-hard problems, that is, problems whose the solution usually requires non-polynomial complexity time algorithms and because of this are usually resolved with the use of heuristic and metaheuristics algorithms. In this work, it was investigated the optimization of CVRP using Genetic Algorithm (GA) with alternative chromosome representations and heuristics. To this end, three strategies, each one employing a different model of chromosome representation for encoding solution in AG were proposed. In addition, the heuristics of Gillett and Miller to generate solutions that are included in the initial population of GA and Hill-climbing for refinement of GA solutions, after a number of generations without improvement, were adopted. In the performed experiments, the results obtained by the proposed strategies were compared with each other and also with the best results found in the literature for a set of known instances. These experiments showed that the proposed strategies provided good results with respect to quality of solutions well as the computational cost. In addition, it was possible to evaluate the viability of each employed chromosome representation and the contribution of the heuristics in the convergence process of GA.