Блощицкий В. П., Казакова Ю. С., Мартыненко Т. В. Определение оптимального пути следования пожарного расчета к месту пожара с помощью эволюционных вычислений

ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ПУТИ СЛЕДОВАНИЯ ПОЖАРНОГО РАСЧЕТА К МЕСТУ ПОЖАРА С ПОМОЩЬЮ ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ

Блощицкий В. П., Казакова Ю. С., Мартыненко Т. В.
Донецкий национальный технический университет, г. Донецк
кафедра автоматизированные системы управления
Основные положения

Источник: Наукові праці Донецького національного технічного університету. Серія: «Обчислювальна техніка та автоматизація», Донецьк: 2010. – випуск 16(131).

Аннотация
Блощицкий В. П., Казакова Ю. С., Мартыненко Т. В. Определение оптимального пути следования пожарного расчета к месту пожара с помощью эволюционных вычислений. Проанализированы факторы, влияющие на продолжительность движения пожарного расчета к месту пожара. Предложена модель представления транспортных магистралей города на основе теории графов. Разработан алгоритм определения оптимального пути следования пожарного расчета к месту пожара на основе эволюционных вычислений: определена fitness-function, модифицированы операторы селекции, кроссовера.
Ключевые слова: пожарное подразделение, модель, транспортная магистраль, оптимальный путь, граф, хромосома, выборочная совокупность, кроссовер.

Анотація
Блощицький В. П., Казакова Ю. С., Мартиненко Т. В. Визначення оптимального маршруту слідування пожарного розрахунку до місця пожежі за допомогою еволюційних обчислень. Проаналізовано фактори, що впливають на тривалість руху пожежного розрахунку до місця пожежі. Запропоновано модель представлення транспортних магістралей міста на основі теорії графів. Розроблено алгоритм визначення оптимального маршруту слідування пожежного розрахунку до місця пожежі на основі еволюційних обчислень: визначена fitness-function, модифіковані оператори селекції, кроссовера.
Ключові слова: пожежний підрозділ, модель, транспортна магістраль, оптимальний маршрут, граф, хромосома, вибіркова сукупність, кросовер.

Abstract Bloshchitsky V., Kazakova J., Martynenko T. Determination of the optimal transit of a fire-fighting crew to a place of a fire by means of evolutionary computation. The factors influencing duration of movement of a fire-fighting crew to a place of a fire are analyzed. The model of representation of the arterial road of a city on the basis of graph theory is offered. The algorithm for definition of an optimal transit of a fire-fighting crew to a place of a fire on the basis of evolutionary computation is developed: fitness-function is determined, operators of selection and crossover are modified.
Keywords: fire subdivision, model, transport highway, optimal way, graph, chromosome, selective aggregate, crossover.

Постановка проблемы. Одним из основных направлений совершенствования управления пожарными подразделениями является применение компьютеризированных систем поддержки принятия решений. Эти системы должны оказать помощь лицам принимающим решение (диспетчерам) в управлении пожарными подразделениями на всех этапах реагирования на вызовы от населения. Системы поддержки принятия решений повышают качество обработки информации, проводят информационно-аналитическую работу и предлагают научно-обоснованные управленческие решения.
Важным этапом при реагировании на сообщение о пожаре является определение маршрута следования к месту пожара, который обеспечит минимальное время прибытия, так как при ликвидации пожаров именно время является решающим фактором, влияющим на масштабы последствий.
Целью работы является решение задачи оптимизации выбора маршрута следования пожарной техники, при этом наилучшим является маршрут с минимальным временем прибытия к месту пожара. Для достижения этой цели необходимо решить следующие задачи:
- проанализировать факторы, которые влияют на продолжительность движения пожарного расчета к месту пожара;
- определить модель представления транспортных магистралей города;
- определить метод поиска оптимального пути следования пожарного расчета.
Постановка задачи. Маршрут следования пожарного расчета – это последовательность улиц и проулков между определенной пожарной частью и объектом пожара. Тогда предлагается представить маршрут в виде набора перекрестков, которые должен проехать пожарный расчет, т. е. в виде вектора X=(p₀, p₁, p₂, …, p_n), где
p₀ – начальный перекресток (расположение пожарного расчета);
p_n – конечный перекресток (расположение объекта пожара);
p_i – перекресток дороги, (i ∈ 1, n);
n – количество перекрестков на пути.
Обоснование выбора маршрута выезда пожарного автомобиля осуществляется исходя из критерия минимизации времени прибытия личного состава и пожарно-технического вооружения на место пожара. При этом на время проезда влияет ряд факторов: длина пути, загруженность дорог и т. д.
Следовательно, необходимо найти маршрут, время движения по которому будет минимальным.
Модель представления транспортных магистралей города предлагается построить на базе применения методов теории графов. Информация о транспортных магистралях города представляется следующим образом: перекрестки улиц – вершины графа, а сами улицы и проулки – его ребра [1] (рис 1).

Рис 1 Модель представления транспортных магистралей города

Маршрут следования на графе – конечная последовательность ребер графа d₁, d₂, …, d_n из вершины p₀ в p_n , если существует последовательность p₀, p₁, …, p_n из n+1 вершин, таких, что каждая пара вершин p_i-1 и p_i для i=1…n инцидентна ребру d_i [2].
Граф, описывающий улично-дорожную сеть должен обладать следующими свойствами [1]:
- не иметь изолированных вершин (недостижимых перекрестков);
- являться связным (из любого перекрестка можно добраться в любой перекресток);
- являться ориентированным (на некоторых улицах возможно только одностороннее движение);
- являться плоским (при пересечении двух улиц всегда существует перекресток);
- являться взвешенным (каждый улица или проулок имеют свою характеристику: длину, загруженность транспортными средствами и т.д.);
- не являться однородным (от различных перекрестков может отходить разное количество улиц);
- не являться полным (каждый перекресток связан с небольшим количеством улиц).
Модель представления транспортных магистралей города не является статической. В модели необходимо предусмотреть возможность оперативного добавления или исключения вершин и ребер, так как периодически в городе идет ремонт участков дороги, проводятся различные массовые гражданские мероприятия, вследствие которых движение на улице может быть перекрыто, а также движение по улице может быть временно невозможным из-за строительных работ, последствий стихийных бедствий, пробок.
Определение маршрута следования предполагает наличие двух вершин – начальной и конечной, между которыми необходимо найти оптимальный путь. Поскольку место расположения пожарной части и объекта пожара не совпадает с определенными перекрестками улиц города, то предлагается создавать постоянные и временные искусственные перекрестки (узлы графа) [1]. Постоянные перекрестки отображают расположение пожарных частей. На месте объекта пожара – временные искусственные перекрестки. При этом используются известные координаты объектов. На рисунке 2 показан пример добавления искусственных перекрестков: перекресток 0 – расположение пожарной части, перекресток 20 – расположение места пожара.
Искусственные перекрестки также можно использовать при временном перекрытии движения по улице. При этом создаются два перекрестка, не связанных между собой, и движение через такой перекресток становится невозможным.

Рис 2 Добавление искусственных перекрестков

