Почему pgRouting не возвращает лучший путь?

9

Пусть следующая часть графа:

введите описание изображения здесь Когда я использую функцию shorttest_path между точками A и B, я получаю синий путь. Почему это происходит?

postgis postgresql pgrouting Хосе Алехандро
источник
В объяснении я ошибся, это красный синий, а не красный, извините!
Хосе Алехандро

Ответы:

7

Так ведет себя кратчайший путь (алгоритм Дейкстры) в pgRouting. Если есть два ребра с одинаковым источником и целью, используется случайный (если быть точным: первый, который выходит из базы данных). Я не знаю, как это исправить, но есть некоторые обходные пути.

Если возможно, вы должны разделить один из этих краев на два. Я не проверял это, но это должно исправить это поведение.

Другое решение для случая, когда вы не можете изменить свой набор данных. Добавьте поле 'shorter_alternative' в свою таблицу. Пример запроса, измените его в соответствии с вашими потребностями. Я надеюсь, что это объясняет идею:

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)

Теперь ребро «0.098» будет содержать идентификатор ребра «0.011». Все остальные ребра будут иметь значение null в поле shorter_alternative. После того как вы сделали запрос shorttest_path, проверьте возвращенный набор данных - если в какой-либо строке задано поле shorter_alternative, измените его.

user1702401
источник
2

Проблема уже была описана в предыдущем ответе. Это проблема «основанных на вершинах» алгоритмов кратчайшего пути, которые заботятся только об источнике и цели.

В трекере ошибок есть тикет и возможное решение для изменения реализации алгоритма: https://github.com/pgRouting/pgrouting/issues/34 (было бы неплохо, если бы кто-то мог попробовать это и отправить запрос на извлечение; - )

Другая возможность заключается в разделении «параллельных дорожных связей», как упоминалось ранее. Или вы можете использовать алгоритм Shooting Star, который проходит от края до края, чтобы он «знал» об обеих дорожных связях.

Или вы можете попробовать заказать дорожную сеть по стоимости, а затем выбрать только различные комбинации источника и цели:

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
);

Это предполагает, что вы ищете наименее дорогой маршрут. В противном случае вам нужно ORDER BY ... DESC.

Вы должны попробовать, если это влияет на производительность.

dkastl
источник
Вчера я создал функцию trsp и, похоже, не имел этой проблемы. В любом случае, спасибо за объяснение !!!
Хосе Алехандро