Математическое моделирование давно и успешно применяется для комплексного предпроектного анализа вновь создаваемых или эффективной эксплуатации существующих технических систем, в частности – для систем мультимодальной транспортной логистики. Стоимость разработки и исследования компьютерных имитационных моделей (цифровых двойников) ничтожно мала по сравнению со стоимостью реальной транспортной инфраструктуры и потенциальными потерями от возможных ошибок при ее проектировании. Основным практическим приложением имитационного моделирования помимо ответа на традиционный вопрос «что будет, если?» является решение обратной задачи, то есть оптимизация интегральных параметров эффективности путем варьирования внутренних определяющих параметров системы. Типичные методики комбинирования методов алгебраической оптимизации и имитационного моделирования рассмотрены во многих теоретических работах (Fu, 2002; Bachelet, Yon, 2007), где приведены различные схемы взаимодействия этих процедур.

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

Однако при создании и последующей параметрической оптимизации имитационной дискретно-событийной или агентно-ориентированной модели сложной транспортно- технологической системы часто возникает необходимость адекватного учета и «интеллектуальных» аспектов ее будущего функционирования на уровне оперативного управления. Действительно, реальная эксплуатация любого многофункционального объекта (порта, контейнерного терминала, нефтедобывающей платформы) предполагает наличие службы локальной диспетчеризации для разрешения возникающих инцидентов различного характера и противоречивых интересов субъектов разного уровня организации. Наиболее часто встречающиеся задачи, для решения которых используется такая диспетчеризация, это определение очередности обслуживания всех текущих или прогнозируемых на коротком временном интервале заявок на обслуживание и управление ограниченным объемом имеющихся ресурсов. Следует отметить, что алгоритмы и компьютеризированные системы автоматизации календарного планирования работ и/или распределения ресурсов, безусловно, относятся к другому (оперативному) уровню управления, нежели предпроектный анализ изучаемой системы. Однако пренебрежение этими аспектами в имитационной модели, то есть отсутствие в ней некого

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

Часто для разрешения этого противоречия используется упрощенный подход, связанный с заданием в логике модели проектного уровня неких жестких правил исполнения последовательности заявок на обслуживание («первым пришел – первым ушел» и т.п.). Практика построения и анализа моделей для различных транспортно-технологических систем (их краткий перечень приведен ниже), показывает, что любые подобные упрощения часто оказываются внутренне противоречивыми и не позволяют получить не только адекватные численные оценки эффективности конкретной конфигурации системы, но даже сделать обоснованный вывод о том, какая из этих сравниваемых конфигураций предпочтительнее.

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

непосредственно внутри логики имитационной модели. Как правило, математическим аппаратом такой «внутренней» оптимизации выступают алгоритмы и методы комбинаторной оптимизации и математического программирования. При этом структурная схема взаимодействия процедур имитационного моделирования и оптимизации на уровне проектного анализа транспортных систем приобретает трехуровневый вид, представленный на рис. 1.

Рис. 1. Трехуровневая схема взаимодействия оптимизации и имитационного моделирования в задачах проектного анализа транспортно-технологических систем

Материалы и методы

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

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

Рис. 2. Демонстрационная дискретно-событийная модель обработки заявок с разделяемым ресурсом

Последовательное исполнение пришедших заявок в порядке поступления. Запрос свободного ресурса осуществляется только после достижения заявкой соответствующего центра обработки (заявка ждет ресурс).

Последовательное исполнение пришедших заявок в порядке поступления. Запрос свободного ресурса осуществляется сразу при появлении заявки в стартовой точке, но она начинает движение к центру обработки только после того, как обещанный ей ресурс достигает точки обработки (ресурс ждет заявку).

Последовательное исполнение пришедших заявок в порядке поступления. Запрос свободного ресурса осуществляется сразу при появлении заявки в стартовой точке, при этом движение к центру обработки заявки и ресурса происходит независимо (упреждающий запрос ресурса).

Использование планирования для упорядочивания последовательности исполнения заявок. Как и для всех ранее рассмотренных случаев, вновь поступившие заявки задерживаются в стартовой области на заданный промежуток времени (этим фактом эмулируется заблаговременность прогноза о поступлении очередного транспортного средства на обработку). И поступление каждой новой заявки инициирует перепланирование, то есть переупорядочение всех заявок, находящихся в «пуле ожидания», то есть не начавших движение к центру обработки. При этом, в свою очередь, реализовано несколько вариантов логики такого планирования:

План исполнения формируется по принципу FIFO (первым пришел – первым ушел). Можно показать, что при этом логика системы в точности отвечает варианту 3.

План исполнения формируется по принципу LIFO (последним пришел – первым ушел).

План исполнения формируется по случайному принципу (случайное переупорядочивание последовательности операций).

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

План исполнения вычисляется в результате процедуры строгой оптимизации, но, в отличие от рассмотренных выше вариантов, процедура перепланирования «пула ожидания» запускается не с каждой вновь поступающей заявкой, а с некой дискретностью (в рассматриваемом случае только для каждой пятой из них).

Сравнение всех рассмотренных вариантов производилось в рамках серии статистических экспериментов варьирования параметров с репликациями. Для каждой конфигурации модель прогонялась в стократной повторности с фиксацией основных статистических показателей эффективности. В частности, после каждого прогона запоминались средние и максимальные времена обслуживания единичной заявки. Временным горизонтом моделирования выбирался период, за который производилось обслуживание одной тысячи входящих заявок (после достижения входящим потоком данного объема поступление новых заявок прекращалось). Длительности переходов всех заявок от стартовой точки до обоих центров обработки и перемещения ресурса между центрами как и длительность погрузки были выбраны равными 10 часам. Интенсивность случайного процесса поступления новых заявок – 0.1 заявка в час.

Результаты

Выборочные результаты серии проведенных компьютерных экспериментов приведены в таблице 1. Нетрудно заметить, что если минимальная «интеллектуализация» процесса исполнения заявок (авансированный запрос ресурса с параллельным движением его и заявки к центру обработки) не дает никакого заметного выигрыша в интегральных показателях пропускной способности по сравнению с «нулевым» вариантом, то подключение эмулятора системы оперативного планирования позволяет качественно повысить эффективность системы. Причем существенное повышение эффективности наблюдается даже при сравнительно низкой частоте перепланирования. Любопытно также, что увеличение дискретности перепланирования не приводит к повышению вычислительной эффективности.

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

В данном случае это объясняется тем, что хотя число актов оптимизации плана за жизненный цикл модели при этом и уменьшается, но пропорционально возрастает размерность

каждой разовой задачи оптимизации (число ожидающих обслуживания заявок, требующих упорядочивания последовательности их исполнения).

Обсуждение

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

1. Имитационные модели работы и снабжения нефтедобывающих платформ и нефтеперегрузочных комплексов (Таровик и др., 2017). В качестве основного аспекта оперативного планирования здесь выступает постоянное нахождение баланса между обслуживанием транспортных судов основного производственного контура и конкурирующих с ними за причальные места судов снабжения. А определяющими факторами при принятии оперативных решений выступают текущие уровни наполненности хранилищ различных грузов и специфичные для судов разных типов «окна погоды».
2. Модели арктических транспортных морских коридоров. Существенным аспектом уровня оперативного планирования, требующим адекватного учета в имитационной модели, здесь выступает проблема оптимальной маршрутизации судов ледового плавания в существенно нестационарных условиях окружающей среды (Topajetal., 2019).
3. Модели контейнерных терминалов. Наиболее значимый аспект оперативного планирования и управления в данном случае связан с оптимальным размещением и штабелированием контейнеров на временных площадках хранения для обеспечения минимального количества операций по их перемещению и перегрузке (Нужнов, Юрко, 2014). К особенно интересным постановкам здесь приводит использование в качестве погрузочно-разгрузочной техники телескопических погрузчиков (ричстакеров). Дело в том, что существенные ограничения, накладываемые геометрией стрелы и спредера погрузчика данного типа, приводят к необходимости соблюдения особых правил формирования штабеля и осуществления большого количества вспомогательных перемещений для «раскапывания» нужного контейнера. Учёт и планирование этих вспомогательных операций (т.н. ContainerRelocationProblem) в операционной деятельности реальных мультимодальных контейнерных терминалов является исключительно нетривиальной задачей (Galle, 2018). Исследование чувствительности интегральных показателей эффективности и пропускной способности контейнерного терминала при различных предопределенных правилах работы козловых кранов и ричстакеров с многоуровневыми штабелями контейнеров проводилось авторами в рамках работ по имитационному моделированию проектируемой западной площадки хранения транспортно-логистического центра «Фрейт Вилладж Калуга Север» (Калужская область).
4. Имитационные модели работы порта. В данном случае блок эмуляции оперативного планирования портовых операций с учетом ограниченности стационарных и движущихся ресурсов (причалы, буксиры, хранилища, бункеровщики средства грузообработки и т.д.) выступает чуть ли не главным элементом имитационной модели. В общем случае получаемая постановка может быть отнесена к классу NP-полных проблем, и одним из стандартных способов ее решения служит сведение задачи, сформулированной в терминах предметной области, к формальной математической постановке задачи удовлетворения целочисленных ограничений и ее решение с использованием специализированных внешних решателей и движков.

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

