Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/28273
Title: | The robust shortest path problem with discrete data | Authors: | Resende, Marisa Cristina Marquês Neto de Matos | Orientador: | Pascoal, Marta Braz | Keywords: | optimização em redes; cenários discretos; caminho robusto mais curto; pré-processamento; reoptimização; network optimization; discrete scenarios; robust shortest path | Issue Date: | 10-Jul-2015 | Citation: | RESENDE, Marisa Cristina Marquês Neto de Matos - The robust shortest path problem with discrete data. Coimbra : [s.n.], 2015. Tese de doutoramento. Disponível na WWW: http://hdl.handle.net/10316/28273 | 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. |
Description: | Tese de doutoramento do Programa Inter-Universitário de Doutoramento em Matemática, apresentada ao Departamento de Matemática da Faculdade de Ciências e Tecnologia da Universidade de Coimbra | URI: | https://hdl.handle.net/10316/28273 | Rights: | embargoedAccess |
Appears in Collections: | FCTUC Matemática - Teses de Doutoramento |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
The robust shortest path problem with discrete data.pdf | 1.06 MB | Adobe PDF | View/Open |
Page view(s) 5
1,371
checked on Oct 15, 2024
Download(s) 50
549
checked on Oct 15, 2024
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.