Подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий
Задачі геометричного проектування (розміщення, компонування, покриття, розбиття) складаються з оптимізаційного відображення геометричної інформації про об’єкти відповідно до заданого критерію якості та обмежень....
Збережено в:
| Дата: | 2021 |
|---|---|
| Автори: | , , , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2021
|
| Назва видання: | Проблемы управления и информатики |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/208940 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий / В.В. Комяк, В.М. Комяк, К.Т. Кязімов, А.В. Панкратов, А.Н. Данилин // Проблемы управления и информатики. — 2021. — № 3. — С. 78–90. — Бібліогр.: 31 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-208940 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-2089402025-11-10T01:05:47Z Подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий Підхід до оцінки заповнюваності людьми мобільних засобів при аварійній евакуації з будинків An approach to assessing the occupancy of mobile units by people during emergency evacuation from buildings Комяк, В.В. Комяк, В.М. Кязимов, К.Т. Панкратов, А.В. Данилин, А.Н. Технические средства для измерений и управления Задачі геометричного проектування (розміщення, компонування, покриття, розбиття) складаються з оптимізаційного відображення геометричної інформації про об’єкти відповідно до заданого критерію якості та обмежень. Geometric design problems (placement, layout, covering, partitioning) involve the optimization mapping of geometric information about objects according to a given quality criterion and constraints. 2021 Article Подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий / В.В. Комяк, В.М. Комяк, К.Т. Кязімов, А.В. Панкратов, А.Н. Данилин // Проблемы управления и информатики. — 2021. — № 3. — С. 78–90. — Бібліогр.: 31 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208940 519.85 10.34229/1028-0979-2021-3-7 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Технические средства для измерений и управления Технические средства для измерений и управления |
| spellingShingle |
Технические средства для измерений и управления Технические средства для измерений и управления Комяк, В.В. Комяк, В.М. Кязимов, К.Т. Панкратов, А.В. Данилин, А.Н. Подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий Проблемы управления и информатики |
| description |
Задачі геометричного проектування (розміщення, компонування, покриття, розбиття) складаються з оптимізаційного відображення геометричної інформації про об’єкти відповідно до заданого критерію якості та обмежень. |
| format |
Article |
| author |
Комяк, В.В. Комяк, В.М. Кязимов, К.Т. Панкратов, А.В. Данилин, А.Н. |
| author_facet |
Комяк, В.В. Комяк, В.М. Кязимов, К.Т. Панкратов, А.В. Данилин, А.Н. |
| author_sort |
Комяк, В.В. |
| title |
Подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий |
| title_short |
Подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий |
| title_full |
Подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий |
| title_fullStr |
Подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий |
| title_full_unstemmed |
Подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий |
| title_sort |
подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2021 |
| topic_facet |
Технические средства для измерений и управления |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/208940 |
| citation_txt |
Подход к оценке заполняемости людьми мобильных средств приаварийной эвакуации из зданий / В.В. Комяк, В.М. Комяк, К.Т. Кязімов, А.В. Панкратов, А.Н. Данилин // Проблемы управления и информатики. — 2021. — № 3. — С. 78–90. — Бібліогр.: 31 назв. — рос. |
| series |
Проблемы управления и информатики |
| work_keys_str_mv |
AT komâkvv podhodkocenkezapolnâemostilûdʹmimobilʹnyhsredstvpriavarijnojévakuaciiizzdanij AT komâkvm podhodkocenkezapolnâemostilûdʹmimobilʹnyhsredstvpriavarijnojévakuaciiizzdanij AT kâzimovkt podhodkocenkezapolnâemostilûdʹmimobilʹnyhsredstvpriavarijnojévakuaciiizzdanij AT pankratovav podhodkocenkezapolnâemostilûdʹmimobilʹnyhsredstvpriavarijnojévakuaciiizzdanij AT danilinan podhodkocenkezapolnâemostilûdʹmimobilʹnyhsredstvpriavarijnojévakuaciiizzdanij AT komâkvv pídhíddoocínkizapovnûvanostílûdʹmimobílʹnihzasobívpriavaríjníjevakuacíízbudinkív AT komâkvm pídhíddoocínkizapovnûvanostílûdʹmimobílʹnihzasobívpriavaríjníjevakuacíízbudinkív AT kâzimovkt pídhíddoocínkizapovnûvanostílûdʹmimobílʹnihzasobívpriavaríjníjevakuacíízbudinkív AT pankratovav pídhíddoocínkizapovnûvanostílûdʹmimobílʹnihzasobívpriavaríjníjevakuacíízbudinkív AT danilinan pídhíddoocínkizapovnûvanostílûdʹmimobílʹnihzasobívpriavaríjníjevakuacíízbudinkív AT komâkvv anapproachtoassessingtheoccupancyofmobileunitsbypeopleduringemergencyevacuationfrombuildings AT komâkvm anapproachtoassessingtheoccupancyofmobileunitsbypeopleduringemergencyevacuationfrombuildings AT kâzimovkt anapproachtoassessingtheoccupancyofmobileunitsbypeopleduringemergencyevacuationfrombuildings AT pankratovav anapproachtoassessingtheoccupancyofmobileunitsbypeopleduringemergencyevacuationfrombuildings AT danilinan anapproachtoassessingtheoccupancyofmobileunitsbypeopleduringemergencyevacuationfrombuildings |
| first_indexed |
2025-11-27T01:55:46Z |
| last_indexed |
2025-11-27T01:55:46Z |
| _version_ |
1849906744382193664 |
| fulltext |
© В.В. КОМЯК, В.М. КОМЯК, К.Т. КЯЗИМОВ, А.В. ПАНКРАТОВ, А.Н. ДАНИЛИН, 2021
78 ISSN 0572-2691
ТЕХНИЧЕСКИЕ СРЕДСТВА
ДЛЯ ИЗМЕРЕНИЙ И УПРАВЛЕНИЯ
УДК 519.85
В.В. Комяк, В.М. Комяк, К.Т. Кязимов, А.В. Панкратов, А.Н. Данилин
ПОДХОД К ОЦЕНКЕ ЗАПОЛНЯЕМОСТИ
ЛЮДЬМИ МОБИЛЬНЫХ СРЕДСТВ
ПРИ АВАРИЙНОЙ ЭВАКУАЦИИ ИЗ ЗДАНИЙ
Ключевые слова: геометрический объект, геометрическая информация, раз-
мещение, конфигурационное пространство, обобщенные переменные, матема-
тическая модель, оптимизация.
Введение
Cинтез сложных систем, как правило, требует учета их пространственной
формы, метрических характеристик, а также ограничений на их размещение. В общем
случае синтез оптимальных конфигураций [1, 2] сложных систем связан с задача-
ми оптимизации размещения, компоновки, покрытия, разбиения пространствен-
ных объектов заданной формы. Это направление исследований относится к тео-
рии геометрического проектирования, основы которого заложены в [3], и связано
с математическим моделированием геометрических объектов и их взаимных от-
ношений [4–10].
Геометрическое проектирование имеет широкий спектр научных и практиче-
ских применений. Одним из важных практических подходов к исследованию это-
го направления является организация управляемой эвакуации людей из мест раз-
вития чрезвычайных ситуаций (ЧС), в том числе из зданий, за необходимое время,
рассчитываемое исходя из их объемно-планировочных решений. Для этого разра-
батываются научно-обоснованные планы эвакуации людей, включающие всевоз-
можные сценарии эвакуации из зданий, состоящие из моделирования движения
людских потоков по коридорам, лестницам, с помощью лифтов, индивидуальных
средств аварийной эвакуации и, наконец, если перечисленные выше средства пе-
рекрыты, из укрытия людей в специально-защищенных помещениях от опасных
факторов ЧС. При моделировании свободного движения потоков людей в качест-
ве модели человека используются эллипсы [11, 12]. Однако когда категория дви-
жения меняется и переходит в активную зону, плотность потока увеличивается.
В связи с этим рассматривают моделирование перемещения людей с учетом при-
родных деформаций тела человека [13].
В [13] тело человека представляется трехкомпонентной моделью с ограниче-
ниями, обеспечивающими условия склейки компонент модели в единый сложный
объект, и рассматривается подвижность тела в виде ограничений на соотношение
углов поворота, вытекающих из физических ограничений на взаимное положение
частей тела. В качестве примера рассматривают горизонтальные и вертикальные
вращения плечевого сустава. Исходя из вышесказанного трехкомпонентная мо-
дель человека представляется сложным объектом в результате объединения трех
Международный научно-технический журнал
«Проблемы управления и информатики», 2021, № 3 79
нежестко связанных эллипсов, один из которых (основной) осуществляет непре-
рывные трансляции и обороты, а два вспомогательных непрерывно вращаются в
допустимых пределах (по отношению к углу поворота основного) относительно
точек «склейки».
Следует отметить, что в каждый фиксированный момент времени при моде-
лировании движения потока людей наблюдается конфигурация размещения объ-
ектов с ограничениями, основные из которых — условия их взаимных непересе-
чений и размещения в области перемещений, а также может быть ряд дополни-
тельных технологических ограничений [12].
В данной работе рассматривается задача плотного заполнения сложными
объектами мобильных средств, которая возникает при аварийной эвакуации лю-
дей. Как сказано выше, такой объект может быть моделью человека, когда он ис-
пользует силовые действия для перемещения путем поворота как всего тела, так и
его частей, тем самым меняя свою пространственную форму. Эта модель может
использоваться как при моделировании активного движения людей в потоке, так
и для максимальной оценки количества людей в помещениях, в мобильных сред-
ствах эвакуации либо для получения оценки локальной плотности потока.
Рассматриваемая в работе задача относится к классу NP-сложных, так как за-
дачи оптимального размещения эллипсов NP-сложные [14]. Для решения задач
такого класса используются, как правило, эвристические алгоритмы. Разработка
эффективных алгоритмов, основанных на применении методов локальной и гло-
бальной оптимизации, требует построения адекватных математических моделей,
основанных на аналитическом описании отношений рассматриваемых объектов с
учетом их непрерывных трансляций и вращений.
Анализ последних исследований и публикаций
Верхняя оценка плотности упаковки эллипсов в контейнер получена в [14].
В работах [15, 16] для решения задач данного класса применяется метод дискрет-
ного элемента. Однако данный метод достаточно ресурсоемкий, что ограничивает
размерность пространства решения и количество используемых частиц. Матема-
тическая модель упаковки двух эллипсов исследуется в [17]. Эффективный чис-
ленный алгоритм для определения факта пересечения эллипсов приводится в [18],
там же исследуется влияние размеров эллипсов на плотность упаковки.
В [19] предлагается метод решения задачи упаковки эллипсов, допускающих
вращения, с использованием современных NLP-решателей (solvers), доступных в
GAMS. В настоящей статье приводится достаточно полный обзор литературы, по-
священный задачам упаковки эллипсов. Для аналитического описания условий
непересечения неориентированных эллипсов авторы используют идею разделяю-
щей прямой, предложенную в [20] для моделирования отношений кругов и вы-
пуклых многоугольников.
Задача оптимальной упаковки эллипсов, допускающих непрерывные враще-
ния, рассмотрена в [21, 22]. Для аналитического описания основных ограничений
размещения используются псевдонормализованные квази-phi-функции [23, 24].
В этих работах строится математическая модель в виде задачи нелинейного про-
граммирования. В [22] авторы смогли улучшить результаты по времени и значе-
нию функции цели для многих тестовых примеров, приведенных в [19].
В фундаментальном исследовании [25] рассмотрены вопросы упаковки как
эллипсов, так и эллипсоидов в различных выпуклых областях. При моделирова-
нии условий непересечения объектов исследуется два подхода: первый основан на
идее разделяющей прямой (плоскости) из [19], а второй [26] — на использовании
аффинных преобразований пространства , 2, 3.nR n Генерация «хороших» стар-
80 ISSN 0572-2691
товых точек и применение солвера Algencan [27] для решения задач нелинейного
программирования позволили авторам [25] улучшить большинство результатов
работы [19].
Однако запись в аналитическом виде условий непересечения каждой пары
эллипсов в перечисленных работах довольно громоздка и/или осуществляется с
помощью системы нелинейных неравенств. В [28] получено достаточно простое
выражение для аналитического описания отношений между эллипсами (непересе-
чения и расположения на минимально допустимом расстоянии) с использованием
предложенной новой квази-phi-функции.
В рассматриваемой работе предложен подход, основанный на математическом
моделировании отношений между эллипсами [11, 28] и построении phi-функций
для сложных объектов [29], представленных в виде объединения эллипсов с за-
данной системой ограничений. Данный подход позволил получить аналитическое
выражение для описания условий непересечения сложных объектов с изменяю-
щейся пространственной формой и представить задачу их оптимального разме-
щения в виде задачи нелинейного программирования для получения локально-
оптимальных решений задачи.
Цель публикации — разработка подхода к оценке заполняемости людьми
мобильных средств для эвакуации из зданий.
Постановка задачи и ее решение
Необходимо разместить в мобильное средство (область) согласно заданной
последовательности его заполнения максимальное количество людей (сложных
объектов) из заданного набора при выполнении условий их непересечения, раз-
мещения в нем и технологических ограничений.
Подход к решению задачи включает:
формирование пространственной конфигурации размещения сложных гео-
метрических объектов;
построение модели человеческого тела, учитывающей его природные де-
формации;
построение математической модели задачи, разработка метода решения
исходя из ее особенностей.
Формирование пространственной конфигурации размещения сложных
геометрических объектов. Как сказано выше, сформулированная задача отно-
сится к классу задач геометрического проектирования [3] и заключается в ото-
бражении w некоторого исходного множества элементов произвольной при-
роды в абстрактное множество Ω соответствующей структуры при выполнении
заданного набора ограничений , :w [1]. Такое отображение называется
конфигурацией и осуществляется в конфигурационном пространстве [1]. Рас-
смотрим эти понятия для сформулируемой задачи.
Конфигурационное пространство геометрических объектов базируется на
формализации понятия геометрической информации. Геометрическая информа-
ция ({ }, { }, { })g s u об эллипсе E включает в себя пространственную форму
{ },s его метрические характеристики { , }a b ( ,a b — полуоси эллипса) и пара-
метры размещения { }.u Будем задавать пространственную форму { }s геометри-
ческого объекта уравнением его границы в виде ( , ) 0,f где 2( , ) ,x y R а
( , )a b — константы, характеризующие его метрические свойства, назовем их
параметрами пространственной формы объекта .s
Свяжем с объектом E собственную систему координат, начало которой —
полюс объекта. При аффинных преобразованиях движение объекта изменяет по-
Международный научно-технический журнал
«Проблемы управления и информатики», 2021, № 3 81
ложение его собственной системы координат относительно неподвижной системы
координат пространства 2.R Для характеристики такого положения зададим па-
раметры размещения ( , , ),u x y ( , )v x y — вектор трансляции относительно
неподвижной системы координат, — угол поворота.
Cформируем конфигурационное пространство E объекта E с обобщен-
ными переменными: метрическими параметрами ( , )a b и параметрами разме-
щения ( , , ).u x y Тогда каждая точка ( , ) ( , , , , )g u a b x y конфигурацион-
ного пространства E определяет геометрический объект 2( ) .E g R
Осуществим параметризацию подмножеств { , , },i c l rS E E E {1, 2,..., }.ni I n
С помощью теоретико-множественных операций сформируем сложный объект
.i i i
i c l rS E E E∪ ∪ (1)
Назовем объекты , ,i i i
c l rE E E базовыми.
Пусть объект i
cE имеет форму ,i
cs метрические параметры ( , )i i i
c c ca b и
параметры размещения ( , , ).i i i i
c c c cu x y Объекты ,i i
l rE E имеют форму , ,i i
l rs s
метрические параметры ( , ),i i i
l l la b ( , ),i i i
r r ra b параметры размещения
( , , )i i i i
l l l lu x y и ( , , )i i i i
r r r ru x y соответственно.
Пусть 1 2{ , , ..., , ..., }i nS S S S — исходное множество геометрических
объектов с обобщенными переменными ( , ), , , ; 1, 2, ..., ,i i i
ii ii iig u ii c l r i n а
i
r{ , , },i i
c ls s s ni I , — множество возможных их пространственных форм (в дан-
ном случае эллипсов). Каждой точке ( )i
ii ig S соответствует параметризо-
ванный геометрический объект 2( ) .i
i iiS g R Конфигурационное пространство
будет иметь вид 1 2 ... nS S S с обобщенными переменными
( , , ),i i i
c l rg g g g 1, 2,..., .i n
С помощью теоретико-множественных операций сформируем сложный геометри-
ческий объект 1 2( , ,..., ,..., )p i nS P S S S S 1 2( ... ... ).p i nS S S S S∪ ∪ ∪ ∪ ∪ Опе-
ратор : pP S задает структуру сложного объекта. Тогда сложному объекту pS в
конфигурационном пространстве будет соответствовать параметризованный гео-
метрический объект 1 1 1 1 1 1
1( ) (( , , ),..., ( , , )) ( ( , , ),...р р n n n
c l r c l r c l rS g S g g g g g g P S g g g
..., ( , , )).n n n
n c l rS g g g
Определение 1 [1]. Отображение :w множества геометрических объ-
ектов 1 2{ , , ..., , ..., }i nS S S S в конфигурационное пространство , которое
удовлетворяет заданному набору ограничений , задает пространственную кон-
фигурацию геометрических объектов , 1, 2,..., .iS i n
Обозначим 0S конфигурационное пространство объекта 0S с обобщенны-
ми переменными 0 0
0 ( , ),g u и пусть 0 (0, 0)v — начало собственной непод-
вижной системы координат, 0 ( , ).L W
Пусть 0
0 ,S∪ аналогично вышеизложенному, сформируем конфигура-
ционное пространство
82 ISSN 0572-2691
0
0 1 2 ... .nS S S S
Введем понятие пространственной конфигурации размещения. Для формиро-
вания системы ограничений зададим на множестве объектов из 0 бинарные
отношения [1]:
а) непересечения {*}, т.е. ( ) * ( ),ji
i ii j iiS g S g если int ( ) int ( ) ,ji
i ii j iiS g S g∩
1, 2,..., ;ni j I n , , .ii c l r
б) включения { }, т.е. 0 0( ) ( ),i
i iiS g S g если 0 0int ( ) ( ),i
i iiS g S g 1, 2,..., .i n
Следует отметить, что int S — топологическая внутренность объекта.
Определение 2. Отображение 0 0:w задает конфигурацию размеще-
ния, если ( ) * ( ),ji
i ii j iiS g S g 0 0( ) ( ),i
i iiS g S g , ,ni j I , , .ii c l r
Построение модели человеческого тела, учитывающей его природные
деформации. Следует отметить, что на условие (1) накладываются дополнитель-
ные технологические ограничения: пары точек ,lG lg и ,rG ,rg отмеченные на
рис. 1, а, используются для «склеивания» компонент модели в единый cложный
объект S (см. рис. 1, а).
На рис. 1 приведена трехкомпонентная модель человеческого тела с ограниче-
ниями, которые обеспечивают: условия склейки компонент модели в единый объект
(а), ограничения на подвижность эллипса, моделирующего плечо человека (б).
а б
Рис. 1
Кроме условий склеивания, на взаимное положение эллипсов накладываются ог-
раничения на соотношение углов поворота, вытекающие из физических ограничений
на взаимное положение частей человеческого тела (рис. 1, б). Так, угол поворота r
эллипса rE не может быть больше, чем угол 1,с и меньше, чем 2 ,с где
с — угол поворота объекта cE (см. рис. 1, б). Соответственно, угол поворота l
эллипса lE не может быть больше, чем угол 2 ,с и меньше, чем 1.с
Вышеперечисленные технологические ограничения формализованы в [13]:
( ) ( ),l l l cg v G v (2)
( ) ( ),r r r cg v G v (3)
2 1,c r c (4)
1 2.c l c (5)
Замечание. Ограничения (2), (3) выбираются из антропологических данных
человека, что приводит к определению параметров ( , ), ( , ).l l l r r rv x y v x y Анало-
гично определяются метрические характеристики , ,i i i
с l r эллипсов , , ,i i i
с l rE E E
1, 2,..., .i n
H
O O
H
El Eс
vl
gl vc
Gl
gr
Gr Er
vr
c
1
2
Международный научно-технический журнал
«Проблемы управления и информатики», 2021, № 3 83
В связи с вышесказанным, обобщенные параметры рассматриваемой за-
дачи размещения представим в виде 1 1 1 1 1 2 2 2 2 2( , , , , , , , , , , ...c c c l r c c c l rg x y x y
..., , , , , ,..., , , , , ).i i i i i n n n n n
c c c l r c c c l rx y x y
Заметим также, что параметры , , 1, 2,..., ,i i
l r i n являющиеся переменными
задачи, определяют параметры пространственной формы сложных объектов ,iS
1, 2,..., .i n
Построение математической модели задачи, разработка метода решения
согласно ее особенностям. Необходимо определить оптимальную геометриче-
скую информацию, характеризующую рациональность размещения
* extr ( ),g F g (6)
где 1 1 1 1 1 1 1 1( , , , , , ..., , , , , , ..., , , , , ) ( , , , ...i i i i i n n n n n
c c c l r c c c l r c c c l r c l rg x y x y x y u
..., , , , ..., , , )i i i n n n
c l r c l ru u — исходная геометрическая информация в задаче раз-
мещения; F — отображение, которое превращает исходную геометрическую ин-
формацию g в оптимальную геометрическую информацию *.g
Иначе говоря, необходимо разместить согласно последовательности номеров
из m единиц в области 0S длиной L и шириной W максимальное число слож-
ных объектов (и найти соответствующий вектор * 1 1 1( , , , ..., , , , ...i i i
c l r c l ru u
..., , , , )),n n n
c l ru n , представленных объединением трех нежестко связанных эл-
липсов , , ,c l rE E E из которых cE (основной) допускает непрерывные трансляции
и повороты, а два вспомогательных ( , )l rE E — непрерывные вращения в допус-
тимых пределах (по отношению к углу поворота основного) относительно точек
их склейки, с соблюдением условий непересечения объектов между собой, раз-
мещения их в области и технологических ограничений.
Таким образом, математическая модель представляется в следующем виде.
Необходимо найти
5 1
* *
( , ) ( )
( , ) arg max ( , )
n nt U R B
n (7)
либо
5 1( , ) ( )
( , ) max ,
n nt U R B
n
где
1 1 1( , , , ..., , , , ..., , , , ),i i i m m m
c l r c l r c l ru u u n 1 2 ( , ,..., , ..., ),i n
{0,1},i B ,n mi I I
*
0
1, если Ф ( , , ) 0,
0 в противном случае,
iS S i i i
c l r
i
u
5 1{( , ) :n nU t R B Ф ( , , , , , ) 0;i jS S ji i i j j
i j c l r c rlu u ,ni j I
*
0Ф ( , , ) 0;iS S i i i
i c l ru ( , , ) 0;i i i
i c l rT u },n mi I I (8)
где Ф ( , , , , , )i jS S ji i i j j
c l r c rlu u — Ф-функция объектов ( , , )i i i
i c l rS u и
( , , ),jj j
j c rlS u 2
0 0\ .S R S
84 ISSN 0572-2691
Следует заметить, что в математической модели (7), (8) неравенство
*
0 ( , , ) 0iS S i i i
c l rФ u обеспечивает размещение сложных объектов ( , , ),i i i
i c l rS u
,ni I в области 0,S дискретные переменные i показывают, находится ли объ-
ект ( , , )i i i
i c l rS u в области 0,S неравенство Ф ( , , , , , ) 0i jS S ji i i j j
c l r c rlu u га-
рантирует условие непересечения объектов ( , , )i i i
i c l rS u и ( , , )jj j
j c rlS u
,ni j I условие ( , , ) 0i i i
c l rT u обеспечивает «склейку» трех эллипсов: ос-
новного и двух вспомогательных, в сложный объект c ограничениями на углы по-
ворота вспомогательных эллипсов [13], * *( , ),g n *g — оптимальная геомет-
рическая информация (6).
Однако запись в аналитическом виде условий непересечения каждой пары
эллипсов, составляющих сложный объект, с помощью Ф-функций довольно гро-
моздка и/или осуществляется с помощью системы нелинейных неравенств, по-
этому в данном исследовании, как и в работе [11], в качестве эффективного сред-
ства математического моделирования отношений непересечения пары эллипсов
предлагается использовать функцию из класса квази-phi-функций.
Согласно определению [22, 23], квази-phi-функцией Ф i jE E ( , , )i j iju u t для
объектов ( )i iE u и ( )j jE u называется всюду определенная непрерывная по всем
переменным функция, для которой функция max Ф ( , , )i j
m
ij
E E
i j ij
t R
u u t является
phi-функцией объектов ( )i iE u и ( ).j jE u Здесь ijt — вектор вспомогательных
переменных, принадлежащих некоторому подмножеству U пространства mR (в
данном случае 1,m а совпадает с 1).R
Дальше используем такое важное свойство для квази-phi-функции: если для не-
которого ijt выполняется Ф ( , , ) 0,i jE E
i j iju u t то int ( ) int ( )i i j jE u E u∩ [11].
Как известно, для двух сложных объектов
1
( ) ( )
in
i i ik i
k
T u T u∪ и ( )j jT u
1
( )
jn
jm j
k
T u∪ квази-phi-функция Ф ( , , )i jT T
i j iju u t может быть записана в виде
Ф ( , , ) min{Ф ( , , ), 1,..., , 1,..., },i j ik jmT T T T
i j ij i j ijkm i ju u t u u t k n m n (9)
где ijt — вектор вспомогательных переменных , 1, ..., , 1, ..., .ijkm i jt k n m n
Запишем условие непересечения двух сложных объектов: ( , , )i i i
i c l rS u u u и
( , , ),jj j
j c rlS u u u в виде функции Ф ( , , , , , , ) 0.i jS S ji i i j j
c l r c r ijlu u u u u u t На основа-
нии (9) функция Ф ( , , , , , , )i jS S ji i i j j
c l r c r ijlu u u u u u t может бать представлена в виде:
1 2
3 4 5 6
7
Ф ( , , , , , , ) min{Ф ( , , ),Ф ( , , ),
Ф ( , , ),Ф ( , , ),Ф ( , , ),Ф ( , , ),
Ф ( , , )
i j ci cj ci lj
ci rj li cj li lj li rj
ri cj
S S E E E Ej ji i i j j i j i
c l r c r ij c c ij c ijl l
E E E E E E E Eji j i j i i j
c r ij l c ij l ij l r ijl
E E i j
r c ij
u u u u u u t u u t u u t
u u t u u t u u t u u t
u u t 8 9,Ф ( , , ),Ф ( , , )}.ri lj ri rjE E E Eji i j
r ij r r ijlu u t u u t
(10)
Международный научно-технический журнал
«Проблемы управления и информатики», 2021, № 3 85
Условия описания непересечения построенных объектов основываются на
описании условий непересечения эллипсов.
Исходя из [11], условия взаимного непересечения эллипсов ( )i iE u и ( )j jE u
описываются неравенством Ф ( , , ) 0,i jE E
i j iju u t где Ф ( , , )i jE E
i j iju u t — ква-
зи-phi-функция, которая записывается в виде
( , , ) ( ) cos ( )sini jE E
i j ij i j ij j i iju u t x x t y y t
2 2 2 2 2 2 2 2( ) cos ( ) ( ) cos ( ).i i i i ij j j j j ijb a b t b a b t (11)
Следует отметить, что квази-phi-функция (11) нормализована, т.е.
max Ф ( , , )i j
m
ij
E E
i j ij
t R
u u t — нормализованная phi-функция объектов ( )i iE u и
( ),i iE u и по значениям совпадает с расстоянием между объектами ( )i iE u и ( ).i iE u
Для формализации условий принадлежности объекта ( , , )i i i
i c l rS u u u
( ) ( ) ( )i i i i i i
c c l l r rE u E u E u∪ ∪ области 0S 0(S — прямоугольная область с верши-
нами 1 (0, 0),v 2 ( , 0),v L 3 ( , ),v L W 4 (0, ))v W воспользуемся нормализо-
ванной phi-функцией, которая построена на основании аналитического описания
условий принадлежности области 0S проекций объекта на оси глобальной систе-
мы координат.
Итак, объект ( , , ) ( ) ( ) ( )i i i i i i i i i
i c l r c c l l r rS u u u E u E u E u∪ ∪ принадлежит прямо-
угольной области 0 ,S если неотрицательная рhі-функция:
0 0
1,...,4
Ф ( , , , , ) Ф ( , , ) min (min( ( ))i iS S S Si i i i i i i i i i
c c c l r c l r kii ii
k ii
x y u u u f u
1, ..., 4
min (min( ( ), ( ), ( ))),i i i i i i
kc c kl l k r r
k
f u f u f u { , , }ii c l r (12)
выполняется
1 2
3 4
( ) ( ) , ( ) ( ) ,
( ) ( ) , ( ) ( ) ,
i i i i i i
i ii ii ii i ii ii ii
i i i i i i
i ii ii ii i ii ii ii
f u x a f u y b
f u L x a f u W y b
2 2 2 2 2 2 2 2( ) ( ) cos ( ) sin ( ) (( ) ( ) ) cos ,i i i i i i i i i
ii ii ii ii ii ii ii ii iia a b b a b
2 2 2 2 2 2 2 2( ) ( ) sin ( ) cos ( ) (( ) ( ) )sin .i i i i i i i i i
ii ii ii ii ii ii ii ii iib a b b a b
Таким образом, формализованы ограничения задачи с помощью нормализованной
квази-phi-функции (10), нормализованной phi-функции (12) и технологических
ограничений в виде (2)–(5).
Рассмотрим основные особенности задачи (7), (8).
1. Задача (7), (8) является задачей смешанного целочисленного программиро-
вания: переменные ,i ,ni I — дискретные (двоичные), а ( , , ),i i i
c l ru ,ni I —
непрерывные.
2. Функция (7) — кусочно-постоянная (пропорциональна числу размещенных
объектов).
86 ISSN 0572-2691
3. Каждому nB соответствует некоторый набор сложных объектов, для
которых часть значений 1,i а остальные — 0,i .ni I Тогда область до-
пустимых решений
( 1)5 9 1
2 : ( , )
n nn
U R U задает допустимые раз-
мещения сложных объектов в области 0 ,S для которых 1,i .n mi I I Раз-
мерность области допустимых решений определяют функции (10), (12).
В связи с перечисленными выше особенностями, стратегия решения задачи
будет следующей.
Поскольку основной особенностью задачи является наличие дискретных и
непрерывных переменных, для ее решения необходимо осуществлять выбор оп-
тимального варианта по дискретным переменным и поиск точки области допус-
тимых решений по непрерывным переменным.
Но особенности предметной области вносят коррективы в стратегию реше-
ния. Выбор оптимального варианта по дискретным переменным может не прово-
диться, его задает последовательность расположения людей в потоке и очеред-
ность их поступления в мобильные средства.
Таким образом, решение задачи состоит из следующей последовательности.
Пусть мощность множества равна 1.n Величина 1n определяется исходя из за-
данного коэффициента заполнения
1
1
0
( )
,
( )
n
i
i
P S
k
P S
например k = 0,8. Решим задачу
(7), (8) на множестве
1 1
1
1
( 1)5 9
2( ).
n
n n
nU R B Если получили решение, при ко-
тором дискретное множество имеет вид
11 2{ , , ..., } {1, 1, ..., 1},n увеличи-
ваем 1n на единицу, т.е. 1 1,n n и снова решаем (7), (8) на множестве
9
( 1)5
2 .
n
n n
nU R B
В противном случае процесс решения прекращается (например, если коэф-
фициент заполнения области меньше заданного) или область дозаполняется вы-
шеизложенным способом путем выбора дискретных переменных согласно после-
довательности расположения людей в потоке.
Решение задачи на множестве U осуществляется в два этапа.
1. Поиск начальной (стартовой) допустимой точки.
2. Нахождение локального экстремума задачи.
В качестве метода для поиска начального приближения рассматривается ме-
тод минимизации по группам переменных [30].
Локальная оптимизация осуществляется с помощью пакета нелинейной оп-
тимизации с открытым исходным кодом IPORT (методом внутренней точки).
Компьютерное моделирование размещения объектов
Создано алгоритмическое и программное обеспечение для компьютерного
моделирования оптимизации размещения объектов.
Проведен ряд вычислительных экспериментов. Для области площадью 1 м2
решалась задача определения максимального количества объектов, размещенных
Международный научно-технический журнал
«Проблемы управления и информатики», 2021, № 3 87
в ней, путем их выбора согласно заданной последовательности номеров из набора
35 объектов с оптимизацией их размещения.
Вычислительные эксперименты проводились на AMD Athlon 64x2 Dual
5200+. Решение подзадач нелинейного программирования осуществлялось с по-
мощью программы IPOPT [31], доступной на открытом некоммерческом ресурсе
(https://projects.coin-or.org/Ipopt). Результаты приведены на рис. 2, 3.
Время поиска локального экстремума для объектов, представленных трех-
компонентной моделью, с непрерывной трансляцией основных эллипсов, а так-
же непрерывными поворотами как основных, так и вспомогательных эллипсов
(см. рис. 2) составляет 275,32 с; для объектов, представленных трехкомпонент-
ной моделью, с непрерывными трансляцией и поворотом основного эллипса
при фиксированной ориентации вспомогательных эллипсов (см. рис. 3) со-
ставляет 178,0 с.
Рис. 2
Рис. 3
Заключение
В статье введено понятие пространственной конфигурации размещения
сложных объектов, примером которых является модель человеческого тела с уче-
том его природных деформаций. Построена новая модель размещения сложных
объектов, представляющих объединение трех нежестко связанных эллипсов, один
из которых (основной) допускает непрерывные трансляции и повороты, а два
(вспомогательных) могут непрерывно вращаться в допустимых пределах (по от-
ношению к углу поворота основного) относительно точек «склейки». Исходя из
особенностей модели, предложена стратегия ее решения. Следует отметить, что в
88 ISSN 0572-2691
результате решения оптимизационной задачи синтезируется не только конфигу-
рация размещения таких объектов, но и их пространственная форма. Осуществле-
но компьютерное моделирование оптимизации размещения рассмотренных в ра-
боте сложных объектов и показана эффективность предложенного подхода путем
сравнения конфигураций размещения для объектов с изменяющейся пространст-
венной формой и постоянными параметрами формы.
Рассмотрение параметров размещения объектов, а также дополнительных па-
раметров, которые позволяют синтезировать новые пространственные формы
объектов, в качестве обобщенных переменных позволит предложить новые мате-
матические модели и оптимизационные методы синтеза пространственных кон-
фигураций. Дальнейшим направлением можно считать также разработку новых
подходов к моделированию движения потоков людей, роботов для получения
верхних оценок заполнения областей объектами. Все это увеличивает круг ре-
шаемых задач по их функциональным возможностям и может использоваться, на-
пример при разбиении отсеков транспортных средств для перевозки грузов и их
сохранении, в системах распознавания образов, робототехнике и т.д.
В.В. Комяк, В.М. Комяк, К.Т. Кязімов, О.В. Панкратов, О.М. Данілін
ПІДХІД ДО ОЦІНКИ ЗАПОВНЮВАНОСТІ
ЛЮДЬМИ МОБІЛЬНИХ ЗАСОБІВ
ПРИ АВАРІЙНІЙ ЕВАКУАЦІЇ З БУДИНКІВ
Задачі геометричного проектування (розміщення, компонування, покриття, ро-
збиття) складаються з оптимізаційного відображення геометричної інформації
про об’єкти відповідно до заданого критерію якості та обмежень. Геометрична
інформація про геометричний обۥєкт складається з трьох компонент:
просторової форми, метричних параметрів форми, параметрів розміщення, і, як
правило, бере участь у синтезі складних систем. Конфігураційний простір гео-
метричних об’єктів ґрунтується на формалізації поняття геометричної
інформації. Відображення множини об’єктів в їх конфігураційний простір
відповідно до заданого набору обмежень задає просторову конфігурацію
геометричних об’єктів. Введено поняття просторової конфігурації розміщення,
за допомогою якого побудовано нову модель розміщення складних об’єктів, що
об’єднують три нежорстко пов’язані еліпси, один (основний) з яких допускає
неперервні трансляції та повороти, а два (допоміжні) можуть неперервно
повертатися в допустимих межах відносно основного кута та точок їх
«склейки». У результаті розв’язання оптимізаційної задачі синтезується не
тільки конфігурація розміщення таких об’єктів, а й просторова форма кожного
з них. Здійснено комп’ютерне моделювання оптимізації розміщення розгля-
нутих у роботі складних об’єктів і показано ефективність запропонованого під-
ходу шляхом порівняння конфігурацій розміщення для об’єктів зі змінною про-
сторовою формою і постійними параметрами форми. Розгляд параметрів роз-
міщення об’єктів, а також додаткових параметрів як незалежних змінних, за
допомогою яких можна синтезувати нові просторові форми об’єктів, дозволить
запропоновувати нові математичні моделі та оптимізаційні методи синтезу
просторових конфігурацій розміщення. Подальшим напрямком можна вважати
також розробку нових підходів до моделювання руху потоків людей, роботів
для отримання верхніх оцінок заповнення областей об’єктами. Все це збільшує
коло розв’язуваних задач за їх функціональними можливостями і може використо-
вуватися, наприклад, при розбитті відсіків транспортних засобів для перевезення
вантажів і їх збереженні, в системах розпізнавання образів, робототехніці тощо.
Ключові слова: геометричний об’єкт, геометрична інформація, розміщення,
конфігураційний простір, узагальнені змінні, математична модель, оптимізація.
Международный научно-технический журнал
«Проблемы управления и информатики», 2021, № 3 89
V.V. Komyak, V.M. Komyak, K.T. Kyazimov, A.V. Pankratov, A.N. Danilin
APPROACH TO THE EVALUATION OF FILLING
BY PEOPLE OF MOBILE MEANS AT EMERGENCY
EVACUATION FROM BUILDINGS
The tasks of geometric design (of arrangement, cutting, coverage, partitioning) con-
sist in optimization display of geometric information about objects in accordance
with a given quality criterion and limitations. Geometric information about a geomet-
ric object consists of three components: spatial shape, metric shape parameters,
placement parameters, and which, as a rule, is involves in the synthesis of complex
systems. The configuration space of geometric objects is based on the formalization
of the concept of geometric information. The mapping of objects into their configura-
tion space according to a given set of constraints defines the spatial configuration of
geometric objects. The article introduces the concept of a spatial configuration of
placement, with the help of which a new model of placement of complex objects is
constructed, representing the union of three loosely coupled ellipses, of which one
(main) allows continuous translations and rotations, and two of auxiliary ellipses can
rotate within acceptable limits (with respect to the angle of rotation of main ellipse)
and relative to the points of their “gluing”. As a result of solving the optimization
problem, not only the arrangement configuration of such objects is synthesized, but
also the spatial form of each of them. Computer modeling of the optimization of the
placement of the complex objects considered in the work was carried out and the ef-
fectiveness of the proposed approach was shown by comparing the location configu-
rations for objects with a changing spatial shape and with constant shape parameters.
Consideration of the parameters of the placement of objects, as well as additional pa-
rameters that allow us to synthesize new spatial forms of objects, as independent
variables will allow us to offer new mathematical models and optimization methods
for the synthesis of spatial configurations. A further direction can also be considered
the development of new approaches to modeling the movement of flows of people,
robots, to get upper bounds for filling areas with objects. All this increases the range
of tasks to be solved according to their functional capabilities and can be used, for
example, when dividing the compartments of vehicles for transporting goods and
storing them, in pattern recognition systems, in robotics, etc.
Keywords: geometric object, geometric information, packing, configuration space,
generalized variables, mathematical model, optimization.
1. Stoyan Y.G., Yakovlev S.V. Configuration space of geometric objects. Cybernetics and Systems
Analysis. 2018. 54, N 5. P. 716–726.
2. Яковлев С.В. О некоторых классах пространственных конфигураций геометрических объектов
и их формализации. Международный научно-технический журнал «Проблемы управления
и информатики». 2018. № 5. С. 73–84.
3. Стоян Ю.Г. Основная задача геометрического проектирования. Х. : Ин-т проблем машино-
строения АН УССР, 1983. 36 с. (Препринт / АН УССР. Ин-т проблем машиностроения;
181).
4. Стоян Ю.Г. Размещение геометрических объектов. Киев : Наук. думка, 1975. 239 с.
5. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объек-
тов. Киев : Наук. думка, 1976. 247 с.
6. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометри-
ческого проектирования. Киев : Наук. думка, 1986. 268 с.
7. Яковлев С.В., Гиль Н.И., Комяк В.М. и др. Элементы теории геометрического проектиро-
вания. Под ред. В.Л. Рвачева. Киев : Наук. думка, 1995. 241c.
8. Modeling and Simulation of Coverage Problem in Geometric Design Systems. S. Yakovlev,
O. Kartashov, V. Komyak, S. Shekhovtsov, O. Sobol, I. Yakovleva. IEEE 15th International
Conference on the Experience of Designing and Application of CAD Systems (CADSM). Polyana.
Ukraine, 2019. P. 20–23.
9. Сomputer simulation of the partitioning by mutually orthogonal lines. Va. Komyak, O. Sobol,
O. Kartashov, I. Yakovleva, Vl. Komyak, A. Danilin, O. Lyashevskaya. IEEE 15th International
Conference on the Experience of Designing and Application of CAD Systems (CADSM). Polyana.
Ukraine, 2019. P. 16–19.
90 ISSN 0572-2691
10. Оптимизация разбиения области на подобласти по заданным ограничениям в пространстве
В.М. Комяк, В.В. Комяк, А.Н. Соболь, А.Н. Данилин, К.Т. Кязимов Международный науч-
но-технический журнал «Проблемы управления и информатики». 2020. № 1. С. 25–37.
11. Коmyak Va., Коmyak V.l., Danilin A.N. Study of ellipse packing in the high-dimensionality
problems. Eastern-European Journal of Enterprise Technologies. 2017. 1/4(85). P. 17–23.
12. Холщевников В.В., Самошин Д.А. Эвакуация и поведение людей на пожарах: учебное по-
собие. М. : Академия ГПС МЧС России, 2009. 210 с.
13. Кязімов К.Т. Характеристики активного потокового руху людей. Сучасні проблеми моде-
лювання. Мелітополь. МДПУ, 2020. Вип. 19. С. 102–110.
14. Toth L.F. Packing of ellipses with continuously distributed area. Journal of Discrete Mathemat-
ics.1986. 60. P. 263–267. doi:10.1016/0012-365X(86)90018-X.
15. Ting J.M., Khwaja M., Meachum L.R., Rowell J.D. An ellipse-based discrete element model for
granular materials. Numerical and Analytical Methods in Geomechanics. 1993. 17(9). P. 603–
623. doi:10.1002/nag.1610170902.
16. Feng Y., Han K., Owen D. An advancing front packing of polygons, ellipses and spheres. Dis-
crete Element Methods. 2002. P. 93–98. doi:10.1061/40647(259)17.
17. Vickers G.T. Nested Ellipses. Applied Probability Trust. 2009. 41(3). P. 131–137.
18. Xu W., Chen H.S. An overlapping detection algorithm for random sequential packing of elliptical
particles. Physica. 2011. 390. P. 2452–2467.
19. Kallrath J., Rebennack S. Cutting ellipses from area-minimizing rectangles. Journal of Global
Optimization. 2013. 59 (2-3). P. 405–437. doi:10.1007/s10898-013-0125-3.
20. Kallrath J. Cutting circles and polygons from area-minimizing rectangles. Journal of Global Op-
timization. 2008. 43 (2–3). P. 299–328. doi:10.1007/s10898-007-9274-6.
21. Панкратов А.В., Романова Т.Е., Суббота И.А. Оптимальная упаковка эллипсов с учетом
допустимых расстояний. Журнал обчислювальної математики. 2014. 1. C. 27–42.
22. Stoyan Yu., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses.
Journal of Global Optimization. 2015. doi: 10.1007/s10898-015-0331-2.
23. Стоян Ю.Г., Панкратов А.В., Романова Т.Е., Чернов Н.И. Квази-phi-функции для матема-
тического моделирования отношений геометрических. Доповіді Національної академії наук
України. 2014. 9. C. 49–54.
24. Stoyan Yu., Romanova T., Pankratov A., Chugay A. Optimized object packings using quasi-phi-
functions. Of the series Springer Optimization and Its Applications, 2015. 105. P 265–293.
25. Birgin E.G., Lobato R., Martínez J.M. Packing ellipsoids by nonlinear optimization. Journal of
Global Optimization. 2016. 65. Р. 709–743.
26. Birgin E.G., Bustamante L.H., Callisaya H.F., Martınez J.M. Packing circles within ellipses. In-
ternational transactions in operational research. 2013. 20(3). P. 365–389.
doi:10.1111/itor.12006.
27. Birgin E.G., Martinez J.M. Practical augmented lagrangian methods for constrained optimization.
Society for Industrial and Applied Mathematics. Philadelphia PA, 2014.
28. Данилин А.Н., Комяк В.В., Комяк В.М., .Панкратов А.В. Упаковка эллипсов в прямоуголь-
ник минимальных размеров. УСиМ. 2016. № 5. С. 5–9.
29. Stoyan Yu., Gil N., Romanova T., Scheithauer G. Phi-function for complex 2D object. 40R Quar-
terly Journal of the Belgian, French and Italian Operations Research Societies. 2004. 2(1).
P. 69–84.
30. Комяк В.М. Математическое и компьютерное моделирование нерегулярного размещения
плоских геометрических объектов в областях произвольной пространственной формы: Дис.
д-ра техн. наук: 01.05.02., 1996. 377 с.
31. Wachter A., Biegler L.T. On the implementation of an interior-point filter line-search algorithm
for large-scale nonlinear programming. Mathematical Programming. 2006. 106 (1). P. 25–57.
doi:10.1007/s10107-004-0559-y.
Получено 19.06.2020
|