Por que o pgRouting não retorna o melhor caminho?

9

Deixe a próxima parte de um gráfico:

insira a descrição da imagem aqui Quando uso a função shortest_path entre os pontos A e B, obtive o caminho azul. Por que isso acontece?

postgis postgresql pgrouting José Alejandro
fonte
Na explicação, eu cometi um erro, é vermelho azul não vermelho, desculpe!
José Alejandro

Respostas:

7

É assim que o shortest_path (algoritmo de Dijkstra) se comporta no pgRouting. Se houver duas arestas com a mesma origem e destino, será usada uma aleatória (para ser mais preciso: a primeira que sai do banco de dados). Não conheço nenhuma solução para isso, mas existem algumas soluções alternativas.

Se possível, você deve dividir uma dessas arestas em duas. Não testei, mas deve corrigir esse comportamento.

Outra solução para o caso, quando você não pode modificar seu conjunto de dados. Adicione o campo 'short_alternative' à sua tabela. Consulta de amostra, modifique-a de acordo com suas necessidades. Espero que explique a ideia:

UPDATE roads t1
SET shorter_alternative = t2.id
FROM roads t2
WHERE 
((t2.source = t1.source AND t2.target = t1.target) OR
(t2.source = t1.target AND t2.target = t1.source)) AND
(t2.length < t1.length)

Agora, a borda '0,098' conterá o ID da borda '0,011'. Todas as outras arestas terão nulo no campo short_alternative. Depois de fazer a consulta shortest_path, verifique o conjunto de dados retornado - se alguma linha tiver um conjunto de campos alternativos mais curtos, altere-o.

user1702401
fonte
2

O problema já foi descrito na resposta anterior. É um problema dos algoritmos de caminho mais curto "baseados em vértices", que se preocupam apenas com a origem e o destino.

Existe um ticket no rastreador de problemas e uma possível solução para alterar a implementação do algoritmo: https://github.com/pgRouting/pgrouting/issues/34 (Seria bom se alguém pudesse tentar fazer isso e enviar uma solicitação pull; - )

Outra possibilidade é dividir "ligações rodoviárias paralelas", como mencionado anteriormente. Ou você pode usar o algoritmo Shooting Star, que é direcionado de ponta a ponta para que "conheça" os dois links da estrada.

Ou você pode tentar solicitar a rede rodoviária por custo e selecionar apenas combinações distintas de origem e destino:

SELECT * FROM shortest_path(
  'SELECT DISTINCT ON (source, target)
      gid as id,
      source::integer,
      target::integer,
      cost::double precision
    FROM ways ORDER BY source, target, cost',
  true,false
);

Isso pressupõe que você procure a rota mais barata. Caso contrário, você precisa ORDER BY ... DESC.

Você precisa experimentar se isso afeta o desempenho.

dkastl
fonte
Ontem eu crio a função trsp e parece que não tenho esse problema. Enfim, obrigado pela explicação !!!.
José Alejandro