ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

РАДІОЕЛЕКТРОНІКИ

Коба Костянтин Миколайович

УДК 519.853.4

МОДЕЛІ І МЕТОДИ РОЗВ’ЯЗАННЯ ЗАДАЧ МАРШРУТИЗАЦІЇ

ПРИ ЛІКВІДАЦІЇ НАСЛІДКІВ ТЕХНОГЕННИХ АВАРІЙ

01.05.02 – математичне моделювання та обчислювальні методи

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Харків – 2005

Дисертацією є рукопис.

Робота виконана в Харківському національному технічному університеті сільського господарства ім. П. Василенка , Міністерство аграрної політики України.

Науковий керівник: доктор технічних наук, професор

Путятін Валерій Петрович,

Харківський національний технічний університет

сільського господарства ім.. П.Василенка,

завідувач кафедри кібернетики.

Офіційні опоненти: доктор фізико-математичних наук, професор

Смеляков Сергій Вячеславович

Харківський університет повітряних сил

Міністерства оборони України, професор кафедри

математичного та програмного забезпечення АСУ;

доктор технічних наук, професор

Комяк Валентина Михайлівна,

Академія цивільного захисту України

Міністерства України з питань надзвичайних ситуацій та у справах захисту населення від наслідків Чорнобильської катастрофи, професор кафедри фізико-математичних дисциплін.

Провідна установа: Інститут проблем моделювання в енергетиці

ім. Г.Є. Пухова Національної академії наук України,

м. Київ.

Захист відбудеться “_21_”___червня___ 2005 р. о _15-00_ годині на засіданні

спеціалізованої вченої ради Д 64.052.02 у Харківському національному університеті радіоелектроніки Міністерства освіти і науки України за адресою: просп. Леніна 14, м. Харків,  61166.

З дисертацією можна ознайомитись в бібліотеці Харківського національного університету радіоелектроніки Міністерства освіти і науки України за адресою: просп. Леніна 14, м. Харків,  61166.

Автореферат розісланий “_17_” ___05___ 2005 р.

Вчений секретар

спеціалізованої вченої ради Безкоровайний В.В.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність. З урахуванням трагічного досвіду аварії на ЧАЕС, відповідно до Законів України, Державних нормативів і Постанови Уряду України № 304 від 07.12.1989 р., в частині створення автоматизованих систем контролю радіаційної обстановки (АСКРО) на АЕС України, розробляються і удосконалюються системи безперервного контролю радіаційної обстановки і підготовки початкових даних для систем моделювання і прогнозування розвитку аварійної ситуації. Крім того, відповідні постанови ставлять вимоги підготовки рішень на евакуацію з урахуванням динаміки аварії. Проте, функції, закладені в існуючих АСКРО, не передбачають розв’язання всього спектру задач, що вимагають негайного вирішення у разі аварії. Тому актуальною проблемою є розробка математичних моделей і методів розв’язання двоєдиної задачі оцінки обстановки і маршрутизації (ООМ) для випадку аварій різного масштабу.

При цьому можна виділити три основні аспекти моделювання і розв’язання задачі ООМ: системний, пов'язаний з інтеграцією моделей і методів розв’язання задачі ООМ у відповідну АСУ; імітаційний, пов’язаний з моделюванням полів забруднення; оптимізаційний, пов'язаний з розв’язанням задач пошуку оптимальних маршрутів.

У роботах М.М. Моісеєва, В.С. Михалевича, М.В. Михалевича, Е.Г. Петрова, І.В. Сергієнка та інших авторів розвивається серія наукових напрямів, присвячених створенню підсистем першого типу на основі аналізу і синтезу територіально розподілених ієрархічних систем, моделей і методів координації, математичних методів підтримки прийняття рішень в режимі реального часу, блоково-ієрархічного підходу, включаючи нові принципи індуктивної математики. Розвитку методів моделювання полів забруднення навколишнього середовища, пожеж і інших шкідливих дій присвячені роботи Ю.О. Абрамова, В.М. Комяк, Л.І. Нефьодова, Г.І. Марчука, В.П. Путятіна, Г.Д. Річардса й ін. При нелінійних функціях мети, а тим більше – в нестаціонарних умовах задачі пошуку оптимальних шляхів стають NP-повними. Методи їх розв’язання розвивалися в роботах В.Г. Вайнера, Е. Рейнгольда, С.В. Смелякова, Ю.Г. Стояна, Н.З. Шора, С.В. Яковлева й ін. При цьому пошук оптимальних шляхів значною мірою спирається на моделі і методи геометричного проектування, закладені в роботах Ю.Г. Стояна, і які отримали подальший розвиток в роботах М.І. Гиля, В.М. Комяк, М.В. Новожилової, С.В. Смелякова, С.В. Яковлева й ін. З урахуванням розвитку геоінформаційних систем і супутникового зв’язку як актуальний шлях розв’язання задач пошуку оптимальних маршрутів в неоднорідній області також слід відзначити розробку програмно-апаратних засобів, розвиток яких знайшов відображення в роботах В.П. Путятіна, К.А. Чурікова й ін.

