2
Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ»)
Интеллектуальная система выбора маршрута в логистике с использованием алгоритма муравья
Внукова З.А.
Логистика - это процесс создания оптимальной инфраструктуры движения товаров и услуг от поставщиков к потребителям. Если говорить простыми словами, то логистика занимается тем, чтобы найти и организовать самый удобный, наиболее выгодный, наименее затратный путь, по которому нужный товар или услуга поступят к своему конечному потребителю.
Логистика в определенной форме существовала с давних времен: еще до нашей эры народы выбирали и строили наиболее удобные торговые пути для переправки сельскохозяйственных грузов и вооружения. На сегодняшний день, основной причиной развития логистики как отдельной науки стал существенный рост производства, увеличение товаропотоков как в мировом масштабе, так и в рамках каждой отдельно взятой страны.
Логистическая структура на любом предприятии включает в себя 2 ключевых направления:
1. логистика сырья, материалов, товаров, услугот поставщиков на предприятие;
2. логистика конечной продукции от предприятия до потребителей, как оптовых, так и конечных, розничных.
Актуальность темы определяется необходимостью совершенствования инструментария системы поддержки принятия решений в логистике, являющейся одним из приоритетных направлений социального инвестирования, так как вложения в логистику определяют возможности поддержки бизнеса государства.
Муравьиные алгоритмы серьезно исследуются европейскими учеными с середины 1990-х годов. Уже получены хорошие результаты муравьиной оптимизации для многих сложных комбинаторных задач: задачи коммивояжера, оптимизации маршрутов грузовиков, раскраски графа, квадратичной задачи о назначениях, оптимизации сетевых графиков, задачи календарного планирования и других. Особенно эффективны муравьиные алгоритмы при on-line оптимизации процессов в распределенных нестационарных системах, например трафиков в телекоммуникационных сетях.
Программная реализация знаменитого алгоритма муравья для решения задачи коммивояжера. Программа проста и является всего лишь примером того, как алгоритм муравья может быть использован для решения практической задачи. Начальные координаты городов каждый раз задаются случайным образом. В результате работы программы пользователю выдается несколько возможных маршрутов с указанием минимального из них.
В классической постановке коммивояжердолжен объехать N городов по замкнутому маршруту, посетив каждый из них лишь однажды, таким образом, чтобы полная длина его маршрута была минимальной. Если решать задачу коммивояжера „в лоб“ - перебором всех замкнутых путей, связывающих города, то придется проверить все (N-1)!/2 возможных маршрутов, то есть простой метод перебора всех вариантов чрезвычайно неэффективный при большом N. Эффективными же признаются решения, гарантирующие получение ответа за время, ограниченное полиномом от размерности задачи. С помощью муравьиных алгоритмов находятся субоптимальные решения, локальные минимумы целевой функции, приближающиеся к абсолютному минимуму.
Данная программа написана на BorlandBuilderC++, версии 6.0. Целью написания является выбор оптимального маршрута коммивояжера. Программа весит 780 КБ.
Программа «Алгоритмы муравьев» открывается при помощи файла TSPbyAnt.exe. На рисунке 1 показан интерфейс программы.
Данная программа имеет несколько вариантов работы, соответственно имеет меню выбора действий. К нему относится:
- задать координаты городов;
- запустить алгоритм;
- скрыть номера городов;
- показать пункт 1, 2, 3…
Меню «задать координаты городов» предполагает расстановку городов в программе (рис.2-3).
Рисунок 1 - Интерфейс программы
Рисунок 2 - Задание координат городов
Меню «запустить алгоритм» предполагает вычисление минимального маршрута по городам.
Рисунок 3 - Вычисление минимального пути
Меню «скрыть номера городов» предполагает очищение номеров городов. логистика программный коммивояжер перевозка
Рисунок 4 - Очищение номеров городов
Меню «Посмотреть путь 1, 2…» предполагает просмотр всех возможных вариантов маршрута по городам.
Рисунок 9 - Все возможные варианты маршрутов
В процессе выполнения данной работы были выявлены и проанализированы требования, предъявляемые к интеллектуальной системе. Всесторонне изучив деятельность ООО ТД «Малахов +» г. Белгорода, для реализации интеллектуальной системы был выбран алгоритм муравья, реализованный программным продуктом BorlandBuilderC++ 6.0.
Исходя из выявленных требований, была протестирована интеллектуальная система «алгоритм муравьев».
Реализованный проект охватывает все потоки информации, использующие при выборе маршрута в логистике и позволяет автоматизировать работу логиста ООО ТД «Малахов +». Интеллектуальная система ускоряет процессы деятельности в логистике в целом, повышает уровень принятия решения в выборе маршрута перевозки груза.