Хотелось бы поделиться опытом создания систем маршрутизации PostgreSQL/PgRouting на карте OpenStreetMap. Речь пойдет о разработке [коммерческих] решений со сложными требованиями, для более простых проектов, вероятно, достаточно обратиться к документации. Насколько мне известно, такие вещи, как полная поддержка односторонних дорог и направлений движения, быстрый роутинг на тысячах адресов (порядка секунд на обычном лаптопе, к примеру, Macbook Pro 13″ 2013 года), создание дорожного графа с заданными свойствами, мета-оптимизация маршрутов вообще нигде и никак не рассматриваются. Как обычно, все данные и результаты доступны в моем GitHub репозитории OSM Routing Tricks, который я буду пополнять по мере публикаций.
Небольшой маршрут из 330 адресов на карте OpenStreetMap (время построения около 5 секунд на вышеупомянутом лаптопе). Можно ли за это же время построить маршрут, скажем, из 5000 точек? Да, можно, и об этом мы тоже поговорим (в следующих частях статьи).
Что такое маршрутизация и зачем она нужна
Пожалуй, легче сказать, где маршрутизация не используется, чем перечислить все ее применения. Например: маршрутизация нужна для доступа к этой статье в сети интернет, для доставки почты или посылок, для путешествий, и даже для спутниковой интерферометрии, о которой я писал ранее, тоже используется маршрутизация (вычисление суммарного сдвига фазы по замкнутым траекториям на растре)! Далее мы будем говорить только о применении расширения PgRouting для СУБД PostgreSQL и карте OpenStreetMap.
В идеале, для поиска оптимального маршрута нам нужно рассмотреть все возможные комбинации из входящих в него адресов. На практике, очевидно, сделать это не удастся для сколько-нибудь значительного количества адресов и потому используются разные приближенные методы. В частности, в расширении PgRouting для поиска оптимального маршрута используется алгоритм отжига. Как и у других методов, у него есть свои преимущества и недостатки, поэтому мы будем обсуждать именно такую реализацию, хотя все или почти все сказанное применимо и к другим методам приближенного поиска оптимального маршрута.
Очень рекомендую также ознакомиться с соответствующей статьей википедии Задача коммивояжёра, поскольку многие старые подходы к задаче и сейчас успешно используются в качестве оптимизаций и решений для частных случаев.
Версии программ и операционные системы
Для новых проектов рекомендую актуальную версию PgRouting 3.0 и СУБД PostgreSQL 12, хотя тот же код обычно работает с PgRouting 2.6 и СУБД PostgreSQL 9 и более давними. Стоит отметить, что на MacOS (любой версии) и Debian/Ubuntu (любой версии) результаты работы функции PgRouting для поиска оптимального маршрута pgr_TSP() сильно отличаются, при этом, как правило, на линуксах результаты при параметрах по умолчанию получаются значительно лучше, при этом используемый алгоритм «отжига» в компиляции на MacOS работает нестабильно, то есть небольшие изменения параметров приводят к непредсказуемым изменениям результатов при недостаточно продуманном дорожном графе, что, кстати сказать, очень помогает при тестировании. Сам я использую и MacOS и Debian/Ubuntu.
Как загрузить OpenStreetMap в базу данных PostgreSQL
Существует много разных утилит, из которых я предпочитаю GDAL, на мой взгляд, наиболее мощную и предсказуемую. Эта утилита позволяет, в частности, преобразовать дамп OpenStreetMap в дамп PostgreSQL и потом загрузить его как обычный SQL скрипт, см. GDAL: PostgreSQL SQL Dump. Можно загрузить и напрямую в базу, см. документацию GDAL. Пример команды загрузки данных из дампа OSM для Германии (germany-latest.osm.pbf) в базу данных PostgreSQL (osmrouting):
ogr2ogr
-f PGDUMP
/vsistdout/ "germany-latest.osm.pbf"
-nln "osm_lines"
-nlt LINESTRING
-progress
--config PG_USE_COPY YES
--config GEOMETRY_NAME the_geom
--config OSM_COMPRESS_NODES YES
--config OSM_CONFIG_FILE "osmconf.ini"
-sql "select * from lines where highway is not null"
-lco FID=id
| psql osmroutingДампы OpenStreetMap по странам предоставляет сервис OpenStreetMap Data Extracts.
Как превратить карту дорог OpenStreetMap в дорожную сеть для роутинга
Простейший путь заключается в поиске и нумерации всех пересечений улиц и разбиении всех дорог на участки между найденными точками пересечения. Точки пересечения будут узлами дорожного графа (сети), а участки — ребрами этого графа. Узлы необходимы в процессе построения дорожной сети, а для роутинга они не нужны, хотя их удобно использовать для поиска ближайших узлов графа для заданных домов (адресов). В чем минусы такого простого подхода, хорошо описанного в документации? В первую очередь тем, что мы никак не можем ограничить пересечения дорог — и полученные маршруты будут в шахматном порядке обходить дома по обе стороны каждой дороги, что выглядит странно, в случае широких улиц такой маршрут очень далек от оптимального и, вдобавок, вовсе не все дороги можно пересечь в произвольном месте. Кроме того, по умолчанию односторонние улицы или полностью исключаются из дорожной сети, или доступны в обоих направлениях. Зато такой вариант очень прост в реализациии для него существуют и специальные утилиты и функции PgRouting.
В предложенной в репозитории дорожной сети каждое ребро разделено на два односторонних (два направления движения транспорта или два тротуара для пешеходов) и добавлены соединяющие кратчайшие пути между дорогами и домами так, чтобы добавленные сегменты соответствовали принятому направлению движения (напомню, в разных странах бывает как левостороннее, так и правостороннее движение) и необходимые узлы сети. Таким образом, сменить направление движения можно только на перекрестках и мы избегаем лишних пересечений дорог и обеспечиваем непрерывную нумерацию домов по каждую сторону каждого участка дорог. При необходимости, протяженные участки можно разбить на более короткие для возможности смены направления движения. Заметим, что такой вариант дорожной сети оптимизирован для автомобильных маршрутов.
На рисунке выше показана визуализация виртуальной дорожной сети из репозитория. На самом деле, геометрически синие и зеленые сегменты накладываются друг на друга, а здесь сделано смещение между ними только для наглядности. Здесь нумерация точек маршрута на каждой стороне последовательная, при этом направление движения на одной из сторон (синей) игнорируется, поскольку у нас пока нет поддержки однонаправленных дорог.
Для пешеходных маршрутов лучше для каждого добавленного узла связи с домами также добавить узел к парному ребру (обратного направления) и определить короткие сегменты между этими узлами, так как во многих случаях пешеходу удобнее пересекать небольшие улицы, нежели двигаться по одной стороне от перекрестка до перекрестка. Для автотранспортных маршрутов такой вариант тоже подходит, только нужно увеличить расстояние между виртуальными узлами. Скажем, 10 м для пешеходного маршрута и 100 м для автомобильного разумная оценка для каждой смены направления вне перекрестка.
Возможно, вас интересует вопрос, почему мы тратим время на создание сложной дорожной сети вместо использования более «продвинутых» методов построения оптимального маршрута? Все очень просто — по хорошей дорожной сети даже простой алгоритм быстро (секунды) построит отличные маршруты, в то время как по посредственной дорожной сети даже лучшие из существующих алгоритмов за разумное время (минуты, часы или дни, в зависимости от задачи) построят плохие маршруты или вообще не смогут завершить вычисления. Это следствие невероятной вычислительной сложности задачи. К примеру, если мы желаем посетить 10 или 100 адресов по обе стороны одной улицы и при этом у нас определены два направления движения и только два перехода между ними, скажем, в начале и в конце улицы — задача имеет единственное решение и любой алгоритм его найдет почти мгновенно! В случае же, когда у нас нет заданных направлений движения и разрешено пересечение улицы около каждого заданного адреса — задача становится не решаемой вычислительно уже для нескольких десятков адресов и разные алгоритмы и для разного числа адресов вернут разные и весьма не оптимальные маршруты. Таким образом, критически важно именно построить дорожную сеть с такими ограничениями, которые запрещают большинство (неоптимальных) маршрутов, так что пространство перебора становится несравнимо меньше и достаточно оптимальный результат гарантирован любым из методов. Именно ограничения на направление движения и допустимые повороты являются самыми эффективными.
Таблицы базы данных PostgreSQL
Мы будем работать с базой «osmrouting», содержащей несколько таблиц, содержимое которых доступно в виде PostgreSQL SQL дампов в репозитории, см. также скрипт инициализации базы данных и загрузки дампов load.sh (также загружает необходимые расширения PgRouting и PostGIS).
Первая таблица является единственной необходимой и содержит данные маршрутной сети и, по желанию, информацию для визуализации (сам алгоритм роутинга работает с идентификаторами ребер графа start_id и end_id и некоторой стоимостью каждого сегмента, задаваемой, например, его длиной length):
-- таблица с ребрами маршрутного графа (сегментами дорожной сети)
-- id - идентификатор для отладки
-- the_geom - геометрия дорожного сегмента для визуализации
-- oneway - флаг односторонней дороги
-- highway - флаг скоростного шоссе (можно запретить на нем повороты и пересечения)
-- pedestrian - флаг пешеходной улицы (можно запретить движение транспорта)
-- start_id - идетификатор стартового узла сегмента для роутинга
-- end_id - идетификатор конечного узла сегмента для роутинга
-- length - длина сегмента (может переопределяться в зависимости от типа дороги и проч.)
osmrouting=# d osm_network
Table "public.osm_network"
Column | Type | Collation | Nullable | Default
------------+---------------------------+-----------+----------+---------
id | integer | | |
the_geom | geometry(LineString,4326) | | |
type | text | | |
oneway | boolean | | |
highway | boolean | | |
pedestrian | boolean | | |
start_id | bigint | | |
end_id | bigint | | |
length | double precision | | | Вторая таблица не является необходимой и используется только для поиска ближайшего узла дорожной сети для заданных адресов:
-- таблица с узлами маршрутного графа
-- id - идентификатор для отладки
-- the_geom - геометрия дорожного узла для визуализации
osmrouting=# d osm_nodes
Table "public.osm_nodes"
Column | Type | Collation | Nullable | Default
----------+----------------------+-----------+----------+---------
id | bigint | | |
the_geom | geometry(Point,4326) | | | Третья таблица также не является необходимой и используется только для хранения адресов и координат домов, которые мы используем в тестовых скриптах:
osmrouting=# d osm_buildings
Table "public.osm_buildings"
Column | Type | Collation | Nullable | Default
----------+----------------------+-----------+----------+---------
id | character varying | | |
the_geom | geometry(Point,4326) | | |
...Также тестовые скрипты создают дополнительные таблицы.
Поиск оптимального маршрута
Скрипт репозитория route.sql содержит необходимые команды для выбора случайных 330 адресов домов и построения маршрута по ним с помощью функции PgRouting pgr_TSP(). На самом деле, указанная функция работает не с координатами, а с матрицей расстояний (есть функции и для работы с координатами, см. документацию PgRouting). Матрица расстояний может быть создана функцией pgr_dijkstraCostMatrix(). Заметим, что в скрипте для генерации этой матрицы указан флаг directed=false, так как по умолчанию pgr_TSP() не работает с односторонними дорогами (точнее, не работает с несимметричной матрицей, которая получается при наличии односторонних дорог). С помощью моих функций pgr_dijkstraSymmetrizeCostMatrix() и pgr_dijkstraValidateCostMatrix() это ограничение можно обойти, как мы увидим далее. Что интересно, маршрут возвращается в виде списка идентификаторов узлов дорожного графа (в нашем случае — все узлы результата соответствуют добавленным нами виртуальным узлам для домов) и для получения маршрута в виде линии нужно полученный список идентификаторов передать в функцию pgr_dijkstraVia() для нахождения всех посещенных ребер дорожной сети в нужном порядке.
Параметр randomize=false обеспечивает выполнение нескольких запусков алгоритма роутинга и возвращение лучшего результата, для целей отладки и ускорения вычислений можно указать randomize=true, но возвращаемый результат в таком случае непредсказуем. В результате выполнения указанного SQL скрипта создается таблица «route» с сегментами маршрута для каждого заданного адреса, которую можно визуализировать с помощью программы QGIS. Файл проекта QGIS также представлен в репозитории, см. route.qgs Полученная карта с маршрутом представлена на картинке до хабраката.
Смотрите на следующем рисунке участок дорожной сети с узлами и построенного маршрута с порядковыми номерами посещенных домов:
Кроме уже означенной проблемы с направлениями движения, местами можно заметить странный порядок нумерации — например, смотрите номера 245,246,247 и другие. Вы можете захотеть «покрутить» доступные параметры для алгоритма отжига — но, даже если это удастся сделать, найденные подходящие параметры для конкретного маршрута не помогут с любым другим маршрутом. Вместо попыток подбора параметров и увеличения времени вычисления следует заняться улучшением дорожной сети (и матрицы расстояний), например, за счет жесткого указания направлений движения.
Заключение
Сегодня мы обсудили самые основы — как получить исходные данные, подготовить маршрутную сеть и выполнить поиск оптимального маршрута средствами PgRouting. Для того, чтобы улучшить полученный маршрут (как минимум, двигаться по дорогам в правильном направлении), нам понадобится добавить некоторые свои функции, чем мы и займемся в следующей части статьи. Далее поговорим о выборе параметров маршрутизации и других улучшениях.