Задача маршрутизації є узагальненням транспортної задачі і задачі розкладу, значний внесок в розв’язання яких внесли А.А. Бакаєв, В.С. Михалевич, І.В. Сергієнко, С.В. Смеляков й ін. За аналогією із стаціонарним випадком її можна віднести до нестаціонарної задачі планування (за вартістю і складом ресурсу).

Таким чином, в межах задач, визначених законодавством України і Державними нормами і регламентами в області забезпечення протирадіаційного захисту людини і навколишнього природного середовища і радіаційної безпеки, актуальною є двоєдина задача оцінки обстановки і маршрутизації, модель і метод розв’язання якої забезпечують адаптацію плану втручання до умов зовнішнього середовища, що змінюються.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася з 2000 р. у Харківському національному технічному університеті сільського господарства ім. П. Василенка (ХНТУСГ) на кафедрі кібернетики відповідно до плану бюджетної теми університету „Розробка й впровадження у виробництво машинно-технологічних систем” (ДР №0100U005610), плану робіт з НДР “Вдосконалення автоматизованої системи контролю радіаційної обстановки (АСКРО) Хмельницької АЕС” (договір № 3/316К від 03.06.2002 р. між ВП “ХМЕЛЬНИЦЬКА АЕС” і ХНТУСГ) за напрямом “Моделювання техногенних катастроф”, при виконанні якої дисертантом розроблена система моделей і методів розв’язання задач оцінки обстановки і оптимізації планів евакуації, а на їх основі – експериментальний комплекс програм і принципи програмно-апаратних реалізацій відповідних математичних моделей.

Наукові питання, що розглядаються в цій роботі, відображають задачі створення державної системи заходів щодо забезпечення готовності до ліквідації аварій на ядерних установках, які поставлені в Законах України “Про використання ядерної енергії і радіаційну безпеку” від 1995 р., “Про захист людини від впливу іонізуючих випромінювань” від 1998 р. і конкретизовані в Нормах радіаційної безпеки України (НРБУ-97) від 1998 р., Постанові Уряду України № 304 від 07.12.1989 р., “Програмі запобігання і реагування на надзвичайні ситуації техногенного і природного характеру”, яка координується МНС України, в частині вдосконалення автоматизованих систем контролю радіаційної обстановки на АЕС України в умовах радіаційної аварії.

Мета і задачі дослідження. Мета роботи полягає в розробці системи моделей і методів розв’язання задачі оцінки обстановки і маршрутизації при техногенній аварії. Для цього в роботі поставлені наступні основні задачі.

