Use este identificador para citar o ir al link de este elemento:
http://hdl.handle.net/1843/JCES-ARLN7K| Tipo: | Dissertação de Mestrado |
| Título: | Formulações e algoritmos exatos para o problema do caixeiro viajante com coleta e entrega sob múltiplas pilhas |
| Autor(es): | Armando Honório Pereira |
| primer Tutor: | Sebastián Alberto Urrutia |
| primer miembro del tribunal : | Geraldo Robson Mateus |
| Segundo miembro del tribunal: | Rafael Augusto de Melo |
| Tercer miembro del tribunal: | Dilson Lucas Pereira |
| Resumen: | 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. |
| Asunto: | Programação inteira Computação Problema do caixeiro viajante |
| Idioma: | Português |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Institución: | UFMG |
| Tipo de acceso: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/JCES-ARLN7K |
| Fecha del documento: | 31-mar-2017 |
| Aparece en las colecciones: | Dissertações de Mestrado |
archivos asociados a este elemento:
| archivo | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| armando_honorio_pereira.pdf | 1.78 MB | Adobe PDF | Visualizar/Abrir |
Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.