У лучшего в мире управляющего по имени Пенультимо родилась очередная гениальнейшая идея, peализовать которую вам и предстоит. Он верит, что поток туристов на Исла-де-Эдукадос повысится, если он сможет рассказать всему миру, как же много замечательных дорожных знаков с длинными надписями eсть у них на острове. Вам предлагается придумать алгоритм, позволяющий подсчитать суммарное количество букв на всех знаках Въезд в город Х на острове, а затем применить полученные знания для подсчёта аналогичной метрики для Республики Беларусь. Обратите внимание язык, используемый для обозначения населённых пунктов, а также тот факт, что въездов в город может быть несколько. Пенультимо также приветствует инициативность, так что можете исследовать этот вопрос для отдельных областей, провести сравнение с количеством людей, проживающих в области, а также провести любые другие исследования, которые покажутся Вам интересными.

Общий метод решения

OverPass

Использование OverPass API в Python

import overpyapi = overpy.Overpass()Data = api.query("""*ваш запрос*""")

relation["type"="boundary"]["boundary"="administrative"]["name:be"="Мнск"];//Дословно: отношение вида административная граница города Минска>; out skel qt;

<*шапка файла*><далее идет подобное перечисление всех узлов>  <node id="277218521" lat="53.8605688" lon="27.3946601"/>  <node id="4623647835" lat="53.8603938" lon="27.3966685"/>  <node id="4713906615" lat="53.8605343" lon="27.3998220"/>  <node id="4713906616" lat="53.8605398" lon="27.3966820"/>  <node id="4713906617" lat="53.8605986" lon="27.3947987"/>  <node id="277050633" lat="53.8463790" lon="27.4431241"/>  <node id="277050634" lat="53.8455797" lon="27.4452681"/>  <node id="4713906607" lat="53.8460017" lon="27.4439797"/><далее указаны пути и ID узлов, из которых они состоят><way id="572768148">    <nd ref="5502433452"/>    <nd ref="277218520"/>    <nd ref="4713906620"/>    <nd ref="277218521"/>    <nd ref="4713906617"/>    <nd ref="4623647835"/>    <nd ref="4713906616"/></way><way id="29079842">    <nd ref="277212682"/>    <nd ref="277051005"/>    <nd ref="4739822889"/>    <nd ref="4739822888"/>    <nd ref="4739845423"/>    <nd ref="4739845422"/>    <nd ref="4739845421"/></way>

import overpyapi = overpy.Overpass()Data = api.query("""relation["type"="boundary"]["boundary"="administrative"]["name:be"="Мнск"];>; out skel qt;""")Xa=Data.ways[0].nodes[0].lon #получаем долготу первого узла первой линииYa=Data.ways[0].nodes[0].lat #получаем широтуXb=Data.ways[0].nodes[1].lonYb=Data.ways[0].nodes[1].latNodeID=Data.ways[0]._node_ids[0] #получаем ID первого узла первой линииprint(len(Data.nodes)) #получаем общее количество узловprint(NodeID)print(Xa,Ya)print(Xb,Yb)

Перейдем непосредственно к задаче