1. Розробити ефективну (за витратами пам'яті і трудомісткістю) чисельну модель і методи розв’язання задачі оцінки обстановки за даними аварійного моніторингу від нерегулярної мережі датчиків змінної структури.

2. Розробити ефективну (за витратами пам’яті і трудомісткістю) чисельну модель і методи розв’язання оптимізаційних задач маршрутизації для типових поєднань критеріїв і обмежень на транспортний ресурс і дозу дії на персонал і населення.

3. Розробити комплекс програм і принципи створення спеціалізованих пристроїв для розв’язання задач маршрутизації за типовими поєднаннями критеріїв і обмежень.

Об’єкт дослідження – процес контролю навколишнього природного середовища і прийняття рішень щодо ліквідації наслідків техногенних аварій.

Предмет дослідження – моделі і методи апроксимації нестаціонарного поля розподілу агресивного середовища на місцевості і оптимізації маршрутів евакуації і проведення аварійних робіт за умов зараження місцевості.

Методи дослідження – для побудови математичної моделі задачі ООМ використовувалися методи системного аналізу, теорії вибору і прийняття рішень, принципи побудови геоінформаційних (ГІС) і експертних систем; при побудові моделі і методів розв’язання задачі оцінки обстановки використовувалися чисельні методи; при побудові моделі і методів розв’язання задачі маршрутизації, для отримання оцінок трудомісткості і витрат пам’яті, використовувалися методи комбінаторної оптимізації, теорії геометричного проектування, математичного програмування.

Наукова новизна основних результатів.

1. Вперше побудована математична модель задачі оцінки обстановки і маршрутизації (ООМ) при техногенній аварії на стаціонарних і рухомих об’єктах, що призводить до забруднення навколишнього середовища, що змінюється в часі, в якій використовуються нормативні критерії і обмеження, а також дані аварійного моніторингу від мережі датчиків змінного складу, нерегулярно розташованих на місцевості.

2. Вперше запропонована регулярна сіткова модель для інтерполяції і прогнозування поля за даними нерегулярного просторового моніторингу, геометрична структура якої відповідає принципам побудови ГІС; для неї отримані оцінки кроку за часом і географічним координатам, що забезпечують апроксимацію поля з точністю, адекватною можливостям мережі датчиків, а також оцінки трудомісткості і витрат пам’яті. Це дозволило зробити висновок щодо ефективності застосування цієї моделі в реальному масштабі часу.

3. Отримали подальший розвиток методи експоненціальних середніх і Фостера-Стьюарта у частині виявлення і прогнозування трендів відносно переліку особливостей даних задач і їх сіткових моделей; обґрунтований вибір поліноміальних і експоненціальних моделей регресії для трендів у вузлах. Це дало можливість отримати лінійні оцінки трудомісткості і витрат пам’яті.

4. Вперше отримані квадратурні і кубатурні формули для оцінювання доз при пересуванні по дорогах, які засновані на використовуванні констант, подібних коефіцієнтам Котеса, і прогнозованих значень поля. Цей метод знаходження криволінійних інтегралів використовує прийняте в ГІС представлення доріг ламаними і областей – комірками даної сітки. Одержані оцінки дози з лінійною трудомісткістю і витратами пам’яті.

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

6. Вперше запропоновано метод розв’язання базових задач оптимізації маршрутів для аварійних бригад, заснований на їх зведенні до задач пошуку оптимальних маршрутів і класичних транспортних задач. Це дозволило отримати лінійні оцінки витрат пам’яті і кубічні – трудомісткості.

7. Вперше запропоновано метод розв’язання квазістаціонарних базових задач оптимізації планів евакуації населення.

Практичне значення отриманих результатів. Запропоновані моделі і методи розв’язання задач оцінки стану навколишнього середовища і оптимізації транспортного ресурсу і маршрутів пересування в зоні техногенної аварії дозволяють розширити можливості існуючих автоматизованих систем контролю радіаційної обстановки, що поширюють свою дію на зону спостереження (постійного), на регіони з істотно більшою територією, як і на області з системою моніторингу, створюваною у разі виникнення аварії, причому без перебудови математичних і (або) програмних моделей, а лише за рахунок оновлення бази даних про мережу датчиків, оскільки решта інформації (про населення і т.п.) може бути наведена у відповідній ГІС.

Впровадження результатів дисертаційної роботи здійснено: на Хмельницькій АЕС, відповідно до НДР “Вдосконалення автоматизованої системи контролю радіаційної обстановки (АСКРО) Хмельницької АЕС”, згідно з договором № 3/316К від 03.06.2002 р., між ВП “ХМЕЛЬНИЦЬКА АЕС” і ХНТУСГ за напрямом “Моделювання техногенних катастроф”; в Інституті фізики високих енергій та ядерної фізики ННЦ ХФТІ НАН України, в навчальному процесі ХНУСГ при викладанні дисциплін: “Математичне моделювання”, “Ідентифікація і моделювання технічних об’єктів”, “Інженерна екологія”.

Особистий внесок здобувача. У роботі [1] розглянута концептуальна постановка задачі пошуку раціонального маршруту пересування людей в регіоні техногенної катастрофи. У роботі [3] запропонована структура розв’язання задачі маршрутизації, пов’язана з оптимізацією планів евакуації населення і переміщення аварійних бригад, заснована на розгляді системи моделей базових задач і методів їх розв’язання. Наведено оцінки обчислювальної ефективності. У патентах України [4, 5, 6] запропоновані апаратурно-програмні реалізації математичних моделей задач маршрутизації. У роботі [7] розглянуті основні етапи технічної реалізації моделей і обґрунтована структура технічних засобів для оперативного прийняття рішень. У роботі [10] розглянуто питання автоматизації прийняття проектних рішень щодо маршрутизації. Роботи [2, 8, 9, 11] опубліковані без співавторів.

Апробація результатів дослідження. Основні результати роботи докладалися і обговорювалися на: VI, VII Міжнародному молодіжному форумі "Радіоелектроніка і молодь в XXI столітті", Харків, ХНУРЕ, 2002 р., 2003 р.; Міжнародній конференції "Теорія і техніка передачі, прийому і обробки інформації", Харків, ХНУРЕ, 2003 р., 2003 р.; III Міжнародній науково-технічній конференції "Проблеми інформатики і моделювання", Харків, НТУ "ХПІ", 27–29 листопада 2003 р.

Публікації. За темою дисертації опубліковано 11 робіт, в тому числі отримано 3 статты у фахових виданнях, 5 доповідей на наукових конференціях, 3 патенти України на винаходи [4–6].

Структура роботи. Дисертація складається із вступу, 5 розділів, висновків, списку використаної літератури і трьох додатків. Загальний обсяг дисертації 160 стор., у тому числі 17 малюнків на 17 сторінках, 1 таблиця на 1 сторінці, список із 141 використаного джерела на 16 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

Вступ містить обґрунтування актуальності роботи, формування мети, об’єкта і завдань дослідження, сукупність наукових результатів, що виноситься на захист, відомості про їхню апробацію та реалізацію.

Розділ 1 "Основні елементи моделі задач оцінки обстановки та маршрутизації" присвячено аналізу нормативних вимог і існуючих технічних засобів, моделей і методів розв’язання задач оцінки дії техногенних аварій, що становлять радіаційну або хімічну небезпеку, і прийняття рішень щодо ліквідації їх наслідків, показано актуальність проблеми розробки ефективних моделей і методів розв’язання задачі оптимізації оцінки обстановки і маршрутизації (ООМ).

Концептуальна модель задачі ООМ полягає в наступному. За даними аварійного моніторингу про дію агресивного середовища (АС), що надходять від нерегулярної мережі датчиків змінної структури, необхідно побудувати регулярну сіткову модель поля інтенсивності дії АС, яка в реальному масштабі часу забезпечує прогнозування і оцінку поточних значень інтенсивності дії АС і тенденції в їх зміні для будь-якої точки зони аварії в даному регіоні , а також розробити метод розв’язання задач розподілу транспортних засобів по пунктах евакуації і аварійних бригадах і вибору системи маршрутів їх переміщення в необхідні пункти, які забезпечують мінімізацію дози дії АС та/або мінімізацію загального часу перевезень при обмеженнях на дозу дії АС та на транспортні ресурси. При цьому дані аварійного моніторингу і прогноз дії АС в регіоні повинні враховуватися в цілях корекції прийнятого до виконання плану розподілу і переміщення транспортних засобів в реальному масштабі часу.

Сформульовані вимоги системного характеру, що пред’являються до моделей і методів розв’язання задачі ООМ, а також вимоги щодо точності і обчислювальної ефективності. На цій основі запропоновані базові елементи математичної моделі цієї задачі, особливості прикладних задач, включаючи основні критерії і обмеження. Показано, що розв’язання задачі ООМ зводиться до двох підзадач – оцінки обстановки і маршрутизації. На цій основі сформульовані основні задачі дослідження.

Розділ 2 "Моделі і методи розв’язання задач оцінки обстановки у стаціонарних умовах". Для поставленої задачі оцінки обстановки в стаціонарних умовах розроблена базова сіткова модель поля зараження, модифікації якої, і , враховують вимоги щодо точності її розв’язання. На основі аналізу обчислювальної ефективності розглянутих моделей обґрунтовано застосування подібних регулярних сіток для лінійної і нелінійної інтерполяції поля замість нерегулярної мережі датчиків змінного складу і розташування.

Для поля з великою варіацією значень по вузлах мережі запропоновано метод біквадратної сплайн-інтерполяції поля на тій же сітці . Для запропонованих моделей отримані верхня і нижня оцінки кроку сітки, що забезпечують лінійну інтерполяцію поля з точністю, адекватною можливостям мережі датчиків .

На основі використання прийнятих в ГІС полігональної моделі доріг і сегментного представлення області та запропонованою сітковою моделі для поставленої задачі маршрутизації розроблені методи оцінювання доз (інтегральної дії АС) при пересуванні по дорогах. Отримані квадратурні формули для криволінійних інтегралів першого типу, засновані на використанні коефіцієнтів, подібних коефіцієнтам Котеса, і значень поля в необхідні моменти часу, що дозволяє оцінювати дози дії для нестаціонарного поля з лінійною трудомісткістю і витратами пам’яті (від числа ребер, що становлять маршрут).

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

Розділ 3 "Моделі і методи розв’язання задач оцінки обстановки у нестаціонарних умовах". Запропонований метод виявлення локальних і глобальних трендів в значеннях поля, заснований на використанні методу Фостера-Стьюарта, який з високим ступенем надійності дозволяє виявляти статистично значущі зміни поля у вузлах сітки (або ) і в області в цілому, причому з лінійною трудомісткістю і витратами пам’яті.

Для поточної оцінки і короткострокового прогнозування поля запропоновані ефективні обчислювальні процедури застосування експоненціальних середніх, що забезпечує згладжування і відсів “застарілих даних” моніторингу, виявлення екстремальних значень в квазістаціонарних умовах.

Обґрунтований вибір поліноміальних (до 3 ступеня) і експоненціальних моделей регресії для трендів. Побудовані методи оцінки параметрів трендів у вузлах сітки і мережі , які мають лінійні оцінки трудомісткості і витрат пам’яті. Одержані оцінки точності запропонованих моделей.

Отримана лінійна апроксимація поля і кубатурні формули для дії АС на маршрутах, що мають лінійну трудомісткість за рахунок їх зведення до стаціонарних моделей і використання полігональної моделі доріг в комірках сітки, відповідно існуючим моделям ГІС.

Для оцінювання сукупної дії АС по декількох чинниках використовується сума апроксимуючих функцій з ваговими множниками, що відображають їх внесок в сукупну дозу, які для кожного чинника визначаються відповідно до динаміки його розвитку.

Розділ 4 "Моделі і методи розв’язання задач маршрутизації". Основні допущення при розв’язанні задач маршрутизації наступні. Транспортні засоби включають три основні категорії – автобуси, вантажні автомобілі і мікроавтобуси в кількості відповідно, загальний транспортний ресурс складає одиниць місткістю людин кожна. Математичним представленням дороги є шлях, як аналог лінії, який відповідно до вимог сучасних ГІС, задається ламаною, або маршрут, коли переміщення по дорозі розглядається в часі. Оскільки число аварійних бригад (АБ) багато менше за число рейсів для евакуації населення, вони прямують для виконання робіт директивно і, як правило, на своєму транспорті, задачі планування евакуації і переміщення АБ розглядаються незалежно.

Базові задачі маршрутизації для аварійних бригад. Бригада переміщається з початкового пункту в пункт за маршрутом за час , де вона виконує роботи за час , після чого переміщається в пункт за маршрутом за час . Для неї задано обмеження за максимальною дозою дії АС

, (1)

де – раніше накопичена доза; а , , – дія АС, отримана членом бригади при рухові з в , при роботі в і при рухові з в . Максимальний час перебування бригади в пункті визначається рівністю в (1), тобто

? ( + + ). (2)

Розв’язання інтегрального рівняння (2) являє собою не тільки складну задачу, але і не гарантує необхідної точності, коли адекватне прогнозування поля можливо лише на інтервали часу, набагато менші за тривалість виконання завдань . У стаціонарному випадку використання не регресійних моделей поля дозволяє перейти до лінійних рівнянь вигляду ? ( + + ), звідки одержуємо [ ? ( + + )] / . У нестаціонарному випадку для (1) розглянемо різницю ? , що визначає збереження ресурсу по дозі дії АС (тобто запобіжну дозу) для бригади , і позначимо множину маршрутів з пункту i в пункт j. У результаті приходимо до наступної базової задачі пошуку оптимального маршруту для аварійної бригади , розташованої в пункті , для виконання робіт на об’єкті .

Задача 4.1. Знайти , (3)

де , (4)

при . (5)

Розглянемо задачу про виконання робіт бригадами, розташованими в пунктах , на об’єктах при . Нехай – перестановка номерів бригад, . Для кожної пари розглянемо задачу (3) і, припустивши, що всі вони мають розв’язок з параметрами , введемо критерії

; ;

; .

Тоді, якщо – множина всіх перестановок номерів бригад, для кожної з яких існує допустиме рішення в значенні (5), базові задачі маршрутизації, пов’язані з пошуком оптимального плану проведення аварійних робіт, мають вигляд

Задача 4.2. Знайти . Задача 4.3. Знайти .

Задача 4.4. Знайти . Задача 4.5. Знайти .

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

Основні моделі базових задач оптимізації маршрутів евакуації. Заданий розподіл транспортного ресурсу між пунктами евакуації

; . (6)

Нехай – накопичена доза для населення в пункті до моменту , – число людей, що підлягають евакуації, а – шлях, по якому населення евакуювало з j в , якому, до моменту початку евакуації чергової групи , відповідає маршрут , що проходиться за час . Тоді населення з пункту j евакуювало групами по чоловік за рейсів, кожний з яких проводиться, в середньому, за час сукупністю транспортних засобів. Число рейсів округляємо до цілих.

Тривалість евакуації з пункту, до прибуття останньої групи в , складає , а рейси починаються в наступні моменти часу

. (7)

Сумарний вплив на групу , з урахуванням доз до початку евакуації () при очікуванні початку перевезення () і самого перевезення () складе

. (8)

Нехай . (9)

Із сукупності маршрутів складається план евакуації з пункту в пункт з показниками і розкладом (7), якщо .

Нехай – множина маршрутів з пункту в пункти і

(10)

. (11)

Тоді базові задачі оптимізації маршрутів евакуації для одного пункту мають вигляд:

Задача 4.6. Знайти шлях , на якому досягається

. (12)

Задача 4.7. Знайти шлях , на якому досягається

. (13)

Зауважимо, що задача 4.6 більш актуальна у разі неоднорідного поля, а задача 4.7 – у разі однорідного поля високої інтенсивності, коли питання стоїть про екстрену евакуацію.

Сукупність маршрутів складає план евакуації (всього населення), визначуваний розподілом вигляду (6) з показниками ефективності

, (14)

, (15)

, (16)

, (17)

якщо шляхи отримані в результаті розв’язання задач 4.6, 4.7, відповідно до ситуації.

Разом з цими основними показниками можуть задаватися і інші, більш адекватно відображаючі поточні проблеми, оскільки жоден критерій не є універсальним. Так, якщо в рівень поля низький, а в – високий, вирівнювання значень і не є актуальним у порівнянні з мінімізацією (вирівнюванням) і ; навпаки, при небезпеці нових викидів критерій (14) або (16) стає домінуючим.

При уведених позначеннях базові задачі оптимізації плану евакуації набудуть наступного вигляду:

Задача 4.8. Знайти . Задача 4.9. Знайти .

Задача 4.8 визначає пошук плану евакуації, що мінімізує максимальну дозу дії по всіх евакуйованих групах, крім того, це мінімізує і час . Задача 4.9 відображає ситуацію, коли рівень поля ще не досяг небезпечних значень, і евакуацію вимагається провести за найкоротший час, хоча і з дотриманням обмежень на дозу дії АС.

Розв’язання базових задач оптимізації маршрутів переміщення аварійних бригад. Основна ситуація: на даному інтервалі планування нових викидів немає, а процеси перерозподілу АС не значущі. У цьому випадку поле допускає подання

(18)

і при очікуванні і перевезенні за маршрутом .... доза складає

, (19)

де Т, – моменти початку перевезення і проходження вершини i, а – тривалість знаходження в аварійній зоні при евакуації. Тоді скорочення тривалості евакуації зменшує сумарну дію АС, а шлях мінімальної довжини визначає і шлях мінімальної дози дії, що при даному ресурсi мінімізує і час очікування.

Використовуючи полігональну модель мережі доріг, знаходимо параметри графа Г, а по них – найкоротші за часом шляхи переходу з вершин в і множини , що за алгоритмом Флойда вимагає порядку операцій. При цьому (19) зводиться до обчислення . Ці шляхи з показниками дають розв’язок задачам 4.6, 4.7.

Розв’язання задачі 4.1. Нехай , – найкоротші за часом шляхи з к в о і з о в l. Тоді

(20)

при фіксованій тривалості перебування на об’єкті о також обертаються в максимум при мінімальних значеннях , (відповідні шляхи визначаються застосуванням алгоритму Флойда). Прирівнюючи в (20) до нуля, знайдемо – максимальну тривалість роботи аварійної бригади в пункті о.

Розв'язання задач 4.2 – 4.5 для випадку =N0 =n. Нехай – квадратна (nn)-матриця витрат часу

де МТ – досить велика величина, – мінімальний час переходу з в і з в при обмеженні (5). Нехай – максимальне з цих значень в с. За МТ візьмемо величину, більшу ніж n.

Матриця с (20) однозначно визначає матрицю доз дії , , в якій значення визначено так само, як і МТ. Нехай – множина таких матриць , що

1, (21)

і – перестановка номерів бригад для роботи на об’єктах: . Вибираючи за функцію мети величини , , отримаємо, що задачі 4.4, 4.5 відповідно при і, зводяться до стандартної задачі про призначення:

Знайти , (22)

яка розв’язується угорським алгоритмом з трудомісткістю ч (операцій).

Нехай і – розв’язок задачі 4.4 і . З матриці отримаємо матрицю , змінивши її елементи за правилом , якщо . Якщо для умова (21) не виконується, матриця дає розв’язок і задачі 4.2. Інакше розв’язуємо задачу (22) для матриці , отриманої з , і т.д. На деякому кроці отримаємо, що для матриці розв'язок існує, а для – ні. Тоді розв’язок задачі 4.2 задається матрицею , що визначає, як описано вище, перестановку із значенням критерію . Розв’язок задачі 4.3 отримаємо аналогічно, розглядаючи замість с матрицю z. Теоретично трудомісткість розв’язання задач 4.2, 4.3 в раз вище, ніж , а фактично – з урахуванням малого числа паралельних доріг – за порядком величини відповідає .

Методи розв'язання базових задач оптимізації планів евакуації. Розв’язання задач 4.6, 4.7 для всіх пунктів визначають розподіл ресурсу М і параметри (14) – (17) плану евакуації. Розв’язання задач 4.8, 4.9 проводиться в два етапи.

Спочатку знайдемо опорне рішення вигляду (6), що задовольняє обмеженням (10), (11) для фіксованого плану перевезень. У цьому випадку максимальне число рейсів з урахуванням (7) таке, що при середній дозі в пункті j максимальний вплив в очікуванні перевезень, задовольняє (8), тобто . За значеннями і одержуємо значення , а за ним – число перевезень : . При одержуємо опорне рішення . При має місце нестача транспортного ресурсу для виконання обмежень, і той, хто приймає рішення, повинен послабити обмеження або залучити додатковий (до ) ресурс . Його розподіл можна отримати, виходячи з рівномірного зменшення в раз: . Тоді розподіл ресурсу М має вигляд , а максимальна доза для всіх пунктів евакуації, в середньому, складе =.

Розділ 5 "Програмна і апаратна реалізація моделей та методів розв’язання задач оцінки обстановки та маршрутизації при техногенних аваріях" присвячено розробці програмного комплексу ГІС "ЕВАКУАЦІЯ" у вигляді відкритої системи для інтерактивної роботи в реальному масштабі часу, що дає змогу значно розширити функції АСКРО Хмельницької АЕС на випадок техногенних аварій (рис. 1–3). Крім того, запропоновані принципи програмно-апаратної реалізації [4–6] математичних моделей та методів розв'язання відповідних задач оцінки обстановки та маршрутизації.

Рис. 1. Представлення бази даних про сіткову модель поля забруднення

Рис. 2. Формування бази даних і оптимізація плану евакуації

Рис.3. Формування бази даних і розподіл аварійних бригад

ОСНОВНІ ВИСНОВКИ

1. На основі аналізу нормативних вимог, існуючих моделей і методів розв’язання задач оцінки дії техногенних аварій і прийняття рішень щодо ліквідації їх наслідків показана актуальність проблеми розробки ефективних моделей і методів розв’язання задачі оцінки обстановки і маршрутизації (ООМ) для випадку комунальних аварій, а також їх програмно-апаратної реалізації.

2. Побудована концептуальна модель задачі ООМ і показано, що для її розв’язання необхідне створення нових комп'ютерних моделей, а також методів апроксимації, оцінювання і оптимізації, що задовольняє заданим вимогам щодо точності і обчислювальної ефективності. На цій основі запропоновані базові елементи математичної моделі цієї задачі, включаючи основні критерії і обмеження. Показано, що розв’язання задачі ООМ зводиться до розв’язання двох підзадач – оцінки обстановки і маршрутизації.

3. Для поставленої задачі оцінки обстановки розроблена і обґрунтована ефективність застосування базової регулярної сіткової моделі для лінійної і нелінійної інтерполяції поля замість використання при аварійному моніторингу нерегулярної мережі датчиків змінного складу і розташування. Отримані оцінки кроку сітки, що забезпечує лінійну інтерполяцію поля з точністю, адекватною можливостям мережі датчиків.

4. На основі використання прийнятих в ГІС полігональної моделі доріг і сегментного подання області для задачі маршрутизації розроблені методи оцінювання доз при пересуванні по дорогах. Отримані квадратурні формули, засновані на використанні коефіцієнтів, подібних до коефіцієнтів Котеса, і значень поля в необхідні моменти часу, що дозволяє оцінювати дози для нестаціонарного поля з лінійною трудомісткістю і витратами пам’яті. Для актуального класу задач розрахунку дії доз при переміщенні по дорожній сіті при експоненціальній зміні поля отримана формула, що зводить дану задачу до стаціонарного аналога з лінійною трудомісткістю і витратами пам’яті.

5. Для виявлення тенденцій і прогнозування дії АС в зоні аварійного моніторингу в нестаціонарних умовах побудована система динамічних моделей поля у вузлах сітки, що враховують особливості розвитку радіаційної або хімічної обстановки, яка з необхідною точністю забезпечує розв’язання цих задач в реальному масштабі часу. Обґрунтовано вибір поліноміальних і експоненціальних моделей трендів і запропоновані методи оцінки їх параметрів, лінійні за трудомісткістю і витратами пам’яті.

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

7. Розроблені методи розв’язання базових задач оптимізації маршрутів для аварійних бригад, засновані на їх зведенні до задач пошуку оптимальних маршрутів і транспортних задач різного типу, а також методи розв’язання базових задач оптимізації планів евакуації населення, засновані також на їх зведенні до задач пошуку оптимальних маршрутів, апріорної і апостеріорної оптимізації транспортного ресурсу. Для запропонованих методів розв’язання базових задач отримані лінійні оцінки витрат пам’яті, а оцінки трудомісткості не перевищують кубічної залежності від числа бригад і пунктів евакуації, що підтверджує їх обчислювальну ефективність.

8. Запропоновано загальний підхід до розв’язання задачі ООМ для неоднорідного і нестаціонарного поля, коли вона стає NP-повною. З урахуванням низької точності даних моніторингу, а також неможливості довгострокового прогнозування поля внаслідок можливості викидів і дії метеорологічних чинників, він заснований на ітеративному розв’язанні задачі ООМ за допомогою запропонованої динамічної моделі поля і методів розв’язання базових задач оцінки обстановки і оптимізації планів евакуації і проведення аварійних робіт.

9. Запропоновані моделі і методи розв’язання задачі ООМ в реальному масштабі часу реалізовані у вигляді інтерактивної геоінформаційної системи ГІС “ЕВАКУАЦІЯ”, яка розширює функції АСКРО Хмельницької АЕС на випадок комунальних аварій. Обчислювальний експеримент з ГІС “ЕВАКУАЦІЯ”, заснований на використанні фактичних даних і існуючих моделей забруднення, показав, що ця система забезпечує розв’язання розрахункових і оптимізаційних задач з необхідною точністю і оперативністю, спрощує введення, контроль і сприйняття даних, що актуально при розробці й адаптації планів втручання, на стаціонарних і мобільних об’єктах за умов гострого дефіциту часу.

10. Запропоновані в роботі спеціалізовані пристрої можуть бути застосовані в цілях підвищення ефективності функціонування автономних систем управління переміщенням аварійних бригад і пересувних лабораторій.

ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

АНОТАЦІЯ

Коба К.М. Моделі і методи розв’язання задач маршрутизації при ліквідації наслідків техногенних аварій. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи – Харківський національний університет радіоелектроніки, Харків, 2005.

Розглянуті прикладні задачі оцінки обстановки і оптимізації планів евакуації і проведення аварійних робіт з урахуванням вимог, затверджених законами України і державними нормами у зв’язку з техногенними аваріями. Побудована математична модель основної задачі оцінки обстановки і маршрутизації (ООМ). Для задач оцінки обстановки розроблені ефективні (за витратами пам’яті і трудомісткістю) чисельна модель і методи розв’язання задачі оцінки обстановки за даними аварійного моніторингу від нерегулярної мережі датчиків змінної структури. Для задач маршрутизації сформульовані основні обмеження і критерії, засновані на мінімаксних і середніх показниках часу і дози, вказані їх типові комбінації, включаючи лексикографічні критерії. Розроблені методи розв’язання базових задач оптимізації маршрутів для аварійних бригад і евакуації населення, засновані на їх зведенні до задач пошуку оптимальних маршрутів і транспортних задач різного типу. Отримані лінійні оцінки витрат пам’яті, а оцінки трудомісткості не перевищують кубічної залежності від числа бригад і пунктів евакуації, що підтверджує обчислювальну ефективність запропонованих моделей і методів оптимізації.

Запропоновані в роботі моделі, методи і алгоритми розв’язання задачі ООМ реалізовані у вигляді відкритої геоінформаційної системи ГІС “ЕВАКУАЦІЯ”, для інтерактивної роботи в реальному масштабі часу, що дає змогу значно розширити функції АСКРО Хмельницької АЕС на випадок комунальних аварій.

Ключові слова: математичне моделювання, математичне програмування, обчислювальні методи, оптимізація, прийняття рішень, маршрутизація, техногенні аварії, евакуація.

АННОТАЦИЯ

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 – математическое моделирование и вычислительные методы – Харьковский национальный университет радиоэлектроники, Харьков, 2005.

Диссертационная работа посвящена задачам оценки обстановки и оптимизации планов эвакуации, а также проведения аварийных работ с учетом требований, утвержденных законами Украины и государственными нормами в связи с техногенными авариями. Разработана система математических моделей, в рамках которой поставлены базовые расчетные и оптимизационные задачи и предложены эффективные методы их решения в реальном масштабе времени, адаптируемые на изменения внешних воздействий, которые реализованы в виде программного комплекса ГИС “ЭВАКУАЦИЯ”.

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

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

Для задач маршрутизации