Эффективные алгоритмы планирования транспортировки продукции: на примере продуктов с особыми условиями перевозки тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Сластников, Сергей Александрович

• Сластников, Сергей Александрович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Сластников, Сергей Александрович

Оглавление

Введение

Глава 1. Анализ современного состояния проблемы разработки автоматизированных систем управления транспортировкой

1.1 Управление транспортировкой как часть логистической системы

1.2 Обзор программных средств для систем планирования в задачах транспортировки

1.3 Постановка задачи развозки нефтепродуктов

1.4 Задача маршрутизации транспорта и ее виды

1.5 Выводы

Глава 2. Анализ методов решения задач маршрутизации транспорта

2.1 Классификация алгоритмов решения

2.2 Математическая постановка ЗМТ

2.2.1 Трехиндексная постановка ЗМТ

2.2.2 Двухиндексная постановка для симметричной ЗМТ

2.2.3 Постановка Фишера-Джекумера

2.2.4 Постановка, основанная на декомпозиции множеств

2.3 Точные методы решения ЗМТ

2.3.1 Метод ветвей и границ

2.3.2 Динамическое программирование

2.3.3 Целочисленное линейное программирование

2.4 Классические эвристические методы

2.4.1 Конструктивные алгоритмы

2.4.2 Двухфазные алгоритмы

2.4.3 Улучшающие алгоритмы

2.5 Метаэвристические алгоритмы

2.5.1 Имитация отжига

2.5.2 Детерминированный отжиг

2.5.3 Генетические алгоритмы

2.5.4 Методы поиска с запретами

2.5.5 Меметические алгоритмы

2.6 Выводы

Глава 3. Построение модифицированного метода муравьиных колоний для

решения ЗМТ

3.1 Общие положения алгоритмов муравьиных колоний

3.2 Классический алгоритм муравьиных колоний для задачи коммивояжера

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

3.4 Разновидности алгоритма муравьиных колоний

3.4.1 «Элитная» муравьиная система

3.4.2 Максиминная муравьиная система

3.4.3 Ранжированная муравьиная система

3.4.4 Муравьиная система «лучший-худший»

3.5 Анализ применения муравьиных алгоритмов

3.6 Модифицированный алгоритм муравьиных колоний для ЗМТ

3.7 Двухфазный модифицированный алгоритм муравьиных колоний для ЗМТ

3.8 Программная реализация муравьиных алгоритмов для ЗМТ

3.9 Вычислительные эксперименты для ЗМТ

3.9.1 Результаты вычислительных экспериментов

3.9.2 Подбор оптимальных значений параметров алгоритма

3.10 Выводы

Глава 4. Проектирование системы планирования доставки продукции

4.1 Требования к системе

4.2 Проектирование архитектуры системы

4.3 Выбор платформы разработки

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

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Эффективные алгоритмы планирования транспортировки продукции: на примере продуктов с особыми условиями перевозки»

Введение

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

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

• транспортные средства, осуществляющие перевозку, состоят из одной или нескольких раздельных секций;

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

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

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

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

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

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

- исследование существующих методов конструирования маршрутов в задачах развозки продукции;

- конструирование эффективных алгоритмов построения (суб)оптимальных маршрутов транспортных средств на основе существующих подходов;

- адаптация построенных алгоритмов под специфические ограничения транспортировки;

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

- создание программной библиотеки, реализующей предложенные алгоритмы;

- разработка архитектуры системы планирования доставки продукции;

- проектирование интерфейса рабочего места диспетчера, отвечающего за транспортировку.

Методика исследования. В диссертации были использованы методы математического моделирования, итерационные методы дискретной оптимизации, методы математической статистики и объектно-ориентированного программирования.

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

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

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

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

2. Зависимости управляющих параметров алгоритма от числа клиентов задачи.

3. Двухфазный алгоритм, основанный на предложенной модификации.

4. Реализация предложенных алгоритмов в виде программной библиотеки.

5. Архитектура системы планирования доставки продукции. Внедрение результатов работы.

1. Разработанные алгоритмы и программное обеспечение использовались при проектировании подсистемы управления транспортировкой нефтепродуктов для розничных сбытовых сетей нефтяных компаний

2. Полученные в диссертации результаты использованы в учебном процессе на кафедре «Кибернетика» МИЭМ НИУ ВШЭ в рамках дисциплин «Корпоративные информационные системы», «Проектирование информационно-управляющих систем»

3. Полученные в диссертации результаты использованы в учебном процессе в институте ИБС НИТУ «МИСиС» (Москва) на кафедре «Информационные бизнес системы» в рамках дисциплины «Архитектура предприятия и проектирование КИС»

Апробация результатов. Основные положения и отдельные результаты были представлены на конференциях:

1. VIII Всероссийская научно - практическая конференция (с участием стран СНГ) «Системы автоматизации в образовании, науке и производстве» -Новокузнецк, 2011 г.

2. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ - Москва, 2011 г.

3. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, посвященная 50-летию МИЭМ-Москва, 2012 г.

4. Четвертая ежегодная научно-практическая конференция «Информационные бизнес системы» - Москва, 2012 г.

5. International Scientific-Practical Conference «Innovative information technologies» - Prague, 2012 г.

6. Международная научно-практическая конференция «Инновации на основе информационных и коммуникационных технологий» - Сочи, 2012 г.

7. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ НИУ ВШЭ - Москва, 2013 г.

8. 2nd International Conference on Information Technology and Quantitative Management, ITQM - Moscow, 2014 r.

Публикации. По теме диссертации опубликовано 11 печатных работ, в том числе 3 статьи в журналах из перечня ВАК.

Глава 1. Анализ современного состояния проблемы разработки автоматизированных систем управления транспортировкой

1.1 Управление транспортировкой как часть логистической системы

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

• поставщиков сырья;

• производителей;

• распределительные центры (дистрибьюторы);

• розничных поставщиков (ритейлеры);

• конечных потребителей.

В последние годы был разработан ряд подходов к интеграции логистических систем: концепция «быстрого реагирования», концепция эффективного ответа потребителю и управление запасами на стороне поставщика.

Концепция «быстрого реагирования» (Quick Response) была разработана группой ведущих американских текстильных и швейных компаний для борьбы с неоправданно долгими сроками выполнения заказов [34]. Применение метода «быстрого реагирования» стало возможным после разработки соответствующих информационных технологий, в частности электронного документооборота (.Electronic Data Interchange), штрихового кодирования и лазерных сканеров. Суть метода заключается в том, чтобы оценивать спрос в реальном времени, насколько это возможно, и как можно ближе к конечному потребителю. Таким образом, для того, чтобы получить выгоду от использования концепции «быстрого реагирования», необходимо наладить обмен информацией об уровне спроса между звеньями цепочки поставок.

Концепция эффективного ответа потребителю {Efficient Customev Response) была разработана в 1992 году лидерами индустрии товаров повседневного спроса и является развитием метода «быстрого реагирования». Одной из приоритетных задач этого метода является сокращение показателя «отсутствие товара на полке магазина». Такое отсутствие может быть обусловлено несвоевременной или неполной поставкой товара, поставкой бракованного или незаказанного товара, ошибками при заказе товара или резким увеличением спроса. Для уменьшения этого показателя внедряется система автоматического контроля наличия товара, что позволяет отслеживать товарные остатки. Кроме того, накапливается и анализируется история продаж, которая позволяет прогнозировать изменение спроса и, таким образом, заказывать нужное количество товара в оптимальное время.

Следующей ступенью развития методик интеграции логистических систем стало появление концепции управления запасами на стороне поставщика (Vendor Managed Inventory, VMI), которая впервые была предложена и внедрена компанией Wal-mart, крупнейшей в мире сетью магазинов розничной торговли. Методика VMI предполагает, что вся ответственность за управление запасами клиентов ложится на поставщика. Концепция управления запасами на стороне поставщика - это нечто большее, чем просто партнерская программа между

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

По данным, изложенным в работе [89], внедрение программы УМ1 приносит для поставщиков и потребителей ряд преимуществ и ограничений. При прочих равных условиях стратегия управления запасами на стороне поставщика позволяет снизить уровень запасов поставщика больше, чем концепция «быстрого реагирования», которая в свою очередь выгоднее использования традиционной методики управления запасами и транспортом. Кроме того, чем выше средний уровень и изменчивость спроса, тем большую выгоду от снижения объемов страховых запасов получает дистрибьютор. Следствием снижения объемов хранимых запасов является увеличение частоты поставок.

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

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

Эту задачу можно разбить на следующие подзадачи:

1) прогнозирование спроса на основании информации о непосредственных продажах;

2) составление среднесрочного плана транспортировки и пополнения запасов у потребителей.

В работах [25, 64] представлены методы прогнозирования спроса как для случая равномерного спроса на продукцию, так и для случая скачкообразного спроса.

Вторая подзадача получила в литературе название задачи распределения запасов (.Inventory Routing Problem). В классической задаче распределения запасов рассматривается процесс распределения одного типа продукции с одного склада множеству клиентов. О каждом потребителе известно: ежедневный объем расходования продукции, размер локального склада (максимальный объем продукции, который может храниться у ритейлера), начальный уровень запасов на локальном складе.

В ходе решения этой задачи определяется:

• когда обслуживать каждого из потребителей;

• какой объем продукции необходимо поставить каждому из потребителей;

• как распределить грузы, меньшие вместимости одного транспортного средства, по маршрутам.

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

1.2 Обзор программных средств для систем планирования в задачах транспортировки