import overpy###########################def line_intersection(line1, line2): #функция поиска пересечений    ax1 = line1[0][0]    ay1 = line1[0][1]    ax2 = line1[1][0]    ay2 = line1[1][1]    bx1 = line2[0][0]    by1 = line2[0][1]    bx2 = line2[1][0]    by2 = line2[1][1]    v1 = (bx2 - bx1) * (ay1 - by1) - (by2 - by1) * (ax1 - bx1)    v2 = (bx2 - bx1) * (ay2 - by1) - (by2 - by1) * (ax2 - bx1)    v3 = (ax2 - ax1) * (by1 - ay1) - (ay2 - ay1) * (bx1 - ax1)    v4 = (ax2 - ax1) * (by2 - ay1) - (ay2 - ay1) * (bx2 - ax1)    return (v1 * v2 < 0) & (v3 * v4 < 0)#######################################citytmp = []city = []Borderway = []Roadway = []Total = 0A = [0, 0]B = [0, 0]C = [0, 0]D = [0, 0]amount = 0progressbar = 0 ReadyData = open('Готовые данные.txt','w')with open("Города Беларуси.txt", "r", encoding='utf8') as file:    for i in range(115):        citytmp.append(file.readline())citytmp = [line.rstrip() for line in citytmp]for i in range(115):    city.append('"' + citytmp[i] + '"')city[0]='"Дзсна"'api = overpy.Overpass()for number in range(0,115):#главный цикл обработки, перебирает города    borderstring = """(relation["type"="boundary"]["boundary"="administrative"]["name:be"=""" + city[number] + """][place=town]; relation["type"="boundary"]["boundary"="administrative"]["name:be"=""" + city[number] + """][place=city];);>; out skel qt;"""    roadstring = """(area[place=town]["name:be"=""" + city[number] + """]; way["highway"][highway!=service]["highway"!="footway"]["highway"!="track"]["highway"!="path"]    ["highway"!="cycleway"]["highway"!="pedestrian"]["highway"!="steps"]["highway"!="residential"](area);area[place=city]["name:be"=""" + city[number] + """]; way["highway"][highway!=service]["highway"!="footway"]["highway"!="track"]["highway"!="path"]    ["highway"!="cycleway"]["highway"!="pedestrian"]["highway"!="steps"]["highway"!="residential"](area););out body; >; out skel qt;"""    print('Getting data about', city[number],'...')        road = api.query(roadstring)        border = api.query(borderstring)    print('got data!, city:', city[number]) #получаем данные    for w in range(len(border.ways)): #перебирает линии границ        for i in range(len(border.ways[w]._node_ids)):#перебирает узлы линий границ             progressbar = i / len(border.ways[w]._node_ids) * 100            print(progressbar, "%;", w, "of", len(border.ways), "parts ready; city-", city[number])            A[0] = border.ways[w].nodes[i].lon            A[1] = border.ways[w].nodes[i].lat            if i == len(border.ways[w]._node_ids) - 1:                break            B[0] = border.ways[w].nodes[i+1].lon            B[1] = border.ways[w].nodes[i+1].lat            for j in range(len(road.ways)):                for k in range(len(road.ways[j]._node_ids)):                    C[0] = road.ways[j].nodes[k].lon                    C[1] = road.ways[j].nodes[k].lat                    if k == len(road.ways[j]._node_ids) - 1:                        break                    D[0] = road.ways[j].nodes[k+1].lon                    D[1] = road.ways[j].nodes[k+1].lat                    if line_intersection((A, B), (C, D)) == 1:                        amount += 1                        print(road.ways[j]._node_ids[k])    print(amount)    Total += amount * len(city[number])    ReadyData.write(str(city[number]))    ReadyData.write(str(amount))    ReadyData.write('\n')    amount = 0print('Total', Total) #и вывод всего

Заметки по коду

Вторая задача

area[name="Москва"];(  node["amenity"="fuel"](area);  way["amenity"="fuel"](area);  relation["amenity"="fuel"](area););out body;>;out skel qt;

import overpyapi = overpy.Overpass()Data = api.query("""area[name="Москва"];(  node["amenity"="fuel"](area);  way["amenity"="fuel"](area);  relation["amenity"="fuel"](area););out body;>;out skel qt;""")print(len(Data.nodes)) #получаем общее количество узлов

Хотелось бы поделиться опытом создания систем маршрутизации 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. Для того, чтобы улучшить полученный маршрут (как минимум, двигаться по дорогам в правильном направлении), нам понадобится добавить некоторые свои функции, чем мы и займемся в следующей части статьи. Далее поговорим о выборе параметров маршрутизации и других улучшениях.

Продолжаем цикл статей про построение систем роутинга со сложными требованиями на основе Open Source базы данных PostgreSQL и расширения PgRouting на карте OpenStreetMap. Сегодня мы поговорим о том, как добавить поддержку односторонних дорог (направлений движения). Зачастую, именно отсутствие этой поддержки является основной причиной смены PgRouting на другой "движок" маршрутизации. Как обычно, все данные и результаты доступны в моем GitHub репозитории OSM Routing Tricks, который я пополняю по мере публикаций.

Небольшой маршрут из 330 адресов на карте OpenStreetMap.

Что такое односторонние дороги и зачем они нужны

