Algoritmos para o problema de roteamento de veículos capacitado com restrições de carregamento bidimensional
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Andre Gustavo dos Santos
Luciana Salete Buriol
Sebastián Alberto Urrutia
Luciana Salete Buriol
Sebastián Alberto Urrutia
Resumo
Esta dissertação aborda o Problema de Roteamento de Veículos Capacitado com Restrições de Carregamento Bidimensional. Dado um depósito central e um conjunto de clientes, onde cada um demanda uma quantidade específica de itens, o problema consiste em definir rotas com distâncias percorridas mínimas para uma frota homogênea de veículos que realiza o atendimento aos clientes. Os itens possuem formas retangulares, devem ser transportados de modo que não haja sobreposição e impedimento entre eles e, em alguns casos, restrições de carregamento sequencial, relacionados à ordem de visitação dos clientes, são exigidas. Para a resolução do problema, foram propostas duas abordagens híbridas de heurísticas e Geração de Colunas. Além disso, um algoritmo Branch-and-Cut da literatura foi usado para resolver uma reformulação do modelo original do problema. Os métodos desenvolvidos foram avaliados por meio das instâncias usadas na literatura e os resultados foram comparados aos previamente publicados. Os métodos híbridos obtiveram resultados satisfatórios, algumas vezes iguais aos ótimos conhecidos, e o Branch-and-Cut conseguiu atestar a otimalidade para várias instâncias.
Abstract
This work addresses the Capacitated Vehicle Routing Problem with two-dimensional loading constraints. Given a central depot and a set of clients, where each demands a specific amount of items, the problem aims to define minimum cost routes for a fleet of homogeneous vehicles that performs customer service. The items have rectangular shapes, they must be transported in a way that there is no overlap between them, and in some cases, sequential loading restrictions, related to the order of visiting the customers, are required. To solve the problem, two hybrid approaches combining heuristics and Column Generation are proposed. Furthermore, the literatures Branch-and-Cut was used to solve a reformulation of the original model of the problem. The methods developed were evaluated by means of the instances used in the literature and the results were compared with those previously published. The hybrid methods achieve satisfactory results, sometimes equal to the optima known, and the Branch-and-Cut could attest to optimality for several instances.
Assunto
Otimização combinatória, Computação, Programação heuristica
Palavras-chave
Roteamento de veículos, Otimização combinatória, Carregamento bidimensional, Geração de colunas, Mateheurísticas