раз. Так, судно может пришвартоваться/отшвартоваться к одному причалу несколько раз – например, при необходимости уступить место другому судну, подвозящему нужный груз или в случае прерывания операции грузообработки из-за прекращения «окна погоды». Для решения проблемы с неизвестным заранее числом экземпляров каждой предопределенной портовой операции авторами был предложен следующий подход – весь ресурс времени в границах от нуля (текущий момент перепланирования) до конца горизонта планирования разбивается на равные участки, соответствующие по длительности выбранному элементарному «кванту времени». В его качестве разумно выбрать такую величину, чтобы ей были кратны все характерные времена операций, описанных в задаче. С учётом проведённого “квантования” временной оси в качестве набора основных переменных задачи оптимизации принимаются факты того, выполняется ли операция данного типа в данный квант времени (Киселёв и др., 2019).

Апробация предложенного метода интеграции комбинаторного планирования в имитационные модели работы порта была проведена в рамках выполнения работ по заданию Министерства промышленности и торговли РФ (тема «ГМТ-Логистика»). В частности, на основе изложенного подхода была реализована комплексная модель грузообработки и бункеровки газомоторным топливом транспортных судов в порту Санкт-Петербург. В качестве внешнего решателя проблемы удовлетворения целочисленных ограничений (Constraint satisfaction problem, CSP) использовалась открытая платформа MiniZinc. Укрупненная структурная схема соответствующего программного решения приведена на рис. 3.

Рис. 3. Структурная схема комплексной модели портовых операций по грузообработке и бункеровке судов сжиженным природным газом

Заключение

Основным ограничением, препятствующим широкому внедрению процедур и модулей комбинаторной оптимизации в практику имитационного моделирования, выступают соображения вычислительной эффективности. Тем не менее, большинство высокоуровневых сред и платформ имитационного моделирования уже сейчас включают в свой состав мощные оптимизационные движки, в функциональность которых помимо стандартных процедур алгебраической оптимизации малой размерности заложены и методы многопараметрического математического программирования. В качестве примера можно указать профессиональный решатель IBM ILOG CPLEX, интегрированный с платформой AnyLogistix, или расширенный программный интерфейсоптимизатора OptQuest, к которому можно обратиться напрямую из кодов модели AnyLogiс. Представляется, что дальнейшее расширение средств интеграции специализированных движков комбинаторной оптимизации и имитационных моделей должно помочь в разрешении указанного противоречия.

Литература

1. Bachelet B., Yon L. Model enhancement: improving theoretical optimization with simulation. Simulation Modelling Practice and Theory. (15). 2007. P. 703–715.
2. Fu M.C. Optimization for simulation: theory vs. practice. INFORMS Journal in Computing 14(3), 2002. P. 192–215.
3. Galle V. Optimization Models and Methods for Storage Yard Operations in Maritime Container Terminals. PhD Thesis in Operations Research. Massachusetts Institute of Technology, 2018, 245 p.
4. Topaj, A.G., Tarovik, O.V., Bakharev, A.A., Kondratenko, A.A. Optimal ice routing of a ship with icebreaker assistance. AppliedOceanResearch. No 86. 2019. pp. 177-187.
5. Киселёв В.А., Чивилихин Д.С., Топаж А.Г. Исследование сведения задачи календарного планирования портовых операций к задаче удовлетворения ограничений // Сборник трудов Всероссийской конференции по математике «МАК-2019», Материалы молодёжной прикладной IT-школы «Математические методы и модели в экологии», Барнаул, 27 июня-1 июля 2019 г., — С. 138-141
6. Нужнов Е. В., Юрко Д. С. Возможности и средства динамического планирования и перегрузки контейнеров на смешанных транзитных терминалах // Труды конгресса по интеллектуальным системам и информационным технологиям IS&IT’14. М., 2014. Т. 2. С. 49 – 56.
7. Таровик О. В., Топаж А. Г., Крестьянцев А. Б. Кондратенко А.А., Зайкин Д.А. Комплексная имитационная модель морской транспортно-технологической системы платформы “Приразломная” // Арктика: экология и экономика. № 3 (27). 2017. С. 86-102.
8. Топаж А.Г., Таровик О.В., Реуцкий А.С. Использование алгоритмов оперативного планирования в имитационных моделях морских транспортно-технологических систем // Сборник трудов Пятой международной научно-практической конференции «Имитационное и комплексное моделирование морской техники и морских транспортных систем (ИКМ МТМТС-2019)», 2019, С. 176-181.

Авторы: А.Г. Топаж, О.В. Таровик, А.С. Реуцкий, В.А. Киселёв
Источник: https://www.anylogic.ru/

Понравилась статья? Тогда поддержите нас, поделитесь с друзьями и заглядывайте по рекламным ссылкам!