УДК 004.421.2

ББК 22.12

DOI 10.24411/2413-046Х-2020-10039

РЕШЕНИЕ ЗАДАЧИ ПОСТРОЕНИЯ ОПТИМАЛЬНОГО МАРШРУТА ДВИЖЕНИЯ ТРАНСПОРТА ПО ПЕРЕСЕЧЕННОЙ МЕСТНОСТИ С ИСПОЛЬЗОВАНИЕМ ГИС

THE PROBLEM OF CONSTRUCTING THE OPTIMAL ROUTE OF TRANSPORT OVER ROUGH TERRAIN WITH GIS USAGE

Жигалов Кирилл Юрьевич, с.н.с., кандидат технически наук, Института проблем управления науки В.А. Трапезникова, Российской Академии наук, Москва, Комплексный научно-исследовательский институт им. Х.И. Ибрагимова Российской академии наук, Грозный

Клочкова Екатерина Николаевна, доцент, Московского университета МВД России имени В.Я. Кикотя

Zhigalov K.Y., KShakalov@mail.ru

Klochkova E.N.

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

Summary. To assess the relevance of integrated solutions for the construction of the route of vehicles on cross-country studied modern foreign and domestic navigation software products presented on the Russian market. Most of the studied navigation systems do not take into account the technical characteristics of vehicles, and do not use the possibility of building a route over rough terrain, reducing the optimization criterion. The aim is to create specialized software solutions designed for developing optimal route of technical means on the basis of available digital maps including a wide range of features moving in the terrain of certain categories of transport, patency rates and efficiency of movement on different terrain. The proposed solution for the improvement of the modern navigation systems.

Ключевые слова: оптимальный маршрут движения, задача построения графа дорог, моделирование

Key words: the optimal route, a task graph construction of roads, modelling

Введение

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

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

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

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

• поиск пункта назначения;
• планирование маршрута;
• редактирование маршрута;
• операции с картой;
• настройка внешнего вида и режима навигации;
• навигация (отображение текущего положения на карте, информирование о следующих маневрах, предупреждение и оповещение о дорожной ситуации); и т.д.

Проведенные исследования показали, что все из рассматриваемых навигационных программ, в общем, решают задачу построения маршрута движения (хотя построенный маршрут не всегда является оптимальным). Основные отличия навигационных программных продуктов заключаются в различном наборе поддерживаемых карт, а как следствие накладываются определенные ограничения на возможности применения ПО. Например, программный продукт iGoPrimo лучше подойдет для построения маршрутов перемещений по дорогам Европы; Прогород, Навител Навигатор, СитиГид – целесообразно использовать в мегаполисах, там, где необходимо учитывать загруженности дорог. Кроме того, можно отметить, что большинство разработчиков создают навигационное программное обеспечение для легкового автотранспорта, не учитывая потребности в передвижения на других видах транспорта (грузовом, специальном транспорте, мотоциклах, велосипедах), а также прокладываемые маршруты движения включают в себя только дороги.

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

Задача построения графов дорог на основе цифровых карт для различных типов транспорта

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

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

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

G: = (V,E), где

V – это множество вершин или узлов,

E – это множество рёбер графа.

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

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

Граф дорог создается по выделенным объектам дорожной сети и представляет собой пользовательскую карту с дугами и узлами. На этапе построения в семантические характеристики дуг и узлов записывается информация о связности сети и атрибуты для решения поисковых задач [3].

Граф дорог и дорожных сооружений создается в виде отдельной пользовательской карты (слоя) без деления на номенклатурные листы. Объекты, описывающие граф дорог, составляют отдельный слой в классификаторе цифровых навигационных планов городов. Граф дорог содержит два основных типа объектов – дуги и узлы.

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

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

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

Пусть имеется:

1) Электронная карта местности (векторная).

Карта местности в общем виде может быть представлена в виде множества К. Данное множество состоит из М графических объектов

K={Q_m), m=1,…M

Определенная картографическая информация закрепляется за каждым объектом (Q_m), который может быть описан следующим образом:

W_m=<N_m(V_k}_M, A_m>, V_k=(x_k, y_k), A_m={a_p}

где N_m – параметр, определяющий принадлежность объекта к одному из классов (лес, гидрография и т.п.);

