Problema do caminho mínimo

O problema de caminho mínimo é um dos problemas genéricos intensamente estudados e utilizados em diversas áreas como Engenharia de Transportes, Pesquisa Operacional, Ciência da Computação e Inteligência Artificial. Isso decorre do seu potencial de aplicação a inúmeros problemas práticos que ocorrem em transportes, logística, redes de computadores e de telecomunicações, entre outros. Podem ser aplicados para encontrar automaticamente direções entre locais físicos, como instruções de direção em sites de mapeamento da web como o MapQuest ou o Google Maps. Para esta aplicação, algoritmos especializados rápidos estão disponíveis. Outras possibilidades de aplicação incluem quaisquer problemas envolvendo redes ou grafos em que se tenha grandezas (distâncias, tempo, perdas, ganhos, despesas) que se acumulem linearmente ao longo do percurso da rede. Se alguém representa uma máquina abstrata não determinística como um gráfico em que os vértices descrevem estados e arestas descrevem possíveis transições, algoritmos de caminho mínimo podem ser usados ​​para encontrar uma sequência ótima de opções para atingir um determinado estado objetivo ou para estabelecer limites mais baixos no tempo necessário para atingir um determinado estado. Por exemplo, se os vértices representam os estados de um quebra-cabeça como o Cubo de Rubik e cada borda direcionada corresponde a um único movimento ou turno, os algoritmos de caminho mínimo podem ser usados ​​para encontrar uma solução que use o número mínimo possível de movimentos. Um problema relacionado é o Problema do Caixeiro-viajante, que consiste em determinar o caminho mais curto que passa exatamente uma vez por cada vértice e retorna ao vértice de partida. Este é um problema NP-Completo, para os quais não há uma solução eficiente.

Uma rede rodoviária pode ser considerada como um gráfico com pesos positivos. Os nós representam cruzamentos e cada aresta do gráfico é associado a um segmento de estrada entre dois cruzamentos. O peso de uma aresta pode corresponder ao comprimento do segmento de estrada associado, ao tempo necessário para atravessar o segmento ou ao custo de atravessar o segmento. Usando arestas direcionadas, também é possível modelar ruas de mão única. Esses gráficos são especiais no sentido de que algumas arestas são mais importantes que outras para viagens de longa distância (por exemplo, rodovias). Esta propriedade foi formalizada usando a noção de dimensão da estrada. Há um grande número de algoritmos que exploram essa propriedade e, portanto, são capazes de calcular o caminho mais curto muito mais rapidamente do que seria possível em gráficos gerais. Todos esses algoritmos funcionam em duas fases. Na primeira fase, o gráfico é pré-processado sem conhecer o nó de origem ou destino. A segunda fase é a fase de consulta. Nesta fase, o nó de origem e o destino são conhecidos. A ideia é que a rede rodoviária seja estática; portanto, a fase de pré-processamento pode ser realizada uma vez e usada para um grande número de consultas na mesma rede rodoviária.

Em situações da vida real, a rede de transporte geralmente é estocástica e depende do tempo. De fato, um viajante que atravessa um link diariamente pode experimentar diferentes tempos de viagem nesse link, devido não apenas às flutuações na demanda de viagens (matriz de origem-destino), mas também devido a incidentes como zonas de trabalho, más condições climáticas, acidentes e avarias de veículos. Como resultado, uma rede estocástica dependente do tempo (DST) é uma representação mais realista de uma rede rodoviária real em comparação com a rede determinística. Apesar dos progressos consideráveis ​​ao longo da década passada, continua sendo uma questão controversa como um caminho ideal deve ser definido e identificado nas redes rodoviárias estocásticas. Em outras palavras, não existe uma definição única de um caminho ideal sob incerteza. Uma resposta possível e comum a essa pergunta é encontrar um caminho com o tempo mínimo de viagem esperado. A principal vantagem do uso dessa abordagem é que algoritmos eficientes de caminho mínimo introduzidos para as redes determinísticas podem ser facilmente empregados para identificar o caminho com o tempo de viagem mínimo esperado em uma rede estocástica. No entanto, o caminho ideal resultante identificado por essa abordagem pode não ser confiável, porque essa abordagem falha em lidar com a variabilidade do tempo de viagem. Para resolver esse problema, alguns pesquisadores usam a distribuição do tempo de viagem em vez do valor esperado para encontrar a distribuição de probabilidade do tempo total de viagem usando diferentes métodos de otimização, como programação dinâmica e algoritmo de Dijkstra. Esses métodos usam otimização estocástica, especificamente estocástica programação dinâmica para encontrar o caminho mais curto em redes com comprimento de arco probabilístico. O conceito de confiabilidade do tempo de viagem é usado de forma intercambiável com a variabilidade do tempo de viagem na literatura de pesquisa em transporte, de modo que, em geral, pode-se dizer que quanto maior a variabilidade no tempo de viagem, menor a confiabilidade e vice-versa.