На рынке программного обеспечения существует ряд продуктов, решающих задачи, связанные с управлением транспортом и логистикой. Наиболее мощными и востребованными на мировом рынке являются решения компаний SAP, Oracle, IBM, PSI Logistics, на российском рынке можно выделить лишь программный продукт, построенный на платформе компании 1С. При попытке анализа подобного рода систем и их функциональных особенностей неизменно встает проблема, связанная с закрытостью данных коммерческих продуктов и отсутствием их описания. Все же попытаемся кратко рассмотреть их через призму задачи построения оптимальных маршрутов.

Компания SAP разработала решение mySAP Supply Chain Management (SCM), предназначенное для управления цепочками поставок. Ключевым компонентом в этой системе является пакет SAP Advanced Planner and Opíimizer (APO), который представляет собой набор инструментов цепи поставок для развитого планирования и принятия решений [10]. Одним из таких инструментов является функция планирования транспортировки/транспортных средств (Transportation Planning/Vehicle Scheduling), доступная начиная с версии SAP АРО 3.0 с 2001 года. Эта функция позволяет планировать транспортные средства и маршруты транспортировки с помощью следующих действий:

• рассматривает жесткие и мягкие ограничения, причем мягкие ограничения моделируются в виде штрафов в функции затрат;

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

В ее основе лежат стандартные эвристические методы, которые используют локальные критерии оптимизации. Позже эта и некоторые другие функции выделилсь в отдельную подсистему SAP Transportation Management, которая была разработана для транспортных и логистических требований всех отраслей промышленности. Она поддерживает целостную систему процессов хранения, выполнения заказов и транспортировки. Безусловным достоинством данного продукта является то, что он помогает оптимизировать процессы управления транспортировкой, в том числе и опасных грузов (к которым можно отнести, в частности, нефтепродукты). В целом, это очень мощное программное решение, дающее возможность автоматического осуществления маршрутизации заказов, сотрудничества с транспортными компаниями, создания всевозможной документации, координации со складскими операциями и решения большого спектра других логистических задач. Недостатками данного продукта являются трудность и длительность его внедрения, сложность использования и высокая стоимость.

Согласно исследованиям Magic Quadrant for Transportation Management Systems агентства Gartner в 2010 и 2011 годах система Oracle Transportation Management является лидером в области систем управления транспортировкой. Программный модуль Oracle Transportation Management входит в состав комплекса приложений для управления цепочками поставок (Supply Chain Management), но является самостоятельной системой и может внедряться как отдельный продукт. Oracle Transportation Management позволяет объединить и оптимизировать планирование и осуществление перевозок, оплату фрахта, а также автоматизировать бизнес-процессы, связанные с любым видом транспортировки груза - от автомобильных перевозок до перевозок по воздуху, воде и железным дорогам, включающих в себя несколько транспортных этапов [91]. Основные возможности системы состоят в следующем:

• планирование перевозок;

• оптимизация использования транспортного оборудования;

• оптимизация погрузочно-разгрузочных работ;

• организация мультимодальных перевозок;

• управление перевозками для любых видов транспорта: авиа, авто, железнодорожным и морским;

• оптимизация маршрутов доставки;

• выбор тарифов и маршрутов доставки в зависимости от заданных режимов перевозки и перевозчиков;

• графическое представление тарифов (тарифные диаграммы);

• отслеживание отгрузок;

• единое информационное пространство с поставщиками и заказчиками;

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

• плановая и фактическая калькуляция доходов и расходов по перевозке;

• расчет стоимости перевозок на основании различных алгоритмов.

Система предлагает несколько алгоритмов построения маршрута и

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

IBM Sterling Transportation Management System является системой управления перевозчиками с использованием облачных вычислений, которая оптимизирует и преобразует сеть цепочек поставок путем планирования и отслеживания всех процессов входящей и исходящей перевозки. Это решение позволяет [93]:

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

• обеспечить прозрачность процессов доставки в реальном времени;

• принимать решения относительно процессов цепочки поставок с использованием бизнес-аналитики.

Компания PSI Logistics разработала систему управления транспортом PSI TMS, которая может применяться в различных областях, в том числе при перевозке сыпучих материалов и штучных грузов. Она поддерживает перевозку различными видами транспортных средств, в числе которых грузовые автомобили, железнодорожные составы, речные суда, а также смешанные транспортные средства. PSI TMS состоит из следующих модулей, которые используются как вместе, так и по отдельности [92]:

• планирование поездок и оптимизация погрузки;

• транспортное управление и контроль;

• управление транспортными заказами и ценами;

• стратегическое планирование транспортной сети;

• сервисный бухгалтерский учет.

Система управления перевозками " 1С:Предприятие 8. TMS Логистика. Управление перевозками" - специализированное решение, которое построено на базе технологической платформы " 1С:Предприятие 8.2" и предназначено для автоматизированного управления бизнес-процессами отдела транспортной логистики предприятия. Использование системы направлено на решение следующих задач [90]:

• создание цепочек перевозок, которые могут состоять из звеньев, обслуживаемых разными видами транспорта;

• планирование цепочки транспортных логистических процессов совместно с различными подразделениями компании;

• выбор исполнителя перевозки по каждому звену перевозки;

• выбор вида перевозки: в отдельном транспортном средстве или в составе сборного груза.

Однако данная система не автоматизирует задачу составления маршрутов каждого транспортного средства, а лишь позволяет визуализировать ее.

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

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

• нахождение оптимальных или субоптимальных решений для задачи развозки нефтепродуктов;

• возможность ее применения независимо от способа организации логистической цепочки доставки нефтепродуктов;

• инвариантность относительно используемых других информационных систем.

1.3 Постановка задачи развозки нефтепродуктов

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

является эффективное планирование перевозок, позволяющее оптимизировать издержки на доставку нефтепродуктов.

Основными задачами службы планирования перевозок являются:

1. Получение информации о заказах АЗС и предложениях нефтехранилищ обслуживаемых компанией.

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

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

Наибольший интерес представляет последняя задача, так как именно на этом этапе возможно добиться наибольшей экономической выгоды путем минимизации расходов на транспортировку. Ее можно описать следующим образом: имеется N нефтебаз, с которых М видов топлива развозятся по п АЗС. Для перевозки топлива используются бензовозы, состоящие из одной или нескольких емкостей. При наливе емкость бензовоза заполняется полностью; при сливе полностью освобождается, таким образом, частичный налив или слив не допускаются. Бензовоз выходит на линию из автопарка и возвращается в парк, количество автопарков равно К, в парке / имеется бензовозов / (7=1,...,К).

Список литературы диссертационного исследования кандидат наук Сластников, Сергей Александрович, 2014 год

Список Я

„Дсбжить » <& л

id 1 Название

1 467,000 'ЛЖОЙЛ-Центрни})тепродукт'' АЗС №503

i____I

2 470 ООО ' ЛЖОЙЛЧДентрнефтелродукт" АЗС №429

3 486 ООО ' ЛЖОЙЛ-Центрнефтепродукт" АЗС №505

4 487 ООО 'ЛУКОЙЛ-Цектрнефтегродукт" АЗС №500

5 488 ООО 'ЛУКОЙтДентрнефтьгродукт ' АЗС №504

6 489 ООО ''ЛУКОЙЛ-Центрнефтегродукт" АЗС №511

7 530 Нефтебаза ООО «ЛУКОЙЛ-Центра юфтелродукт » Софри-ю

Аббревиатура АЗС N«503 АЗС №429 АЗС №505 АЗС №500 АЗС №504 АЗС №511 1-6 №1

L

Фпгьтры

Записей 7, фт^трь! не установлены

Рис. 4.4. Справочник клиентов

Список Справочник клиентов О

„ Эака»ы I ч^ Сгракмник клиенте» О

Ншевиие * Нефтебаза ООО «ЛУКОИЛ-Центриафталродукт» Софрто А «5«

Долгота .37,99 """"" """ ~~ ~

Аббрваыгура «N91

—Р а

—эалатъяеосполохв»««нашртв >

Карта Л/!**

п:

^ Со>р»»1-ъ| ^ Го ооо ] [* Ф Выход

Рис. 4.5. Отображение картографической информации о клиенте Кроме этого, в диалогах может быть отображена информация о других объектах, непосредственно связанных с данным. Транспортное средство, например, характеризуется набором отсеков (емкостей), из которых оно состоит. Информация об этом отображается внутри соответсвующего диалога в виде таблицы (рисунок 4.6).

ИжтроЬн Скм* Спрмк«

Главная »* Заказы Справочники

V Справочник клиентов

V Справочник складов

V Справочник расстояний ^ Транспортные средства

V Емкости

V Товары

V» Единицы измерения

* Отчеты

* • Отчеты

л-" Администрирование

» Конфигуратор системы » Настройки доступа

* Протокол действий пользователей

^ Экспорт и импорт данных

Шаблоны экспорта Экспорт * Загрузчик данных

Список Транспортное средствоО

Номерной знак А111НК199 ГЬк->* «¿л-ная сбиэя гругспод счнэ ть 2Э>Э0 л

Добавить Осрытъ *" * а ) Емкость

1 514 Бак 500 л

Трек пор тми средство О ]

Не эксплуатируется

683 Бак на 1000 литров б88 Бак на 1000 литров

Фипктпы _

Записей 3, фильтры не установлены

^Сохранить] | Готово <5 Выход

Рис. 4.6. Диалог транспортного средства

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

Эжазы С-. Закдд

9 ЛобАВИТъ

Н*чагы*>и к/иен

1 N9

2 АХ N9^29

3 АЗС N0503

4 АЭС N9511

Допустимые транспортные средам ля« »им О

| Транспортное средство АШМК199 * Ы^]

_х _ _ _ " * 4

Квечы! клиент Пердеоммое количество Едчеша нмюрвия Тоеар

АЭСУНЭТ 4 ци тонна АИ 95 Евро 5

АЗС №503 3 00 топка ДИ 95 Евро 5

АЗС N9511 3 00 тонн» АН 95 Евро 5

У Орыс-о Гоод Хотьково / **

(тс(Точка прибытия!

Кр-Ю рГОНиь'СК

р")ч"> п гв а

V Стараг

Ьь ¿¿.их I " К)Г

Ху*ОВ I- и Лыт«р*о р-зм ц»0*.

^ ли ел* £у

ПОЛЛОМ

г'ои.а

Под Доиод'-д000-

Г рбнки 4»>а

* ^ Фоь 5 <к

!

Записей 4 фигътры ив установлены

О Яндекс Сообщить об 9тибке Условия использования

¡Ц Сохранить) } Готово; Выход

Рис. 4.7. Отображение построенных маршрутов

Заключение

На основании выполненной диссертационной работы можно сделать следующие основные выводы:

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

2) Показано, как задачу транспортировки продукции с особыми условиями перевозки можно свести к задаче маршрутизации транспорта с ограничениями грузоподъемности на примере задачи развозки нефтепродуктов.

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

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

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

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

6) Разработанные алгоритмы были реализованы в виде динамической программной библиотеки на языке С++.

7) Для системы планирования доставки продукции была спроектирована архитектура и выбрана технологическая платформа для ее реализации.

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

Список литературы

Источники на русском языке

1. Басова A.B. Математические модели и генетические методы решения нелинейных задач транспортного типа: дис. канд. техн. наук: 05.13.18, 05.13.17 / Басова Алина Викторовна. - Ростов-на-Дону, 2004. - 126 с.

2. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. Воронеж: ВГТУ, 1995. - 69 с.

3. Бауэрсокс Д.Д., Клосс Д.Д. Логистика: интегрированная цепь поставок. 2-е изд. М.: ЗАО «Олимп-бизнес», 2008. - 640 с.

4. Гладков JI.A., Курейчик В.М., Курейчик В.В. Генетические алгоритмы. Ростов-на-Дону: ООО «Ростиздат», 2004. - 400 с.

5. Дубравина Т.В. Решение модифицированных транспортных задач металлургического комплекса с использованием генетических алгоритмов: дис. канд. техн. наук: 05.13.01 / Дубравина Татьяна Викторовна. - М., 2005. - 140 с.

6. Емельянова Т.С. Об одном генетическом алгоритме решения транспортной задачи с ограничением по времени. // Известия Южного Федерального университета. Технические науки. - 2008. - №4 (81). - С. 45-50.

7. Емельянова Т.С. Разработка и исследование алгоритмов решения транспортных задач с использованием генетических методов: автореф. дис. канд. техн. наук: 05.13.01 / Емельянова Татьяна Сергеевна. - Таганрог., 2009.- 16 с.

8. Еремеев A.B. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации: дисс. канд.физ.-мат.наук: 05.13.16 / Еремеев Антон Валентинович. - Омск, 2000. - 119 с.

9. Игнатьев A.JI. Использование алгоритма муравьиных колоний для решения задачи маршрутизации транспортных средств. // Современные информационные технологии и ИТ-образование : Сборник трудов. — М.: МГУ, 2009. - 846 с.

10.Кале В. Внедрение SAP R/3. Руководство для менеджеров и инженеров. Пер. с англ. П.А. Панов. М.: Компания АйТи, 2006.-470 с.

11. Конников П.В., Кудинов В.А. Оптимизация методом муравьиной колонии как метаэвристика. // Ученые записки. Электронный научный журнал курского государственного университета. - 2008. - №4. - С. 27-31.

12. Курейчик В.М., Кажаров A.A. О некоторых модификациях муравьиного алгоритма. // Известия Южного Федерального университета. Технические науки. -2008. - №4 (81). - С. 7-12.

13. Меламед И.С., Сигал И.Х. Задача коммивояжера: некоторые вопросы теории, алгоритмы, эксперимент. М.: ВЦ РАН, 1997. - 30 с.

14. Пожидаев М.С. Алгоритмы решения задачи маршрутизации транспорта: дис. канд. техн. наук: 05.13.18 / Пожидаев Михаил Сергеевич. - Томск, 2010.- 136 с.

15. Прокофьева О.С. Разработка методики оптимизации развозочных маршрутов: дис. канд. техн. наук: 05.22.10 / Прокофьева Оксана Сергеевна. -Иркутск, 2004.- 167 с.

