Formulações e algoritmos exatos para o problema do caixeiro viajante com coleta e entrega sob múltiplas pilhas
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
Geraldo Robson Mateus
Rafael Augusto de Melo
Dilson Lucas Pereira
Rafael Augusto de Melo
Dilson Lucas Pereira
Resumo
No Problema do Caixeiro Viajante com Coleta e Entrega sob Múltiplas Pilhas um único veículo deve atender um conjunto de requisições de coleta e entrega. Cada requisição é definida por duas localizações, a localização de coleta onde um item deve ser carregado no veículo, e a localização de entrega onde o item previamente carregado deve ser entregue. Enquanto transportados, os items são armazenados em pilhas de capacidade limitada. Cada pilha deve seguir a política Last-In-First-Out. O que significa que somente o último item carregado em cada pilha está disponível para entrega. O objetivo do problema é encontrar uma rota para o veícula que atenda todas as requisições e que minimize a distância percorrida.Nesta dissertação, propomos três novas formulações de programação inteira para o problema junto com desigualdades válidas. A primeira formulação é uma reformulação de um modelo na literatura, baseado em uma observação, um conjunto de varíaveis do modelo é eliminado, o que resulta também na eliminação de um conjunto de restrições, com isso o objetivo é obter a solução de relaxação linear mais rápida. A segunda formulação é um misto de dois modelos na literatura. E a terceira formulação, no melhor do nosso conhecimento, é uma formulação compacta para o problema.Propomos algoritmos de planos de corte para essas novas formulações. Os algoritmos são testados em instâncias de benchmark e os resultados computacionais são comparados com a literatura. Instâncias para as quais uma solução ótima era conhecida previamente na literatura são resolvidas mais eficientemente nesse trabalho. Também, novos certificados de otimalidade são fornecidos para várias instâncias.
Abstract
Assunto
Programação inteira, Computação, Problema do caixeiro viajante
Palavras-chave
Coleta e entrega, Planos de cortes, Caixeiro viajante, Problema de roteamento de veículos, Restrições de carregamento