Algoritmos exatos para o problema do caminho mais curto robusto e para o problema de localização de concentradores em árvore

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%.