Utilize este identificador para referenciar este registo: http://hdl.handle.net/10451/4626
Título: Modelos envolvendo variáveis com dependências temporais para problemas de roteamento
Autor: Godinho, Maria Teresa, 1967-
Orientador: Gouveia, Luís, 1957-
Palavras-chave: Programação linear inteira
Variáveis (Estatística)
Optimização
Teses de doutoramento - 2011
Data de Defesa: 2011
Resumo: Nesta tese propomos modelos compactos em Programação Linear Inteira envolvendo variáveis com dependências temporais para o Problema da Determinação de Rotas Óptimas de Veículos com Restrições de Capacidade na variante de Procura Unitária. O trabalho apresentado compreende duas vertentes: 1. uma vertente de natureza teórica, em que comparamos os novos modelos entre si e com outros conhecidos da literatura, apresentamos desigualdades obtidas por projecção do conjunto das soluções admissíveis das respectivas relaxações em Programação Linear quer no espaço definido pelas variáveis naturais quer no espaço definido pelas variáveis estendidas; 2. uma vertente de natureza computacional, em que avaliamos a qualidade dos limites inferiores produzidos pelas respectivas relaxações em Programação Linear e onde analisamos o efeito da adição de algumas desigualdades válidas aos mesmos. Os resultados discutidos permitem concluir que o melhor dos modelos propostos não é dominado por nenhum dos restantes modelos compactos publicados para o problema.
In this thesis, we introduce some new Time-Dependent Integer Linear Programming formulations for the (Unit-Demand) Vehicle Routing Problem. The new models are then studied from both a theoretical and a computational point of view. In particular, we: 1. Explore several dominance relationships among the new models as well as between the new models and others from the literature and produce some ine- qualities which result from projecting the feasible Linear Programming set of the new models into the space of flow and design variables; 2. Perform a computational study to access the strength of the linear programming relaxation of the new models and to evaluate the efficacy of adding new valid inequalities to those models. Our results allow us to conclude that the stronger of the models models presented in this thesis is not dominated by any of the other compact models known from the literature.
Descrição: Tese de doutoramento, Estatística e Investigação Operacional (Optimização), Universidade de Lisboa, Faculdade de Ciências, 2011
URI: http://hdl.handle.net/10451/4626
Aparece nas colecções:FC - Teses de Doutoramento

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ulsd061482_td_Maria_Godinho.pdf948,35 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.