В первую очередь, мы говорим об односторонних дорогах на карте, то есть таких, по которым движение разрешено только в одну сторону. Разумеется, двигаться по ним в другую сторону запрещено. Особенно часто такое ограничение встречается на мостах, в туннелях и на высокоскоростных шоссе, где движение в противоположную сторону опасно для жизни. Разумеется, нам необходимо соблюдать направление движения для автотранспортных средств, здесь не может быть компромиссов. В то же время, для пешеходного роутинга это не является обязательным, хотя и удобно двигаться по маршруту по направлению движения автомобилей проще ориентироваться, можно воспользоваться общественным транспортом или такси и т.п. Замечу, что некоторые (многие, на самом деле) открытые системы роутинга игнорируют это правило, то есть они подразумевают пешеходный роутинг (по пешеходным дорогам и по окружающим не пешеходные дороги тротуарам, которые могут и отсутствовать в действительности), независимо от длины маршрута и наличия тротуаров в туннелях и на скоростных шоссе.
Кроме того, поддержка односторонних дорог позволяет улучшить маршрутную сеть заданные направления движения заметно упрощают поиск оптимального маршрута за счет очень значительного снижения количества возможных вариантов, можно учесть рельеф местности (довольно трудно с грузом или без подняться по множеству ступенек крутой лестницы, особенно, если можно вместо того спускаться по ней) и принудительно сделать некоторые участки односторонними, можно сделать односторонними виртуальные соединения между домами и улицами (так что маршрут будет построен с последовательной нумерацией, даже если он несколько раз проходит по одной улице поскольку длина маршрута в таком случае не меняется, сам PgRouting никак не гарантирует, что все адреса на такой улице будут посещены в один и тот же проход по ней). И так далее, есть еще много возможностей, доступных для роутинга с поддержкой направлений движения.

Добавляем поддержку односторонних дорог в PgRouting

Официальная документация PgRouting для функции pgr_TSP Using Simulated Annealing approximation algorithm сообщает нам:

If using directed := true, the resulting non symmetric matrix must be converted to symmetric by fixing the non symmetric values according to your application needs.

Отлично, но в документации нет ни слова о том, как это сделать. Нам придется начать с теории и разобраться, возможно ли это и как именно это сделать. Англоязычная страница википедии, посвященная проблеме коммивояжера, содержит нужный нам раздел Travelling salesman problem: Asymmetric:

Solving an asymmetric TSP graph can be somewhat complex. The following is a 33 matrix containing all possible path weights between the nodes A, B and C. One option is to turn an asymmetric matrix of size N into a symmetric matrix of size 2N.

Здесь сказано, что решение задачи коммивояжера на асимметричной матрице расстояний усложняется, поэтому лучше превратить асимметричную матрицу в симметричную (ценой удвоения размера матрицы) и решать более простую симметричную задачу на симметричной матрице расстояний. Почти то же самое, что и в документации PgRouting, зато здесь объяснено, зачем же нужна именно симметричная матрица. Далее на этой же викистранице приводится алгоритм конвертации асимметричной матрицы в симметричную и пример конвертации простой матрицы. Идея простая каждый узел и каждое ребро заменить на два и задать такую матрицу расстояний между ними, чтобы полученный на такой матрице путь соответствовал искомому. Ниже мы рассмотрим этот пример из вики. К сожалению, графическое представление соответствующего графа я рисовал на листочках от руки и показать здесь не могу (почерк у меня как у физика, так что извините).

Пусть у нас задана асимметричная матрица весов:

Ей соответствует следующая симметричная матрица весов:

где -w это виртуальные соединения для виртуальных узлов, которые рекомендуется задать некоторым отрицательным числом, потому что

w=0 is not always low enough

Теперь мы можем написать соответствующую функцию-обертку для PgRouting. Поскольку PgRouting отбрасывает все отрицательные значения в матрице весов, мы используем нулевое значение (мы это компенсируем заданием очень высоких весов для запрещенных направлений) и добавляем еще [избыточные] ребра с очень высоким весом, поскольку PgRouting требует указания весов между всеми узлами матрицы (в теории этого не требуется, это просто техническое ограничение, которому нам приходится соответствовать).

