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

Согласно данным Главного таможенного управления КНР, товарооборот между Россией и Китаем за 2021 год достиг рекордных показателей – 146,88 млрд долл. [1]. Это, в том числе, связано с тем, что в Китае начало открываться всё больше компаний, которые предоставляют посреднические услуги для оптовых покупателей, организуя полный цикл взаимодействия с производителем продукции: выезд на завод, покупка пробных образцов, закупка партии товаров, доставка из Китая в Россию и др. Основной заработок таких компаний – процент с продаж и логистические услуги по доставке товара заказчику. Доставлять каждый товар по отдельности – довольно дорогое удовольствие, ввиду чего осуществляется их объединение с целью уменьшения стоимости отправки всего заказа. При наличии нескольких позиций в заказе такое объединение товаров по группам не представляет ничего сложного, но когда речь идет о 30 и более товарах, операторы не в силах справиться с расчетами, а переборные алгоритмы затрачивают на это довольно много времени. При единичных отправках это не критично, однако данная проблема является узким местом при попытке масштабирования бизнеса и увеличения товарооборота.

Цель статьи – разработать систему поддержки принятия решений, способную находить приемлемые для бизнеса варианты распределения товаров по группам для уменьшения стоимости отправки заказов.

Магомедов Олег Русланович студент бакалавриата. Санкт-Петербургский государственный экономический университет, Санкт-Петербург. Сфера научных интересов: системы поддержки принятия решений; мультиагентные системы; разработка распределенных систем. Автор 6 опубликованных научных работ.

Несмотря на то, что переборные алгоритмы будут давать более точный результат, их применение при увеличении количества товаров в заказе не представляется возможным из-за значительного увеличения времени расчетов даже с учетом распараллеливания. Ввиду этих обстоятельств было принято решение использовать мультиагентный подход, который в последнее время набирает популярность [2; 3; 9; 12]. Так как имелись ограничения на использование различных зависимостей в виде фреймворков мультиагентного моделирования, архитектура данной системы и протокол взаимодействия между агентами реализовывались без их использования.

Базовые понятия

Рассмотрим некоторые базовые понятия, связанные с построением мультиагентых систем.

Мультиагентная система (далее – МАС) – система, состоящая из одной или более групп агентов, конкурирующих или сотрудничающих друг с другом с целью выполнить общую задачу таким образом, чтобы увеличить ценность принимаемых решений для всей системы [4].

Под агентом понимается автономный программный объект, способный достигать поставленных целей в условиях неопределенности путем выработки и анализа вариантов принятия решений и согласованного взаимодействия с другими агентами. По уровню поведения агентов можно разделить на проактивные и реактивные. Проактивные агенты анализируют свои знания об окружающей среде и сами проявляют инициативу, вступая в переговоры с другими агентами. Реактивные агенты реагируют на события окружающей среды и непосредственное взаимодействие с ними. Реакцией агента на событие также может быть вступление в переговоры с другими агентами, принятие или отказ от соглашений с агентами. Необходимо отметить, что МАС, основанная на реактивных агентах, может проявлять свойства системы, построенной на проактивных агентах [11]. Хотя в таких случаях изначальным импульсом к действию агентов является событие, агенты обретают способность анализировать окружающую среду и предпринимать действия по улучшению состояния системы.

Мультиагентная система поддержки принятия решений для минимизации стоимости ...

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

Описание предметной области

Чтобы лучше понять задачу, рассмотрим предметную область. Целью разрабатываемого алгоритма является минимизация стоимости перевозки заказа, который содержит определенное количество товаров.

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

Для расчета цены посылки вычисляется ее плотность путем деления суммы весов всех товаров на сумму объемов всех товаров в посылке. Затем находится тариф по тарифной сетке (см. Таблицу 1), который зависит от плотности посылки. Тариф содержит диапазон плотности посылок, для которого он работает, тарифную ставку и тип расчета (по весу или по объему). Как правило, чем больше плотность посылки, тем меньше тарифная ставка. Если тип расчета в тарифе по весу, для получения стоимости посылки производится умножение ее веса на тарифную ставку, в противном случае – на тарифную ставку умножается объем.

Таблица 1

Пример тарифной сетки

№	Плотность кг/м. куб	Ставка $	Тип расчета (1 – по весу, 2 – по объему)
1	1000 и более	3,30	2
2	801…999	3,40	2
18	101…110	4,70	2
19	Менее 100	520,00	1

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

Стек используемых технологий

Для разработки мультиагентной системы был выбран компилируемый высокоуровневый язык программирования Dart [8]. Язык разработан компанией Google и в основном используется в связке с Flutter [10] для мультиплатформенной разработки клиентских приложений. Тем не менее он неплохо подходит для написания мультиагентных систем, где особенно важна параллельная работа агентов. Dart представляет возможность параллельного выполнения программы посредством изолятов, а наличие фреймворка Flutter позволяет написать мультиплатформенный графический клиент для работы с системой.

