Designing of intelligent system for cargo transportation with consolidation
- Authors: Skobelev P.O1, Lada A.N1, Kozhevnikov S.S1, Rybak D.S1, Pustovoy I.A1, Tsarev A.V1
-
Affiliations:
- «SEC «Smart Solutions»
- Issue: Vol 21, No 3 (2013)
- Pages: 65-73
- Section: Articles
- URL: https://journals.eco-vector.com/1991-8542/article/view/19849
- DOI: https://doi.org/10.14498/tech.2013.3.%25u
- ID: 19849
Cite item
Full Text
Abstract
Keywords
Full Text
Введение Задача выбора маршрутов и построения расписаний перевозки грузов, являющаяся одной из известнейших задач комбинаторной оптимизации, имеет различные постановки в зависимости от типов ограничений, но наиболее актуальной считается «Задача маршрутизации с ограничением по времени» (Vehicle Routing Problem with Time Windows) [1, 2]. При этом целью является минимизация времени в пути, общего пробега и количества ресурсов при соблюдении условий выполнения каждого заказа в рамках временного окна, сопоставленного с заказом. Решение задачи точными методами за приемлемое время не представляется возможным. В течение последних 50 лет были разработаны различные алгоритмы составления расписаний на основе эвристических методов [3, 4]. Однако практически ни один из них не учитывает возможность динамического изменения ситуации в реальном масштабе времени как один из важнейших факторов, диктуемых современными реалиями бизнес-процессов. Большинство известных алгоритмов подразумевают, что вычисления будут производиться на основании исходных данных, изначально переданных в систему. Но в реальности возникают непредвиденные ситуации: поломки, опоздания, изменения тарифов и т. п., которые влияют на построенное расписание. Для бизнеса требуется быстрая реакция на любое значимое изменение и адаптивная перестройка расписания в реальном времени. Таким образом, актуальной является задача разработки системы, которая могла бы в реальном времени перестраивать расписания ресурсов в условиях динамично меняющегося мира. Эффективное решение подобной задачи может быть построено с использованием мультиагентного подхода [5]. В создаваемых мультиагентных системах разрабатываются и реализуются методы распределенного решения задач (distributed problem solving), когда любая сложная задача (например задача распределения, планирования и оптимизации ресурсов грузового флота) декомпозируется на более простые автономно решаемые подзадачи (выполнения одного заказа, загрузки одного грузовика и др.), а далее между полученными частными решениями происходит взаимное согласование, для чего ищутся и разрешаются конфликты путем переговоров и взаимных уступок в интересах достижения решения общей задачи. Мультиагентный подход к решению задачи управления сборными грузовыми перевозками В статье представлена система управления сборными грузовыми перевозками, которая позволяет решить проблему адаптивного перестроения расписания [6]. По сравнению с предыдущей версией системы грузоперевозок, которая оперировала исключительно перевозками FTL (Full Truck Load) [7, 8], данная система предоставляет возможность планирования перевозок LTL (Less Than Truckload), что приводит к значительному увеличению прибыли от выполнения грузоперевозок [9]. Описание объектной модели системы управления грузоперевозками Для описания предметной области управления грузоперевозками разработана объектная модель, являющаяся основой онтологии предметной области, в которой можно выделить следующие ключевые сущности: Заказ, Требование, Состояние, Груз и Ресурс. На рис. 1 представлена диаграмма классов. Р и с. 1. Диаграмма классов объектной модели Основной сущностью является Заявка (Order), которая описывает Заказ пользователя на выполнение перевозки груза. Данная сущность содержит поля «стоимость перевозки», «стратегия выполнения перевозки». В рамках заявки создается список Грузов (Cargo), подлежащих перевозке. Далее в заявку добавляется список Требований (Requirement). Данная сущность описывает подзадачу в рамках заявки (погрузка, разгрузка, стоянка). Требование может включать список предпочитаемых ресурсов. В этом случае оно может быть запланировано только с использованием указанных ресурсов. Результат работы системы (расписание) представляется в виде набора Состояний (State), которые содержат данные о Местоположении ресурсов и размещении грузов (CargoPart) в определенный момент времени (отметка на временной шкале). Виды агентов, используемых в системе управления грузоперевозками В соответствии с функциональным назначением в системе используются агенты 8 видов (табл. 1), каждый из которых относится к одному из 2 типов: агент потребности (Demand) или агент возможности (Resource) [10]. Типы сообщений агентов представлены в табл. 2. Таблица 1 Типы агентов Вид агента Назначение Требование погрузки (D) Обеспечить погрузку груза в заданный интервал времени и в заданной локации. Требование разгрузки (D) Обеспечить разгрузку груза в заданный момент времени и в заданной локации. При необходимости собрать грузы с нескольких ресурсов, если используется несколько ресурсов в рамках заявки. Требование стоянки (D) Обеспечить стоянку ресурса в течение заданного интервала времени. Требование техобслуживания (D) Обеспечить техобслуживание ресурса в заданный промежуток времени (не связано с конкретной заявкой). Поддержка многопроходного алгоритма (R) Обеспечить поддержку многопроходного алгоритма планирования, используя: – сбор заявок, которым не удалось запланироваться в текущем проходе; – принятие решения о необходимости следующего прохода; – последовательное ослабление ограничений в новых проходах; – фильтрацию опций совместно с агентами требований. Сервисный (R) Обеспечить завершение цикла планирования и промежуточное сохранение текущих результатов в БД через заданные промежутки времени во время цикла планирования. Грузовик (R) Обеспечить предоставление возможности перевозки грузов из точки А в точку Б. Трейлер (R) Обеспечить отслеживание возможной перегрузки трейлера в процессе выполнения заказов. Таблица 2 Типы сообщений Тип сообщений Агент Описание сообщения Распланирование Требование Запрос на перепланирование требования Дефрагментация Требование Сообщение о необходимости провести дефрагментацию своей части расписания по заданным параметрам Допустимость опоздания Требование Включение/выключение признака допустимости опоздания в контексте требования. Отправляется агентом многопроходного планирования Обслуживание допустимого сдвига Требование В зависимости от содержимого сообщения выполняется одно из действий: – сообщение текущего допустимого сдвига требования; – уменьшение текущего допустимого сдвига требования в соответствии с параметрами сообщения; – увеличение текущего допустимого сдвига требования в соответствии с параметрами сообщения Запрос о предоставлении ресурсов Требование Запрос у агента грузовика временного слота для выполнения задачи перевозки грузов Вытеснение груза из трейлера Трейлер Предписание требованию освободить перевозимые грузы из трейлера Внешние изменения Сервисный Сообщение о произведенных пользователем изменениях Запись в следующий проход планирования Многопроходного планирования Сообщение о необходимости занести требование в очередь следующего прохода планировщика Фильтрация опций планирования Многопроходного планирования Запрос на исключение из сообщения опций, конфликтующих с требованиями, не участвующими в текущем проходе планирования Адаптивное планирование сборных грузовых перевозок Для решения задачи управления сборными грузовыми перевозками на основе мультиагентного подхода разработан метод адаптивного планирования. В общем виде процесс работы системы можно разделить на следующие этапы: инициализация; основной цикл планирования; принятие решения о завершении цикла планирования. В случае завершения выполняется пункт 4, иначе – пункт 2; завершение цикла планирования. Инициализация. На этапе инициализации система загружает все необходимые объекты из базы данных (БД) и создает агентов для каждого из требований, зафиксированных в очереди на планирование. Основной цикл планирования. Менеджер агентов последовательно передает управление агентам из основной очереди. Агент, получивший управление, исключается из очереди. Он может ставить других агентов как в основную, так и в экстренную очередь. Менеджер агентов обрабатывает экстренную очередь в приоритетном порядке и не переходит к основной очереди, пока не будет обработана экстренная. Алгоритм гарантирует целостность расписания в случае пустой экстренной очереди. После завершения обработки очередей данные готовы к записи в БД. Принятие решения о завершении цикла планирования. Если все ограничения, предусмотренные многопроходным алгоритмом, отключены системой и за текущий проход не запланировано ни одной заявки, принимается решение о завершении цикла планирования. Завершение цикла планирования. При завершении цикла планирования выполняется подсчет ключевых показателей эффективности (Key Performance Indicators (KPI)) и сохранение результата в БД. После завершения цикла планирования предусмотрена возможность дальнейшей проактивной работы планировщика с целью повышения KPI. Новый цикл планирования может быть инициирован любым изменением со стороны пользователя либо прямым перезапуском планировщика. Построение и анализ опций планирования Для построения опций планирования используется единый механизм для всех типов требований, который состоит из следующих этапов: выборка групп ресурсов для планирования; фильтрация групп ресурсов; действия для каждой группы ресурсов: – определение вариантов планирования; – фильтрация вариантов планирования (первая стадия фильтрации); – построение и анализ опций планирования по вариантам;ъ – фильтрация опций планирования (вторая стадия фильтрации); – оценка опций планирования. Для ускорения процесса реализован механизм кэширования опций планирования. При анализе опций планирования лучшая опция для каждой группы ресурсов записывается в кэш. Далее при планировании агент требования запоминает текущее время и сообщает об изменении данной группы ресурсов менеджеру групп ресурсов, который запоминает время последнего изменения. Если у требования имеется предыдущее запланированное требование, этап подбора групп ресурсов пропускается и используется тот же ресурс, что и в предыдущем требовании. Анализ опции планирования состоит из следующих этапов: построение цепочки операций; построение набора требований, с которыми необходимо проверить конфликты; анализ каждого требования набора обработчиками конфликтов. На данный момент в системе поддерживаются следующие типы конфликтов: по времени, объему, весу, температуре, типу трейлера, совместимости грузов, неразрешимый (если во время анализа будет обнаружен конфликт типа «неразрешимый», опция планирования отклоняется). Обработка конфликтов В системе существуют два обработчика конфликтов: 1) обработчик конфликтов по времени; 2) обработчик конфликтов между грузами. Обработчик конфликтов по времени анализирует следующее условие: tend + δbc ≤ tstart + δstop + δac, (1) где tend – время окончания выполнения планируемого требования; tstart – время начала выполнения рассматриваемого требования; a – локация, с которой начинается выполнение планируемого требования; b – локация, в которой заканчивается выполнение планируемого требования; c – локация, с которой начинается выполнение рассматриваемого требования; δbc – время, необходимое для перемещения между локациями b и c; δac – время, необходимое для перемещения между локациями a и c; δstop – время, на которое возможно смещение рассматриваемого требования. Если условие (1) выполняется, возможно планирование без конфликта по времени с рассматриваемым требованием. Для обработчика конфликтов между грузами перед анализом выполняется построение «карты загрузки» для планируемого требования. Карта представляет собой набор пар <время, индекс загрузки>. Индекс загрузки отражает несколько показателей: загрузку по объему; загрузку по весу; минимальную допустимую температуру для набора грузов; максимальную допустимую температуру для набора грузов; словарь <груз, количество>, подробно отражающий текущую загрузку. Далее производится анализ для каждого требования, входящего в интервал времени, на который построена «карта загрузки», и оценивается возможность разместиться с грузами в трейлере с учетом всех ограничений. Если размещение невозможно, регистрируется конфликт до ближайшего требования погрузки. Алгоритм многопроходного адаптивного планирования Для ускорения планирования, улучшения качества и возможности фиксации приоритетных целей (например планирование без опозданий) реализован механизм многопроходного планирования, цель которого заключается в следующем: – привести как можно большее количество заявок в соответствие набору критериев; – снизить влияние фильтрации по конфликтам, когда весь ресурс (или его часть) становятся недоступными для требований, причем ресурс может освободиться далее в процессе планирования. Ниже приведен алгоритм многопроходного планирования: Инициализация. Все N ограничений активны. В первом проходе разрешены конфликты с любыми требованиями. Проход планирования. Агент многопроходного планирования записывает в очередь для выполнения следующего прохода все требования, которым не удалось запланироваться. Если проход не первый, разрешены конфликты только с требованиями, участвующими в текущем проходе. Как только все требования были запланированы или встали в очередь следующего прохода, активируется агент многопроходного планирования и производит одно из действий: Начало следующего прохода с теми же ограничениями. Для этого очередь следующего прохода должна быть не пуста и за последний проход запланирована хотя бы одна заявка. Далее повторяется пункт 2 для очередного прохода алгоритма. Начало следующего прохода с отменой очередного ограничения. Для этого очередь следующего прохода должна быть не пуста и за последний проход не запланирована ни одна заявка. Далее повторяется пункт 2 для очередного прохода алгоритма. Завершение цикла планирования. Для этого либо очередь следующего прохода должна быть пуста, либо за последний проход не запланирована ни одна заявка и сняты все ограничения. Архитектура и функции системы управления сборными грузовыми перевозками Для реализации представленного алгоритма и анализа выбранного подхода была разработана система управления грузоперевозками. Архитектура системы управления грузоперевозками (рис. 2) построена в соответствии с топологией «звезда». Все коммуникации между модулями системы осуществляются через сервер. Веб-портал представляет собой веб-интерфейс, через который осуществляется ввод заявок, мониторинг ресурсов, просмотр отчетов, ввод фактической информации о расположении ресурсов и этапах выполнения заявок. Р и с. 2. Архитектура системы управления сборными грузовыми перевозками Мобильный интерфейс водителя – программно-аппаратное решение, позволяющее водителю проставлять фактические отметки времени в процессе выполнения заявок, а также просматривать информацию о состоянии автомобиля, показания датчиков, дату и место ближайшего технического обслуживания и ряд других параметров. Мобильное веб-приложение предназначено для водителей, у которых отсутствует мобильный интерфейс водителя. Мобильное веб-приложение имеет ограниченную функциональность по сравнению с мобильным интерфейсом водителя, и его основной функцией является предоставление водителю возможности проставления фактических времен выполнения операций. Модуль поставщика географических данных позволяет получать информацию о скорости и времени движения по дорогам, основываясь на данных из внешних источников гео-информации. Данный модуль использует внешний сервис CloudMade для получения актуальной информации о маршрутах и скорости на дорогах. Модуль поставщика GPS передает в систему данные о фактическом месторасположении грузовиков, основываясь на данных GPS. Модуль планирования предназначен для адаптивного построения расписания и его перестроения при внешних изменениях. Результатом работы планировщика является набор состояний, описывающих назначение определенных ресурсов на некоторые заявки на шкале времени. Расписание ресурсов после выполнения работы модуля планирования представляется в виде диаграммы Гантта (рис. 3). На текущий момент при наличии сцены в 500 заявок и 40 доступных грузовиков вся сцена целиком планируется в течение 30 минут. Инкрементальное планирование (при добавлении новой заявки) выполняется в течение 1 минуты. Р и с. 3. Расписание ресурсов, представленное в виде диаграммы Гантта Выводы В результате проведенных исследований и разработок в области применения мультиагентного подхода к решению задачи управления сборными грузоперевозками была разработана система, позволяющая в реальном времени отслеживать выполнение операций, вносить управляющие воздействия, которые, в свою очередь, влияют на процесс построения расписания ресурсов. В дальнейшем планируется развитие системы в виде Software as a Service (SaaS) решения, которое позволяло бы множеству компаний пользоваться одним решением для оптимизации бизнеса за счет снижения затрат на покупку дорогостоящего программного обеспечения. Планируется также добавить в систему возможность автоматической корректировки построенного плана с учетом GPS-данных, что позволит более точно вычислять время завершения каждой операции, увеличить количество совпадений прогнозируемого времени выполнения с фактическим, что приведет к улучшению качества построенного расписания.About the authors
Petr O Skobelev
«SEC «Smart Solutions»Group President 17 Moscovskoe Shosse, office center «Vertikal», Samara, 443013
Alexander N Lada
«SEC «Smart Solutions»Head of Department 17 Moscovskoe Shosse, office center «Vertikal», Samara, 443013
Sergey S Kozhevnikov
«SEC «Smart Solutions»Deputy General Director 17 Moscovskoe Shosse, office center «Vertikal», Samara, 443013
Dmitry S Rybak
«SEC «Smart Solutions»Senior Developer 17 Moscovskoe Shosse, office center «Vertikal», Samara, 443013
Ivan A Pustovoy
«SEC «Smart Solutions»Senior Developer 17 Moscovskoe Shosse, office center «Vertikal», Samara, 443013
Alexander V Tsarev
«SEC «Smart Solutions»Deputy General Director 17 Moscovskoe Shosse, office center «Vertikal», Samara, 443013
References
- T.K. Ralphsy, L. Kopmanz, W.R. Pulleyblankx, and L.E. Trotter, Jr. On the Capacitated Vehicle Routing Problem. – Available from: On the Capacitated Vehicle Routing Problem
- Jesper Larsen. Parallelization of the Vehicle Routing Problem with Time Windows. – Available from: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.8068
- Handbook of Scheduling: Algorithms, Models and Performance Analysis. Edited by J. Y-T. Leung // Chapman & Hall / CRC Computer and Information Science Series. – 2004.
- Stefan Vos. Meta-heuristics: The state of the Art // Local Search for Planning and Scheduling. Edited by A. Nareyek // ECAI 2000 Workshop, Germany, August 21, 2000 // Springer-Verlag, Germany, 2001.
- Скобелев П.О. Интеллектуальные системы управления ресурсами в реальном времени: принципы разработки, опыт промышленных внедрений и перспективы развития // Приложение к теоретическому и прикладному научно-техническому журналу «Информационные технологии». – 2013. – № 1. – С. 1-32.
- Diyazitdinova A., Ivashenko A., Skobelev P., Tsarev A., Martyshkin D., Syusin I. Multi-Agent Platform for Full Truck Load Scheduling // Interactive Systems and Technologies: The problems of Human-Computer Interaction. Volume III. – Collection of scientific papers. – Ulyanovsk: UlSTU, 2009. – Pp. 132-143.
- Амелина Н.О., Лада А.Н., Майоров И.В., Скобелев П.О., Царев А.В. Исследование моделей организации грузовых перевозок с применением мультиагентной системы для адаптивного планирования мобильных ресурсов в реальном времени // Проблемы управления. – 2011. – № 6. – С. 31-37.
- Granichin O., Skobelev P., Lada A., Mayorov I., Tsarev A. Comparing adaptive and non-adaptive models of cargo transportation in multi-agent system for real time truck scheduling. – Proceedings of the 4th International Conference on Evolutionary Computation Theory and Applications (ECTA’2012), October 5-7, 2012, Barcelona, Spain. – SciTePress, 2012. – Pp. 282-285.
- Granichin O., Skobelev P., Lada A., Mayorov I., Tsarev A. Cargo transportation models analysis using multi-agent adaptive real-time truck scheduling system. – Proceedings of the 5th International Conference on Agents and Artificial Intelligence (ICAART’2013), February 15-18, 2013, Barcelona, Spain. – SciTePress, Portugal, 2013, Vol. 2. – P. 244-249.
- Виттих В.А., Скобелев П.О. Мультиагентные модели взаимодействия для построения сетей потребностей и возможностей в открытых системах // Автоматика и телемеханика. – 2003. –№ 1. – С. 162-169.