Содержание

Введение 1. Актуальность темы 2. Цель и задачи исследования, планируемые результаты 3. Современное состояние проблемы 3.1 Анализ и сравнение существующих методов построение оптимального маршрута прокладки газопровода 3.2 Анализ и сравнение реализованных программных средств построение оптимального маршрута прокладки газопровода 4. Постановка математической модели Выводы Список источников

Введение

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

1. Актуальность темы

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

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

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

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

2. Цель и задачи исследования, планируемые результаты

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

Для достижения поставленной цели, необходимо выполнить следующие задачи:

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

3. Современное состояние проблемы

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

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

3.1 Анализ и сравнение существующих методов построение оптимального маршрута прокладки газопровода

Локальный поиск (оптимизация)

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

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

Эвристические методы вставок

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

• метод ближайшего соседа (Nearest Neighbor);
• метод ближайшего города (Nearest Town);
• метод самого дешевого включения (Most Cheap Inclusion);
• метод минимального остовного дерева (Minimum Spanning Tree).

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

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

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

Метод Кларка-Райта

Метод Кларка-Райта был разработан учеными из Британии, Г. Кларком и Дж. В. Райтом. Метод Кларка-Райт является одним из наиболее часто применяемых эвристических методов, используемых для поиска решений транспортной задачи. Данный метод относится к числу итерационных, приближенных методов. Чаще всего этот метод используют для решения транспортной задачи при помощи компьютеров. Для того, чтобы оценить операцию слияния двух маршрутов, введен термин выигрыш. Мера, на которую уменьшается стоимость при комбинировании двух маршрутов в один маршрут, называется выигрыш. Масштабируемость, гибкость и простота являются достоинствами метода Кларка Райта, также погрешность решения не превосходит 5-10%. Ввиду того, что алгоритм имеет жадный характер, полученные решения уступают решениям, полученным более сложным алгоритмом. В задачах со многими ограничениями после нескольких первых итераций вероятность слияний маршрутов может сильно уменьшится, вследствие чего теряется возможность контроля количества маршрутов [4].

3.2 Анализ и сравнение реализованных программных средств построение оптимального маршрута прокладки газопровода

На сегодняшний день реализованных программных продуктов построения оптимального маршрута прокладки газопровода не существует. Однако, данная система разрабатывалась на основе муравьиного алгоритма, который реализован в таки программных средствах: Maxoptra, Zig-Zag, Муравьиная логистика.

Maxoptra

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

Zig-Zag

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

Муравьиная логистика

Программа автоматизации транспортной логистики - это удобный инструмент логиста и помощник руководителя в управлении предприятием. Делает процесс планирования маршрутов удобным и эффективным [5].

4. Постановка математической модели

Выбор проекта прокладки газопровода предлагается выполнять в 2 этапа.

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

Для решения задачи поиска минимального по стоимости работ маршрута, была предложена модель в виде графа, узлы которого это газорегуляторные установки (ГРУ), а дуги между узлами – это стоимость прокладки газопровода с учетом местного ландшафта, то есть, стоимость строительных работ на участке С_ij (см. рис 1).

Инженер ставит предполагаемые точки расположения ГРУ (узлы графа). Для этого он использует данные, которые в какой-либо мере зависят от положения будущего газопровода и природных условий, в которых он может оказаться:

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

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

Затем с помощью классического муравьиного алгоритма вычисляется маршрут минимальный по стоимости работ [6].

Пусть муравей находится в узле i , а узел j – это один из узлов, доступных для перехода: j∈S_i . Обозначим вес ребра, соединяющего узлы i и j , как w_ij , а интенсивность феромона на нем – как t_ij . Тогда вероятность перехода муравья из i в j будет равна:

где α и β – это регулируемые параметры, определяющие важность составляющих (веса ребра и уровня феромонов) при выборе пути. Очевидно, что при α=0 алгоритм превращается в классический жадный алгоритм, а при β=0 он быстро сойдется к некоторому субоптимальному решению. Выбор правильного соотношения параметров является предметом исследований, и в общем случае производится на основании опыта.

