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

Armando Honório Pereira

Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/JCES-ARLN7K

Full metadata record

DC Field	Value	Language
dc.contributor.advisor1	Sebastián Alberto Urrutia	pt_BR
dc.contributor.referee1	Geraldo Robson Mateus	pt_BR
dc.contributor.referee2	Rafael Augusto de Melo	pt_BR
dc.contributor.referee3	Dilson Lucas Pereira	pt_BR
dc.creator	Armando Honório Pereira	pt_BR
dc.date.accessioned	2019-08-12T15:56:01Z	-
dc.date.available	2019-08-12T15:56:01Z	-
dc.date.issued	2017-03-31	pt_BR
dc.identifier.uri	http://hdl.handle.net/1843/JCES-ARLN7K	-
dc.description.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.	pt_BR
dc.language	Português	pt_BR
dc.publisher	Universidade Federal de Minas Gerais	pt_BR
dc.publisher.initials	UFMG	pt_BR
dc.rights	Acesso Aberto	pt_BR
dc.subject	Coleta e entrega	pt_BR
dc.subject	Planos de cortes	pt_BR
dc.subject	Caixeiro viajante	pt_BR
dc.subject	Problema de roteamento de veículos	pt_BR
dc.subject	Restrições de carregamento	pt_BR
dc.subject.other	Programação inteira	pt_BR
dc.subject.other	Computação	pt_BR
dc.subject.other	Problema do caixeiro viajante	pt_BR
dc.title	Formulações e algoritmos exatos para o problema do caixeiro viajante com coleta e entrega sob múltiplas pilhas	pt_BR
dc.type	Dissertação de Mestrado	pt_BR
Appears in Collections:	Dissertações de Mestrado

Files in This Item:

File	Description	Size	Format
armando_honorio_pereira.pdf		1.78 MB	Adobe PDF	View/Open

Show simple item record