УДК 004

РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА С ПОМОЩЬЮ ИММИТАЦИОННОГО МОДЕЛИРОВАНИЯ

Дроздовская Виктория Игоревна1, Дроздовский Артем Сергеевич2, Алехина Алина Энодиевна3
1Белорусский государственный университет информатики и радиоэлектроники, магистрант
2Белорусский государственный университет информатики и радиоэлектроники, магистрант
3Белорусский государственный университет информатики и радиоэлектроники, кандидат экономических наук, доцент

Аннотация
В данной статье приводится описание метода имитационного моделирования для решения задачи коммивояжера.Решение такой задачи может использоваться для моделирования транспортных сетей, при реализации модели цепочки поставок.

Ключевые слова: иммитационное моделирование, решение задачи коммивояжера


THE SOLUTION OF THE TRAVELING SALESMAN PROBLEM USING SIMULATED

Drozdovskaya Viktoria Igorevna1, Drozdovskiy Artem Sergeevich2, Alehina Alina Enodievna3
1Belarusian State University of Informatics and Radio Electronics, undergraduate
2Belarusian State University of Informatics and Radio Electronics, undergraduate
3Belarusian State University of Informatics and Radio Electronics, Candidate of Economic Sciences, Associate Professor

Abstract
This article describes the simulation method for solving the traveling salesman problem. The solution of this problem can be used for modeling of transport networks, the implementation of supply chain model.

Рубрика: 05.00.00 ТЕХНИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Дроздовская В.И., Дроздовский А.С., Алехина А.Э. Решение задачи коммивояжера с помощью иммитационного моделирования // Современные научные исследования и инновации. 2016. № 10 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2016/10/72955 (дата обращения: 20.11.2016).

В настоящее время моделирование является основным методом исследований во всех областях знаний и научно обоснованным методом оценок характеристик сложных систем, в частности транспортных, используемым для принятия решений в различных сферах деятельности [1].

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

Исходными данными для задачи являются координаты месторасположения склада и магазинов-дистрибьюторов. Система имитационного моделирования AnyLogic позволят использовать импорт данных, в том числе и из Excel. Таким образом географическое местоположение склада и магазинов-дистрибьютеров целесообразно считывать из документа. Фрагмент используемого в данной работе файла Excel с данными приведены на рисунке 1.

Рисунок 1 – Исходные данные

Применение метода имитационного моделирования для решения задачи коммивояжера можно продемонстрировать на примере модели движения товаров от склада к магазинам-дистрибьюторам. Эта модель состоит из одного склада и десяти магазинов-дистрибьюторов, которые заказывают различное количество товара каждые 2-3 дня. Склад имеет в распоряжении свой парк грузовых автомобилей. Реализация заказа осуществляется следующим образом: склад получает заказ от магазина-дистрибьютора и проверяет количество товара на складе. Если заказанное количество товара имеется в наличии, склад реализует поставку к магазину-дистрибутору. Иначе заказ не выполняется, и дистрибутор ждет, пока требуемое количество товара не поступит на склад.

Модель поставки товаров основана на трех основных методологиях имитационного моделирования: системной динамике, агентном и дискретно-событийном моделировании и создана с помощью системы имитационного моделирования AnyLogic.

Данная система позволяет комбинированное использование всех трех методов. В случае имитационного моделирования транспортной сети было принято решение поместить диаграмму системной динамики и дискретно событийную диаграмму внутрь агента – объекта системы AnyLogic.

Рассмотрим агентное моделирование в рамках поставленной задачи. С точки зрения практического применения агентное моделирование можно определить, как метод имитационного моделирования, исследующий поведение децентрализованных агентов и то, как это поведение определяет поведение всей системы в целом. При разработке агентной модели, инженер вводит параметры агентов, определяет их поведение, помещает их в некую окружающую среду, устанавливает возможные связи, после чего запускает моделирование. Индивидуальное поведение каждого агента образует глобальное поведение моделируемой системы. Основным объектом системы является агент Main. Он включает в себя такие агенты, как retailers – магазины-дистрибьюторы, которых по условию 10, и warehouse – склад. Именно этот агент будет выполняемым нашей модели.
Фрагмент созданной в среде AnyLogic агентной модели представлен на рисунке 2.


Рисунок 2 – Фрагмент агентного моделирование сети

Сущности объектов склада и дистрибьюторов описаны в агентах Retailer и Warehouse соответственно. Агент Truck описывает грузовой автомобиль. Для заказа используется агент Order.

Системная динамика – это подход имитационного моделирования, своими методами и инструментами позволяющий понять структуру и динамику сложных систем. Системная динамика представлена диаграммой пополнения склада товарами. Она проиллюстрирована на рисунке 1. Параметр capacity формирует поток восполнения запасов товаров на складе productionRate. Параметр productsInStorage определяет вместимость склада. Параметр products показывает текущее количество товаров на складе. При загрузке грузовика товарами products уменьшается на величину заказа.

Рисунок 3 – Диаграмма пополнения склада товарами

Чтобы анализировать процессы, протекающие в мире, иногда удобно рассматривать их как последовательность отдельных важных моментов – событий. Подход к построению имитационных моделей, предлагающий представить реальные действия такими событиями и называется «дискретно-событийным» моделированием (discrete event modeling).

Процессное моделирование используется на среднем или низком уровне абстракции: каждый объект моделируется индивидуально, как отдельная сущность, но множество деталей «физического уровня» (геометрия, ускорения/замедления) опускается. Такой подход широко используется в моделировании бизнес-процессов, производства, логистики. Данная модель является многоподходной. Дистрибуторы, грузовики и склад являются агентами, каждый из которых имеет свое поведение: диаграмма системной динамики задает пополнение склада, движение грузовиков описывает диаграмма состояний для агента Грузовик (рисунок 4).

Рисунок 4 – Диаграмма состояния грузового автомобиля

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

Среда выполнения позволяет выбирать время выполнения моделирования. Эксперимент можно провести с сильным ускорением, что является наиболее оптимальным для получения конечного результата к концу определенного отчетного периода. Результаты работы модели представлены на рисунке 5.

Рисунок 5 – ГИС карта с агентами модели

После выполнения модели, было получено значение кратчайшего пути доставки. Оптимальный путь составляет 67 км. А также было подсчитано общее время на доставку и время, потраченное на остановки на светофорах: 6 часов 46 минут и 35 минут, соответственно.

Для прослеживания промежуточных результатов модель можно имитировать с минимальным ускорением.

Инструмент для имитационного моделирования AnyLogic позволяет создать наглядную, понятную модель, которая обладает высоким уровнем визуализации данных.


Библиографический список
  1. Akopov, A.S. Designing of integrated system-dynamics models for an oil compa-ny / A.S. Akopov // International Journal of Computer Applications in Technology – 2012. – P. 220–230..
  2. AnyLogic [Электронный ресурс] / AnyLogic – Санкт-Петербург, 2016. – Режим доступа : http://www.anylogic.ru/use-of-simulation. – Дата доступа : 22.09.2016.


Все статьи автора «Дроздовская Виктория Игоревна»


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться:
  • Регистрация