16. Сластников С.А. Анализ методов решения задачи маршрутизации транспорта. // Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ: Тезисы докладов. - М.: МИЭМ, 2011. - С.73-74.

17. Сластников С.А. Выбор методики интеграции логистической системы и ее применение. // Труды VIII Всероссийской научно-практической конференции (с участием стран СНГ) AS'2011 «СИСТЕМЫ АВТОМАТИЗАЦИИ в образовании, науке и производстве». - Новокузнецк: изд. центр СибГИУ, 2011. - С. 291-295.

18. Сластников С.А. Проблема интеграции управления запасами и транспортировки автомобильного топлива. // Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, посвященная 50-летию МИЭМ: Тезисы докладов. - М.: МИЭМ, 2012. - С.65-66.

19. Сластников С.А. Анализ эвристических и метаэвристических методов для решения задачи распределения автомобильного топлива. // Качество. Инновации. Образование.— 2012. —№ 11.-С. 50-55.

20. Сластников С.А. Применение метаэвристических алгоритмов для задачи маршрутизации транспорта. // Экономика и математические методы. — 2014. -Том 50.-№ 1.-С. 117-126.

21. Сластников С.А. Решение задач маршрутизации транспорта методом муравьиных колоний // Мехатроника, автоматизация, управление. - 2014 . — № 1. - С. 18-21.

22. Трутнев Д.Р. Архитектуры информационных систем. Основы проектирования: Учебное пособие. — СПб.: НИУ ИТМО, 2012. - 66 с.

23. Чернышев С.В. Модели, методы и алгоритмы эффективного решения задачи маршрутизации транспорта на графах больших размерностей: автореф. канд. физ-мат. наук: 05.13.18 / Чернышев Сергей Владленович. -М., 2011.-22 с.

24. Штовба С.Д. Муравьиные алгоритмы. // Exponenta Pro. Математика в приложениях. - 2003. - №4. - С. 70-75.

Источники на иностранных языках

25. Armstrong J.S., Green К.С. Demand forecasting: evidence-based methods. // Working Papers 24/05. - Australia. -Monash University, 2005. -18 p.

26. Augerat P., Belenguer J.M., Benavent E., Corberan A., Naddef D., Rinaldi G. Computational results with a branch and cut code for the capacitated vehicle routing problem. // Technical report RR 949-M. - Grenoble, France. - University Joseph Fourier, 1995.

27. Balinski M., Quandt R. On an integer program for a delivery problem. // Operations Research. - 1964.-№ 12.-P. 300-304.

28. Barrios В., Faulin J., Jorba J., Juan A., Riera D. On the use of Monte Carlo simulation, cache and splitting techniques to improve the Clarke and Wright

savings heuristics. // Journal of the Operational Research Society. - 2011. - №62. -P. 1085-1097.

29. Beasley J. Route-first cluster-second methods for vehicle routing. // Omega. — 1983. -№ 11.-P. 403^108.

30. Belov A., Slastnikov S. A Metaheuristic Approach for the Problem of Motor Fuel Distribution // 2nd International Conference on Information Technology and Quantitative Management, ITQM 2014, Volume 31. - Procedía Computer Science, 2014. P.143-150.

31. Bin Y., Zhong-Zhen Y., Baozhen Y. An improved ant colony optimization for vehicle routing problem. // European Journal of Operational Research. - 2009. -№ 196.-P. 171-176.

32. Bell J., McMulIen P. Ant Colony Optimization Techniques for the Vehicle Routing Problem. // Advanced Engineering Informatics. - 2004. - № 18. - P. 4148.

33. Blasum U., Hochstattler W. Application of the Branch and cut method to the Vehicle Routing Problem. // Technical Report. - Germany. - University of Cologne, 2000. - 20 p.

34. Bowers M., Agarwal A. Hierarchical production planning: Scheduling in the apparel industry. // International Journal of Clothing Science and Technology. — 1993. - Vol. 5. №3/4. - P. 36^13.

35. Braysy O., Dullaert W., Hasle G., Mester D., Gendreau M. An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows. // Transportation Science. -2008. -№42.-P. 371-386.

36. BuIInheimer B., Hartl R.F., Strauss C. A new rank based version of the Ant System - A computational study. // Working Papers Adaptive Information Systems and Modelling in Economics and Management Science. - Vienna. -Vienna University of Economics and Business, 1997. - 16 p.

37. Bullnheimcr B., HartI R.F., Strauss C. Applying the ant system to the vehicle routing problem. // Second Metaheuristics International Conference, MIC'97. -France: Sophia-Antipolis, 1997.

38. Chen X., Ong Y.S., Lim M.H., Ping Y.S. Cooperating memes for vehicle routing problems. // International Journal of Innovative Computing, Information and Control. -2011. -Vol. 7. №11 - P. 6483-6506.

