Полунин Сергей молод. Ему всего лишь по состоянию на февраль 2024-го, 34 года. Вместе с тем, в декабре 2023 года он попал в список доверенных лиц Владимира Путина на президентских выборах 2024 года.
Показана возможность применения методов динамического программирования для учета учетом рельефа местности при проектировании транспортной схемы сети дорог.
Ключевые слова: рельеф местности, динамическое программирование, оптимизация
Y.M. Eldeshtejn,
Candidate of technical sciences, professor,
Krasnoyarsk state agrarian University ,O.V. Bolotov,
Candidate of technical sciences, associate professor,
Siberian state technological University,
Krasnoyarsk, Russia
Зона Севера охватывает 70% территории России и представляет собой великую кладовую минеральных и лесных ресурсов, что особенно важно в условиях мирового сырьевого кризиса. В то же время, средняя заселенность северных территорий составляет только около двух человек на 1 кв. км.
Инфраструктура северных территорий, и особенно инфраструктура Крайнего Севера, в целом катастрофически неразвита.
Одним из важнейших тормозов экономического развития Севера является транспортная проблема. Огромные территории значительно удалены от наземных путей сообщения. Водный транспорт – речной и морской – остаётся основным средством связи с «Большой Землёй» ввиду дороговизны воздушного транспорта. Через Северный Морской путь осуществляется подвоз продуктов, бытовых товаров, топлива и многого другого. Навигационный период поставки северного завоза ограничен: он возможен с июня по сентябрь, а на притоках,- только в период весеннего половодья. Поэтому перебои с поставками имеют катастрофические последствия для местных жителей. Отсутствие наземного транспорта затрудняет сообщение между населёнными пунктами регионов, усложняет доставку работающих вахтовым методом, замедляет обмен трудовыми и иными ресурсами с «Большой Землёй».
Для построения оптимальной транспортной схемы разработан целый ряд алгоритмов, таких, как алгоритм Дейкстры, алгоритм Беллмана-Форда, алгоритм Флойда-Уоршела, и целый ряд других [1, 2]. Они основаны на использовании понятия минимального остовного дерева (или минимального покрывающего дерева). Эти алгоритмы были использованы и эффективно реализованы нами при разработке методики оптимизации транспортных схем освоения лесосырьевых баз [3, 4, 5, 6].
Данная задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют точки на карте, рёбра — это линии между двумя точками по которой можно проложить прямую дорогу, а вес ребра равен стоимости строительства соответствующей дороги.
Минимальное остовное дерево в связанном взвешенном неориентированном графе - это остовное дерево, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
На рисунке 1 приведен пример транспортной схемы, построенный с применением одного из вышеуказанных алгоритмов на условной карте местности.
Недостатком всех этих алгоритмов является то, что все дороги там размечаются по прямым линиям. В данном примере одна ветка проходит через заболоченную местность, где затраты на строительство значительно выше, а вторая прямо через озеро, что вообще недопустимо при строительстве дорог круглогодового действия. Для решения этой проблемы можно рассмотреть два варианта:
1 - введение дополнительной обязательной вершины остовного дерева с нулевой стоимостью, так как это показано на рисунке пунктирной линией;
2 - определение
оптимальной формы трассы с помощью метода динамического программирования.
Рисунок 1. Оптимальная транспортная схема
Недостатком первого варианта является то, что положение этой вспомогательной точки объективно ничем не обосновано, а, следовательно, едва ли оптимально.
Как известно, задачи динамического программирования обладают следующими свойствами:
1 – она может быть разбита на этапы (в данном случае она разбивается на этапы в пространстве);
2 – регрессивность решения, т.е. процесс решения разворачивается от конца к началу;
3 – аддитивность решения, т.е. решение всей задачи и значение целевой функции (в данном случае это минимум затрат на прокладку дороги) получается путем суммирования результатов решения на отдельных этапах.
Рассматриваемая задача обладает всеми этими свойствами.
На рисунке 2 в координатной сетке 1х1 км. приведено решение задачи огибания озера методом динамического программирования.
Вдоль проблемной ветки дороги, изображенной пунктирной стрелкой, выделена область определенной ширины (в данном примере эта область составляет около двух километров). На каждом ребре координатной сетке и на диагоналях указаны затраты на прокладку одного километра дороги в некоторых условных единицах. Эти затраты определяются рельефом, состоянием грунта и пр.
В этом примере принято пять возможных направлений прокладки дороги: С, Ю, В, С-В, Ю-В. На границах запретной зоны (в данном случае озера) вместо реальной стоимости прокладки дороги поставлен запрет в форме М – сколь угодно большого числа, большего любого наперед заданного.
Рисунок 2. Оптимизация прокладки дороги методом динамического программирования
Оптимальное решение выделено толстыми стрелками. Минимальные затраты на строительство дороги составили 47 у.е., что отражено в клетке соответствующей началу участка (началу пунктирной стрелки).
Очевидно, что метод динамического программирования позволяет учитывать природно–географические особенности местности и решать проблемы, связанные с оптимизацией транспортной схемы.
Библиографический список
1 Кормен, Т., Лейзерсон, Ч., Штайн, К. Минимальные остовные деревья// Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова.— 2-е изд. — М.: Вильямс, 2005.— 1296 с.
2 Кормен, Т. Х., Лейзерсон, Ч. И., Ривест, Р. Л., Штайн, К. Алгоритмы: построение и анализ, 3-е издание = Introduction to Algorithms, Third Edition. — М.: «Вильямс», 2013. — 1328 с.
3 Ельдештейн, Ю.М., Болотов, О.В., Болотова, А.С. Комплексное решение задач прогнозирования запасов древесины, оптимизации величины расчетной лесосеки и дорожно-транспортной сети / Ю. М. Ельдештейн, О.В. Болотов, А. С. Болотова // Вестник СибГТУ. – Красноярск, 2001. – С. 52-57.
4 Ельдештейн, Ю.М. «Введение в логистику»/ Ю.М. Ельдештейн,- Красноярск, КГАУ, 2015. - 392 с.
5 Свидетельство о государственной регистрации программ для ЭВМ №2008614147 / Ю.М. Ельдештейн, О.В. Болотов, Р.А. Черных; заявитель и патентообладатель СибГТУ.- Заявка № 2008612990, заявл. 02.07.2008, зарегистрировано в Реестре программ для ЭВМ 29.08.2008.
6
Свидетельство
о государственной регистрации программ для ЭВМ №2009610561 / О.В. Болотов, Ю.М. Ельдештейн, Р.А. Черных;
заявитель и патентообладатель СибГТУ. - Заявка № 2008615673, заявл. 03.12.2008,
зарегистрировано в Реестре программ для ЭВМ 23.01.2009.
ИСТОЧНИК: Логистика - евразийский мост: материалы 10-й Междунар. научн.-практ. конф. (14-16 мая 2015 г., г.Красноярск); Краснояр. гос. аграрн. ун-т, - Красноярск, 2015. - 582 с. - с. 98-101