Определение оптимального пути следования пожарного расчета к месту пожара с помощью эволюционных вычислений. Задача определения оптимального пути принадлежит большому множеству задач, называемых «NP-полными» (недетерминистски полиномиальными). Наиболее точное решение для NP-полных задач может быть получено с помощью метода полного перебора, однако он практически неосуществим для большого числа данных. На практике используются эвристические и метаэвристические методы, заменяющие исчерпывающий поиск приближенным, что позволяет получить быстрое решение при умеренном проигрыше результата [3]. При выборе метода решения задачи поиска оптимального пути пожарного расчета критерием является точность решения и скорость выполнения алгоритма, так как определение маршрута выполняется в критической обстановки и от правильности решения зависит количество жертв и размер ущерба от пожара. Для определения оптимального маршрута пожарной техники и личного состава предлагается использовать эволюционные вычисления, они дают хорошую точность и время выполнения.
Эволюционные вычисления – это метод оптимизации, основанный на эволюции популяции особей, в процессе которой определяется наилучшее значение целевой функции.
Для применения эволюционного алгоритма к данной задаче необходимо определить:
- структуру хромосомы;
- процедуру генерации выборочной совокупности;
- оператор селекции;
- оператор кроссовера;
- оператор мутации;
- стратегию отбора.
Хромосома (особь) – это маршрут следования пожарного расчета от пожарной части к месту пожара [4], он представляет собой набор перекрестков (вершин графа):

X = {p₀, p₁, p₂, … , p_n}

(1)

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

H = {X1, X2, ..., Xm},

(2)

где m – количество элементов выборочной совокупности.
Для формирования хромосомы выбираются начальный и конечный перекрестки. Затем необходимо найти ациклический путь между начальным и конечным перекрестками (т. е путь на графе между вершинами p₀ и p_n).
Для каждой хромосомы вычисляется значение фитнесс-функции (fitness-function).
Оператор селекции осуществляется на основе «колеса рулетки».
Например, в результате выполнения оператора селекции выбраны два маршрута следования: X₁={0,2,3,6,10,11, 20}, X₂={0, 2,5,9,10,13,17,18,20} (рис. 3).

Рис 3 Пример выполнения оператора селекции

Для пары выбранных хромосом с вероятностью V_c (для данной задачи V_c выбирается в пределах [0,5..0,8]) осуществляется кроссовер (создание потомков).
Для примера (рис. 3) результатом оператора кроссовера будут два вектора: Q₁={0,2,3,6,10, 13,17,18,20}, Q₂={0, 2,5,9,10, 11, 20} (рис. 4).
Для полученного потомка с вероятностью V_m (для данной задачи V_m выбирается в пределах [0,001..0,01]) необходимо выполнить оператор мутации, что позволяет избежать попадания в локальный оптимум [4].

Рис 4 Результат выполнения оператора кроссовера

Расширяется популяция за счет добавления новых, только что сформированных особей. Для сокращения популяции до исходного размера предлагается использовать элитный отбор. При этом элитные особи составляют 10% от выборочной совокупности.
Процесс заканчивается при выполнении одного из условий:
1) выборочная популяция состоит из одинаковых элементов;
2) достижение заданной точности, для всех хромосом отличие в значениях fitness-function не превышает заданного значения ε;
3) достижение популяцией определенного возраста (числа эпох).
Если выполняется второе или третье условие, то решением будет вектор с наименьшим значением целевой функции.
Выводы. В статье предложена модель дорожно-транспортной сети на основе методов теории графов. Разработан алгоритм определения оптимального пути пожарного расчета к месту пожара с помощью эволюционных вычислений. Разработана структура хромосомы, процедура генерации выборочной совокупности, модифицированы операторы селекции и кросовера в соответствии с предложенной моделью дорожно-транспортной сети.

Литература

Моргун О.М., Моргун Л.О. Комп’ютерна система оптимізації вибору маршрутів слідування аварійно-рятувальної техніки. // Пожежна безпека: теорія і практика – Выпуск №1’2008.
Харитонова, Е. В. Графы и сети: учебное пособие / Е. В. Харитонова. – Ульяновск: УлГТУ, 2006. – 92 с.
Скобцов Ю. А. Основы эволюционных вычислений: учебное пособие. – Донецк: ДонНТУ – 2008. 330 с.
Снитюк В.Е., Джулай А.Н. Эволюционный метод определения кратчайшего пути проезда пожарного расчета к месту пожара с оптимизированным пространством поиска. XII-th International Conference Knowledge-Dialogue-Solution June 20-25, 2006, Varna (Bulgaria).