Problemas do caminho mais curto com restrições adicionais

Abstract

Neste trabalho estudam-se problemas do caminho mais curto com restrições adicionais. Este tipo de problemas tem variadas aplicações práticas onde é destacado o planeamento de rotas de veículos e o encaminhamento de mensagens em redes de comunicações. O problema de caminho mais curto com restrições adicionais tem tido também grande aplicação como sub-problema de outros problemas. É o caso do problema de caminho mais curto com janelas temporais que surge como sub-problema do problema de determinação de rotas de veículos com janelas temporais. É feita uma descrição das várias variantes do problema de caminho mais curto com restrições adicionais, é apresentada uma revisão da literatura sobre os métodos usados na resolução deste tipo de problemas e são descritas algumas aplicações deste tipo de problemas.

In this work, shortest path problems with additional constraints are studied. This type of problems has several practical applications, such as vehicle routing planning and the routing of messages in communications networks. The shortest path problem with additional constrains has also application as a sub-problem of other problems. This is the case of the shortest path problem with time windows occurring as sub-problem of the vehicle routing problem with time windows. We present a description of several variants of the shortest path problem with additional constraints, a short literature review on resolution methods for these problems and a description of some applications of this type of problems.