способ прокладывания маршрута передвижения на пересеченной местности

Формула изобретения

Способ прокладывания маршрута передвижения на пересеченной местности, включающий загрузку электронной карты местности, определение точек старта А(х_A, у_A) и финиша В(х _B, у_B), отличающийся тем, что анализируют проходимость местности с помощью введенных коэффициентов, определяют тип и тактико-технические характеристики транспортного средства, предназначенного для перемещения по местности, определяют непроходимые для выбранного транспортного средства зоны административного Z_i и физического характера, отображают на электронной карте непроходимые зоны, исключают из расчетов непроходимые зоны , сравнивают область проходимости с непроходимыми зонами Z_i и , если область проходимости , то определяют новые непроходимые зоны Z_i и , если область проходимости , то формируют возможные маршруты движения на карте K={Q _m} для выбранного транспортного средства, при этом определяют наличие матрицы высот для K={Q_m}, если матрица высот отсутствует, то определяют минимальное расстояние между изолиниями, если матрица высот присутствует, то определяют шаг матрицы высот, выбирают размер сетки d, формируют на K={Q_m} двухмерную сетку с размером d, формируют на K={Q_m} трехмерную сетку с учетом матрицы высот , формируют на K={Q_m} элементарные ячейки, рассчитывают приведенный вес для каждого участка маршрута W_r, при этом производят оценку участка пути с помощью вычисления частных коэффициентов k_i, сравнивают k_i с единицей, если k_i 1, определяют непроходимые зоны Z₁ и , если k_i 1, производят расчет обобщенного коэффициента проходимости для участка пути производят расчет длины участка пути , производят расчет приведенного веса дуги W_r графа, определяют затраты на границах участка местности g ₁₂=(g₁+g₂)/2, производят расчет рационального маршрута для выбранного транспортного средства при минимизации длины пути и энергетических ресурсов с использованием алгоритма Дейкстры.

Описание изобретения к патенту

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

