ЭВОЛЮЦИОННЫЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ

Авторы

  • В. А. Тененев
  • А. С. Шаура
  • Д. С. Шаура

DOI:

https://doi.org/10.22213/2410-9304-2019-4-143-148

Ключевые слова:

задача маршрутизации транспортных средств, генетический алгоритм, нечеткая кластеризация, С-means, условная дискретная оптимизация

Аннотация

Рассматривается задача маршрутизации транспортных средств, являющаяся обобщением задачи коммивояжера. Существует несколько основных моделей маршрутизации, каждая из которых характеризуется наличием дополнительных условий (по грузоподъемности, транспортному парку,  времени доставки, количеству баз и т. д.) и описывает группу реальных  задач транспортной логистики. Эта задача относится к классу NP-трудных, а наличие дополнительных условий еще более усложняет ее решение.

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

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

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

Библиографические ссылки

Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

Applegate D.L., Bixby R.B., Chav´atal V. and Cook W.J. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006.

Pouya Baniasadi, Vladimir Ejov, Michael Haythorpe, and Serguei Rossomakhine. A new benchmark set for Traveling salesman problem and Hamiltonian cycle problem. 2018.

TSPLIB. library of sample instances for the TSP (and re-lated problems) from various sources and of various types. https://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/.

Dunn J. C. A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters, Journal of Cybernetics 3: 32-57, 1973.

Bezdek J. C. Pattern Recognition with Fuzzy Objective Function Algoritms, Plenum Press, New York. 1981.

Uzay Kaimak, Magne Setnes. Extended Fuzzy Clustering Algorithms. ERIM report series ERS-2000-51-LIS. Rotterdam, Netherlands, November 2000, 24 pp.

Akhand M. A. H., Sultana T, Shuvo M. I. R, Al-Mahmud. Constructive and Clustering Methods to Solve Capacitated Vehicle Routing Problem. Orient. J. Comp. Sci. and Technol;10 (3). 2017. DOI: http://dx.doi.org/10.13005/ojcst/10.03.02.

Благодатский Г. А., Тененев В. А., Шаура А. С. Численная реализация алгоритма управления запасами при длительных сроках поставки комплектующих в условиях «узких» мест производственного цикла // Интеллектуальные системы в производстве. 2016. № 4 (31). С. 40–44. DOI: 10.22213/2410-9304-2016-4-40-44.

Abdoun Otman, Jaafar Abouchabaka, Chakir Tajani. Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem. Int. J. Emerg. Sci. 2. 2012.

Батищев Д. И., Неймарк Е. А., Старостин Н. В. Применение генетических алгоритмов к решению задач дискретной оптимизации. Н. Новгород, 2007. 88 с.

Загрузки

Опубликован

12.01.2020

Как цитировать

Тененев, В. А., Шаура, А. С., & Шаура, Д. С. (2020). ЭВОЛЮЦИОННЫЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ. Интеллектуальные системы в производстве, 17(4), 143–148. https://doi.org/10.22213/2410-9304-2019-4-143-148

Выпуск

Раздел

Статьи