Программные продукты и системы

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

Для решения задачи поиска оптимального маршрута целесообразно представить транспортную сеть в виде ориентированного графа [1, 2]. В нем требуется построить маршрут c: (e1, e2, …, en) как непрерывную совокупность дуг между множеством вершин, отображающих транспортные узлы сети V, который обеспечивает минимум общей стоимости транспортировки S(c) и ее продолжительность Pr(c):

                                        (1)

где ei – участок сети, входящий в маршрут c;  – длина ребра ei;  – стоимость транспортировки продукции с использованием транспортного средства типа q на дуге ei;– функция, определяющая время транспортировки продукции на маршруте c.

Сформулированная задача является NP-слож­ной, поэтому для ее решения целесообразно использовать эвристические методы. К эффек- тивным современным эвристическим методам относятся так называемые метаэвристики, отображающие обобщенные стратегии поиска оптимума в пространстве решений: метод имитации отжига (simulated annealing), метод поиска с запретами (tabu search), оптимизационный метод муравьиной колонии (ant colony optimization), генетические и эволюционные алгоритмы. Преимущество данных методов состоит в том, что они позволяют исследовать большее пространство для поиска решения, близкого к оптимальному [3, 4].

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

Цель первой колонии – сократить стоимость транспортировки продукции. Вторая колония ищет минимальный по общей стоимости проектирования и строительства маршрут. Обе колонии используют независимые друг от друга феромонные тропы: m1 и m2. На основе объединения полученных двумя колониями на каждой итерации процедуры поиска локальных решений количеств феромона и весов ребер h1 и h2 первого и второго типов третья колония искусственных муравьев осуществляет поиск оптимального решения поставленной задачи.

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

1. Первоначальный маршрут, определяемый значениями феромона и веса первого и второго типов (,  и h1, h2 соответственно) для каждой дуги графа "(ij)ÎV.

2. Параллельный поиск M муравьями маршрутов по информации о количестве феромонов (m1 и m2) и весах (h1 и h2). Муравей на каждом шаге прокладки трассы в графе выбирает следующую присоединяемую вершину по правилу расчета величины нечеткой возможности перехода:

(2)

где Ä – операция умножения нечетких чисел;  – количество первого феромона на дуге (i, j);  – количество второго феромона на дуге (i, j);  – привлекательность перехода в вершину j из вершины i по критерию скорости доставки;  – привлекательность перехода в вершину j из вершины i по критерию стоимости доставки; wÎ[0, 1] – весовой коэффициент, отражающий относительную значимость критерия стоимости маршрута;  – множество вершин в графе, которые муравей m еще не посетил, но они доступны для перехода на текущей итерации.

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

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

3. Перерасчет количества феромона первого и второго уровней по окончании каждой итерации t после того, как все муравьи завершат построение маршрута:

,

,

           (3)

где r – коэффициент испарения феромона; Dmij(t) – суммарное изменение уровня феромона на дуге графа (i, j); Tl(t) – общий маршрут, построенный муравьем l на итерации t; Pl(t) – относительная оценка качества найденного маршрута; Q –константа, показывающая общее количество феромона у муравья. Величина Pl(t) позволяет сопоставлять полученные на различных итерациях трассы между собой, определяя тем самым наиболее рациональный маршрут:

                                      (4)

где  – общая стоимость (нечеткое высказывание) транспортировки продукции по маршруту Tl(t); η – коэффициент значимости показателя «стоимость»; n – время доставки продукции при использовании трассы Tl(t); ξ – коэффициент значимости показателя «временная протяженность».

Нечетко-продукционный эвристический алгоритм работы первой и второй колоний муравьев направлены на поиск соответственно минимального по стоимости и времени маршрута доставки продукции. Он включает следующие этапы.

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

,                                                  (5)

где  – стоимость прокладки q-го вида сети на участке между узлами i и j как функция от расстояния r; Iq – стоимость метра канала вида q.

2.     Поэтапное построение маршрутов с использованием правил поведения муравьев (ППм). На каждом этапе M муравьев ищут решения с использованием информации об уровне феромона и локальной информации.

Первое правило дает возможность осуществлять расчет значения вероятности передвижения муравья из вершины в вершину.

ППм-1. «ЕСЛИ (величина феромона ti,jl на дуге (i, j) типа l ЕСТЬ «Am1») И (величина совокупной стоимости транспортировки Sijl на дуге (i, j) ЕСТЬ «Bm2»), ТО (вероятность перехода (pijl)q в узел j с использованием кабеля l на итерации q ЕСТЬ «Dm4»)».

Индексы m1, m2, m3, m4 определяют конкретные значения лингвистических переменных A, B, C, D соответственно.

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

ППм-2. «ЕСЛИ муравей m достиг пути, построенного муравьем m*», ТО (пути муравьев m и m*, а также их табу-листы объединяются) И (муравей m* ликвидируется)».

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

,                                   (6)

где r – темп испарения феромона (0£r£1);  – приращение концентрации феромонов на очередной итерации алгоритма.

Этапы повторяются до тех пор, пока результат не перестанет изменяться в течение заранее определенного числа итераций. Алгоритм может быть остановлен и по истечении определенного времени выполнения либо после выполнения заданного количества итераций (не менее 100).

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

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

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

Литература

1.     Dorigo M., Maniezzo V., Colorni A. The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, 1996, vol. 26, no. 1, pp. 29–41.

2.     Глушко С.И., Какатунова Т.В. Нечеткая модификация алгоритма муравьиных колоний // Научное обозрение. 2013. № 1. С. 377–381.

3.     Гимаров В.А., Дли М.И., Круглов В.В. Задачи распознавания нестационарных образов // Изв. РАН. Теория и системы управления. 2004. № 3. С. 137.

4.     Бояринов Ю.Г., Борисов В.В., Мищенко В.И., Дли М.И. Метод построения нечеткой полумарковской модели функционирования сложной системы // Программные продукты и системы. 2010. № 3. С. 26–31.

5.     Дли М.И., Карпова Т.П. Критерии оптимизации путей доставки продукции при использовании нечетких моделей муравьиных колоний // Вестн. РАЕН. 2012. № 1. С. 55–56.

References

1.     Dorigo M., Maniezzo V., Colorni A. The Ant System: Op­timization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics. Part B: Cybernetics. 1996, vol. 26, no. 1, pp. 29–41.

2.     Glushko S.I., Kakatunova T.V. Fuzzy modification of ant colonies algorithm. Nauchnoe obozrenie [Scientific survey]. 2013, no. 1, pp. 377–381.

3.     Gimarov V.A., Dli M.I., Kruglov V.V. Recognition prob­lems for nonsteady images. Izv. RAN. Teoriya i sistemy upravleniya [Journ. of computer and systems sciences international]. 2004, no. 3, pp. 137.

4.     Boyarinov Yu.G., Borisov V.V., Mishchenko V.I., Dli M.I. Building method of fuzzy semi-markov model of complex system functioning. Programmnye produkty i sistemy [Software & Systems]. 2010, no. 3, pp. 26–31.

5.     Dli M.I., Karpova T.P. Optimization criteria of production transportation routes using fuzzy models of ant colonies. Vestnik RAEN [The bulletin of the Russian Academy of Natural Sciences]. 2012, no. 1, pp. 55–56.