Известен способ прокладывания маршрутов движения на местности с использованием бумажных карт [Военная топография. Под редакцией генерал-лейтенанта технических войск А.С.Николаева. // М.: Военное изд-во, 1977 г.], заключающийся в прокладывании пользователем маршрутов и измерении их длины при помощи циркуля, курвиметра и линейки.

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

Известны способы определения кратчайшего маршрута движения (патенты США № 4408192 от 20.11.1984 г., НКИ 340/995; № 5486822 от 23.01.1986 г., НКИ 340/995, G08G 1/123), в которых предложено использовать находящуюся в памяти бортовой ЭВМ карту дорог города (цифровую векторную карту), информация о точке отправления и точке назначения вводятся в ЭВМ водителем, а затем рассчитывается кратчайший путь.

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

Известен способ, реализованный на устройстве выбора оптимального маршрута маневра (патент RU № 2045773, МПК G06F 17/16 от 19.10.1995 г.), в котором предложено управление движением разнотипных транспортных средств по автодорожной сети с различной проходимостью участков дорог. Устройство обеспечивает автоматизированный выбор оптимального маршрута движения для транспортного средства на пересеченной местности при минимизации расхода горюче-смазочных материалов.

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

Наиболее близким по своей сущности к заявляемому изобретению является способ прокладывания оптимального движения мобильных объектов по пересеченной местности [Дорогов А.Ю., Лесных В.Ю., Раков В.И., Титов Г.С. Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети. // Санкт-петербургский государственный электротехнический университет, 2006 г.], включающий загрузку электронной карты местности, определение точки старта A(x_A, y_A) и финиша B(x_B, y _B), отображение непроходимых зон на электронной карте местности, формирование участка местности со стороной d, определение координат участка местности, определение затрат для каждого участка местности g_i определение затрат на границах участков местности:

,

определение затрат на маршруте:

,

где N - число точек маршрута, построение маршрута с помощью шаговых операций выбора направления дальнейшего движения C_k, управление всей операцией:

нахождение оптимальных маршрутов.

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

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

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

Цель достигается тем, что в известном способе, включающем загрузку электронной карты местности, определение точек старта A(x_A, y _A) и финиша B(x_B, y_B), согласно изобретению анализируют проходимость местности с помощью введенных коэффициентов, определяют тип и тактико-технические характеристики транспортного средства, предназначенного для перемещения по местности, определяют непроходимые, для выбранного транспортного средства, зоны административного Z_i и физического характера, отображают на электронной карте непроходимые зоны, исключают из расчетов непроходимые зоны сравнивают область проходимости Q с непроходимыми зонами Z_i и если область проходимости то определяют новые непроходимые зоны Z_i и если область проходимости то формируют возможные маршруты движения на карте для выбранного транспортного средства, при этом определяют наличие матрицы высот для карты местности , если матрица высот отсутствует, то определяют минимальное расстояние между изолиниями, если матрица высот присутствует, то определяют шаг матрицы высот, выбирают размер сетки d, формируют на двухмерную сетку с размером d, формируют на трехмерную сетку с учетом матрицы высот , формируют на элементарные ячейки, рассчитывают приведенный вес для каждого участка маршрута W_r, при этом производят оценку участка пути с помощью вычисления частных коэффициентов k _i, сравнивают k_i, с единицей, если k_i 1, то определяют непроходимые зоны Z_i и , если k_i 1, то производят расчет обобщенного коэффициента проходимости для участка пути , производят расчет длины участка пути производят расчет приведенного веса дуги W_r графа, определяют затраты на границах участков местности , производят расчет рационального маршрута для выбранного транспортного средства при минимизации длины пути и энергетических ресурсов с использованием алгоритма Дейкстры.

Сопоставительный анализ технического решения со способом, выбранным в качестве прототипа, показывает, что заявляемый способ отличается новыми операциями, такими как, анализ проходимости местности с помощью введенных коэффициентов, определение типа и тактико-технических характеристик транспортного средства, предназначенного для перемещения по пересеченной местности, определение непроходимых для выбранного транспортного средства зон административного Z_i и физического характера, исключение из расчетов непроходимых зон , сравнение области проходимости Q с непроходимыми зонами Z_i и , если область проходимости то определяют новые непроходимые зоны Z_i и если область проходимости то формируют возможные маршруты движения на электронной карте для выбранного транспортного средства, при этом определяют наличие матрицы высот для , если матрица высот отсутствует, то определяют минимальное расстояние между изолиниями, если матрица высот присутствует, то определяют шаг матрицы высот, производят выбор размера сетки d, формируют на двухмерную сетку с размером d, формируют на трехмерную сетку с учетом матрицы высот , формируют на элементарные ячейки, производят расчет приведенного веса для каждого участка маршрута W_r, при этом производят оценку участка пути с помощью вычисления частных коэффициентов k_i, сравнивают k_i с единицей, если k _i 1, то определяют непроходимые зоны Z_i и , если k_i 1, то производят расчет обобщенного коэффициента проходимости для участка пути , расчет длины участка пути , расчет приведенного веса дуги W_r графа, расчет рационального маршрута для выбранного транспортного средства при минимизации длины пути и энергетических ресурсов с использованием алгоритма Дейкстры.

Таким образом, заявляемое техническое решение соответствует критерию изобретения «новизна».

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

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

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

Таким образом, изобретение соответствует критерию «промышленная применимость».

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

На фиг.2 - блок-схема алгоритма формирования элементарных ячеек на цифровых векторных картах.

На фиг.3 - блок-схема алгоритма определения критерия затрат пути.

На фиг.4 - структурная схема прокладывания маршрута.

На фиг.5 - схема элементарного участка.

Способ включает следующие операции:

- загрузка электронной векторной карты;

- определение точки старта А(x_A, y _A) и финиша B(x_B, y_B);

- анализ проходимости местности с помощью введенных коэффициентов;

- определение типа и тактико-технических характеристик транспортного средства, предназначенного для перемещения по местности;

- определение непроходимых, для выбранного транспортного средства, зон административного Z_i и физического характера;

- отображение на электронной карте непроходимых зон;

- исключение из расчетов непроходимых зон ;

- сравнение области проходимости Q с непроходимыми зонами Z_i и ,

- формирование возможных маршрутов движения на карте для выбранного транспортного средства;

- определение наличия матрицы высот для ,

- определение шага матрицы высот;

- определение минимального расстояния между изолиниями;

- выбор размера сетки d;

- формирование на двухмерной сетки с размером d;

- формирование на трехмерной сетки с учетом матрицы высот ;

- формирование на элементарных ячеек;

- расчет приведенного веса для каждого участка маршрута W_r,

- оценка участка пути с помощью вычисления частных коэффициентов k_i;

- сравнение k_i с единицей;

- расчет обобщенного коэффициента проходимости для участка пути ;

- расчет длины участка пути ;

- расчет приведенного веса дуги W _r графа;

- определение затрат на границах участков местности

;

- расчет рационального маршрута с использованием алгоритма Дейкстры.

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

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

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

В данном способе учитывается:

- тактико-технические характеристики средства перемещения, предназначенного для движения по выбранному маршруту;

- тактические свойства местности в сочетании с сезонными климатическими условиями;

- длина пути и энергетические ресурсы, затрачиваемые средством перемещения на преодоление выбранного маршрута.

Задача навигации может быть сформулирована следующим образом.

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

1) Электронная векторная карта участка местности, которая может быть представлена в виде множества К, состоящего из М графических объектов

С каждым объектом Q_m связана определенная картографическая и тематическая информация. Тогда каждый объект множества К может быть представлен в виде:

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

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

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

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

,

которая позволяет для каждой точки с координатами (x, y) определить соответствующую ей высоту H.

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

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

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

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

Решаемые способом задачи следующие:

- оценка влияния тактических свойств местности в сочетании с сезонными климатическими условиями на передвижение конкретного средства перемещения;

- формирование возможных маршрутов движения;

- определение критерия для оценки затрачиваемых средством перемещения ресурсов, при преодолении сформированных маршрутов;

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

Проходимость местности определяется ее пересеченностью. Местность с оврагами, крутыми скатами и обрывами, реками и заболоченными участками, с большими площадями лесных массивов в сочетании с сезонными явлениями (дождь, снег и т.п.) существенно затрудняют движение по ней средств перемещения [Военная топография в служебно-боевой деятельности оперативных подразделений. Под редакцией Ю.Г.Маслака // М.: Академический проект, 2005 г.].

Проходимость местности можно оценить с помощью следующих коэффициентов: угла ската в направлении предполагаемого движения; плотность грунта ; густоту леса (кустарников) R; мощность растительного покрова M_R; глубину водной преграды с учетом плотности дна Г_B; интенсивность гололедных явлений E_Г ; глубину снежного покрова h_С, толщину льда Т _Л.

Учитывая тактико-технические характеристики (ТТХ) средств перемещения [Военная топография. Под редакцией генерал-лейтенанта технических войск А.С.Николаева. // М.: Военное изд-во, 1977 г.], введем для них следующие коэффициенты проходимости:

- преодоление скатов при сухом твердом грунте _d в направлении предполагаемого движения. Для автомобилей повышенной проходимости _d 30°, для гусеничных тягачей с прицепами _d 25°, для танков и самоходных артиллерийских установок (САУ) _d 40°, для пешеходов значение _d не учитывается, т.к. практически любые скаты для пешеходов являются преодолимыми;

- проходимость по асфальтовым и грунтовым поверхностям _n, имеющих различную плотность. Автомобильные дороги с твердым покрытием допускают движение транспорта в любую погоду. При: _n=0 - техника, способная перемещаться только по асфальту; _n=1 - техника, способная перемещаться по супесчаной почве в сухую погоду; _n=2 - техника, способная перемещаться по песчаной почве в сухую погоду; _n=3 - техника, способная перемещаться по суглинистой почве или чернозему при промокании грунта до 5 см, _n=4 - техника, способная перемещаться по суглинистой почве или чернозему при промокании грунта до 10 см, _n=5 - техника, способная перемещаться по грунту при его промокании более 10 см.

При влажности грунта 50% (в обычном состоянии грунты имеют влажность 20%) преодолеваемые скаты меньше в 2 раза. [В.А.Ильиных, В.А.Колесов. Военная топография: Учебное пособие / В.А.Ильиных, В.А.Колесов. - СПб.: ВКА имени А.Ф.Можайского, 2008. - 193 с.]:

- проходимость по снежному покрову с учетом его глубины h_max;

- предельная глубина водной преграды Г_max при средней плотности грунта (глина, суглинок), без герметизации двигателя. Для автомобилей весом до 2 т Г_max 0,6 м, для автомобилей весом до 5 т Г_max 0,9 м, для гусеничных артиллерийских тягачей Г_max 1 м; для средних танков Г_max 1,2 м, для тяжелых танков Г_max 1,5 м, для подразделений в пешем порядке Г_max 1 м;

- требуемая толщина льда T_min . Для автомобилей весом 2-4 т T_min 16 см, для автомобилей весом 6-8 т T_min 27 см, для автомобилей весом до 10 т Т_min 35 см, для средних танков T_min 50 см, для тяжелых танков Т_min 70 см, для пехоты Т_min 4 см;

- густота леса (кустарников) R _max. Для танков, бронетранспортеров и автомобилей повышенной проходимости лес является проходимым в том случае, если среднее расстоянии между деревьями более 6 м и отсутствует подлесок. Лес, со средним расстоянием между деревьями [3,5] м, толщиной деревьев менее 20 см и порослью, проходим для танков с валкой деревьев. Лес, проходимый для танков на ровной местности, на скатах крутизной более 10° становится труднопроходимым.

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

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

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

- формирование графа на множестве ЭУ, оценку возможных путей на ЭУ (ребер графа) критерием, учет особенностей их рельефа, физических свойств местности и ТТХ средства перемещения;

- построение маршрута следования средства перемещения и отображение его в виде линии на электронной векторной карте местности.

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

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

Вес дуги зависит от:

- длины самой дуги;

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

Анализ существующих алгоритмов поиска пути (алгоритм поиска в ширину, алгоритм Форда-Беллмана, алгоритм Дейкстры и алгоритм Флойда) показал, что для решения задачи маршрутизации наиболее пригодным является алгоритм Дейкстры [Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. // Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001 г.; Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990 г.; Шапорев С.Д. Математическая логика. Курс лекций и практических занятий. // М.: Наука, 2000 г.]. Этот алгоритм находит в заданном графе единственный путь, обладающий минимальным весом. В отличие от алгоритма поиска в ширину, алгоритм Дейкстры работает не только дугами графа, вес которых равен единице. Алгоритм Форда-Беллмана работает с дугами, имеющими отрицательный вес. В нашем случае вес дуг не может быть отрицательным, т.к. учитываемые в методике длина пути и затрачиваемые энергетические ресурсы не могут быть отрицательными. Алгоритм Флойда требует больших вычислительных операций. Поэтому для дальнейших расчетов используется алгоритм Дейкстры.

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

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

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

Рельеф местности является основным фактором, влияющим на движение средства перемещения, поскольку одна из его характеристик - крутизна ската в направление движения, оказывает влияние при учете многих физических свойств местности. Очевидно, чем ближе текущее значение угла , характеризующего крутизну ската к максимальному углу подъема средства перемещения _d, тем интенсивнее расход энергетических ресурсов на передвижение, поэтому для расчета коэффициента k₁ , учитывающего крутизну ската, предлагается выражение:

Значение угла ската для транспортных средств не должно превышать 40°, поскольку, согласно [Военная топография. Под редакцией генерал-лейтенанта технических войск А.С.Николаева. // М.: Военное изд-во, 1977 г.], максимально преодолимая крутизна скатов (для танков и САУ) не превосходит 40°.

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

Интенсивность проявления гололедных явлений Е_Г в выражении (5) задается на качественном уровне и соответствует 0 - отсутствию, 1 - слабому, 2 - среднему, 3 - сильному проявлению гололедных явлений.

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

Плотность грунта в выражении (3) задается на качественном уровне {0, 1, 2, 3, 4, 5}. При этом: 1 соответствует супесчаной почве в сухую погоду, 2 - песчаной почве в сухую погоду, 3 - суглинистой почве или чернозему при промокании до 5 см (средний дождь), 4 - суглинистой почве или чернозему при промокании до 10 см (сильный дождь, ливень), 5 - состоянию почвы в осеннюю, весеннюю распутицу (промокание более 10 см).

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

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

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

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

Характеристика леса R в выражении (7) задается на качественном уровне R {1, 2, 3} и соответствует: 1 - лес, проходимый для транспортных средств (среднее расстояние между деревьями более 6 м, отсутствует подлесок); 2 - лес, проходимый для танков с валкой деревьев, (среднее расстояние между деревьями [3-5 м], толщина деревьев менее 20 см, мелкая поросль); 3 - лес, непроходимый для транспортных средств (среднее расстояние между деревьями менее 3 м, толщина деревьев более 20 см, поросль, бурелом). Для пешеходов любой лес считается проходимым.

Коэффициент k₈ , характеризующий проходимость в зависимости от мощности растительного покрова. Этот коэффициент сильно коррелирует с плотностью грунта (погодными условиями) и определяется из выражения

Мощность растительного покрова М _R в выражении (8) задается на качественном уровне М _R {0, 1, 2} и соответствует: 0 - густая низкая растительность (дерн); 1 - не высокая растительность (ниже 50 см, степь); 2 - высокая растительность (выше 50 см, сельхозугодия).

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

Рассмотрим основные шаги рассматриваемого способа:

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

Области проходимости для средства перемещения формируются из объектов Эти объекты образуют множество , , К^d К. Области, не вошедшие в К^d, - это ограничения административного Z_i и физического Z характера.

Значение обобщенного коэффициента проходимости для участка пути рассчитывается по формуле:

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

Вершины четырехугольника (они же вершины формируемого графа) характеризуются координатами (x, y, h); значения (x, y) определяются построением сетки, а значения высоты h - с помощью цифровой модели рельефа. Стороны четырехугольника и его диагонали (они же предполагаемые дуги формируемого графа) в общем случае будут иметь различную длину и разную сложность прохождения. Сложность прохождения обусловлена характером рельефа в сочетании с физическими свойствами местности на оцениваемый момент времени. Таким образом, для множества К ^d сформирована условная геометрическая поверхность из ЭУ, каждый из которых удовлетворяет ограничениям на проходимость без учета рельефа (эта поверхность и все построения на ней используются только для расчетов и не отображаются на карте). На этой поверхности предлагается строить граф возможных путей, удовлетворяющий условиям алгоритма Дейкстры и условиям задачи маршрутизации.

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

- вершинами графа являются узловые точки ЭУ - {1, 2, 3, 4};

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

Сначала для оцениваемой дуги r_ij определяется возможность передвижения в зависимости от рельефа. Для этого рассчитывается значение угла ската в оцениваемом направлении (см. фиг.5) по формуле:

При этом положительный знак угла ската указывает на подъем, а отрицательный - на спуск.

Рассчитанное значение угла ската сравнивается с предельно-допустимым значением . Если угол превышает допустимый, то вес дуги соответствует бесконечности, а данное направление (дуга) вычеркивается из общего графа.

Если значение угла лежит в допустимых пределах, то для этого направления (дуги):

- рассчитываются его фактическая длина d_Фij по пространственным координатам соответствующих вершин ЭУ с помощью формулы [Александров П.С. Лекции по аналитической геометрии. - М.: Наука, 1968 г.]:

- рассчитываются частные коэффициенты k_i.

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

В выражениях (13)-(14) нижние индексы i, j - номера вершин ЭУ в оцениваемом направлении движения от i к j.

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

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

Таким образом, на исходном множестве объектов К - электронной карте, сформирован двухмерный граф с множеством вершин и дуг разного веса. Множество вершин представляют узлы сетки (вершины ЭУ) с координатами (x, y), не принадлежащие ограничениям запрета на передвижение. Дуги графа характеризуют возможность передвижения из одной вершины в другую с учетом накладываемых ограничений на передвижение. Каждая дуга обладает весом. Вес дуги положителен и включает в обобщенной форме длину пути и энергетические ресурсы. Сформированный граф удовлетворяет условиям задачи и условиям работы алгоритма Дейкстры.

4. В результате использования алгоритма Дейксты формируется непрерывная последовательность вершин ЭУ, примыкающих друг к другу с началом в точке А и концом в точке В; суммарный вес дуг, соединяющих соседние вершины, будет минимальным. Это последовательность, с точки зрения длины пути и энергетических затрат, представляет собой рациональный маршрут состоящий из К_M вершин графа, проложенный на карте из пункта А в пункт В, который отображается в виде линии на электронной карте, что является искомым решением поставленной задачи.

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