39. Christofides N., Eilon S. An algorithm for the vehicle-dispatching problem. // Operational Research Quarterly. - 1969. - № 20. - P.309-318.

40. Christofides N., Eilon S., Watson-Gandy C. Distribution Management: Mathematical Modelling and Practical Analysis. - Griffin, London. - 1971. - 240 P-

41. Christofides N., Mingozzi A., Toth P. State space relaxation procedures for the computation of bounds to routing problems // Networks. - 1981. - №11. - P. 145-164.

42. Clarke G., Wright J. Scheduling of vehicles from a central depot to a number of delivery points. // Operations Research. - 1964. -№ 12. - P. 568-581.

43. Colorni A., Dorigo M., Maniezzo V. Distributed Optimization by Ant Colonies. // In European Conference on Artificial Life. - Paris: Elsevier Publishing, 1991. -P. 134-142.

44. Cordón O., Fernandez de Viana I., Herrera F., Moreno, L. A New ACO

Model Integrating Evolutionary Computation Concepts: The Best-Worst Ant System. // In Proceedings of ANTS 2000 - From Ant Colonies to Artificial Ants: Third International Workshop on Ant Algorithms, 2000. - P. 22-29.

45. Desrochers M., Desrosiers J., Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. // Operations Research. - 1992. -№40.-P. 342-354.

46. Desrochers M., Desrosiers J., Soumis F. Routing with time windows by column generation. //Networks. - 1984. -№14 -P. 545-565.

47. Desrochers M., Laporte G., Nobert Y. Optimal routing under capacity and distance restrictions. // Operations Research. - 1985. -№33. - P. 1050-1073.

48. Dijkstra E. A note on two problems in connexion with graphs. // Numerische Mathematik. - 1959. - Vol. 1. - P. 269-271.

49. Dorigo M. Optimization, Learning and Natural Algorithms: PhD thesis, Politécnico di Milano, Italie, 1992.

50. Dorigo M., Di Caro G. The Ant Colony Optimization meta-heuristic. // In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization. — London: McGraw-Hill, 1999.-P. 11-32.

51. Dorigo M., Gambardella L.M. Ant Colonies for the Traveling Salesman Problem. // BioSystems. - 1997. -№ 43. - P.73-81.

52. Dorigo M., Stutzle T. Ant Colony Optimization. - Cambridge: MIT Press, 2004.-319 p.

53. Dueck G. New optimization heuristics: The great deluge algorithm and the record-to-record travel. // Journal of Computational Physics. — 1993. — № 104. -P. 86-92.

54. Dueck G., Scheurer T. Threshold accepting: A general purpose optimization algorithm. //Journal of Computational Physics. - 1990. -№ 90. - P. 161-175.

55. Foster B., Ryan D. An integer programming approach to the vehicle scheduling problem. // Operational Research Quarterly. - 1976. -№27. - P. 367-384.

56. Fisher M., Jaikumar R. A generalised assignment heuristic for vehicle routing problem.//Networks. - 1981.-№11.-P. 109-124.

57. Gelatt D., Kirkpatrick S., Vecchi C. Optimization by Simulated Annealing. // Science, New Series. - 1983. - Vol. 220. №4598. - P. 671-680.

58. Gendreau M., Hertz A., Laporte G. A Tabu Search Heuristic for the Vehicle Routing Problem. // Management Science. - 1994. - №10, Vol. 40. - P. 12761290.

59. Gillett B., Miller L. A heuristic algorithm for the vehicle dispatch problem. // Operations Research. - 1974. - №22. - P. 340-349.

60. Glover F. Future Paths for Integer Programming and Links to Artificial Intelligence. // Computer and Operations Research. - 1986. - Vol. 13. №5. - P. 533-549.

61. Glover F. Tabu Search. // INFORMS Journal on Computing. - 1989. - Part 1: Vol. 1. №3; Part 2: Vol. 2. № 1.

62. Haimovich M., Rinnooy Kan A. Bounds and heuristics for capacitated routing problems. // Mathematics of Operations Research. - 1985. - №10. - P. 527-542.

63. Holland J. Adaptation in Natural and Artificial Systems. - Ann Arbor: The University of Michigan Press, 1975. - 183 p.

64. Hyndman R.J., Shenstone L. Stochastic models underlying Croston's method for intermittent demand forecasting. // Journal of Forecasting. - 2005. -Vol. 24. №6.-P. 389-402.

65. Kinderwater G., Savelsbergh M. Vehicle routing: Handling edge exchanges. // In: E.H.L. Aarts, J.K. Lenstra (eds.). Local Search in Combinatorial Optimization. - Chichester: Wiley, 1997. - P. 337-360.

66. Laporte G. The Vehicle Routing Problem: An overview of exact and approximate algorithms. // European Journal of Operational Research. - 1992. -№59.-P. 345-358.

67. Laporte G., Gendreau M., Potvin J., Semet F. Classical and Modern Heuristics for the Vehicle Routing Problem. // International Transactions in Operation Research. - 2000. - Vol. 7. №4-5. - P. 285-300.

68. Laporte G., Nobert Y. Exact algorithms for the vehicle routing problem. // In: S. Martello, G. Laporte, M. Minoux and C. Ribeiro (eds.). Surveys in Combinatorial Optimization. - Amsterdam: North-Holland, 1987.-P. 147-184.

69. Laporte G., Semet F. Classical Heuristics for the Vehicle Routing Problem. // Les Cahiers du Gerad. - 1999. - G-98-54. - 21 p.

70. Lin S. Computer solutions of the traveling salesman problem. // Bell System Technical Journal. - 1965. - № 44. - P. 2245-2269.

71. Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. // C3P Report 826: California Institute of Technology, 1989.-67 p.

72. Nguyen Q.C., Ong Y.S., Lim M.H. A probabilistic memetic framework. // IEEE Transactions on Evolutionary Computation. - 2009. - Vol. 13. №3. - P. 604-623.

73. Orloff C. Route-constrained fleet scheduling. // Transportation Science. - 1976. -№10.-P. 149-168.

74. Rao M., Zionts S. Allocation of transportation units to alternative trips - A column generation scheme with out-of-kilter subproblems. // Operations Research. - 1968. - №16. - P. 52-63.

75. Rego C., Roucairol C. A Parallel Tabu Search Algorithm Using Ejection Chains for the Vehicle Routing Problem. // In: Meta-Heuristics: Theory and Applications. Osman I.H., Kelly J.P. (eds.). Boston: Kluwer Academic Publishers, 1996.-P. 661-675.

76. Rochat Y., Taillard E. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. // Journal of Heuristics. - 1995. -№1. — P. 147-167.

77. Sodsoon S., Changyom P. Max-Min Ant System (MMAS) for Vehicle Routing Problem with Time Windows. // KKU Engineering Journal. - 2011. - Vol.38. №3 - P. 313-323.

78. Sodsoon S., Sindhuchao S. A Max-Min Ant System Applied to The Vehicle Routing Problems. // RMUTI Journal. - 2008. - №3. - P. 39-47.

79. Solomon M. Algorithms for the vehicle routing and scheduling problem with time window constraints. // Operations Research. - 1987. - №35. - P. 254-265.

80. Shtovba S.D. Ant Algorithms: Theory and Applications. // Programming and Computer Software. - 2005. - Vol. 31. № 4. - P. 167-178.

81. Stutzle T., Hoos H. Improvements on the Ant-System: Introducing the MAX-MIN Ant System. // In Proceedings of the International Conference in Norwich Artificial Neural Nets and Genetic Algorithms, 1998. - P. 245-249.

82. Stutzle T., Hoos H. MAX-MIN Ant System. // Future Generation Computer Systems.-2000.-№16.-P. 889-914.

83. Thompson P., Psaraftis H. Cyclic transfer algorithms for the multivehicle routing and scheduling problems. // Operations Research. - 1993. - №41. P. 935946.

84. Toth P., Vigo D. The Granular Tabu Search (and its Application to the Vehicle Routing Problem). // INFORMS Journal on Computing. - 2003. - Vol. 15. №4. -P. 333-346.

85. Toth P., Vigo D. The vehicle routing problem. - Philadelphia: SIAM Monographs on Discrete Mathematics and Applications, 2002. - 367 p.

86. Wren A. Computers in Transport Planning and Operation. London: Ian Allan, 1971.- 152 p.

87. Wren A., HoIIiday A. Computer scheduling of vehicles from one or more depots to a number of delivery points. // Operational Research Quarterly. — 1972. -№23.-P. 333-344.

88. Xu J., Kelly J. A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem. // Transportation Science. - 1996. - Vol. 30. №4. - P. 379-393.

89. Yao Y., Evers P., Dresner M. Supply Chain Integration in Vendor-Managed Inventory. // Decision Support Systems. - 2007. - Vol. 43. №2. - P. 663-674.

Интернет-источники

90. 1С:Предприятие 8. TMS Логистика. Управление перевозками // URL: http://solutions.lc.ru/catalog/tms/structure (дата обращения 15.06.2013).

91. Oracle Transportation Management // URL: http://www.oracle.com/ru/products/applications/018756-018756-ru.html (дата обращения 20.03.2012).

92. PSI Transportation Management System // URL: http://www.psilogistics.com/fileadmin/downloads/PSI Logistics/pdf/tms/Flyer T MS en.pdf (дата обращения 11.06.2013).

93. Sterling Transportation Management System // URL: http://www-03.ibm.com/software/products/ru/ru/transportation-management/ (дата

обращения 30.06.2013).