CREATE OR REPLACE FUNCTION pgr_dijkstraSymmetrizeCostMatrix(matrix_cell_sql text,    OUT start_vid BIGINT, OUT end_vid BIGINT, OUT agg_cost float)RETURNS SETOF RECORD AS$BODY$DECLARE    sql text;    r record;BEGIN    sql := 'with edges as (' || matrix_cell_sql || ')        select 3e9+start_vid as start_vid, end_vid as end_vid, agg_cost from edges        union        select end_vid, 3e9+start_vid, agg_cost from edges        union        select 3e9+start_vid, start_vid, 0 from edges        union        select start_vid, 3e9+start_vid, 0 from edges        union        select start_vid, end_vid, 1e6 from edges        union        select 3e9+start_vid, 3e9+end_vid, 1e6 from edges        ';    FOR r IN EXECUTE sql LOOP        start_vid := r.start_vid;        end_vid   := r.end_vid;        agg_cost  := r.agg_cost;        RETURN NEXT;    END LOOP;END;$BODY$LANGUAGE plpgsql VOLATILE STRICT;

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

An Infinity value was found on the Matrix

Заполним все значения матрицы весов с помощью еще одной функции-обертки (можно было бы упростить pgr_dijkstraSymmetrizeCostMatrix() и не добавлять в ней избыточные ребра, но в таком случае при полной исходной матрице мы получим не полную итоговую матрицу, что, на мой взгляд, не есть правильно):

CREATE OR REPLACE FUNCTION pgr_dijkstraValidateCostMatrix(matrix_cell_sql text,    OUT start_vid BIGINT, OUT end_vid BIGINT, OUT agg_cost float)RETURNS SETOF RECORD AS$BODY$DECLARE    sql text;    r record;BEGIN    sql := 'WITH RECURSIVE src AS (' || matrix_cell_sql || '),    dst AS (        select            *        from src where start_vid =            (select                start_vid            from src            group by start_vid            order by count(*) desc            limit 1)        union        select            src.*        from src, dst        where src.start_vid=dst.end_vid    )    select * from dst';    FOR r IN EXECUTE sql LOOP        start_vid := r.start_vid;        end_vid   := r.end_vid;        agg_cost  := r.agg_cost;        RETURN NEXT;    END LOOP;END;$BODY$LANGUAGE plpgsql VOLATILE STRICT;

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

Исходные данные

Мы используем все те же данные, что и в предыдущей части статьи плюс определенные выше дополнительные функции. Несколько расширенный скрипт load.sh из репозитория загрузит в базу данных PostgreSQL все необходимое.

Поиск оптимального маршрута для автомобиля

Поскольку для пешехода тротуары доступны в любом направлении, а для автомобиля одностонние дороги доступны лишь в одном направлении, необходимо указывать разные весовые функции для роутинга пешеходного и автомобильного. Как уже упоминалось ранее, наша дорожная сеть оптимизирована для автомобильного роутинга, о нем и поговорим. Итак, запретим (укажем очень большую длину миллион метров) движение в противоположном направлении. Ранее при подготовке дорожной сети мы разделили каждую дорогу на две, одна из которых (type='osm') совпадает с исходной и вторая (type='osmreverse') инвертирована. Соответственно, для односторонней дороги добавленная нами ее инвертированная копия должна быть запрещена для любого движения (вообще говоря, можно ее и вовсе не создавать, но тогда будет немного сложнее объяснить построение дорожной сети). Кроме того, для прямого движения должна быть доступна только исходная дорога (type='osm') и для обратного инвертированная (type='osmreverse'). В таком случае, итоговые прямая и обратная весовые функции имеют вид:

    case when (type='osmreverse' and oneway) then 1000000 else length end as cost,    case when type ilike 'osm%' then 1000000 else length end as reverse_cost,

где length геометрическая длина соответствующего сегмента дороги. Усложнив дорожную сеть (заранее исключив ненужные сегменты), можно взамен упростить весовые функции.

Построим оптимальный маршрут все для тех же случайных 330 адресов домов и с помощью функции PgRouting pgr_TSP() и добавленных выше функций pgr_dijkstraSymmetrizeCostMatrix() и pgr_dijkstraValidateCostMatrix(). Теперь мы можем использовать флаг directed=true, так как теперь мы добавили для pgr_TSP() поддержку односторонних дорог (точнее, симметризацию и заполнение пропущенных значений в несимметричной матрице, которая получается при наличии односторонних дорог). Как и ранее, в результате выполнения немного модифицированного SQL скрипта route.sql создается таблица "route" с сегментами маршрута для каждого заданного адреса, которую можно визуализировать с помощью программы QGIS. Файл проекта QGIS тоже обновлен, см. в репозитории route.qgs Полученная карта с маршрутом представлена на картинке до хабраката.