Использование одного языка программирования для разработки мультиагентной системы и графического интерфейса для взаимодействия с ней позволяет легко использовать сущности и бизнес-логику мультиагентной системы из кода графического интерфейса. Изоляты – это потоки выполнения программы, которые могут работать конкурентно. При старте программы запускается главный изолят, который выполняет функцию main, являющуюся точкой входа программы. Далее главный изолят может создавать и управлять жизненным циклом других изолятов, что использовалось в архитектуре разработанной системы. Изоляты не разделяют память как потоки в таких языках программирования, как C#, Python, Java, и для их взаимодействия используются сообщения. При разработке системы возникла необходимость, чтобы все изоляты имели одинаковые знания об окружении системы, и это вызвало дублирование данных, чего можно было бы избежать, если бы в Dart была разделяемая память между потоками выполнения.

Структура разработанной мультиагентной системы

Главным объектом системы является Environment (среда окружения). Он хранит состояние всей системы, отвечает за создание, удаление агентов, является посредником в переговорах между агентами и фиксирует результаты соглашений агентов, изменяя состояние системы [5]. В среде окружения действуют три типа агентов: Order Agent (агент заказа), Product Group Agent (группа продуктов), Product Agent (одиночный продукт). Product Group представляет из себя посылку, состоящую более чем из одного продукта. Product представляет посылку, состоящую из одного продукта. Order Agent отвечает за хранение информации о заказе, а именно продуктов, групп продуктов и тарифной сетки. Также Order Agent отвечает за обновление продуктов и групп продуктов, когда агенты продуктов и групп продуктов заключают соглашение, как бы выполняя роль брокера.

Жизненный цикл МАС можно условно разделить на 3 этапа: инициализация, работа и завершение работы. Последовательно рассмотрим каждый из этапов.

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

Работа. Когда Environment инициализирован, начинается этап работы системы, состоящий из последовательных переговорных этапов, называемых эпохами. В ходе эпохи идут переговоры агентов и принимаются соглашения между ними. Основной концепцией разработанной МАС является проведение переговоров между агентами и принятие ими соглашений об изменении системы, но только тех, которые улучшают результат (уменьшается конечная стоимость заказа). Эпохи продолжают создаваться до тех пор, пока не будет достигнуто состояние, которое не улучшается в течение определенного количества эпох, задаваемого конфигурацией Environment (см. Рисунок 1).

Рассмотрим соглашения, которые могут заключать агенты.

• 1.    Объединение продуктов и групп продуктов. Объединяться могут продукт с продуктом, продукт с группой продуктов, группа продуктов с продуктом, группа продуктов с группой продуктов. В результате объединения продукта с продуктом создается новая группа продуктов, которая содержит 2 объединившихся продукта. При объединении продукта и группы продуктов продукт добавляется к группе, а в случае объединения двух групп про-

• Мультиагентная система поддержки принятия решений для минимизации стоимости ...
2. Удаление продукта из группы продуктов. Продукт удаляется из группы продуктов и добавляется в Environment. Сообщение о соглашении содержит идентификатор группы продуктов, из которой удаляется продукт, и идентификатор продукта, который удаляется из группы.

• 3.    Удаление продукта из группы продуктов с заменой. Продукт удаляется из группы продуктов и добавляется в Environment, в то же время к группе продуктов добавляется другой продукт, взятый из Environment. Соглашение является составным и содержит два соглашения – удаление продукта из группы продуктов, а также объединение продукта с группой продуктов.

• 4.    Обмен продуктами между группами продуктов. В результате продукт из первой группы перемещается во вторую группу, а продукт из второй группы – в первую группу. Соглашение содержит идентификаторы групп, между которыми происходит обмен, а также продукты, которые требуется обменять.

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

Рисунок 1. Блок схема жизненного цикла МАС

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

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

Было реализовано 4 типа эпох.

Regular . В данном типе эпохи агенты продуктов и групп продуктов обмениваются сообщениями и могут прийти к соглашению об объединении, удалении продукта из группы продуктов и удалении продукта из группы продуктов с заменой.

Only Products to Groups . На данном шаге отправляют сообщения только продукты и сообщения идут только группам. Агенты могут прийти к соглашению об объединении продукта с группой продуктов, либо об удалении продукта из группы с заменой.

Exchange . На данном шаге производится переговоры по поводу обмена продуктами между группами.

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

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

Мультиагентная система поддержки принятия решений для минимизации стоимости ...

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

