Расчет расстояний между несколькими источниками и целями с помощью pgRouting

Я использую Postgres / PostGIS / pgRouting для подготовки набора данных для анализа, который я выполняю. Одно поле в наборе данных, которое мне нужно подготовить, - это кратчайшее расстояние между набором данных из 100 000 домашних хозяйств (точечные данные) и набором данных из нескольких десятков центров активности (также точечные данные). При подготовке к этому я создал узел и набор сетевых данных. Я также обновил свои наборы данных family и activity_centre столбцами, содержащими значения id ближайших узлов.

До сих пор я мог использовать функцию driving_distance () для расчета расстояния по дороге от центрального делового района (CBD) до каждого домохозяйства, но я хочу сделать это для всех центров за один проход, и мне не нужно создавать отдельные наборы данных о расстоянии. для каждого центра.

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

Есть ли решение для этого?

Большое спасибо,

Ro


distance shortest-path
person Roman Trubka    schedule 16.08.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Не знаю, правильно ли я понял вашу проблему. Если это похоже

  • у вас 100к семей
  • меньшее количество (может быть 1000) других достопримечательностей (центр деятельности, железнодорожный вокзал и т. д.)
  • цель состоит в том, чтобы показать кратчайший путь от / до одного из домохозяйств к / от интересующей точки без излишних вычислений во время выполнения.
  • Я дальше предполагаю, что данные о дорогах, которые у вас есть, ориентированы, т.е. могут быть дороги с односторонним движением.
  • эти точки не меняются слишком часто,

тогда вы можете попробовать такой подход:

  1. Подготовьте ориентированный граф со всеми 100 + 1k узлами и дорогами в качестве ребер. Дороги будут направлены от узла к узлу с весами, пропорциональными их расстоянию.
  2. Подготовьте обратный график того же - т.е. просто переключите узлы из и в, сохраняя одинаковые веса.
  3. Для каждой точки интереса P выполните Dijkstra, который вернет полную карту-предшественницу (дерево кратчайших путей в виде массива) из 100 + 1k точек, что дает кратчайшее расстояние от P до всех других точек. Это целочисленный массив из 100 + 1k значений.
  4. Повторите это на обратном графике. это даст вам predcessor_map, который дает кратчайшее расстояние до каждой интересующей точки P от всех других точек.
  5. Теперь у вас есть 2 * 1k массивов, каждый из которых имеет 100 + 1k значений. С каждым массивом вы также знаете положение в нем точки P.

Расчет времени выполнения:

  • Чтобы вычислить кратчайший путь от P до любой другой точки, используйте первый массив. Перейдите к местоположению целевой точки в массиве, посмотрите, каково ее соответствующее значение, и перейдите к этому элементу в массиве, повторяйте, пока не достигнете позиции P.

пример: если P находится в 7-й позиции, а ваша конечная точка - в 12-й позиции, перейдите к элементу массива 12, прочтите его значение array_val [12] = 10, теперь с 10, скажем, array_val [10] = 7, тогда ваш путь 7-10-12.

  • Аналогично, если вы проделаете эту операцию со вторым массивом, то кратчайшим путем будет путь в обратном порядке, то есть 12-10-7.

Наблюдения:

  1. Выше двух шагов намного быстрее выполнять во время выполнения (миллисекунды). Во время выполнения вам не потребуется Дейкстра: a.
  2. Первый расчет для 2 * 1k деревьев кратчайших путей должен занять в общей сложности около 2 * 1000 * 0,8 = 1600 секунд (на ноутбуке с Linux с 4 ГБ ОЗУ и процессором i5).
  3. Однако вы можете напрямую использовать для этого boost-graph ..

Использование pgrouting:

Если вы хотите использовать pgrouting, вы можете изменить функцию boost_wrapper.cpp boost_dijkstra так, чтобы она возвращала полную карту предшественника, а не только один кратчайший путь (скопируйте его в path_vect). Это заставит pgrouting dijkstra всегда возвращать дерево кратчайших путей, а не только кратчайший путь. Я еще не тестировал это (обратите внимание, что pgrouting внутренне выполняет переупорядочение индекса, но этот метод должен вернуть вам исходные идентификаторы индекса).

person SRC    schedule 04.09.2012