The robust shortest path problem with discrete data

Abstract

Problemas de optimização são frequentemente utilizados para modelar fenómenos reais, sendo, deste modo, um instrumento de apoio à decisão. Tais modelos dependem de parâmetros que podem ser afectados pela incerteza. Na prática, é bastante comum que estes parâmetros assumam um conjunto de cenários possíveis, cujos valores podem variar num dado intervalo ou ser discretos. Uma forma de lidar com a incerteza, denominada optimização robusta, tem como objectivo minimizar o pior caso que possa ocorrer para todos os cenários. Esta tese considera o problema do caminho robusto mais curto com o mínimo desvio máximo de custo numa rede com um número finito de cenários. O problema consiste na determinação de um caminho entre dois nós, com o mínimo custo de robustez, isto é, com o mínimo desvio máximo de custo com respeito ao caminho mais curto em cada cenário. Na literatura, têm sido desenvolvidos predominantemente métodos de resolução do problema anterior, ou de algumas das suas variantes, quando são considerados intervalos de custo. Contudo, para o caso discreto, o tema não tem sido explorado significativamente. Após serem demonstrados resultados fundamentais relativamente às soluções óptimas do problema do caminho robusto mais curto, são introduzidos três novos métodos exactos. Um deles é um método de rotulação, enquanto os outros dois têm por base a enumeração de caminhos limitados superiormente em termos de custo. Um destes algoritmos, denominado híbrido, utiliza uma técnica de desvios de caminhos para eliminar caminhos que o outro método de enumeração determina, por meio da aplicação de uma regra eliminatória utilizada no algoritmo de rotulação. Resultados computacionais em redes aleatórias mostram que as versões rotulação e híbrida são os algoritmos mais eficientes. A redução da rede é outro dos tópicos tratados, com vista a simplificar a busca de um caminho robusto mais curto. Neste contexto, são desenvolvidas técnicas de pré-processamento para identificar arcos contidos em qualquer solução óptima, e nós que não estão contidos em nenhuma solução óptima. Os métodos seguem dois tipos de abordagem, estática e dinâmica. A primeira fixa o limite inferior dos custos, enquanto a segunda actualiza aqueles valores, de acordo com o mínimo custo de robustez dos caminhos que vão sendo obtidos. Nestas condições, os conjuntos de arcos e de nós identificados pela última destas estratégias contêm os conjuntos identificados pelo método estático. Testes computacionais em redes geradas aleatoriamente mostram que as regras de pré-processamento são eficazes para os nós, se o número de cenários usados pelas condições testadas for limitado. Além disto, determinar um caminho robusto mais curto após pré-processamento dinâmico dos nós foi mais eficiente do que resolver o problema após o pré-processamento estático ou mesmo sem pré-processamento, em alguns casos. O último tema aborda a reoptimização do caminho robusto mais curto, após eliminação ou inclusão de cenários ou de arcos na rede inicial. Esta consiste na resolução do problema na rede modificada, assumindo que a solução óptima original, bem como os custos dos caminhos mais curtos e o valor óptimo iniciais são conhecidos. Inicialmente, são deduzidas condições que permitem verificar se a solução óptima se mantém. Quando estas não são satisfeitas, é desenvolvido um algoritmo para calcular a nova solução num conjunto de caminhos específico previamente determinado. O método de procura tem por base a construção de uma árvore de caminhos, que começa por incluir os sub-caminhos da solução óptima original que podem ser estendidos a caminhos potencialmente óptimos. Em cada passo, é adicionado um arco a cada caminho na árvore e as regras de extensão são aplicadas, de acordo com o mínimo custo de robustez conhecido na rede modificada. A aplicação dos algoritmos de reoptimização é ilustrada.

Optimization problems are often used to model real phenomena and thus aid decision making. Such models depend on parameters that may be affected by uncertainty. In practice, it is quite common that these parameters are known to assume a given set of possible scenarios, which can range within an interval or be a discrete set of values. A way to handle uncertainty, called robust optimization, aims at minimizing the worst case that can happen for all scenarios. This thesis considers the minmax regret robust shortest path problem in a network, with a finite set of scenarios. The goal of this problem is to determine a path between two nodes, with the minimum robustness cost, that is, with the minimum maximum deviation cost with respect to the shortest path in each scenario. In the literature, methods to solve the latter problem or some of its variants have been mainly developed when each cost ranges within a given interval. However, for the discrete case, the subject has not been significantly explored. After proving fundamental results concerning optimal solutions of the robust shortest path problem, three new exact methods to solve it are introduced. One is a labeling method, whereas the other two are based on an upper-bounded ranking of paths. One of these methods, denominated hybrid, uses a deviation technique that allows to skip some of the paths determined by the other ranking method, through the application of a pruning rule used in the labeling algorithm. Computational results in random networks reveal that the labeling and the hybrid versions are the most efficient algorithms. The reduction of the network in order to simplify the search for a robust shortest path is also addressed. In this context, preprocessing techniques for identifying arcs that belong to all optimal solutions, and nodes that do not belong to any optimal solution, are developed. The methods follow two types of approach, static and dynamic. The first fixes the cost lower-bounds, while, the second, updates them according with the least robustness cost of the computed paths. Under these conditions, the sets of arcs or nodes identified by the latter strategy contain the sets identified by the static method. Computational results in randomly generated networks show that the preprocessing rules are effective for nodes, if the number of scenarios used in the test conditions is limited. Besides, determining a robust shortest path after the dynamic preprocessing of nodes has shown to be more effective than solving the problem after the static preprocessing or even without preprocessing for some cases. The reoptimization of the robust shortest path, after deleting or inserting scenarios or arcs in the initial network, is the last approached subject. It consists in solving the problem in the modified network, assuming that the original optimal solution as well as the shortest path costs and the optimal value in the initial network are known. First, conditions to verify if the optimal solution remains the same are deduced. When these do not hold, an algorithm is developed in order to calculate the new solution in a specific set of paths previously determined. The method is based on the construction of a paths tree, which initially includes the sub-paths of the original optimal solution that can be extended and produce potentially optimal paths. At each step, one arc is added to each path in the tree and the extension rules are applied, according with the least robustness cost known in the transformed network. The application of the reoptimization algorithms is illustrated.