Designing of intelligent system for cargo transportation with consolidation



Cite item

Full Text

Abstract

Principles of designing intelligent scheduling system for transport logistics with cargo consolidations are described in the paper. The description of adaptive scheduling method based on multi-agent technologies are given.

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

  1. 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
  2. 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
  3. Handbook of Scheduling: Algorithms, Models and Performance Analysis. Edited by J. Y-T. Leung // Chapman & Hall / CRC Computer and Information Science Series. – 2004.
  4. 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.
  5. Скобелев П.О. Интеллектуальные системы управления ресурсами в реальном времени: принципы разработки, опыт промышленных внедрений и перспективы развития // Приложение к теоретическому и прикладному научно-техническому журналу «Информационные технологии». – 2013. – № 1. – С. 1-32.
  6. 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.
  7. Амелина Н.О., Лада А.Н., Майоров И.В., Скобелев П.О., Царев А.В. Исследование моделей организации грузовых перевозок с применением мультиагентной системы для адаптивного планирования мобильных ресурсов в реальном времени // Проблемы управления. – 2011. – № 6. – С. 31-37.
  8. 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.
  9. 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.
  10. Виттих В.А., Скобелев П.О. Мультиагентные модели взаимодействия для построения сетей потребностей и возможностей в открытых системах // Автоматика и телемеханика. – 2003. –№ 1. – С. 162-169.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2013 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies