Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/ESBF-A9UMM3| Tipo: | Dissertação de Mestrado |
| Título: | Algoritmos exatos para o problema do caminho mais curto robusto e para o problema de localização de concentradores em árvore |
| Autor(es): | Joao Carlos Abreu Junior |
| Primeiro Orientador: | Thiago Ferreira de Noronha |
| Primeiro Coorientador: | Andrea Cynthia Santos |
| Primeiro membro da banca : | Andrea Cynthia Santos |
| Segundo membro da banca: | Rafael Castro de Andrade |
| Terceiro membro da banca: | Sebastián Alberto Urrutia |
| Resumo: | Este trabalho e dedicado ao estudo de dois problemas de otimizacao NP-Difíceis. O primeiro problema e o problema do caminho mais curto robusto (RSP, do ingles Robust Shortest Path) que e uma generalizacao do problema de caminho mais curto (SP, do ingles Shortest Path). O RSP considera que os custos dos arcos sao definidos por um intervalo de valores continuo. Entre os diferentes criterios de otimizacao robusta, esse trabalho se dedicada ao criterio minmax com arrependimentorelativo. Neste trabalho sao dadas tres contribuicoes para o RSPcom arrependimento relativo: (i) a primeira formulacao por programacao linear inteira mista, (ii) desigualdades validas para essa formulacao e (iii) extensao desse problema em grafos com ciclos de custo positivo. Os resultados computacionais mostraram que os algoritmos baseados nas contribuicoes propostas sao capazes de resolver instancias de ate 1500 nos. O segundo problema que esse trabalho trata e o problema de localizacao de concentradores em arvore (THLP, do ingles Tree Hub Location Problem). Seja G = (N,A) um grafo completo direcionado, onde N e o conjunto de nos e A e o conjunto de arcos. Alem disto, Wij R+ e a demanda de fluxo do no i N para o no j N, cij e o custo de trafegar cada unidade de fluxo em um arco (i, j) A e p um numero inteiro positivo. O THLP consiste em selecionar um subconjuntoP N com p nos, denominados concentradores (do ingles Hubs), e conecta-los na forma de uma arvore. Em seguida, cada um dos nos em N \ P, denominados nos clientes, e alocado a um unico no em P de modo que exista um unico caminho entre cada par de nos i, j N e cujo custo total de rotear as demandas Wij seja minimizado. O custo de trafegar uma unidade de fluxo entre dois nos concentradores k,m P sofre um fator de desconto e e dado por ckm × . O estado da arte de algoritmos para este problema e capaz de resolver instancias deate 100 nos usando um algoritmo baseado em decomposicao de Benders, em um elevado tempo computacional. Isto se deve especialmente ao fato de que O(|N|2) subproblemas devem ser resolvidos a cada iteracao do algoritmo, utilizando um algoritmo de programacao linear. Neste trabalho, propomos um algoritmo ad-hocque resolve cada subproblema em O(|N|2). Desta forma, acelara-se o tempo de execucao do algoritmo de decomposicao de Benders para o THLP. Resultados preliminares indicam que o tempo de resolucao dos subproblemas pode ser acelerado em ate 29,52%. |
| Abstract: | This work is dedicated to the study of two NP-Hard optimization problems. The first problem is the robust shortest path problem (RSP) which is a generalization of the shortest path problem (SP). The RSP considers that the costs of the arcs are defined by a range of continuous values. Among the different robust optimization criterion, this work is dedicated to criterion with minmax relative regret. This work gave three contributions to RSP with relative regret. The first, is the integerlinear programming formulation to this problem. The seccond is the proposal of valid inequalities. The final is that it extends this problem for graphs with positive cost cycles. Computational results show that algorithms based on proposed contributions are able to solve instances up to 1500 nodes. The second problem this work investigates is the Tree Hub Location problem (THLP). Let G = (N,A) a complete directed graph, where N is the set of nodes and A is the set of arcs. Besides, Wij R+ is the flow demand of node i N to node j N. cij is the cost travel to each flow unit in an arc (i, j) A, and p is a positive integer. The THLP is to select a subset P N with p nodes, called hubs, and connect them in the form of a tree. Then, each node in N \ P, called a customer, is allocated to a single node in P so there is a unique path between eachpair of nodes i, j N whos total cost route demands that Wij is minimized. The cost of one unit flow traveling between two hub nodes k,m P suffers a discount factor and is given by ckm × . The state of the art algorithms for this problem is able to resolve instances up to 100 nodes using an algorithm based on Benders decomposition, in a high computational time. This is primarily due to the fact that O(|N|2) subproblems must be solved at each iteration of algorithm, usinga linear programming algorithm. In this work, we propose an algorithm ad-hoc solving each subproblem in O(|N|3). This way, speeds up the execution time of the Benders decomposition algorithm to THLP. Preliminary results indicate that the time resolution of subproblems can be accelerated by up to 29.52%. |
| Assunto: | Otimização matemática Pesquisa operacional Computação |
| Idioma: | Português |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Instituição: | UFMG |
| Tipo de Acesso: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/ESBF-A9UMM3 |
| Data do documento: | 14-Set-2015 |
| Aparece nas coleções: | Dissertações de Mestrado |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| jo_ocarlosabreujunior.pdf | 809.18 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.