После того, как муравей успешно проходит маршрут, он оставляет на всех пройденных ребрах след, обратно пропорциональный стоимости пройденного пути:

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

Математически это можно представить как:

Графически это можно представить как:

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

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

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

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

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

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

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

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

- для сетей среднего и высокого давлений по формуле

где

P_н – абсолютное давление в начале газопровода, МПа;

P_к – абсолютное давление в конце газопровода, МПа;

P₀ =0,101325 МПа;

λ – коэффициент гидравлического трения;

l – расчетная длина газопровода постоянного диаметра, м;

d – внутренний диаметр газопровода, см;

ρ₀ – плотность газа при нормальных условиях, кг/м;

Q₀ – расход газа, м/ч, при нормальных условиях;

- для сетей низкого давления по формуле

где

P_н – давление в начале газопровода, Па;

P_к – давление в конце газопровода, Па;

λ ,l ,d ,ρ₀ ,Q₀ – обозначения те же, что и в формуле (5).

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

где ν – коэффициент кинематической вязкости газа, м²/с, при нормальных условиях;

Q₀ ,d – обозначения те же, что и в формуле (5), и гидравлической гладкости внутренней стенки газопровода, определяемой по условию (8),

где Re – число Рейнольдса;

n – эквивалентная абсолютная шероховатость внутренней поверхности стенки трубы, принимаемая равной для новых стальных – 0,01 см, для бывших в эксплуатации стальных – 0,1 см, для полиэтиленовых независимо от времени эксплуатации – 0,0007 см;

d – обозначение то же, что и в формуле (5).

В зависимости от значения Re коэффициент гидравлического трения λ определяется:

- для ламинарного режима движения газа 2000

- для критического режима движения газа Re =2000-4000

- при Re > 4000 - в зависимости от выполнения условия (8);

- для гидравлически гладкой стенки (неравенство (8) справедливо):

- при 4000 < Re < 100000 по формуле

- при Re >100000

- для шероховатых стенок (неравенство (8) несправедливо) при Re > 4000

где n – обозначение то же, что и в формуле (8);

d – обозначение то же, что и в формуле (5).

Используя формулы гидравлического расчета, мы получаем расчетные потери давления в газопроводах для труб разного диаметра. Трубы изготавливаются из разного материала (сталь или пластмасса), что влияет на их стоимость, которая также зависит и от диаметра трубы [8].

В итоге получаем задачу принятия решения с двумя критериями:

• С₁ – минимальная суммарная стоимость труб разного типа и диаметра;
• С₂ – минимальные суммарные потери давления в газопроводе.

Любая задача принятия решения требует определения перечня альтернатив, и получения матрицы полезностей, оценивающей альтернативы по каждому критерию. В качестве альтернатив предлагаются варианты использования труб разного типа и диаметра для прокладки трубопровода на выбранном маршруте. При этом трубы разного типа и разного диаметра можно использовать на каждом отдельном участке маршрута. Например, если на участке между 1 и 2 газорегулятором проложить полимерную трубу с диаметром 5см, то потери составят 12,26 Па. а стоимость 10000р., а если взять стальную трубу, с таким же диметром, то потери составят 10,19 Па. но стоимость составит 20000р. Но на одних участках можно проложить стальную трубу, а на других нет, или можно проложить полимерную или, стальную трубы, но потери и стоимость будут разные. Таким образом получаем определенное количество альтернатив и заполняем матрицу полезностей, элементами которой являются оценки альтернатив по двум выбранным критериям. Полученная задача может быть решена любым из многокритериальных методов [9].

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

• А1 – T1D5T1D6T1D8;
• A2 – T1D8T1D7T2D5; и т.п.

Здесь Ti – тип трубы, используемый для прокладки на соответствующем участке, D – диаметр трубы в см. Используется два типа труб: полимерные (Т1) и стальные (Т2)

Для решения данной задачи можно использовать разные методы: метод аддитивной свертки, метод мультипликативной свертки, метод уступок, метод целевого программирования, метод главного критерия, метод ранжирования и т. д. [10]

Выводы

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

Список источников