КОМП’ЮТЕРНА СИСТЕМА ОПТИМІЗАЦІЇ ВИБОРУ МАРШРУТІВ СЛІДУВАННЯ АВАРІЙНО-РЯТУВАЛЬНОЇ ТЕХНІКИ
К.т.н., доцент Моргун О.М.*, Моргун Л.О.**
*Академія пожежної безпеки ім. Героїв Чорнобиля (м. Черкаси)
**Московський фізико-технічний інститут
Источник: http://www.nbuv.gov.ua/portal/natural/Pbtp/texts/2008-1/st_17%20morgun.pdf
Розглянуто застосування математичного апарату теорії графів для розробки методики мінімізації терміну прибуття аварійно-рятувальної техніки до місця виникнення надзвичайної ситуації.
Представлено аспекти практичної реалізація пошуку оптимального маршруту, в тому числі, інформаційну базу та програмне забезпечення.
Ключові слова: оптимізація, маршрут слідування, теорія графів, комп’ютерна система, програмне забезпечення.
Постановка проблеми. Сучасні системи управління, в тому числі й інформаційно-аналітичні системи прогнозування, моніторингу та забезпечення реагування на надзвичайні ситуації, можуть бути ефективними лише за умови, що для обробки інформації використовується комп’ютерна техніка. Для забезпечення оперативного управління силами та засобами аварійно-рятувальних служб у складі таких комп’ютеризованих інформаційно-аналітичних систем мають існувати так звані автоматизовані підсистеми зв’язку та оперативного управління (АПЗОУ) [1].
Однією з найважливіших функцій АПЗОУ є формування наказу на проведення робіт з ліквідації надзвичайної ситуації, до складу якого обов’язково входить маршрут слідування аварійно-рятувальної техніки до заданого об’єкту. При цьому виникає необхідність вирішення проблеми скорочення терміну прибуття техніки на об’єкт.
Формулювання цілей дослідження. Метою роботи є розв’язання комплексної задачі мінімізації терміну прибуття аварійно-рятувальної техніки на об’єкт. Аналіз показує, що належний результат може бути досягнутий за рахунок трьох факторів:
- вибір оптимального маршруту слідування аварійно-рятувальної техніки за мінімумом витраченого часу на прибуття до об’єкта;
- створення програмного забезпечення, яке використовує при оптимізації маршруту слідування швидкодіючі алгоритми;
- побудова управління програмним забезпеченням таким чином, щоб потрібні вхідні дані могли бути введені оператором в найкоротший термін.
Для досягнення цієї мети необхідно розв’язати наступні задачі:
- проаналізувати апарат теорії графів для вибору підходящого алгоритму пошуку оптимального за швидкодією маршруту слідування;
- проаналізувати діяльність оператора для визначення експлуатаційних характеристик програмного забезпечення, які забезпечували б його ефективну роботу в момент отримання повідомлення про надзвичайну ситуацію;
- проаналізувати фактори, які впливають на тривалість виїзду і термін прибуття аварійно-рятувального підрозділу на об’єкт, в тому числі стан доріг, інтенсивність вуличного руху, наявність поворотів тощо;
- визначити величини середніх швидкостей аварійно-рятувальної техніки під час руху транспортними магістралями міста;
- розробити програмне забезпечення для автоматичного пошуку оптимального маршруту слідування техніки від місця розташування пожежної частини до об’єкту з урахуванням вимог до діяльності оператора.
Аналіз публікацій, на які спирається автор. Математичні моделі, за допомогою яких можуть бути представлені маршрути слідування, в основному побудовані на використанні теорії графів [2]. Відомі також і деякі алгоритми побудови оптимальних за різними критеріями маршрутів на графах [3]. Але все це може бути прийнято тільки за основу, оскільки, як самі моделі, так і відповідні алгоритми оптимізації, передбачають рівноправність ребер графу. Для реальних же ситуацій таке припущення є неприйнятним.
Виклад основного матеріалу. Мінімізація терміну прибуття аварійно-рятувальної техніки до об’єкту здійснюється шляхом пошуку оптимального маршруту слідування на базі застосування методів теорії графів. При цьому інформація про транспортні магістралі міста має бути належним чином пристосована: перехрестя вулиць та провулків повинні бути представлені вершинами деякого графа, а самі вулиці та провулки – його ребрами.
У відповідності з цим ідеальний граф математичної моделі міста має такі властивості:
- граф не містить ізольованих вершин; у протилежному випадку це означало б наявність недосяжних для проїзду перехресть;
- граф не є повним; це означає, що кожне перехрестя міста безпосередньо зв’язане вулицею чи провулком лише з невеликою кількістю інших сусідніх перехресть;
- граф не є однорідним, тобто степені його вершин можуть бути різними; це означає, що від того чи іншого перехрестя може відходити різна кількість вулиць;
- граф є плоским; це означає, що при перетині двох вулиць обов’язково існує відповідне перехрестя;
- граф є зв’язним; це означає, що завжди можна проїхати від одного перехрестя до будь-якого іншого, і вулиці, недосяжні для проїзду, відсутні;
- граф є орієнтованим; це означає, що на деяких вулицях або провулках можливий лише односторонній рух.
Однак, математична модель міста у вигляді графа не є статичним утворенням. Практичний досвід підказує, що в цій моделі повинна бути передбачена можливість оперативного виключення або вставлення заданих вершин та ребер. Це пов’язано з наступним.
Як відомо, в місті періодично відбувається ремонт окремих ділянок дорожнього покриття транспортних магістралей, а також комунікацій. Досить часто рух транспортних засобів на тих чи інших ділянках вулиць може бути неможливим через різноманітні будівельні роботи, стихійні лиха чи катастрофи або через наслідки бойових дій. Крім того, рух транспорту деякими вулицями може бути тимчасово заборонений через проведення різноманітних масових громадських заходів.
Всі указані фактори приводять до того, що певними ділянками деяких вулиць проїхати автомобільним транспортом стає тимчасово неможливо. За таких умов, в кращому випадку, виникає потреба у використанні об’їзних шляхів, в гіршому випадку, ті чи інші райони міста стають недоступними.
Для обчислення терміну переміщення між двома заданими перехрестями міста мають бути відомі відстані між кожною парою сусідніх перехресть, безпосередньо зв’язаних вулицею чи провулком. Знаючи середню швидкість переміщення техніки вздовж тієї чи іншої вулиці, можна знаходити середній термін переміщення між кожною парою сусідніх перехресть.
Інформацію про середню швидкість переміщення техніки вздовж тієї чи іншої вулиці можна отримати на підставі технічної документації, в якій указані характеристики транспортних магістралей міста (ширина, якість та вид дорожнього покриття, наявність перешкод тощо). Такі дані є у розпорядженні міських органів, що підпорядковані головному архітектору.
Проте практичний досвід показує, що таке осереднення швидкості переміщення вздовж всієї вулиці не завжди відповідає дійсності. Зокрема, на окремих її ділянках можуть бути різними якість дорожнього покриття та умови проїзду. Більш точним відображенням реальної дійсності було б використання середньої швидкості переміщення не для всієї вулиці, а для окремих її ділянок, розташованих між сусідніми перехрестями. Це принципово можливо, але приводить до різкого зростання обсягів даних, що мають бути отримані перед розв’язуванням задачі оптимізації і оброблені в процесі її розв’язування. Крім того, як відомо, зміни в якості дорожнього покриття та умов проїзду тими чи іншими вулицями ніким не контролюються і відповідна оперативна інформація не може бути отримана вчасно.
Зі швидкістю переміщення пов’язана ще одна проблема. Із практики відомо, що швидкість переміщення транспортного засобу вздовж вулиці істотно відрізняється від швидкості його повороту на іншу вулицю. Може статися так, що маршрут, прокладений швидкісними магістралями, не буде оптимальним через втрати часу на повороти. Це означає, що реально має вибиратись найкоротший маршрут вулицями з найбільшою допустимою швидкістю руху і з якнайменшою кількістю поворотів.
Розглянемо підхід, який дозволить нам під час пошуку оптимального маршруту на графі враховувати нерівноправність його ребер, яка полягає в тому, що в одних випадках при переході з одного ребра на друге не відбувається додаткових втрат часу (якщо ці ребра відповідають одній і тій же вулиці), а в інших випадках перехід з одного ребра на друге пов’язаний з додатковими втратами часу (якщо ці ребра належать різним вулицям).
Зазначимо, що це вимагає внесення принципових змін в традиційну методику пошуку оптимального маршруту, оскільки теорією графів такий підхід не передбачений.
Як відомо, традиційно на графі нумерують тільки вершини. Застосовуючи нове поняття – комплект ребер графа, ми будемо тепер нумерувати не тільки вершини графа, але й його ребра. Для цього всю сукупність ребер графа ми розіб’ємо на декілька комплектів, до складу кожного з яких включимо ті ребра, що мають певну спільну ознаку. Отже, з’являється ще одне поняття – індекс ребра, який є порядковим номером комплекту, до якого це ребро належить.
В пристосуванні до пошуку оптимального маршруту слідування аварійно-рятувальної техніки до складу одного комплекту будемо включати ребра, які належать одній і тій же вулиці.
Таким чином, методика пошуку оптимального маршруту на графі, яка забезпечує мінімальний термін переміщення від однієї заданої вершини до іншої, має бути вдосконаленою шляхом врахування умови, що всі ребра вздовж маршруту повинні належати якнайменшій кількості комплектів. Критерій оптимізації стає комплексним, тобто час переміщення складається тепер не тільки із часу переміщення вздовж ребер, але й з часу, що витрачається на переходи від одного комплекту ребер до іншого.
Для врахування змін комплектів ребер вздовж маршруту запропоновано використовувати спеціальну дискретну функцію штрафів, яка має розглядатись в кожній вершині при переході з одного ребра на інше. Якщо перехід здійснено до ребра з того ж самого комплекту, що й попереднє, то функція штрафів приймає нульове значення. Якщо ж у даній вершині перехід здійснено на ребро із іншого комплекту, то функція штрафів приймає значення, яке у загальному випадку залежить від номерів комплектів ребер і від номера вершини.
В пристосуванні до пошуку оптимального маршруту слідування аварійно-рятувальної техніки значення функції штрафів можна брати рівним середньому часу, що витрачається на поворот.
Використання алгоритму оптимізації передбачає наявність двох вершин графа, між якими і визначається оптимальний маршрут. Така ситуація в пристосуванні до пошуку оптимального маршруту слідування аварійно-рятувальної техніки дещо відрізняється від реальної, оскільки ні місце розташування об’єкту, ні місце дислокації пожежної частини, як правило, не співпадають з перехрестями вулиць міста. Дана проблема вирішується шляхом попереднього утворення постійних або тимчасових штучних перехресть.
В місцях розташування пожежних частин передбачають постійні штучні перехрестя. В місцях розташування об’єктів штучні перехрестя мають створюватись тимчасово в момент надходження відповідного виклику. При цьому можна вибрати один із трьох варіантів:
- використання відомих координат об’єкту, що вимагає попередньої підготовки надмірної кількості даних;
- орієнтовне визначення координат об’єкту шляхом лінійного інтерполювання номерів будинків, розташованих на перехрестях;
- приписування об’єкту найближчого з двох перехресть, між якими він знаходиться.
Штучні перехрестя доцільно використовувати також в наступних випадках:
- при нерівномірному розташуванні будинків вздовж вулиці або при їх відсутності;
- на непрямих вулицях, рух вздовж яких пов’язаний з поворотами;
- при тимчасових перекриттях вулиць.
В останньому випадку в місці тимчасового перекриття вулиці вводять відразу два штучних перехрестя, умовно не зв’язаних між собою. Зрозуміло, що проїзд через таке перехрестя стає формально неможливим.
Практична реалізація пошуку оптимальних маршрутів передбачає збір певного експериментального матеріалу для створення інформаційної бази задачі, а також розробку відповідного програмного забезпечення.
Інформаційна база задачі містить кодифікатор вулиць та провулків з вказівкою середньої швидкості переміщення, кодифікатор і реальні координати всіх перехресть та пожежних частин, а також дані про відповідність перехресть та вулиць з прив’язкою до номерів будинків по парні та непарній стороні.
При визначенні середньої швидкості переміщення слід враховувати рівень організації служби, кваліфікацію водіїв та їх ознайомленість з маршрутом, стан дорожнього покриття, інтенсивність вуличного руху, умови перебування в режимі чекання, погодні умови, час року і доби, а також тактико-технічні якості і умови експлуатації транспортних засобів.
До складу програмного забезпечення задачі оптимізації маршрутів слідування входять програма редагування баз даних та програма пошуку оптимального маршруту, яка включає додатковий блок перекриття вулиць.
Управління програмою пошуку оптимального маршруту передбачає два етапи: підготовчий та оперативний. На підготовчому етапі виконуються наступні операції: вказівка місця дислокації пожежної частини, налаштування друку, вибір належної інформаційної бази, а також встановлення або зняття перекриття вулиць у відповідності з отриманими даними.
Етап оперативної роботи з програмою реалізується при отриманні повідомлення про адресу об’єкту виникнення надзвичайної ситуації. При цьому спочатку здійснюється вибір відповідного йому перехрестя. А далі розв’язується задача пошуку найкращого шляху на графі між заданими вершинами із застосуванням алгоритму Дійкстри [2]. В результаті черговий караул в найкоротший термін отримує дорожній лист, що містить оптимальний маршрут слідування з елементами навігації.
Висновки. Аналіз математичного апарату теорії графів показав можливість його використання для розробки методики мінімізації терміну прибуття аварійно-рятувальної техніки до місця виникнення надзвичайної ситуації. Ідеальний граф математичної моделі транспортних магістралей міста не містить ізольованих вершин, не є повним, не є однорідним, є плоским, зв’язним і орієнтованим.
Пошук оптимального маршруту, який забезпечує мінімальний час переміщення між заданими перехрестями, доцільно проводити з використанням однієї і тієї ж середньої швидкості руху вздовж всієї вулиці, а також з врахуванням середніх значень втрат часу на поворотах.
Для реалізації пошуку оптимального маршруту необхідне використання таких нових понять як комплект ребер графа (ребер, що мають певну спільну ознаку), індекс ребра (для визначення належності ребра до того чи іншого комплекту), а також дискретна функція штрафів (для визначення розміру штрафу при переході з одного ребра на інше). У пристосуванні до графу, що являє собою математичну модель міста, до складу комплектів ребер мають входити ті ребра, що відповідають одній і тій же вулиці, індекс ребра являє собою порядковий номер комплекту, функція штрафів може бути задана як константа, рівна середньому часу, що витрачається на поворот.
Практична реалізація пошуку оптимального маршруту слідування можлива при умові утворення штучних перехресть в місцях розташування пожежних частин, в місці розташування об’єкту або шляхом умовного його перенесення в місце розташування найближчого перехрестя, в місцях розриву неперервної послідовності будинків, в місці повороту непрямої вулиці, в місці перекриття вулиці для проїзду.
Розроблене програмне забезпечення з точки зору оператора має три основні характеристики:
- шукає оптимальний маршрут слідування, для якого термін прибуття на об’єкт є мінімальним;
- при пошуку оптимального маршруту використовує такий алгоритм, що термін виконання потрібних обрахунків є мінімальним;
- управління роботою програми передбачено таким, що потрібні для її роботи дані можуть бути введені найпростішим шляхом в найкоротший термін.
СПИСОК ЛІТЕРАТУРИ
- Шаровар Ф.И. Автоматизированные системы управления и связь в пожарной охране. – М.: Радио и связь, 1987. – 304 с.
- Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2001. – 384 с.
Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2003. – 304 c.