Formulações e algoritmos exatos para o problema do caixeiro viajante com coleta e entrega sob múltiplas pilhas

Página do item simplificado
dc.creatorArmando Honório Pereira
dc.date.accessioned2019-08-12T15:56:01Z
dc.date.accessioned2025-09-09T00:25:12Z
dc.date.available2019-08-12T15:56:01Z
dc.date.issued2017-03-31
dc.identifier.urihttps://hdl.handle.net/1843/JCES-ARLN7K
dc.languagePortuguês
dc.publisherUniversidade Federal de Minas Gerais
dc.rightsAcesso Aberto
dc.subjectProgramação inteira
dc.subjectComputação
dc.subjectProblema do caixeiro viajante
dc.subject.otherColeta e entrega
dc.subject.otherPlanos de cortes
dc.subject.otherCaixeiro viajante
dc.subject.otherProblema de roteamento de veículos
dc.subject.otherRestrições de carregamento
dc.titleFormulações e algoritmos exatos para o problema do caixeiro viajante com coleta e entrega sob múltiplas pilhas
dc.typeDissertação de mestrado
local.contributor.advisor1Sebastián Alberto Urrutia
local.contributor.referee1Geraldo Robson Mateus
local.contributor.referee1Rafael Augusto de Melo
local.contributor.referee1Dilson Lucas Pereira
local.description.resumoNo 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.
local.publisher.initialsUFMG

Arquivos

Pacote original

Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
armando_honorio_pereira.pdf
Tamanho:
1.73 MB
Formato:
Adobe Portable Document Format
Baixar

Coleções

Pós-Graduação em Ciência da Computação - Dissertações

Logo UFMG