{V_k} – множество координат (x_k, y_k) объекта Q_m;

A_m – тематическая информация, присоединенная к соответствующему объекту Q_m, элементы a_p которой характеризуют текущее состояние объекта (например, толщина льда).

2) Цифровая модель рельефа местности

где H – высота в точке с координатами (x, y).

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

3) Условия, накладываемые на возможность перемещения по данной местности.

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

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

б) ограничения, связанные с физическими характеристиками местности  (Z_i^Ф). При этом они могут зависеть от времени года, погоды и других природных факторов. Например, непреодолимая в весенний период водная преграда.

Постановка задачи на разработку программного комплекса оптимизации движения

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

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

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

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

Между тем, при анализе возможных маршрутов необходимо использовать более широкий набор данных, а именно:

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

Кроме того, при поиске оптимального маршрута движения необходимо использовать оценки по нескольким факторам, в том числе:

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

С учетом вышесказанного, можно сказать, что необходимо решить задачу поиска оптимального маршрута движения из начальной точки  А{x_A , y _A)|AÎQ_m в конечную B(x_B, y_B)|BÎQ_m, учитывая при построении свойства местности и технические характеристики транспортного средства. Оптимальность маршрута определяется минимизацией пройденного расстояния и энергетических затрат.

Для решения данной задачи требуется провести проектирование и разработку специализированного программного обеспечения (ПО) прокладки маршрута движения технического средства.

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

1. Построение на основе электронной цифровой карты графа дорог, доступных для движения техники, имеющих заданные технические характеристики.  Данный граф должен быть мультизначным, т.е. допускать введение множественных параметров для описания дуг, в частности:
2. протяженности пути в км;
3. коэффициенты проходимости для отдельных транспортных средств, описывающего снижение максимальной скорости движения вследствие низких дорожных характеристик (снег, крутые уклоны, заболоченность и пр.);
4. коэффициент энергозатрат на движение для отдельных транспортных средств, характеризующий увеличение затрат топлива вследствие особенностей этапов движения – уклон или подъемы, глубокий песок, заболоченность и пр.;
5. коэффициенты, которые позволяют учесть влияние на движение транспортного средства свойств пересекаемой местности, а также возможную их зависимость от погодных и климатических условий.   
6. Создание вариантов маршрутов движения.
7. Расчет значения критерия оптимальности для каждого сформированного маршрута движения.
8. Выбор маршрута движения в зависимости от полученных значений критерия, минимизирующего пройденное транспортным средством расстояние и затраты на преодоление данного пути.

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

При оценке проходимости учитывают следующие коэффициенты [4,5]:

• угла скатав направлении предполагаемого движения;
• плотность грунта;
• густота леса (кустарников);
• мощность растительного покрова;
• глубина водной преграды с учетом плотности дна;
• интенсивность гололедных явлений;
• глубина снежного покрова;
• толщина льда.

Решение задачи построения оптимального маршрута движения по пересеченной местности должно предусматривать:

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

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

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

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

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

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

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

Выводы:

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

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

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

ЛИТЕРАТУРА

1. Военная топография в служебно-боевой деятельности оперативных подразделений. / Под ред. Ю.Г. Маслака – М.: Академический проект, 2005.
2. Геоинформатика. В 2 кн. Кн. 1: Учебник для студ. высш. учеб. заведений / Под ред. В.С. Тикунова. – 2-е изд., перераб. и доп. – М. : Издательский центр «Академия», 2008.
3. Дистель Р. Теория графов. – Новосибирск: Издательство института математики, 2012.
4. Жигалов К.Ю. Подготовка техники к использованию в системах автоматизированного управления строительства автодорог//Естественные и технические науки. 2014. №1 (69). С.285-287.
5. Жигалов К.Ю. Автоматизация управления и мониторинга процессов строительства с использованием ГИС систем//Фундаментальные исследования. 2014. № 12-3. С. 492-494.
6. Ильиных В.А., Колесов В.А.. Военная топография: Учебное пособие / В.А.Ильиных, В.А.Колесов. – СПб.: ВКА имени А.Ф.Можайского, 2008.
7. Клочкова Е.Н. Обоснование выбора алгоритма поиска пути решения задач построения маршрута к месту назначения. – М.: Вестник Московского университета МВД России. №5. 2015.