O problema de caminhos mínimos (SP shortest path problem) é frequentemente colo- cado em prática em uma grande variedade de aplicações em diversas áreas. Nessas aplicações geralmente se deseja realizar algum tipo de deslocamento ou transporte entre dois ou mais pontos específicos em uma rede. Tal ação deve ser executada de forma ótima em relação a algum critério, por exemplo o menor custo possível, ou o menor gasto de tempo ou o máximo de confiabilidade/segurança. Na prática, muitas vezes não desejamos apenas o menor custo ou o menor tempo, mas desejamos otimizar uma combinação de diferentes critérios, por exemplo, um caminho que seja rápido e barato. Como não é possível otimizar sobre todos os critérios de uma só vez, nós escolhemos um dos critérios para representar a função custo, que será minimizada, e para os demais critérios representamos como recursos e definimos os limites que julgamos aceitáveis para o consumo de cada um desses recursos. Esta variação é cha- mada de problema de caminhos mínimos com restrições por recursos, ou como preferimos chamar, problema de caminhos mínimos com recursos limitados (RCSP resource constrained shortest path problem), o qual será o objeto de estudo neste trabalho. A adição de restrições por recursos no SP, infelizmente torna o problema NP-difícil, mesmo em grafos acíclicos, com restrições sobre um único recurso, e com todos os consu- mos de recursos positivos. Temos reduções dos famosos problemas N P-difíceis Mochila e Partição para o nosso problema. Em contextos diversos são encontrados problemas de cunho teórico e prático que po- dem ser formulados como problemas de caminhos mínimos com recursos limitados, o que nos motivou a estudá-lo a fim de desenvolver um trabalho que resumisse informações sufi- cientes para auxiliar pesquisadores ou desenvolvedores que tenham interesse no problema. Nós apresentamos aqui, uma detalhada revisão bibliográfica do RCSP, tendo como foco o desenvolvimento de algoritmos exatos para o caso onde possuímos um único recurso e a im- plementação e comparação dos principais algoritmos conhecidos, observando-os em situações práticas. / The problem of choosing a route to a trip, where we want minimize the distance of the path is a major problem in computing. In this basic form, this is the shortest path problem. But sometimes, besides the length we need to consider more parameters for selecting a good path. A common parameters to consider is the consumption of resources in a limited budget. A shortest path with these additional constraints is called resource constrained shortest path - RCSP. This paper has two main objectives: to present a literature review of the problem RCSP, focusing on exact algorithms for the case where we have a single resource, and implement and compare some algorithms, observing them in practical situations. The Shortest Path (SP) problem is among the fundamental problems of computer sci- ence. Its been deeply studied and subject of many publications. Also, many efficient solutions (polynomial time algorithms) are known for this problem. The SP is widely applied in many fields of science, not only computer science. These situations usually need to transport a load between two or more specific spots of a network. This action must be taken optimally regarding to some criterion, for instance the least cost, or the least time or maximum relia- bility. While new solutions for SP were presented, new demands were issued too, with new variations for the problem. One of these variations comes from the fact that, in a real scenario, a combination of many criteria must be optimized, for instance a path with least cost and least time. This problem is known as Multiobjective Shortest Path. Since its not possible to optimize all criteria at once, one of them is chosen to represent the cost function to be minimized and the others to represent resources with defined boundary. This variation, known as Resource Constrained Shortest Path (RCSP), was the object of the present study. By adding resource constraints, the SPbecomes N P-hard, even in acyclic graphs with only one resource constrained and all resource consumption being positive. There are reduc- tions from the famous NP-hard problems Knapsack and Partition to our problem. In many fields, are found theoretical and practical problems that may be expressed as a Resource Constrained Shortest Path Problem, which motivated us to study this problem in order to summarize enough information to researchers and developers involved with this problem. This paper presents a detailed bibliographic revision to RCSP, focusing on the development of exact algorithms for the case when there is only only one resource and on the implementation and comparison of the main known algorithms in practical situations.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-14012013-165742 |
| Date | 14 November 2012 |
| Creators | Joel Silva Uchoa |
| Contributors | Carlos Eduardo Ferreira, Cláudio Nogueira de Meneses, Gerardo Valdisio Rodrigues Viana |
| Publisher | Universidade de São Paulo, Ciência da Computação, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds