A carregar...
Publicação
Modelos envolvendo variáveis com dependências temporais para problemas de roteamento
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 948.35 KB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
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.
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
Palavras-chave
Programação linear inteira Variáveis (Estatística) Optimização Teses de doutoramento - 2011