Algoritmos para o problema de roteamento de veículos com cross-docking
Carregando...
Arquivos
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
Thiago Ferreira de Noronha
Gilberto de Miranda Junior
Haroldo Gambini Santos
Gilberto de Miranda Junior
Haroldo Gambini Santos
Resumo
Esta dissertação aborda o Problema de Roteamento de Veículos com Cross-Docking. Dados um conjunto de requisições por produtos, um único centro de consolidação (CD), e múltiplos fornecedores e consumidores, o problema consiste em definir rotas de custo mínimo para uma frota homogênea de veículos que realiza o transporte de produtos dos fornecedores aos consumidores via CD. Inicialmente, os veículos partem do CD em direção aos fornecedores, coletam os produtos e retornam ao ponto inicial para realizar o processo de consolidação. Em seguida, a mesma frota de veículos transporta os produtos aos consumidores. As rotas definidas devem respeitar as restrições de capacidade dos veículos e janela de tempo de cada fornecedor e consumidor. São propostas três heurísticas construtivas, uma heurística baseada na metaheurística Iterated Local Search e uma mateheurística que integra esta última e um modelo de Programação Inteira Mista baseado em Particionamento de Conjuntos. As heurísticas propostas foram avaliadas em instâncias da literatura e comparadas com as melhores heurísticas existentes para este problema. Os resultados obtidos mostram a eficiência das soluções implementadas.
Abstract
This work addresses the Vehicle Routing Problem with Cross-Docking. Given a set of goods requests, a single Cross-Dock (CD), and several suppliers and customers, the problem consists in defining a minimum cost set of routes for a fleet of homogeneous vehicles that leaves the CD towards the suppliers, pickups the goods and returns to the initial point to perform the consolidation process. Thus, the same fleet of vehicles delivers the goods to the customers. The routes designed must respect the capacity constraints of the vehicles as well as the time windows constraints. We proposed three constructive heuristics, a heuristic based on the Iterated Local Search metaheuristic, and a matheuristic that integrates the latter and a Mixed Integer Programming model based on Set Partitioning. The heuristics were evaluated on instances from the literature and compared to the best existing heuristics for this problem. The results showed the efficiency of the implemented solutions.
Assunto
Otimização matemática, Algoritmos de computador, Computação
Palavras-chave
Roteamento de veículos, Otimização combinatória, Cross-Docking, Matheurística, Heurística