Смотрите на следующем рисунке участок построенного маршрута с порядковыми номерами посещенных домов (здесь черным цветом обведены односторонние дороги):

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

Как и указано на карте OpenStreetMap, в построенном маршруте движение выполняется слева направо для участка дороги с пунктами маршрута 329,330,331 на левой стороне дороги:

и в том же направлении (слева направо) для участка дороги с пунктами маршрута 72,73,74 на правой стороне дороги (второй проход по этому участку дороги):

Нумерация домов по сторонам улиц между перекрестками последовательная. Зачастую нумерация последовательная и после перекрестков (см. картинки выше). Таким образом, мы добились заметного улучшения качества маршрута, не меняя дорожную сеть и не занимаясь оптимизацией параметров функции pgr_TSP().

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

Заключение

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

Если рассмотреть весь маршрут детально, то его еще можно улучшить, в том числе, с помощью оптимизации параметров функции pgr_TSP(). Но дело в том, что только путем оптимизации этих параметров подобного полученному выше результату добиться не удастся в самом деле, алгоритм оптимизации маршрутов PgRouting ничего "не знает" про наши предпочтения о последовательной нумерации и другие. Так что поддержка односторонних дорог, на самом деле, дает нам намного больше, чем можно было бы ожидать.

Можно ли добиться аналогичного результата с последовательной нумерацией зданий между перекрестками иначе, не увеличивая матрицу весов с соответствующим замедлением построения маршрута? Да, можно. Более того, можно еще и значительно ускорить построение маршрута (например, на один-два десятичных порядка), в том числе, с учетом односторонних дорог. Об этом мы и поговорим в следующий раз.

Продажа MAPS.ME

Что изменилось в декабре 2020 года

• Для получения карт внедрили Mapbox SDK. В результате карты практически перестали работать в офлайне
  
• Фоновое скачивание работало плохо
  
• Пропали карты метро и навигация по метро
  
• Испортилась пешеходная навигация, исчезла диаграмма с перепадом высот
  
• Пропали личные данные: подписки на отключение рекламы, отзывы, записи пройденных маршрутов
  
• Интерфейс стал монструозным, сильно напоминая Google Maps. Размер карт увеличился в четыре раза, при этом ухудшилась детализация. Например, размер карт Москвы вырос с 50 до 200 МБ
  
• Исчез ландшафтный режим
  
• Приложение стало тормозить

Форки MAPS.ME

Альтернативы MAPS.ME

• OsmAnd, есть бесплатная и платная версии (треки и тропинки, поддерживаются тепловые карты Strava и тайлы OpenTopo), не требует создания аккаунта, поддерживает закладки, работает в офлайне, отличается насыщенным UI, iOS, Android. В последних версиях под Android исправлен баг с поиском, из-за которого раньше поиск на карте практически не работал. Если кому-то интересно, вот телеграм-канал с разработчиками.
  
  
  OsmAnd для Android
  
• Mapy.cz (есть популярные трейлы, горизонтали высот, хорошо подходит для велоспорта), работает в офлайне, Android-версия Mapy.cz Cycling & Hiking offline maps, также версии под iOS, Windows и AppGallery. Это приложение фокусируется на Центральной Европе, а международная версия называется Windy Maps
  
• Guru Maps
  
• Bike Citizens
  
• Naviki
  
• MapFactor Navigator
  
• Pocket Earth, только для iOS
  
• MapOut, только для iOS
  
  
  3D-эффект в MapOut
  
• Gaia GPS, походы и путешествия

На правах рекламы

О проекте

О редакторах

Об источниках данных

Редактирование OpenStreetMap средствами iD

В заключение

1-6 марта приглашаем на мероприятия, приуроченные к Международному Дню открытых данных 2021.

Это крупнейшее ежегодное международное событие, которое помогает продвигать концепцию открытых данных среди органов государственной власти, бизнес-корпораций, некоммерческих организаций и гражданского общества. Организатором Дня открытых данных в России выступает АНО Информационная культура.

