УДК 697.245

ВЫБОР ОПТИМАЛЬНЫХ ТРАСС ПРОКЛАДКИ ИНЖЕНЕРНЫХ СЕТЕЙ С НАИМЕНЬШЕЙ СТОИМОСТЬЮ

Кузнецов Роман Николаевич1, Горских Алексей Александрович2, Глазкова Светлана Юрьевна3
1Воронежский государственный архитектурно-строительный университет, доцент кафедры теплогазоснабжения и нефтегазового дела
2Пензенский государственный университет архитектуры и строительства, старший преподаватель кафедры экономики, организации и управления производством
3Пензенский государственный университет архитектуры и строительства, старший преподаватель кафедры экономики, организации и управления производством

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

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


SELECTION OF OPTIMAL ROUTING OF ENGINEERING NETWORKS WITH THE LOWEST COST

Kuznecov Roman Nikolaevich1, Gorskih Aleksej Aleksandrovich2, Glazkova Svetlana Jurevna3
1Voronezh State University of Architecture and Civil Engineering, assistant professor of the department of heat and oil and gas business
2Penza state university of architecture and construction, senior lecturer in economics, organization and management of production
3Penza state university of architecture and construction, senior lecturer in economics, organization and management of production

Abstract
Investigated the cost calculation model surfaces. Method is proposed to take into account the terrain and other factors in the trace route of engineering networks, allows you to build an anisotropic surface of the accumulated value, taking into account the direction of laying of utilities.

Keywords: cost surface, engineering network routing, optimal routing


Библиографическая ссылка на статью:
Кузнецов Р.Н., Горских А.А., Глазкова С.Ю. Выбор оптимальных трасс прокладки инженерных сетей с наименьшей стоимостью // Современная техника и технологии. 2014. № 8 [Электронный ресурс]. URL: http://technology.snauka.ru/2014/08/4280 (дата обращения: 28.05.2017).

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

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

1) Построение поверхности накопленной стоимости из поверхности стоимости;

2) Трассировка оптимального маршрута от исходной точки до конечной точки по поверхности накопленной стоимости.

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

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

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

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

Для расчета изотропной стоимости для варианта «шаблона ферзя» использовались следующие уравнения:

накопленная стоимость по четырем прямым направлениям:


где i принимает значения 2, 4, 5 и 7; MAo — накопленная стоимость движения до ячейки O; Mo и Mi — стоимости движения по отдельным ячейкам O и ячейке с индексом i соответственно; MAoi — накопленная стоимость движения от ячейки O до ячейки с индексом i; а — размер ячейки.

Накопленная стоимость при движении по диагоналям:


где i принимает значения 1, 3, 6 и 8.

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

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

Для расчета пространственных расстояний использовались следующие уравнения. Расстояния для четырех прямых направлений:


где i принимает значения 2, 4, 5 и 7; Hi — длина отрезка; а — горизонтальный размер ячейки сетки.

Расстояния для четырех диагоналей:


где i принимает значения 1, 3, 6 и 8.

Стоимость движения через ячейку сетки зависит от угла наклона. Назначая веса в соответствии с углами склонов, накопленную стоимость можно рассчитать по следующим уравнениям:

для четырех прямых соединений:


где i принимает значения 2, 4, 5 и 7; MAoi — накопленная стоимость движения от ячейки O до ячейки с индексом i; Mo, Mi — изотропные стоимости ячейки O и ячейки с индексом i соответственно; MAo — накопленная стоимость движения до ячейки O; Hi — высота ландшафта; а — горизонтальный размер ячейки; у — весовой коэффициент уклона.

Для четырех диагональных соединений:


где i принимает значения 1, 3, 6 и 8.

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

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

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


Библиографический список
  1. Бородавкин П.П. Подземные магистральные трубопроводы (проектирование и строительство)/ П.П. Бородавкин -М.: Недра, 1982.-384с.
  2. Горбань А.Н. Обучение нейронных сетей / А.Н. Горбань. М.: Изд. СССР-США СП “ParaGraph”, 1990. -160 с.
  3. Кристофидес Н. Теория графов. Алгоритмический подход / Н.Кристофидес – М.: Мир, 1978.-432с.
  4. Курейчик В.М. Генетические алгоритмы и их применение -2-е изд., доп./ В.М. Курейчик -Таганрог: Изд-во ТРТУ, 2002.-242с.


Все статьи автора «ALEKSEY-GORSKIH»


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: