Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,931

THE INTELLIGENT SYSTEM FOR TRANSPORTATIONS SCHEDULING OF THE GAS STATIONS NETWORK

Aksenov K.A. 1 Smoliy E.F. 1 Skvortsov A.A. 1 Aksenova O.P. 1 Safrygina E.M. 1 Volkova A.V. 1
1 Ural Federal University named after First President of Russia B.N. Yeltsin
В статье описывается разработка гибридной системы поддержки принятия решений, предназначенной для планирования поставок топлива по сети авто заправочных станций, основанной на имитационном, мультиагентном и экспертном моделировании. Статья фокусируется на описании различных методов, используемых в системе поддержки принятия решений BPsim.DSS. Был разработан прототип интеллектуальной системы планирования на основе BPsim.DSS. Данная система концентрируется на задачах управления и автоматизации отделов логистики. Система реализует следующие функции: прогнозирование объема продаж на будущий день, поиск эффективного плана развоза топлива, планирование рейсов для каждого бензовоза. В имитационной модели BPsim.MAS рассчитывается прогноз объема продаж топлива. Планирование реализуется на основе интеллектуальной подсистемы в BPsim.MSN на основе визуальной машины логического вывода (посредством диаграмм UML) и скриптов языка Transact-SQL. Результаты тестирования подтверждают эффективность данных решений – объем продаж топлива может быть увеличен без дополнительных инвестиций за счет более эффективного использования парка бензовозов.
In this work is considered the development of hybrid decision support systems based on simulation, multi agent and expert modeling for transportations scheduling of the gas stations network. The paper is focused on description of various methods, used in decision support system BPsim.DSS. An intelligent scheduling system prototype, based on BPsim.DSS system, was developed. This system focuses on control and logistics departments activity automation. The following features are implemented: forecast of next day petroleum sale; optimal fuel shipping plan search; shipping scheduling for each gas-tank truck. Petroleum sale forecast is calculated within a BPsim.MAS simulation model. Search and planning capabilities are implemented with SQL scripts generating tools and UML methodology-based conceptual models, included in BPsim.MSN. Monitoring tests allowed effective logistics solutions be developed and deployed. Fuel sale volumes were raised without additional investments, which allowed a more effective use of fuel-tank trucks.
transportations scheduling
gas stations network
simulation modeling
multi agent systems

  Задачи логистики

Основой планирования перевозок являются расписания и графики перевозок, составленные на основе систематизации заключенных договоров, поданных заявок, изучения грузопотоков. Расписания и графики должны обеспечить: удовлетворение потребностей наибольшего числа заказчиков перевозок; минимизацию затрат времени на перевозку; регулярность перевозок; максимизацию объема продаж нефтепродуктов сети АЗС; эффективность использования транспортных средств; взаимосвязь с графиками и расписаниями других видов транспортных средств (например, железнодорожный транспорт, осуществляющий доставку топлива на нефтебазы); минимизацию порожних пробегов транспортных средств.

Обзор существующих методов в сфере планирования и управления перевозками

Организация системы перевозок является сложной задачей, которая фактически сводится к долгосрочному и краткосрочному планированию (в частности, составлению расписаний) перевозок, а также оперативному управлению транспортными средствами.

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

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

Постановка задачи на разработку интеллектуальной системы

Общая задача планирования развоза топлива по сети АЗС заключается в определении плана развоза топлива до начала рабочей смены множества структур вида , где Mi - маршрут i-й перевозки, Бi - бензовоз, осуществляющий i-ю перевозку, Тi - сроки начала и окончания выполнения i-й перевозки, эффективных по критерию суммарных расходов на i-ю перевозку , где Ci1 - стоимость перевозки топлива по маршруту Mi;  Ci2 - величина упущенной прибыли во время дозаправки емкости АЗС топливом; Ci3 - расходы топлива бензовоза Бi и другие расходы при осуществлении i-й перевозки.

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

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

Первый этап заключается в генерации заказов на основе информации о текущих остатках топлива в емкостях АЗС. Этапы 1-3 программно реализованы в фреймовой экспертной подсистеме [3], машина логического вывода которой использует в своей основе конструктор диаграмм поиска решений [5; 6] (рис. 1), построенных на основе диаграмм последовательности языка UML.

Рис. 1. Диаграмма поиска решения.

На втором этапе осуществляется выбор поставщиков для заказов. При помощи модифицированного транспортного алгоритма производится подбор поставщика нефтепродуктов для каждого заказа.

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

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

На пятом этапе проводится уточнение плана-графика в результате его проигрывания в ходе имитационного эксперимента.

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

Программная реализация и применение интеллектуальной системы планирования

Система поддержки принятия решений реализована на базе программного комплекса BPsim.DSS [1; 2], предназначенного для моделирования организационно-технических систем. Архитектура программного комплекса BPsim.DSS построена на принципах трехуровневой иерархической архитектуры InterRaP [1]. Общая схема взаимодействия модулей интеллектуальной системы представлена на рис. 2.

Рис. 2. Схема взаимодействия модулей интеллектуальной системы планирования.

В настоящий момент интеллектуальная система планирования находится в стадии разработки. Готовую интеллектуальную систему планируется внедрить в отдел логистики екатеринбургской компании по обеспечению нефтепродуктами. Сеть данного предприятия состоит из 24 АЗС. Основные параметры модели:

1) количество узлов (блоков модели) всего 179 (в том числе 59 операций и 120 интеллектуальных агентов). Общее количество правил агентов 941;

2) количество ресурсов 703. Количество динамических заявок: бензовозов - 12, заявок на развоз (при имитации в течение «суток») - 22.

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

Был проведен эксперимент по оценке скорости работы алгоритма с моделью, усовершенствованной правилами «глобального условия» и старым алгоритмом. Результаты представлены на рис. 2. В результате разделения типов правил и совершенствования алгоритма добились ускорения работы модели в среднем в 5 раз.

Перед началом планирования специалист по логистике задает основные параметры задачи (рис. 3).

Рис. 3. Форма параметров задачи планирования.

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

Заключение

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

Работа выполнена в рамках государственного контракта 02.740.11.0512.

Рецензенты

  • Поршнев С.В., д.т.н., профессор, заведующий кафедрой Автоматики и информационных технологий, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.
  • Доросинский Л.Г., д.т.н., профессор, заведующий кафедрой Информационных технологий, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.