Рассказываем, какие мероприятия мы приготовили для участников в этом году.
Накануне Дня открытых данных, с 1 по 5 марта, проведем серию практических онлайн мастер-классов по работе с открытыми данными.

• 1 марта, мастер-класс Вскрываем декларации. Как при помощи регулярных выражений привести Wordовскую табличку к пригодной для анализа форме. Доступна видеозапись.
• 2 марта, мастер-класс О чем говорят депутаты Госдумы? Анализ текстовых данных на Python.
• 3 марта, мастер-классы по работе с геопространственными данными и картами для новичков и профи.
• 4 марта, мастер-класс по поиску открытых данных от DataMasters.
• 5 марта, мастер-класс Российская официальная статистика: как сделать работу с данными удобнее, а данные понятнее?.
• 5 марта, мастер-класс Визуализация данных в ObservableHQ.

6 марта пройдет онлайн-конференция День открытых данных.

В центре внимания вопросы о том, что происходит с открытостью в России и мире и как использовать данные для эффективного решения конкретных проблем и задач общества. В дискуссиях примут участие не только российские эксперты, но и представители крупнейших международных проектов, продвигающих ценности и идеологию открытых данных: Global Data Barometer, The Humanitarian Data Exchange.

В программе дискуссии и выступления:

• Дискуссия. Бизнес на открытости: зачем заниматься открытым кодом и открытыми данными
• Дискуссия. Как инструменты оценки влияют на открытость государства?
• Дискуссия. Доступность данных о госфинансах
• Дискуссия. Данные переписи населения 2021: приватность vs. польза для общества
• Выступления. Что происходит с тематикой открытости в мире?

Программа и регистрация: opendataday.ru/msk. Трансляция будет доступна и бесплатна для всех желающих.

Найти

Дано

Решение

Overpass API мощный инструмент для извлечения данных из базы OSM по запросу пользователя. Он оптимизирован для задач любого масштаба: от получения нескольких элементов из базы до сотен миллионов объектов, которые отбираются согласно запросу в виде XML или Overpass QL модернизированной версии Overpass XML. Подробнее об Overpass API здесь.

Подробная инструкция по установке OSM лежит здесь.

sudo apt-get updatesudo apt-get install g++ make expat libexpat1-dev zlib1g-dev apache2 -ywget http://dev.overpass-api.de/releases/osm-3s_ВЕРСИЯ.tar.gztar -zxvf osm-3s_ВЕРСИЯ.tar.gzcd osm-3s_ВЕРСИЯ./configure CXXFLAGS="-O2" --prefix=$EXEC_DIRmake installcd ../chmod -R 755 ./overpass

Достойная альтернатива Geofabrik BBBike.

ПУТЬ_К_INIT_OSM3S.SH ПУТЬ_К_ФАЙЛУ_BZ2 ПУТЬ_КУДА_РАСПАКОВВАТЬ ДИРЕКТОРИЯ_OVERPASS_API
Примечание: в данном случае все действия выполняются в каталоге overpass.

ПУТЬ_К_OSM3S_QUERY --db-dir = ПУТЬ_К_DB

root@MIP-USER55:~# cd overpass/root@MIP-USER55:~/overpass# ./osm-3s_v0.7.56.7/bin/osm3s_query --db-dir=dbencoding remark: Please enter your query and terminate it with CTRL+D.[out:json][timeout:25];(nwr["landuse"="forest"];);out count;{  ...,  "elements": [{  "type": "count",  "id": 0,  "tags": {    "nodes": "23",    "ways": "19723",    "relations": "4206",    "total": "23952"  }}  ]}

echo "ИМЯ_СЕРВЕРА localhost" | sudo tee /etc/apache2/conf-available/ИМЯ_СЕРВЕРА.conf && sudo a2enconf ИМЯ_СЕРВЕРАsudo iptables -A INPUT -m state --state NEW -m tcp -p tcp --dport ПОРТ -j ACCEPTsudo a2enmod cgisudo a2enmod ext_filtersudo cp /etc/apache2/sites-available/000-default.conf /etc/apache2/sites-available/ИМЯ_КОНФИГА_ДЛЯ_СЕРВЕРА.conf

