Содержание

Вступ 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]

Висновок

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

Список джерел