TrueDrive – программный модуль для проведения сетевого анализа на дорожной сети.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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