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

Олейникова Светлана Александровна доктор технических наук доцент, Воронежский государственный технический университет 394026, Россия, г. Воронеж, Московский проспект, 14 Oleinikova Svetlana Aleksandrovna Doctor of Technical Science Associate Professor, Department of Automated and Computing Systems, Voronezh State Technical University 394026, Russia, g. Voronezh, Moskovskii prospekt, 14 s.a.oleynikova@gmail.com Другие публикации этого автора

Ромащенко Денис Алексеевич магистр, кафедра автоматизированных и вычислительных систем, Воронежский государственный технический университет 394026, Россия, Воронежская область, г. Воронеж, Московский проспект, 14 Romashchenko Denis Alekseevich Master’s Degree, the department of Automated and Computing Systems, Voronezh State Technical University   394026, Russia, Voronezh, Moskovsky Prospekt 14 denrom93@mail.ru

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

В процессе организации грузоперевозок возникают такие проблемы как: оптимальное построение маршрутов перевозки грузов; сведение к минимуму затрат на перевозки и недогруза транспортного средства. В связи с тем, что заказы могут поступать в систему в то время, когда транспортные средства уже движутся по составленному ранее маршруту, их нужно обрабатывать в режиме «on-line». При этом нужно обеспечить минимальные издержки при эксплуатации транспортных средств.

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

Однако существующие подходы охватывают не все специфики, возникающие при решении современных транспортных задач.

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

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

Рассматривается задача оптимизации процесса грузоперевозок.

Пусть имеется n узлов, каждый из которых характеризуется своими географическими координатами (x_i, y_i), i = 1,…,n.

узлы i и j могут быть соединены между собой «дорогами». Таким образом, систему узлов и дорог можно рассматривать как граф, вершинам которого соответствуют узлы, а ребрам – дороги.

Пусть в системе имеется m транспортных средств (ТС), каждое из которых характеризуется:

- грузоподъемностью c_j, j = 1,…,m;

- месторасположением в данный момент времени (x_j, y_j);

- объемом груза, который средство перевозит в данный момент времени l_j, 0 ≤ l_j ≤ c_j;

- маршрутом движения (т.е. последовательностью узлов u_jk, которые данное средство будет последовательно проходить, доставляя имеющийся груз или забирая уже запланированный ранее заказ). Эта последовательность образует множество U_j=(u_j1,…,u_jkj).

В некоторые моменты времени в систему поступают заказы, причем предполагается, что в данный момент времени может поступить несколько заказов. Каждый заказ характеризуется:

- объемом груза v_k;

- прибылью, которую система получит от перевозки груза p_k;

- географическими координатами источника заказа (x_k1, y_k1);

- географическими координатами назначения заказа (x_k2, y_k2).

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

- объем перевозимого груза;

- «идентификатор» перевозимого груза.

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

`z_(k)=K*sqrt((x_(k2)-x_(k1))^(2)+(y_(k2)-y_(k1))^(2))` . (1)

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

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

Будем также предполагать, что любой заказ можно делить для перевозки несколькими транспортными средствами произвольным образом. Иными словами, если v_k – общий объем заказа k, то в момент времени t идентификатор этого заказа можно поставить нескольким транспортным средствам с обозначением объема от данного заказа.

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

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

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

Таким образом:

id_j[n] – идентификатор n-ного заказа для ТС_j, j=1,…,m;

vol_j[n] – объем груза n-ного заказа для ТС_j, j=1,…,m.

Кроме того, при формировании ограничений задачи необходимо иметь доступ к грузоподъемности ТС в любом из рассматриваемых узлов. Обозначим через l_js объем груза, который ТС_j будет иметь в узле s`epsi` U_j.

Исходя из описанных выше особенностей задачи, сформулируем ее математическую модель. Целью является получение максимальной прибыли. Однако, с учетом того, что любой заказ, поступивший в систему, принимается к обслуживанию, максимизация прибыли в данном случае будет равносильна минимизации затрат на перевозку заказов. Опишем это с помощью критериальных функций. Пусть до приема заказа k у некоторого транспортного средства TC_j была суммарная длина маршрута L_j. С учетом введенных ранее обозначений, она будет определяться следующим образом:

`L_(j)=sum_(i=1)^(k_j)sqrt((x_(j i+1)-x_j)^2+(y_(j i+1)-y_j)^2)` . (2)

