Оценка временных параметров эвакуационных планов на основе оптимизационно - имитационной математической модели

О. А. Косоруков

ОЦЕНКА ВРЕМЕННЫХ ПАРАМЕТРОВ ЭВАКУАЦИОННЫХ ПЛАНОВ НА ОСНОВЕ ОПТИМИЗАЦИОННО - ИМИТАЦИОННОЙ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

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

Цель разработки - на основе опыта проведения эвакуаций населения, нормативных и рекомендуемых требований, разработать математическую модель, обеспечивающую планирование эвакуации населения.

Математический аппарат, используемый при моделировании

При построении и исследовании модели использовались математические постановки и результаты раздела прикладной математики «Исследования операций» в части задач анализа и синтеза коммуникационных сетей, а также методы и алгоритмы решения оптимизационных задач математического и, в частности, целочисленного программирования. Использовались также результаты теория вероятностей и техника имитационного моделирования. В качестве программного инструментария, сочетающего оптимизационные и имитационные подходы, используется программа RISKOptimizer компании PalisadeCorp. Для моделирования функционалов оценки времени движения по дугам сети используются самообучающиеся алгоритмы на основе технологии нейронных сетей реализованные в программе Deductor Professional компании BaseGroupLabs. Процесс моделирования гибко увязывается с инструментарием обработки географических данных фирмы ESRI программного продукта ArcDesktop с использованием модулей расширения SpecialAnalyst и NetworkAnalyst.

Анализ чувствительности математической модели

Модель должна предусматривать проведение анализа чувствительности характеристик эвакуационных мероприятий по входным параметрам модели:

- метеорологические условия;

- астрономические условия;

- параметры 1111 (расположение, привязка к СЭП, ожидаемая численность, прогнозируемые параметры плотности входного потока);

- структура коммуникационной сети (архитектура, топология и параметры пропускных способностей);

- параметры ПЭП (порядок вывода, численность эвакуируемых);

- параметры управления транспортными средствами (ТС) (распределение по колоннам, распределение колонн по 1111, маршрут движения колонн).

Содержание данных Название или обозначение

Информация необходимая для использования программы Network Analyst

Количество ПП. K

Количество эвакуируемых через каждый 1111 считаем априори заданными величинами Q1, ... ,Qk

Количество ПЭП Р

Количество транспортных колонн r

Количество машин в колоннах (от 1 до R) CRi ,.,CRr

Количество человек в машинах каждой из колонн Vi,.  ,Vr

Время прибытия колонн на приписанные 1111 от начала эвакуации (в минутах) TNi ,...,TNr

Время посадки, время высадки, время разворота, расстояние без заправки, время заправки Характеристики транспортных средств

Содержание данных Название или обозначение

Матрицы инцидентности коммуникационных сетей различных типов (от 1 до I) А|

Количество типов коммуникационных сетей I

Индексы вершин, являющимися площадками посадки (1111) О = {О, ,..., Ок}

Математические ожидания случайных величин, являющихся параметрами a функций переменных интенсивностей для различных 11 М 1а, ...., М ка

Стандартные отклонения случайных величин, являющихся параметрами a функций переменных интенсивностей для различных 1111 ^1а, ...., ^а

Математические ожидания случайных величин, являющихся параметрами Ь функций переменных интенсивностей для различных 11 М1ь, ... ., Мкь

Стандартные отклонения случайных величин, являющихся параметрами Ь функций переменных интенсивностей для различных 1111 ^1ь, ... ., ^кь

Коэффициенты корреляции между параметрами а и Ь (предполагаются положительными) Г1аЬ к аЬ

Индексы вершин, являющихся приемными эвакуационными пунктами (ПЭП) Т = {Г1, .,гр }

Индексы 11, к которым приписаны колонны (от 1 до К). О^,. ,ОКк

Матрица приписки эвакуируемых, которая показывает, в каком количестве из каждого 11 производится перевозка в каждый 1Э1 (возможно данное количество равно 0) W

Матрица порядка выполнения эвакуационного задания, в которой для каждого 11 представлен порядок вывоза эвакуируемых, если план содержит несколько 1Э1 V

Количество вершин в маршруте из 1 в ] (WІj Ф 0) Би

Массив вершин, которые идентифицируют маршрут из І в j (^ Ф 0) i - |« 1 '1,. ' , 1!30 = j

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

Алгоритм реализации модели

Коммуникационная сеть задачи, вообще говоря, является комбинированной, то есть состоящей из нескольких сетей различных типов. Основной является сеть автомобильных дорог. Объединение подсетей в единую комбинированную коммуникационную сеть происходит через смежные узлы, в которых могут происходить смена типа транспортных средств и перегрузки потоков. Структура каждой из подсетей задается матрицей инцидентности.

т

1

1 ( 0 1

Л

1. А =

І0

а.

-1

матрица инцидентности графа,

0 - дуга ] не содержит вершины I,

-1 - дуга ] заканчивается в вершине /, 1 - дуга ] начинается в вершине I.

Дуги имеют направления. Поэтому улица с двусторонним движением представляется парой дуг.

2. Некоторые вершины являются пунктами посадки (1111).

О = {О, Ок} - индексы вершин ПП, к - количество ПП.

*2

3. РД, 1 2) = - количество пришедших за период [ 11,12] на I-й

*1

ПП.

М(1) - интенсивность входного потока на 1-ом ПП в момент времени 1; это переменная величина, задаваемая случайными параметрами.

Вид функции М(1) схематично изображен ниже (имеет вид РБЯТ-распределения) и задается тремя параметрами а, Ь и С, которые являются связанными, т.к. общее количество пришедших известно.

Рис. 1 - Вид функции Л1

Таким образом, можно считать случайными величинами из них только а и Ь, например:

£а, ф - случайные величины (параметры функции переменной интенсивности).

Исходим из предположения, что ^а и ф две зависимые (положительная корреляция) нормально распределенные случайные величины с параметрами ца, оа и цЬ, оЬ.

Таким образом, параметры случайных величин, определяющих поток на 1111, образуют массив данных вида:

1 к

Ца ,. .., Ца

1 к

°а ,. .., °а

1 Ц Ь ,. к .., Ц Ь

1 к

^Ь ,. .., °Ь

4. Количество эвакуируемых через каждый 1111 считаем априори заданными величинами: 01,... ,0к.

5. Некоторые вершины являются приемными эвакуационными пунктами (ПЭП). Т = {г1,...,гр} - индексы вершин (ПЭП), р - количество ПЭП.

6. Каждый пункт посадки имеет эвакуационное задание, которое содержит информацию по:

• количеству эвакуируемых и местам вывоза (ПЭП);

• последовательности вывоза в различные ПЭП (если их несколько);

• маршрутам движения колонны.

А) Таблица 3 - Количество эвакуируемых

- количество эвакуаируемых из ПП с индексом ОI в ПЭП с индексом г]. р

При этом ^ WIj = 0|

]=1

Б) Таблица 4 - Порядок выполнения вывоза эвакуируемых

VII =0, если Wil=0, иначе VII - порядковый номер вывоза из ПП с индексом О1 в ПЭП с индексом г].

В) Для любой пары индексов (I, ]): Wi] Ф 0 известен маршрут вывоза: ву - количество вершин в маршруте из I в ] и массив вершин I = II , ..., ] = ],

которые идентифицируют данный маршрут.

Таким образом, структуры данных А), Б) и В) полностью описывают эвакуационный план ПП.

7. Для оценки временных показателей эвакуационного плана необходимо производить оценку времени движения отдельной колонны по конкретной дуге предписанного маршрута.

Время прохождения колонны по дуге ] зависит от свойств дуги, от ее загруженности ранее прибывшими колоннами и от времени прихода Ю данной колонны в начало дуги ].

Информация о ранее прибывших колоннах отражается в виде двух массивов:

П, ., - времена поступления колонн в начало дуги ];

т1, ., тК - время прохождения колонн по дуге ].

Таким образом, мы предполагаем, что нам известен некоторый набор функций, вообще говоря, различных для каждой дуги

Р] (11',., 1^, т1', ..., тК', Ю), которые определяют время прохождения дуги колонной, прибывшей в момент Ю при заданной предыстории. Возможные варианты этих функций будут рассмотрены далее.

В более детализированном варианте функции Р] зависят от некоторых внешних факторов, как то: время суток; время года; погодные условия; загруженность неэвакуационным транспортом; ситуации аварий или иных источников полных или частичных заторов.

Некоторые из них целесообразно рассматривать как случайные величины (входы имитационной модели).

Принципиальная схема алгоритма решения

В данной модели предполагается, что заданны эвакуационные планы по всем ПП, транспортные ресурсы распределены, законы поступления людей на ПП известны.

В качестве основных выходных параметров модели рассматриваем

Т1, ., Тк - время окончания эвакуации на каждом ПП и общее время эвакуации Т,

где

Т = тахТ

1<<к I,

являющаяся основным критерием эвакуационного плана.

Таким образом, данная модель позволяет оценить качество эвакуационного плана по критерию «время проведения эвакуации» (Т).

Предполагается, что транспортные ресурсы функционируют в циклическом режиме (возвращаются на предписанную ПП) и не перераспределяются динамически в процессе реализации эвакуационного плана.

Особенности реализации

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

Рассмотрим следующую систему управляющих таблиц.

Номер Время Признак Дуга

1 300 1 5

К 374 1 3

номер очередной дуги маршрута

признак 0-колонна закончила работу, 1-работает

/ время выхода на очередную дугу маршрута (мин) номер колонны

К - количество колонн;

т - количество дуг коммуникационной сети.

Таблица 4 -

1 ... у ...

1

і ... а ...

т

Таблица 4 показывает в маршруты каких колонн входит отдельно взятая дуга (матрица инцидентности дуг по отношению к маршрутам колонн).

а

0 _ если текущий маршрут]-й колонны

не проходит через дугу I,

1 _ если проходит.

1 ... у ...

1

і ... Ьц ...

т

Табл. 5 отображает графики прибытия колонн в вершины коммунальной сети.

0, если Эц (табл. 4) или] колонна еще не двигалась по дуге І,

- последнее время начала движения колонныЦ по дуге І

Таблица 6 -

1 ... у ...

1

і ... Тц ...

т

Табл. 6 содержит времена прохождения колон по дугам коммунальной сети.

0, если а=0 (табл. 4) или колонна] еще не двигалась по дуге I,

- последнее время прохождения колонной } дуги I

Схема реализации алгоритма представлена на рис.2.

Рис. 2 - Схема реализации алгоритма

Задачи по корректировки плана эвакуации и способы их решения

Используя Модель в качестве базовой, рассматривается серия экстремальных задач для выбора оптимальных параметров плана эвакуации.

Параметрами оптимизации являются:

• распределение транспортных средств по колоннам;

• распределение колонн по площадкам посадки (ПП);

• размещение ПП;

• определение зон обслуживания для ПП;

• выбор пунктов эвакуации (ПЭ);

• размещение эвакуируемых по ПЭ;

• определение порядка выполнения плана эвакуации для каждого ПП;

• определение маршрутов эвакуационных колонн.

Базовым инструментом для решения поставленных оптимизационных задач является программа Ы8КОрйт12ег, сочетающая оптимизационные и имитационные подходы.

© О. А. Косоруков - канд. физ.-мат. наук, доц. ин-та экономики и финансов «Синергия».