Применение соглашения сразу после его получения Environment имеет недостаток. В примере выше соглашение между агентами А и В могло оказаться выгоднее соглашения А и Б, но в любом случае применяется соглашение между А и Б, так как оно пришло в Environment первым. Тем не менее в ходе испытаний оказалось, что в большинстве случаев такой недостаток компенсируется в следующих эпохах. Так, в примере выше агенты А и Б при объединении образуют агента группы продуктов, который содержит продукты А и Б. Но если группа А и В лучше для системы, чем группа А и Б, то на типе эпохи Exchange произойдет удаление продукта Б из группы и замена его на продукт В. В результате получим состояние идентичное тому, которые получилось бы при изначальном объединении продуктов А и В в группу.

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

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

Результаты и обсуждение

Главным преимуществом МАС по сравнению с переборными алгоритмами является скорость выполнения работы. Следует отметить, что при увеличении количества продуктов в заказе скорость выполнения их группировки переборными алгоритмами падает в несколько раз. Были проведены замеры времени выполнения переборного алгоритма и МАС на выборках входных данных с постепенным увеличением количества товаров в заказе в формате «часы : минуты : секунды : миллисекунды» (см. Таблицу 2).

Таблица 2

Сравнение времени работы переборного алгоритма с МАС

Количество продуктов	Время группировки (мультиагентная система)	Время группировки (переборный алгоритм)
5	0:00:04,880135	0:00:00,112994
6	0:00:04,525058	0:00:00,174604
7	0:00:04,947600	0:00:00,217338
8	0:00:04,455448	0:00:01,408652
9	0:00:06,053171	0:00:21,815098
10	0:00:09,406804	0:08:36,785325
30	0:00:17,780205	–
50	0:00:43,907667	–
70	0:01:03,459164	–
100	0:02:06,676889	–

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

При увеличении количества продуктов в заказе повышается вероятность того, что мультиагентная система составит не самую лучшую группировку продуктов. Данное явление прослеживается из-за вероятностного фактора, обусловленного тем, что порядок переговоров между агентами продуктов и групп продуктов не определен, и применяются те соглашения между агентами, которые первыми попали в Environment. При росте продуктов значительно повышается количество возможных линий переговоров, вследствие чего повышается шанс того, что переговоры приведут к разным результатам. Чтобы максимально улучшить результат группировки заказа, программа последовательно запускает много МАС на одном и том же заказе с разной конфигурацией, а затем выбирает результат с минимальной итоговой ценой заказа. Также возможным способом улучшения является добавление новых соглашений между агентами. Система хорошо справляется с задачей группировки товаров, хотя определенно имеет потенциал к дальнейшему улучшению.

Стоит отметить, что МАС разрабатывалась как полностью автономный сервис, как система поддержки принятия решений. Важным дополнением к МАС является графический интерфейс пользователя, который имеет двойную ценность. Во-первых, графический интерфейс упрощает исследование поведения системы для ее последующего улучшения; во-вторых, за счет упрощения взаимодействия с мультиагентной системой становится возможным ввести роль оператора заказов, который будет работать с системой, – выбирать конфигурацию и контролировать оптимальность результатов с возможностью их ручной модификации.

GUI для работы с МАС

Разработанный графический интерфейс позволяет загрузить необходимый заказ из файла JSON. На экране отображаются продукты, группы продуктов и тарифная сетка заказа (см. Рисунок 2). Интерфейс позволяет запустить МАС на заданном заказе и далее оценить полученные результаты (получившиеся продукты и группы, время выполнения МАС). Для ручного редактирования продуктов и групп продуктов реализована возможность перетаскивать их с помощью мыши, тем самым добавляя продукт к группе продуктов или соединяя группы продуктов [6]. Для более удобного просмотра продуктов и групп добавлена возможность их сортировки по различным критериям (цене, весу, объему, плотности).

Заключение

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

Мультиагентная система поддержки принятия решений для минимизации стоимости ...

в ходе разработки и тестирования решения было выявлено важное свойство МАС – при правильном подборе соглашений между агентами система восстанавливается и продолжает улучшаться, достигая необходимого результата даже после принятия неудачных соглашений. Система почти в 100 % случаев не уступает переборным алгоритмам и показывает хорошие результаты на заказах с большим количеством продуктов. Узким местом таких систем является нечестная конкуренция между агентами, так как применяются те соглашения, которые пришли в систему первыми, и отклоняются соглашения, которые пришли позже и несовместимы с предыдущими. Вследствие этого возможным улучшением систем является создание механизма приема и оценки входящих соглашений с целью отбора и применения лучших.

Рисунок 2. GUI для работы с МАС

Также улучшения результата системы можно достичь сменой реактивной архитектуры агентов на проактивную [7].

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

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