Caminhos mais curtos em grafos de conjuntos convexos

Abstract

No nosso dia-a-dia somos constantemente confrontados com a falta de tempo, causada quer pela falta de organização quer pela carga excessiva de compromissos. De forma a contrariar tal tendência, deparamo-nos, por exemplo, a procurar trajetos com menor duração. Ou seja, todos os dias e na maior parte deles sem nos apercebemos, estamos a resolver intuitivamente problemas de caminho mais curto(PCMC). Daí se tratar de um problema tão fundamental e um dos mais estudados em otimização combinatória. O problema do caminho mais curto consiste em, dado um grafo, encontrar uma sequência de arestas de forma a conectar um vértice de origem a um vértice de destino com o menor custo possível. Uma generalização deste problema clássico surge quando se define a posição de cada vértice do grafo como sendo uma variável de decisão contínua que se encontra restrita a um determinado conjunto convexo. Deixa-se assim de ter posições fixas para os vértices do grafo. Posto isto, o comprimento de uma aresta determina-se segundo uma função convexa das posições dos vértices que esta liga. Esta vertente do problema apresenta uma vasta aplicabilidade, nomeadamente, no planeamento do movimento de veículos autónomos e na navegação ao nível da robótica. No entanto, possui uma enorme complexidade, revelando-se NP-difícil. A demonstração desta ilação constituirá um dos alvos deste estudo. Além disso, estudar-se-á este problema com o intuito de apresentar uma forte formulação convexa inteira mista baseada em funções perspetiva, que posteriormente será relaxada, tornando assim possível encontrar caminhos globalmente ótimos de forma eficiente em grafos e espaços de grandes dimensões. Para terminar, tirar-se-ão conclusões atendendo aos resultados da implementação computacional da formulação desenvolvida.

In our daily lives, we are constantly confronted with a lack of time, caused either by a lack of organization or an excessive workload of commitments. To counteract this trend, we find ourselves, for example, seeking shorter routes. In other words, every day, and in most cases without realizing it, we are intuitively solving shortest path problems (SPPs). That's why it's such a fundamental problem and one of the most studied in combinatorial optimization.The shortest path problem consists of, given a graph, finding a sequence of edges in order to connect a source vertex to a destination vertex with the lowest possible cost. A generalization of this classical problem arises when each vertex's position in the graph is defined as a continuous decision variable that is constrained to a specific convex set. This means that the vertices of the graph no longer have fixed positions. In this context, the length of an edge is determined by a convex function of the positions of the vertices it connects. This aspect of the problem has broad applications, especially in autonomous vehicle motion planning and robotics navigation. However, it exhibits significant complexity, proving to be NP-hard. Demonstrating this conclusion will be one of the objectives of this study. Furthermore, we will investigate this problem with the aim of presenting a strong mixed-integer convex formulation based on perspective functions, which will later be relaxed, making it possible to efficiently find globally optimal paths in graphs and high-dimensional spaces. In conclusion, we will draw conclusions based on the results of the computational implementation of the developed formulation.