При принятии заказа необходимо определить новый путь U_j^нов=(u_j1^нов,…,u_jkj^нов), включающий точки погрузки и выгрузки заказа k. При этом будет рассчитан новый маршрут La_j. Назовем данный маршрут альтернативным. Расчет будет проводиться по формуле (2), только перебор будет осуществляться по узлам множества U_j^нов. Тогда минимизация затрат на перевозку груза ТС_j будет описана следующим образом:

`y_j=La_j-L_j->min` . (3)

Минимизация суммарных затрат будет описываться следующей функцией:

`sum_(j=1)^(m)y_j->min` . (4)

качестве ограничений будут использоваться ограничения на вместимость транспортного средства. Суммарный объем груза, который перевозит транспортное средства, совместно с назначенным объемом данного заказа не должно превышать вместимости ТС. Пусть для ТС_j данный заказ будет n-ным. Тогда:

`l_ju+vol_(j)[n]<=c_j` . (5)

Здесь u – узел на графе, непосредственно предшествующий узлу – источнику заказа для TC_j.

Исследуемая задача относится к классу транспортных задач. От классической транспортной задачи ее отличает, в первую очередь, необходимость получения решений в режиме «on-line». Поскольку заказы поступают в случайные моменты времени, то в момент поступления очередного заказа необходимо учитывать не только текущее расположение транспортных средств, но и их текущую грузоподъемность. Значения этих показателей существенно влияют на выбор решения. Необходимость получения оперативного решения также существенно влияет на выбор метода решения задачи.

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

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

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

Агент – это программно или аппаратно реализованная система, обладающая следующими свойствами ^[2]:

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

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

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

- целенаправленная активность (pro-activity) – способность агентов не просто реагировать на стимулы, поступающие из среды, но и осуществлять целенаправленное поведение, проявляя инициативу. Получая от диспетчера информацию о новом заказе, агент будет анализировать целесообразность использования своего ТС для его выполнения, и, в случае необходимости, уведомить других агентов о принятии данного заказа, об изменении маршрута, появлении свободного места для погрузки и т.д.

Исходя из этого, очевидно, что мультиагентный подход является подходящим для решения данной задачи. Его применение для решения данной задачи обуславливается следующими причинами:

- совместная деятельность агентов должна обеспечить оптимальное (или близкое к оптимальному) решение задачи;

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

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

Любая МАС состоит из следующих основных компонентов ^[2]:

1. Множество организационных единиц, в котором выделяются подмножество агентов, манипулирующих подмножеством объектов.
2. Множество задач.
3. Среда, т.е. некоторое пространство, в котором существуют агенты и объекты.
4. Множество отношений между агентами.
5. Множество действий агентов (например, операций над объектами).

Определим каждый из этих компонентов для исследуемой задачи. Множество объектов, которыми можно манипулировать для решения задачи – это ТС. Манипуляция заключается в возможности назначения и изменения маршрута для них. Тогда организационные единицы, манипулирующие объектами, это диспетчер, принимающий заказы и координирующий все передвижения, и множество абстрактных агентов А_ТС, каждый из которых отвечает за определенное ТС. Цель каждого А_ТС_j, j=1,…,m заключается в принятии такого решения, которое было бы выгодно (с точки зрения минимизации маршрута) данному ТС_j. Множество задач - это заказы, которые необходимо выполнить. С математической точки зрения пространство, в котором будут осуществлять свою деятельность интеллектуальные агенты - это дорожный граф.

Остановимся более детально на определении отношений между агентами и действии агентов. В данной задаче агенты осуществляют тесное взаимодействие для определения целесообразности принятия заказа своему ТС. Проанализируем специфику данного взаимодействия. Агент-диспетчер (А_Д), получив заказ, рассылает всем агентам А_ТС сообщение, в котором отражена вся касающаяся данного заказа информация. Каждый А_ТС_j, получив эти сведения, анализирует степень увеличения маршрута в случае, если он возьмет груз (весь или частично). В качестве результата он должен отправить всем агентам следующее сообщение:

- величина увеличения маршрута;

- объем принятого груза.

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

Рисунок 1 - Структура мультиагентной системы

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

Поскольку в исследуемой задаче агент отвечает за определенное ТС, он, при поступлении нового заказа, должен выполнить следующие основные задачи:

- определить точку своего маршрута, из которой можно забрать заказ;

- определить точку своего маршрута, в которую необходимо следовать дальше (вместе с новым заказом);

- определить точку маршрута, после которой нужно следовать в точку выгрузки нового заказа;

- определить точку маршрута, в которую будет направлено ТС после выгрузки заказа;

- определить величину изменения маршрута с учетом данного заказа и уведомить об этой величине других агентов;

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

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

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

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