Введение
Обеспечение пожарной безопасности современного мегаполиса только стационарными депо не всегда и не везде позволяет гарантировать 10-минутное нормативное время [1] прибытия к местам возможных возгораний. Ввиду постоянно изменяющейся обстановки стационарная дислокация пожарных депо не обеспечивает равномерного покрытия территории, несмотря на их научно обоснованную локацию [2, 3]. Дополнительное введение в систему обеспечения пожарной безопасности (СОПБ) мобильных пожарных расчетов (МПР), размещенных в определенных точках временного позиционирования (ТВП), гипотетически позволит динамически адаптировать систему к меняющейся обстановке. Однако эффективное позиционирование таких подразделений связано с необходимостью учитывать прогнозируемые риски возникновения пожаров [4, 5], реальные дорожные условия и ограниченность ресурсов.
Существующие подходы к решению задач размещения и перемещения (передислокации) подразделений зачастую используют упрощенные эвристики, не учитывающие динамику городской среды, либо ориентированы на детерминированные модели, неспособные адаптироваться к изменяющимся условиям. Интеграция с геоинформационными сервисами (ГИС) для получения актуальных данных о времени проезда и построения маршрутов либо отсутствует, либо носит фрагментарный характер, а применяемые алгоритмы не обеспечивают достаточной гибкости для учета неформализуемых ограничений и многокритериальности. В связи с этим возникает потребность в создании интеллектуального инструментария, который на основе единого методологического подхода объединял бы прогнозные модели, метаэвристические алгоритмы и адаптеры к внешним ГИС-сервисам, позволяя тем самым повысить обоснованность и оперативность управления мобильной компонентой гибридной СОПБ [6].
Цель исследования – интеллектуализация решения задачи оптимального позиционирования МПР для системы поддержки принятия решения (СППР) по управлению мобильной компонентой в составе гибридной СОПБ мегаполиса.
Материалы и методы исследования
Рассмотрим математическую постановку задачи на позиционирование МПР.
Сначала сформулируем задачу размещения. Пусть имеется территория мегаполиса, разбитая на элементарные ячейки (индекс i = 1,…, K); для каждой i-й ячейки известны:
– прогнозируемая вероятность возникновения пожара Pi (получена, например, методами машинного обучения [7]);
– минимальное время прибытия пожарных расчетов от всех L (или ближайших) стационарных депо Tistat (рассчитано ГИС-сервисом).
Также задано множество потенциальных ТВП размером N, в которых могут быть размещены МПР. Для каждой ТВП j и каждой ячейки i известно время прибытия tij (также из ГИС). Необходимо выбрать ровно M различных ТВП (M < N) для дислокации МПР таким образом, чтобы минимизировать некоторую глобальную целевую функцию F, характеризующую совокупный риск после передислокации (считается, что изначально МПР где-то размещены).
Для выбранного множества S ⊂{1,…, N}, |S| = M «новое» время прибытия в ячейку i определяется как
Интегральный спрос (риск) ячейки становится: 
Целевая функция может быть задана, например, как
– суммарный риск по всем ячейкам; или как
– максимальный риск; или иная агрегирующая функция. Без ограничения общности будем считать, что требуется минимизировать суммарный риск.
Задача является NP-трудной комбинаторной оптимизацией, исключающей возможность применения точных методов (полный перебор, методы целочисленного линейного программирования) за приемлемое время, поэтому для ее решения автором предлагается использовать генетические алгоритмы (ГА). С учетом анализа альтернатив (классические и метаэвристики), ГА предлагают наилучший баланс между качеством решения, скоростью и гибкостью для данной задачи.
Для перемещения МПР на целевые ТВП решается задача назначения, постановка которой для данной предметной области (логистика МПР) формулируется следующим образом.
Пусть R = {1, 2,…, M} – множество МПР, подлежащих перемещению на множество целевых ТВП T = {1, 2,…, M}, полученных в результате решения задачи размещения.
Для каждого МПР i ∈ R известна его текущая позиция (точка временной дислокации), а для каждой пары (МПР i, ТВП j) задана стоимость перемещения cij ≥ 0, которая может выражать расчетное время в пути (с учетом дорожного трафика), расстояние или иные затраты.
Требуется найти биекцию (перестановку) π, минимизирующую сумму ci,π(i), то есть:
,
где SM – множество всех перестановок чисел от 1 до M, а π(i) – номер ТВП, назначаемой МПР с индексом i. Результатом решения является матрица назначений [xij], на основе которой формируются индивидуальные задания для каждого МПР.
При переходе к бинарным переменным xij ∈ {0, 1} с условиями, что каждый МПР должен быть назначен ровно на одну ТВП (& vv), т.е.
,
получаем стандартную форму задачи о назначениях:
,
которая точно решается за полиномиальное время венгерским алгоритмом.
Однако венгерский алгоритм не предназначен для работы с несколькими независимыми критериями одновременно, а при наличии сложных нелинейных или неформализуемых ограничений (например, учет динамически меняющегося трафика, приоритетов, временных окон, запретов, T > R), задача также становится NP-трудной, и для ее решения целесообразно применять метаэвристики, включая ГА [8], что обосновано стратегическими целями создания интеллектуальной СППР. Использование единого методологического подхода на обоих этапах решения задачи оптимизации позиционирования МПР упрощает разработку, сопровождение и развитие системы (один фреймворк, одна библиотека).
Покажем решение задач размещения/перемещения МПР с использованием ГА.
Результаты исследования и их обсуждение
Формирование «сквозного» примера
Интеллектуальное (с использованием ГА) решение задачи позиционирования МПР покажем на «сквозном» примере, для чего определим оптимальное (рациональное) соотношение стационарной и мобильной компоненты в составе СОПБ мегаполиса. Воспользуемся авторской имитационной моделью (ИМ) [9, 10], которая, используя данные от геоинформационного сервиса «Яндекс Карты», позволяет для каждой ячейки «цифровой сетки» мегаполиса рассчитать минимальное время прибытия в ее «центр» пожарных расчетов, а также вычислить долю ячеек, для которых время не превышает установленный норматив (в РФ это 10 мин) – покрытие территории. К существующим стационарным депо (в количестве 50 единиц) в модель последовательно вводились МПР (количеством от 2 до 20): места для предполагаемых пожарных депо генерировались случайным образом, многократно (до 1000 итераций) имитируя интеграцию мобильной компоненты в существующую инфраструктуру СОПБ.
Результаты решения задачи прогнозирования на примере такого мегаполиса, как Санкт-Петербург, представлены на рис. 1, где красными треугольниками обозначены позиции стационарных депо, оранжевыми кружками – текущие позиции МПР, клетками различных оттенков синего – время прибытия в центр клетки ближайшего пожарного расчета, а окружностью красного цвета – точка «насыщения» логистической (S-образной) кривой.
Из графика видно, что точка М = 10 является естественным оптимумом: дальнейшее увеличение ресурсов дает незначительный эффект при линейном росте затрат.
Рис. 1. Результаты решения задачи прогнозирования: минимального времени прибытия пожарных расчетов в точку возгорания (слева) – с использованием ГИС; зависимости покрытия от количества МПР (справа) – с использованием ИМ Примечание: составлен автором по результатам данного исследования
Поэтому в дальнейшем с помощью ГА будем решать задачу позиционирования 10 МПР.
Генетический алгоритм для задачи оптимального размещения МПР
Ввиду того, что ГА широко и успешно применяются для решения задач размещения, в том числе и в данной предметной области [11, 12], а их блок-схема является устоявшейся и общеизвестной, то отметим здесь только ключевые отличительные и положительные «точки» применения ГА к задаче оптимального размещения МПР.
1. Кодирование решения (хромосома). Каждая особь (хромосома) кодирует одно допустимое решение – множество S из M выбранных ТВП. Так как порядок точек не важен, хромосома представляет собой вектор длины M, каждый элемент которого – идентификатор ТВП (целое число от 1 до N, где N пусть будет равно 50); все гены в хромосоме должны быть различны.
2. Функция приспособленности (фитнес-функция). Фитнес-функция явно включает прогнозный интегральный спрос Di(S), поэтому размещение оптимизируется не под равномерное покрытие и детерминированный спрос, а под взвешенную карту риска. Однако так как мы добавляем МПР к существующей инфраструктуре, то в фитнес-функции обязательно учитывается базовая защищенность Tistat стационарными депо.
3. Параметры алгоритма для M = 10, N = 50: размер популяции P = 100–300 (этого достаточно, чтобы охватить разнообразие решений); количество поколений Gmax 200–500 (при большем числе поколений улучшения становятся незначительными); вероятность мутации pm = 0,05–0,1 (поскольку хромосома состоит из 10 генов, мутация одного гена с вероятностью 0,1 дает разумное исследование пространства); турнирный отбор размера t = 2–3 (обеспечивает достаточное давление отбора без преждевременной сходимости); элитизм E = 1–3 лучшие особи гарантированно переходят в следующее поколение.
4. Особенности работы операторов: скрещивание («кроссинговер на основе объединения») – при M = 10 и N = 50 объединение двух родительских множеств дает в среднем около 15–18 уникальных точек (так как родители могут пересекаться), из этого объединения случайно выбирается 10 точек, что эффективно комбинирует генетический материал; мутация заменой (replacement/random mutation) – при замене одного гена необходимо убедиться, что новое значение не совпадает с остальными девятью; но так как N = 50, то вероятность случайно выбрать уже существующую точку невысока (≈ 9/49), и в случае коллизии можно просто повторить выбор.
5. Вычислительная сложность. Вычисление фитнес-функции требует для каждой особи расчета F(S) по всем K ячейкам (например, если мегаполис разбит на километровые квадраты, то K может быть порядка тысяч: Москва – 2561,5 км², Санкт-Петербург – 1439 км²). Общее время на поколение O(P∙K∙M) – это примерно 4–5 миллионов операций на поколение; вся эволюция из 500 поколений на современных компьютерах займет несколько минут. При усложнении задачи ГА может быть распараллелен [13] и давать приемлемые решения за разумное время, особенно если М не слишком велико (до нескольких десятков).
Генетический алгоритм для задачи назначения МПР на целевые ТВП
Процесс перемещения МПР к новым местам дислокации подразумевает решение соответствующей задачи выбора целевых ТВП для каждого из расчетов. Подобная задача в работе [14] была сведена к оптимизационной, решаемой с помощью ГА; при этом количество объектов и мест для их дислокации было одинаковым и равнялось 10. Рассмотрим применение ГА для назначения МПР на целевые ТВП с таким же количеством, а также расширенный вариант задачи, когда имеется 12 ТВП, каждая из которых имеет собственный вес важности, влияющий на приоритет для размещения.
1. С точки зрения ГА кодирование решения (то есть хромосома) может быть представлено как последовательность чисел (в данном случае, длиной M = 10), индекс которых соответствует определенному МПР, а значение – целевой ТВП. Таким образом, каждый ген хромосомы определяет место дислокации МПР (требуемое) и может принимать значения 10 (для основной задачи) или 12 (для расширенной с весами). При этом условием корректности хромосомы является уникальность значений ее генов, поскольку МПР должны иметь разные целевые ТВП. Форма записи аналогична используемой при решении задачи оптимального размещения МПР с тем отличием, что их порядок в хромосоме строго задан.
2. Функция приспособленности оценивает, насколько выбранное решение (то есть назначение каждому МПР своей ТВП) «удачно» в том смысле, что все пожарные расчеты с учетом логистики мегаполиса и его дорожной обстановки смогут достичь мест дислокации за минимально возможное время; формальная запись такой минимизируемой целевой функции имеет следующий вид:
3. 
.
4. При решении расширенной задачи целевая функция может быть также расширена с учетом нарушений весовых ограничений путем добавления соответствующего слагаемого –
,
где penaltyi – штраф за нарушение.
При Т = 12 фитнес-функция должна учитывать два фактора – затраты на перемещение (минимизация) плюс важность выбранных ТВП (максимизация суммарного веса занятых позиций). Здесь возможны несколько способов комбинирования: аддитивная свертка с весовым коэффициентом, штраф за неиспользование «важных» ТВП, двухкритериальный подход и ранжирование по важности, – но в любом случае фитнес-функция обязательно изменяется по сравнению со случаем без весов.
3. Параметры алгоритма для M = 10, Т = 10(12). При M = 10 и T = 12 пространство поиска содержит 12! / 2! ≈ 2,4×108 вариантов (против 10! = 3.6×106 при T = 12), что больше, но все еще обозримо для ГА. Поэтому параметры можно оставить близкими к прежним (см. ГА для размещения), возможно слегка увеличив размер популяции и количество поколений.
4. Особенности работы операторов. Для случая M = 10 и Т = 10 решается задача биекции, и поэтому для скрещивания предлагается использовать специализированный оператор для перестановок, например, PMX (частично отображаемый кроссинговер) или OX (порядковый); для M = 10 и Т = 12 PMX не подходит, так как хромосома не является перестановкой всех 12 элементов, а лишь выборкой 10 из 12, поэтому оптимальным здесь является union crossover (как для задачи размещения). Для случая M = 10 и Т = 10 применяется обменная мутация (swap mutation) – случайным образом выбираются две позиции в хромосоме, и их значения меняются местами, что сохраняет свойство перестановки и вносит локальные изменения; для M = 10 и Т = 12 используется заменяющая мутация (replacement mutation) – случайно выбирается позиция в хромосоме, и ее значение заменяется на другое число от 1 до 12, не присутствующее в текущей хромосоме. Это гарантирует уникальность всех генов.
5. Вычислительная сложность. Вычисление фитнес-функции для одной особи потребует O(M) операций (суммирование 10 затрат, а при T > M еще и 10 весов). При установленных выше параметрах алгоритма общее число операций составит порядка нескольких миллионов, что незначительно для современных вычислительных средств. Для сравнения, венгерский алгоритм имеет сложность O(M3) = 1000 операций, но его применение, как уже отмечалось, не обеспечит преемственность и гибкость интеллектуальной СППР.
Таким образом, при M = 10, N = 50 и Т ≥ 10, ГА с указанными параметрами гипотетически эффективно решают задачу позиционирования МПР.
Проверка работоспособности интеллектуальной СППР
Произведем проверку работоспособности СППР, использующей описанные выше ГА для решения задачи позиционирования МПР. Ее прототип реализован как интегрированное Python-приложение с модульной архитектурой. Модули СППР и информационные потоки между ними подробно описаны в авторской статье [15]; здесь же упрощенно покажем только функционал контура управления позиционированием МПР, обращение к которому осуществляется через графический интерфейс.
Основу интерфейса составляет использование библиотеки Tkinter, оперирующей различными графическими элементами, их гибким размещением и обработкой действий пользователя. Пользовательское окно состоит из трех следующих областей: вводимые пользователем данные – количество стационарных депо, ТВП и МПР; «тепловая» карта пожаров с нанесением стационарных депо, ТВП и маршрутов следования МПР; лог работы ГА при решении оптимизационных задач размещения и назначения. «Тепловая» карта представляет собой сетку (ассоциируемую с частью мегаполиса), ячейки которой имеют цвета в зависимости от вероятности возникновения пожара, рассчитываемого (в текущей версии прототипа) на основе нормального распределения. Координаты стационарных депо соответствуют их реальному размещению для Санкт-Петербурга, которые могут быть получены автоматически из внешнего ГИС-сервиса (в онлайн-режиме). Для получения оптимального пути следования расчетов между ячейками городской сетки используется разработанный ранее программный модуль [16], а также информация о дорожной обстановке, которая может быть получена из ГИС-сервиса [17] (например, Яндекс Навигатор).
Рис. 2. Результаты решения задачи размещения (слева) / перемещения (справа) МПР с использованием ГА Примечание: составлен автором по результатам данного исследования
Прототип работает в трех режимах, последовательно вызываемых пользователем. В первом производится генерация точек на сетке, в ячейках которой размещаются стационарные депо, ТВП и находящиеся в них МПР; производится визуализация результатов на карте. Во втором решается задача по новому размещению МПР с использованием соответствующих формы хромосомы и фитнес-функции; выбранные для размещения ТВП помечаются соответствующим образом. В третьем решается задача по назначению ТВП для каждого МПР при новых формах хромосомы и фитнес-функции; полученные в результате маршруты следования МПР от текущих ТВП к целевым также отображаются на карте.
Такая архитектура обеспечивает гибкость, наглядную демонстрацию предложенных методов и возможность независимой модификации отдельных модулей (например, замены источника данных о времени или ГИС-провайдера) для дальнейших исследований.
Результаты решения задачи позиционирования МПР с использованием ГА представлены на рис. 2, где зелеными кружками показаны целевые ТВП, а ломаными белыми линиями – оптимальные маршруты следования.
Результаты, полученные с использованием ГА на примере Санкт-Петербурга, доказывают их применимость для решения задачи позиционирования МПР в составе интеллектуальной СППР по управлению мобильной компонентой СОПБ мегаполиса.
Заключение
Таким образом, интеллектуализация СППР по управлению мобильной компонентой в составе гибридной СОПБ мегаполиса достигнута за счет адаптации ГА к решению задачи позиционирования МПР. Тем самым доказана возможность применения единого метаэвристического подхода для согласованного решения взаимосвязанных задач размещения и оперативного назначения МПР на целевые ТВП. Новизна предложенного решения заключается в расширении аппарата оптимизации логистики пожарной охраны с интеграцией прогнозных рисков и геоинформационных данных, а его практическая значимость подтверждена работоспособностью прототипа СППР. Перспективы дальнейших исследований связаны с распараллеливанием алгоритмов, интеграцией дополнительных критериев (приоритетность объектов, дорожные пробки в реальном времени и т. п.) и валидацией на реальных данных пожарного гарнизона.
Конфликт интересов
Финансирование
Библиографическая ссылка
Ахунова Д. Г. АЛГОРИТМЫ ИНТЕЛЛЕКТУАЛЬНОЙ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЯ НА ПОЗИЦИОНИРОВАНИЕ МОБИЛЬНЫХ ПОЖАРНЫХ РАСЧЕТОВ // Современные наукоемкие технологии. 2026. № 4. С. 19-25;URL: https://top-technologies.ru/ru/article/view?id=40724 (дата обращения: 10.05.2026).
DOI: https://doi.org/10.17513/snt.40724