TrueDrive: инструменты сетевого анализа для построения маршрутов и зон транспортной доступности

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

TrueDrive – программный продукт для проведения сетевого анализа на дорожной сети. На базе TrueDrive можно создать веб-сервис, с помощью которого можно запускать алгоритмы сетевого анализа. На данный момент доступны следующие алгоритмы анализа дорожной сети:

• Расчёт кратчайшего маршрута между точками
• Расчёт зон доступности из заданных точек за заранее заданное время или расстояние.

        

Слева: расчёт кратчайшего маршрута, справа: расчёт зоны доступности

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

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

Преимущества технологии

TrueDrive является не просто очередным программным продуктом для создания сервисов сетевого анализа, это продукт, обладающий уникальными преимуществами. К основным преимуществам веб-сервиса TrueDrive можно отнести следующие:

• Высокая скорость работы алгоритмов позволяет осуществлять типовые расчёты на лету.
• Возможность использования не только стандартных параметров дорог для оптимизации (время и расстояние), но и особых параметров, заранее рассчитанных на этапе построения индекса дорожного графа. Например, можно использовать критерий безопасности движения (при наличии данных) или применить формулу расчёта параметра оптимизации на лету, для чего используется нотация SQL.
• Возможность использования барьеров. Каждый запрос может содержать набор пространственных ограничений на движение по определенным сегментам дорог или зонам. Если движение на таких участках невозможно или затруднено (полупрозрачные барьеры), то при расчете маршрута это обстоятельство будет учтено. Для использования барьеров перестройка индекса дорожного графа не требуется, каждый запрос расчёта может содержать собственный набор барьеров.
• При оптимизации времени в расчётах могут быть использованы «штрафы на повороты» в зависимости от угла поворота. Таким образом, при правостороннем движении поворот налево будет занимать больше времени, чем поворот направо. Эта особенность позволяет приблизить результаты расчёта к реальным условиям.
• При расчёте зон доступности могут быть использованы сразу несколько центров. Количество их не ограничено и может достигать нескольких сотен, тем самым, например, за один запуск можно получить распределение зон доступности сразу для множества магазинов или логистических центров.
• Полигоны, полученные в процессе расчёта зон доступности, выглядят очень детализированными, в точности повторяя границы пройденных участков дорожной сети. Детализированная граница зон доступности позволяет с большей точностью определять достижимость определённых точек и рассчитывать параметры наложения (например подсчёт демографии, охваченной зоной).
• В расчёте зон доступности из нескольких центров возможен режим, при котором итоговые зоны будут конкурировать, т. е. не будут накладываться друг на друга. В таком случае спорные области наложения будут разделяться между конкурирующими центрами по критерию близости к таким центрам. Алгоритм чем-то похож на построение полигонов Тиссена, только расчёт ведётся по дорожной сети.

Ключевые особенности

Ключевыми особенностями веб-сервиса являются:

• наличие готовых инструментов сетевого анализа, включая:
• поиск кратчайшего маршрута между заданными точками,
• оптимизацию порядка объезда промежуточных точек маршрута,
• расчёт изолированных зон доступности,
• расчёт конкурентных зон доступности;
• возможность использования уже готовых наборов данных для расчёта (индексов), а также построение новых наборов (на заказ) на базе пользовательских данных;
• поддержка операционных систем Linux и Windows Server;
• программное обеспечение TrueDrive разработано на территории РФ и полностью принадлежит российской компании;
• возможность глубокой интеграции с инфраструктурной платформой CoGIS позволяет решать сложные тематические задачи, использующие сетевой анализ, в рамках существующей информационной инфраструктуры.

Технологические возможности

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

Виды оптимизации

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

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

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

 

  

Построенные маршруты по времени и по расстоянию

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

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

Ещё более впечатляющим является вариант использования характеристик, которые определяют аварийность каждого участка дорог с учётом протяжённости сегмента. Такой алгоритм позволит найти самый безопасный маршрут.

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

Способы передвижения

Использование алгоритмов сетевого анализа предполагает «движение» по сети дорог. Но двигаться по дорогам можно разными способами: на легковом автомобиле, грузовом автомобиле, спецтехнике, велосипеде или просто пешком.

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

Для каждого способа передвижения можно задать свою «стоимость проезда» (например, время) для каждого сегмента дорог. Влияние на эту стоимость, например на время проезда по определенному сегменту дороги, может оказывать длина сегмента, качество дорожного покрытия, уклон и другие характеристики.

Способ передвижения задается при каждом запуске алгоритма сетевого анализа. Можно запускать сразу несколько расчётов, используя разные настройки, включая задание типа транспортного средства.

Использование барьеров

После построения индексированного графа дорог по исходным данным фиксируется множество характеристик связности дорог и их параметров. Это позволяет создать вспомогательные структуры данных, при использовании которых существенно увеличивается скорость расчёта. Логический граф дорог на момент создания индексной структуры становится неизменным.

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

Изменение итогового маршрута при добавлении барьера

Барьеры могут быть точечными, линейными или полигональными. Точечные барьеры привязываются к ближайшему сегменту дорог и формируют виртуальный барьер на этом сегменте. Линейный барьер помечает как «не проездные» те сегменты, которые пересекаются с заданной линией. Полигональные барьеры аналогичным образом помечают те сегменты, которые полностью или частично попадают внутрь полигона.

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

Степень «прозрачности» барьера задаётся параметром penalty. Примеры значений:

• -1 – абсолютный барьер (проезд запрещён)
• 0 – мгновенная телепортация (стоимость проезда по сегменту игнорируется)
• 0.5 – скорость передвижения в два раза быстрее
• 1 – барьер отсутствует
• 2 – скорость передвижения в два раза медленнее

Таким образом, задание барьера на дороге может как полностью запретить проезд, так и уменьшить приоритет проезда по заданному сегменту.

Особым случаем является задание параметра penalty в диапазоне от 0 до 1. Значения из этого диапазона позволяют, наоборот, увеличить скорость проезда по сегменту дороги. Такая возможность может быть использована в ситуациях, когда характеристики дороги изменились в лучшую сторону, например поверх щебёночной насыпи положили асфальтовое покрытие.

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

Особенности проезда перекрёстков

Каждый перекрёсток состоит их сходящихся в одной точке нескольких сегментов дорог. Во время движения транспортное средство использует только два сегмента. Это может быть проезд прямо, поворот направо, налево или разворот.

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

Кроме того, по статистике проезд под разными углами занимает разное время проезда перекрёстка. Например, проезд прямо в среднем занимает существенно меньше времени, чем поворот налево, поскольку при повороте требуется существенно снизить скорость и только после проезда перекрёстка можно опять ускориться.

TrueDrive позволяет учесть такие обстоятельства поворотов. Для этого при построении индекса дорожного графа следует указать желаемые параметры замедления в зависимости от углов проезда перекрёстка.

Алгоритм поиска оптимального маршрута

Алгоритм поиска оптимального маршрута предназначен для вычисления маршрута, соединяющего несколько заданных точек остановок. В результате будет построен маршрут, который позволяет за минимальное время/расстояние проехать из начальной точки в конечную, проезжая через все промежуточные точки.

Расчёт оптимального маршрута с промежуточными точками

Порядок промежуточных точек

При задании нескольких точек остановки для расчёта оптимального маршрута существует два режима оптимизации:

• Сохранение порядка промежуточных остановок
• Оптимизация порядка промежуточных остановок.

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

Если выбран режим оптимизации порядка промежуточных точек, то используется алгоритм поиска оптимального маршрута, учитывая все возможные комбинации порядка заданных точек остановок. Нужно учитывать, что расчёт с включенным режимом оптимизации порядка промежуточных точек может выполняться медленнее, чем расчёт с сохранением порядка промежуточных точек.

Иерархия дорог

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

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

Расчёт оптимального маршрута без использования иерархии дорог (5-7 сек)

TrueDrive предлагает режим расчёта оптимального маршрута, при котором используется иерархия дорог. При этом между городами (протяженными участками) используется подграф, состоящий из скоростных дорог, а в небольшом радиусе точек остановки используется полный граф дорог.

Расчёт оптимального маршрута с использованием иерархии дорог (1-1,5 сек)

Режим использования иерархии дорог позволяет существенно сократить время расчёта протяженных маршрутов и обеспечить более ожидаемый результат для путешествий или междугородних перевозок, при которых движение между городами почти всегда происходит по большим магистралям, даже несмотря на возможное существование более оптимального проезда. В зависимости от поставленной задачи и на усмотрение пользователя можно включить или выключить режим учета иерархии дорог для поиска оптимального маршрута.

Алгоритм построения зон транспортной доступности

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

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

Построение зон транспортной доступности (10, 15, 20 мин)

Кольца

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

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

Виды сопоставления зон разных точек

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

• Зоны разных точек независимы друг от друга
• Объединение зоны разных точек
• Конкурентные зоны

  

Независимые зоны, объединение зон, конкурентные зоны

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

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

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

Возможности интеграции

TrueDrive представляет собой программный продукт, с помощью которого можно запустить веб-сервис. Взаимодействие с сервисами TrueDrive может быть реализовано путем прямого сетевого соединения по протоколам HTTP/HTTPS, посредством RESTful.

TrueDrive прекрасно интегрируется в экосистему инфраструктурной платформы CoGIS и поддерживается всеми её клиентами. Это позволяет расширить функциональность геоинформационной системы на базе CoGIS за счет алгоритмов сетевого анализа.

Веб-сервис TrueDrive можно интегрировать в платформу CoGIS следующим образом:

• Использование сервисов TrueDrive напрямую из CoGIS-клиентов.
• Использование функций TrueDrive как составной части GP-моделей в рамках инструментов геообработки на серверной стороне информационной системы.

Внешний TrueDrive API работает по протоколу, совместимому с Network Analyst Server, что позволяет встраивать TrueDrive в информационные системы, имеющие в своей основе ArcGIS Server.

Технологии

Технологии разработки TrueDrive обеспечивают высокую производительность и надежность разработанных решений, не накладывают ограничений на использование и являются кроссплатформенными. В частности, ядро TrueDrive написано на C++, а логика верхнего уровня TrueDrive на .NET Core (C#), ASP.NET Core.

Соответствие политике импортозамещения

Программное обеспечение TrueDrive имеет свидетельство о государственной регистрации программы для ЭВМ №2007612625 от 20.06.2007.

TrueDrive разработано на территории РФ и полностью принадлежит российской компании.

ПО TrueDrive 13.11 включено в реестр отечественного ПО (рег. № 19975 от 13.11.2023 https://reestr.digital.gov.ru/reestr/1931364/).

TrueDrive является частью отечественной инфраструктурной платформы CoGIS.

Программное обеспечение CoGIS внесено в Единый реестр российских программ для электронных вычислительных машин и баз данных (рег. номер ПО 3789 от 16.08.2017, https://reestr.minsvyaz.ru/reestr/114149/).