МЕТОД ГЕНЕТИЧЕСКИХ ХИМЕР ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАЦИОНАЛИЗАЦИИ МАРШРУТОВ МОРСКОЙ ТРАНСПОРТИРОВКИ
Аннотация
Решение задачи оптимизации маршрутов является одной из основных проблем организации любой перевозки. Многокритериальная оптимизация невозможна методически, но и однокритериальная оптимизация может явиться серьезной проблемой, поскольку поставленная задача с увеличением объёма исходных данных становится трансвычислительной. В то же время оптимизация маршрутов имеет важное практическое значение особенно для таких развивающихся регионов, как Арктика. В отличие от развитых регионов, где наиболее рациональные маршруты давно установились естественным путем (в результате проб и ошибок), в Арктическом регионе не существует устоявшегося решения, что делает задачу поиска оптимального решения крайне актуальной. Выбранным критерием оптимальности для изложения проблемы служит геометрическая длина маршрута, хотя в реальном применении понятие «расстояние» может быть существенно дополнено. Таким образом, задача сводится к известной задаче коммивояжера. В статье обсуждаются существующие методы поиска решения этой задачи. Возможным вариантом решения представляются методы эволюционного программирования, основывающегося на генетических алгоритмах. Показано, что генетические алгоритмы требуют модификации для корректного использования в решении поставленной задачи. Авторы статьи предлагают модификацию, основанную на методе генетических химер. В статье изложена основа модифицированного метода, описан реализованный в средеMS Excel прототип алгоритма, а затем описана созданная в специализированной среде AnyLogic 6 рабочая модель. Адекватность прототипа доказана сравнением с результатами полного перебора для небольшого числа базовых точек, позволяющего точно вычислить правильное решение. Для рабочей модели, в свою очередь, устанавливается адекватность проверенному прототипу. Специально спланированные эксперименты по тестированию подтверждают адекватность прототипа и модели. В заключение рассмотрены различные примеры использования модели и расположения портов.
Ключевые слова
рационализация маршрутов, задача коммивояжера, генетические алгоритмы, доказательство адекватности
Читать полный текст статьи: PDF
Список литературы
Лебедев Г. В. Перспективы развития арктической морской транспортной системы / Г. В. Лебедев, Г. Е. Румянцев // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2014. - № 3 (25). - С. 179-189.
Ботнарюк М. В. Анализ состояния и перспективы развития Северного морского пути / М. В. Ботнарюк // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2013. - № 1 (20). - С. 186-194.
Давыденко А. А. Обоснование концепции создания транспортной системы совместного использования в арктическом регионе Российской Федерации / А. А. Давыденко, А. В. Кириченко, А. А. Кузнецов // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2015. - № 3 (31). - С. 120-124. DOI: 10.21821/2309-5180-2015-7-3-120-124.
Schrijver A. On the history of combinational optimization (till 1960) / A. Schrijver // Handbooks in Operations Research and Management Science. - 2005. - Vol. 12. - Pp. 1-68. DOI: 10.1016/S0927-0507(05)12001-5.
García A. Polynomially solvable cases of the bipartite travelling salesman problem / A. García, Tejel // European Journal of Operational Research. - 2017. - Vol. 257. - Is. 2. - Pp. 429-438. DOI: 10.1016/j.ejor.2016.07.060.
Bremermann H. J. Optimization through evolution and recombination / H. J. Bremermann // Self-Organizing Systems. - USA, Washington DC, Spartan Books, 1962. - Pp. 93-106.
Knuth D. E. Postscript about NP-hard problems / D. E. Knuth // ACM SIGACT News. - 1974. - Vol. 6. - Is. 2. - Pp. 15-16. DOI: 10.1145/1008304.1008305.
Changdar C. An efficient genetic algorithm for multi-objective solid travelling salesman problem under fuzziness / C. Changdar, G. S. Mahapatra, R. K. Pal // Swarm and Evolutionary Computation. - 2014. - Vol. 15. - Pp. 27-37. DOI: 10.1016/j.swevo.2013.11.001.
Nguyen H. D. Implementation of an effective hybrid GA for large-scale travelling salesman problems / H. D. Nguyen, I. Yoshihara, K. Yamamori, M. Yasunaga // IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). - 2007. - Vol. 37. - Is. 1. - Pp. 92-99. DOI: 10.1109/TSMCB.2006.880136.
Morton G. A contribution to the “Travelling-salesman” Problem / G. Morton, A. H. Land // Journal of the Royal Statistics Society. Series B (Methodological). - 1955. - Vol. 17. - No. 2. - Pp. 185-203.
Turing A. M. Computer machinery and intelligence / A. M. Turing // Mind. - 1950. - Vol. 59. - No. 236. - Pp. 433-460. DOI: 10.1093/mind/LIX.236.433.
Holland J. H. Adaptation in Natural and Artificial Systems / J. H. Holland. - UK, London: The MIT Press, 1992. - 211 p.
Eiben A. E. Genetic algorithms with multi-parent recombination / A. E. Eiben, P.-E. Raué, Zs. Ruttkay // International Conference on Parallel Problem Solving from Nature. - Springer Berlin Heidelberg, 1994. - Pp. 78- 87. DOI: 10.1007/3-540-58484-6_252.
Об авторах
Кузнецов Александр Львович - доктор технических наук, профессор
thunder1950@yandex.ru. kaf_pgt@gumrf.ru
ФГБОУ ВО «ГУМРФ имени адмирала С. О. Макарова»Кириченко Александр Викторович - доктор технических наук, профессор
a.v.kirichenko@mail.ru. KirichenkoAV@gumrf.ru
ФГБОУ ВО «ГУМРФ имени адмирала С. О. Макарова»Попов Герман Борисович - аспирант
ФГБОУ ВО «ГУМРФ имени адмирала С. О. Макарова»
