Journal influence
Bookmark
Next issue
Intelligent expert method for determine the optimal route of product transportation
The article was published in issue no. № 4, 2013 [ pp. 220-223 ]Abstract:To reduce transport costs a modern enterprise needs to select the optimal combination of different technical and economic indicators of the product delivery route. Searching rational track for goods movement is the foundation for building an efficient logistic system, which determines the timeliness of production output, production process duration, production costs. The optimal route is often determined by cost and transit time criteria. The combined use of these criteria causes the need for a two-criterion optimization algorithm. An NP class task affiliation is the reason for using heuristic methods (simulated annealing, genetic and ant algorithms, tabu search method, and others). Ant algorithms are based on the modeling of the behavior of individual ants acting according to simple rules, while the total system (colony) has an intellect. Using an ant colony to optimize the route of transporting products with two-criteria requires using two different colonies for each criterion, and the third generalizing colony is for route selection based on two criteria. To consider uncertainty when solving these problems it is appropriate to use fuzzy sets for unspecified parameters of mathematical models and fuzzy inference methods with expert judgment. The ant algorithms peculiarity is providing transport costs information on the site, as well as the weighting factors that determine the degree of algorithm greed in the form of fuzzy numbers and then applying the operations of fuzzy-logic convolution. The developed algorithms can improve the efficiency and reliability of enterprise logistics system.
Аннотация:Одна из задач сокращения транспортных расходов современного предприятия состоит в выборе оптимального по совокупности различных технико-экономических показателей маршрута доставки продукции. Поиск рациональной трассы перемещения грузов является фундаментом для построения эффективной логистической системы предприятий, определяющей своевременность выпуска продукции, длительность производственного процесса, себестоимость выпускаемой продукции. Чаще всего оптимальность маршрута определяется по критериям стоимости и времени транспортировки. Совместное применение данных критериев приводит к необходимости использования двухкритериального оптимизационного алгоритма, а принадлежность задачи к классу NP определяет целесообразность применения эвристических методов (метод имитации отжига, генетические и муравьиные алгоритмы, метод поиска с запретами и другие). Муравьиные алгоритмы основаны на моделировании поведения отдельных муравьев, действующих по простейшим правилам, в то время как общая система (колония) обладает интеллектом. Использование муравьиных колоний для двухкритериальной оптимизации маршрута транспортировки продукции предполагает необходимость использования двух различных колоний для каждого критерия и третьей, обобщающей, колонии для выбора трассы по двум критериям одновременно. Для учета неопределенности при решении этих задач целесообразно использовать нечеткие множества для неопределенных значений параметров математических моделей, а также методы нечетко-логического вывода с использованием экспертных оценок. Особенность предложенных муравьиных алгоритмов заключается в представлении информации о стоимости транспортировки на участке и весовых коэффициентов, определяющих степень жадности алгоритмов, в виде нечетких чисел с последующим применением операций нечетко-логической свертки. Разработанные алгоритмы позволят повысить эффективность и надежность логистической системы предприятия.
Authors: Dli M.I. (midli@mail.ru) - (Smolensk Branch of the Moscow Power Engineering Institute, Smolensk, Russia, Ph.D, Gimarov V.V. (feu@sci.smolensk.ru) - (Smolensk Branch of the Moscow Power Engineering Institute, Smolensk, Russia, Ph.D, (midli@mail.ru) - , Russia, Ivanova I.V. (ivanova_iv@list.ru) - (Smolensk Branch of the Moscow Power Engineering Institute, Smolensk, Russia | |
Keywords: condition-action rules, multi-objective optimization, multicriteria optimization, intellectual methods, heuristic search methods, transportation routes optimization, products transportation |
|
Page views: 12013 |
Print version Full issue in PDF (7.95Mb) Download the cover in PDF (1.45Мб) |
В условиях интенсивного развития системы внутренних и внешних хозяйственных связей, а также глобализации международных товарных рынков транспортная составляющая в себестоимости готовой продукции, связанная с доставкой, разгрузочно-погрузочными работами и временным хранением, постоянно растет. Проблема снижения транспортных расходов в современной экономике остро стоит не только перед предприятиями, специализирующимися на оказании услуг по передвижению грузов, но и перед организациями, использующими собственную распределительную сеть (магазинов, филиалов и т.д.), между которыми осуществляется оборот продукции. Обычно схема доставки достаточно сложна и сопряжена с необходимостью использования нескольких видов транспортных средств (автомобильные, железнодорожные, морские и авиаперевозки). В этой связи оптимизация транспортно-логистических маршрутов (модификации существующей логисти- ческой системы) является многокритериальной математической задачей, ее решение имеет важное значение для поддержания конкурентоспособности и бесперебойного функционирования отдельных предприятий. В качестве критериев оптимизации, как правило, используются стоимость и время транспортировки, наилучшие комбинации которых достигаются при условии использования нескольких видов транспорта. Для решения задачи поиска оптимального маршрута целесообразно представить транспортную сеть в виде ориентированного графа [1, 2]. В нем требуется построить маршрут c: (e1, e2, …, en) как непрерывную совокупность дуг между множеством вершин, отображающих транспортные узлы сети V, который обеспечивает минимум общей стоимости транспортировки S(c) и ее продолжительность Pr(c):
где ei – участок сети, входящий в маршрут c; Сформулированная задача является NP-сложной, поэтому для ее решения целесообразно использовать эвристические методы. К эффек- тивным современным эвристическим методам относятся так называемые метаэвристики, отображающие обобщенные стратегии поиска оптимума в пространстве решений: метод имитации отжига (simulated annealing), метод поиска с запретами (tabu search), оптимизационный метод муравьиной колонии (ant colony optimization), генетические и эволюционные алгоритмы. Преимущество данных методов состоит в том, что они позволяют исследовать большее пространство для поиска решения, близкого к оптимальному [3, 4]. Для решения задачи поиска оптимального маршрута доставки продукции предложено использовать двухкритериальный алгоритм: первый критерий – минимизация стоимости транспортировки, второй – общая временная протяженность доставки продукции по маршруту. Авторами предложен муравьиный алгоритм решения двухкритериальной задачи, сущность которого состоит в использовании трех колоний муравьев: по одной для каждого из двух критериев и третьей, обобщающей, для принятия итогового решения по выбору оптимальной трассы. Цель первой колонии – сократить стоимость транспортировки продукции. Вторая колония ищет минимальный по общей стоимости проектирования и строительства маршрут. Обе колонии используют независимые друг от друга феромонные тропы: m1 и m2. На основе объединения полученных двумя колониями на каждой итерации процедуры поиска локальных решений количеств феромона и весов ребер h1 и h2 первого и второго типов третья колония искусственных муравьев осуществляет поиск оптимального решения поставленной задачи. Для описания процедуры построения решения с использованием третьей колонии муравьев авторами разработан обобщающий муравьиный алгоритм поиска оптимального маршрута транспортировки, который включает следующие этапы. 1. Первоначальный маршрут, определяемый значениями феромона и веса первого и второго типов ( 2. Параллельный поиск M муравьями маршрутов по информации о количестве феромонов (m1 и m2) и весах (h1 и h2). Муравей на каждом шаге прокладки трассы в графе выбирает следующую присоединяемую вершину по правилу расчета величины нечеткой возможности перехода:
где Ä – операция умножения нечетких чисел; Поскольку количество феромона первого и второго типов и вес ребра второго типа задаются нечеткими числами m1и На каждой итерации t обобщающего муравьиного алгоритма искусственный муравей строит решение задачи, двигаясь по графу начиная от исходной вершины, согласно правилу (2). 3. Перерасчет количества феромона первого и второго уровней по окончании каждой итерации t после того, как все муравьи завершат построение маршрута:
где r – коэффициент испарения феромона; Dmij(t) – суммарное изменение уровня феромона на дуге графа (i, j); Tl(t) – общий маршрут, построенный муравьем l на итерации t; Pl(t) – относительная оценка качества найденного маршрута; Q –константа, показывающая общее количество феромона у муравья. Величина Pl(t) позволяет сопоставлять полученные на различных итерациях трассы между собой, определяя тем самым наиболее рациональный маршрут:
где Нечетко-продукционный эвристический алгоритм работы первой и второй колоний муравьев направлены на поиск соответственно минимального по стоимости и времени маршрута доставки продукции. Он включает следующие этапы. 1. Расчет первоначальной величины феромона t0l, задающей исходную конфигурацию системы распределения, по формуле
где 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* ликвидируется)». Обновление количества феромонов включает два этапа: испарение и добавление нового количества феромона после завершения построения решений на каждой итерации и осуществляется по формуле
где 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: 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. 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 problems 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. |
Permanent link: http://swsys.ru/index.php?id=3690&lang=en&like=1&page=article |
Print version Full issue in PDF (7.95Mb) Download the cover in PDF (1.45Мб) |
The article was published in issue no. № 4, 2013 [ pp. 220-223 ] |
Perhaps, you might be interested in the following articles of similar topics:
- Программное обеспечение для разработки моделей нечетких систем автоматического управления
- Коэволюционный алгоритм для задач условной и многокритериальной оптимизации
- Система вычисления приоритетов на основе матриц парных сравнений
- Программный комплекс формирования многокомпонентных экспертиз
- Информационная поддержка принятия решений при возникновении аварийной ситуации на объектах газопровода на основе продукционных правил
Back to the list of articles