<VirtualHost *:ПОРТ>   ServerAdmin webmaster@localhost   ExtFilterDefine gzip mode=output cmd=/bin/gzip   DocumentRoot ПУТЬ_К_OVERPASS_API/html   ScriptAlias /api/ ПУТЬ_К_OVERPASS_API/cgi-bin/   <Directory "ПУТЬ_К_OVERPASS_API">      AllowOverride None      Options Indexes FollowSymLinks      Require all granted   </Directory>   <Directory "ПУТЬ_К_OVERPASS_API/cgi-bin/">      AllowOverride None      Options +ExecCGI -MultiViews +SymLinksIfOwnerMatch      Require all granted   </Directory>   ErrorLog ${APACHE_LOG_DIR}/error.log   CustomLog ${APACHE_LOG_DIR}/access.log combined</VirtualHost>

sudo a2ensite КОНФИГ.confsudo a2dissite 000-default.confsudo a2dissite ВСЕ_ДРУГИЕ_КОНФИГИ.confsudo service apache2 reload

nohup ПУТЬ_К_OVERPASS_API/bin/dispatcher --osm-base --db-dir=ПУТЬ_К_DB --meta &

nohup ПУТЬ_К_OVERPASS_API/bin/dispatcher --areas --db-dir=ПУТЬ_К_DB &chmod 666 "../db/osm3s_OVERPASS_API_ВЕРСИЯ_areas"nohup ПУТЬ_К_OVERPASS_API/bin/rules_loop.sh ПУТЬ_К_DB &

http://localhost:ПОРТ/api/interpreter?data=[output:json][timeout:25]; area[name="Рязань"]->.searchArea; ( nwr["leisure"="park"](area.searchArea); ); out count;

"elements": [{  "type": "count",  "id": 0,  "tags": {    "nodes": "0",    "ways": "57",    "relations": "11",    "areas": "0",    "total": "68"  }}  ]}

ODANT цифровая интеграционная платформа отечественной разработки, предназначенная для построения информационных систем различной сложности и распределенности. Подробнее об ODANT здесь.

nwr["amenity"="recycling"](area.searchArea);nwr["amenity"="waste_disposal"](area.searchArea);nwr["amenity"="waste_basket"](area.searchArea);

nwr["amenity"="bench"](area.searchArea);

Leaflet библиотека с открытым исходным кодом, написанная на JavaScript, предназначенная для отображения карт на веб-сайтах. Поддерживает большинство мобильных и стационарных платформ из числа тех, что поддерживают HTML5 и CSS3. Leaflet позволяет разработчику, не знакомому с ГИС, легко отображать растровые карты, состоящие из маленьких фрагментов тайлов, с, возможно, дополнительными слоями, накладываемыми поверх основного. Подробнее о Leaflet здесь.

const polygon = L.polygon(КООРДИНАТ).addTo(map);const area = L.GeometryUtil.geodesicArea(polygon.getLatLngs());

Эпилог и выводы

О проекте

Из чего складывается качество жизни в мегаполисе

• Уровень шума.
• Социальная инфраструктура.
• Транспортная инфраструктура.

• Экология. Качество воздуха на наш взгляд важнейший аспект экологии, влияющий на жизнь в городе. Поэтому в разделе Экология сейчас представлены два слоя: качество воздуха и источники загрязнения, среди которых ТЭЦ, заводы и водоочистные сооружения.
• Застройка. В этом разделе доступны два взаимодополняющих слоя: процент плотности застройки и процент застройки.

Плотность застройки

Расчет плотности застройки

Резюмируем: фактор застройка для оценки качества городской среды лучше всего анализировать в разрезе двух параметров: процента плотности застройки и процента застройки. Именно их комбинация позволит увидеть картину целиком.

Обратная сторона ХоумХаба

Наши источники данных

Пайплайн генерации тайлов

О планах и о команде

После того как большинство факторов качества городской среды будет реализовано, мы предоставим удобный интерфейс для выбора интересующих факторов и опциональной установки их важности. Можно будет подбирать подходящие под конкретные требования микрорайоны и дома. Кому-то очень важна экология, а транспортная доступность второстепенна. Кто-то в первую очередь обращает внимание на уровень социальной инфраструктуры и плотность застойки. В общем, можно будет находить жилье на любой вкус.

Заключение