Эвристический поиск оптимального маршрута судна по Северному морскому пути

ВЕСТНИКД

ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

МОРСКОГО И РЕЧНОГО ФЛОТА ИМЕН И АДМИРАЛА С, О. МАКАРОВА,

12. Code of Safety for Fishermen and Fishing Vessels, London: IMO, 2006.

13. Jin, D., Hauke Kite-Powell, and Wayne Talley. “The safety of commercial fishing: determinants of vessel total losses and injuries.” Journal of Safety Research 32.2 (2001): 209-228.

14. Jin, D., Hauke Kite-Powell, Erik Thunberg, Andrew Solow, and Wayne Talley. “A model of fishing vessel accident probability.” Journal of Safety Research. 33(2002): 497-510.

15. Perez-Labajos, Carlos. “Fishing safety policy and research.” Marine Policy. 32 (2008): 40-45.

16. Final Report of Flagship Project, EU strategy for the Baltic Sea region. “To lay the groundwork for developing a plan to reduce the number of accidents in fisheries.” 2014, BSAC. Web. <http://www.bsac.dk/archive/ Dokumenter/Flagship%20Project/BSAC%20Safety%20Report%20FINAL.pdf>.

17. Moyseenko, Sergey, Leonid Meyler, Vitaly Bondarev, and Oksana Faustova. “Analysis of the problem of risk assessment in commercial fishing.” Proc. XI Baltic Maritime Forum, Swetlogorsk, 26-30 May 2014. Kaliningrad: BFFSA Publ. House, 2014. 76 - 83. Print. (in Russian).

18. Moyseenko, Sergey, Vladimir Skrypnik, and Oksana Faustova. “Differential-integral approach to the modeling of the development of emergency situations in shipping and oceanic fisheries.” Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S. O. Makarova 4(26) (2014): 47-53. (in Russian).

19. Ventzel, Elena, and Lev Owcharov. Theory of probability. Moscow: Nauka, 1973. (in Russian).

20. Topalov, Valeriy, and Vladimir Torskiy. Risks in Shipping. Odessa: Astroprint, 2007. (in Russian).

21. Abchuk, Vladimir. Risk theory in the marine practice. Leningrad: Sudostroenie, 1983. (in Russian).

22. Moyseenko, Sergey, Leonid Meyler, and Oksana Faustova. “Formation of the integrated risk assessment of a disaster in multimodal cargo transportation.” Proc. X Baltic Maritime Forum. Swetlogorsk, 28-31 May 2013. Kaliningrad: BFFSA Publ. House, 2013. 265 - 270. Print. (in Russian).

________ИНФОРМАЦИЯ ОБ АВТОРАХ

Мойсеенко Сергей Сергеевич — доктор педагогических наук, кандидат технических наук, профессор.

Балтийская государственная академия рыбопромыслового флота Калининградского государственного технического университета (БГАРФ КГТУ) moiseenkoss@rambler. ru Мейлер Леонид Ефимович — кандидат технических наук, доцент. Балтийская государственная академия рыбопромыслового флота Калининградского государственного технического университета (БГАРФ КГТУ) transport@bga.gazinter. net

INFORMATION ABOUT THE AUTHORS

Moiseenko Sergey Sergeevich —

Doctor of pedagogical sciences,

Candidate of Engineering, professor.

Baltic Fishing Fleet State Academy

of the Kaliningrad State Technical University

moiseenkoss@rambler.ru

Meyler Leonid Efimovich —

Candidate of Engineering, associate professor.

Baltic Fishing Fleet State Academy of the Kaliningrad State Technical University (BFFSA KSTU) transport@bga.gazinter. net

УДК 681.3: 656.62 Д. А. Акмайкин,

С. Ф. Клюева, П. А. Салюк

ЭВРИСТИЧЕСКИМ ПОИСК ОПТИМАЛЬНОГО МАРШРУТА СУДНА ПО СЕВЕРНОМУ МОРСКОМУ ПУТИ

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

Выпуск 5(33) 2015.

Выпуск5(33) 2015

ВЕСТНИК

ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

МОРСКОГО И РЕЧНОГО ФЛОТА ИМЕНИ АДМИРАЛАС. О. МАКАРОвА

го маршрута судна для трассы Северного морского пути. Выполнена формализация постановки задачи. В работе представлена пошаговая реализация разработанного эвристического алгоритма построения оптимального маршрута судна. Представленная в статье программная реализация алгоритма А2015 включает сравнение его с классическими алгоритмами Дейкстры и Флойда-Уоршелла. Представленный алгоритм позволяет в некоторых случаях на порядок быстрее сформировать оптимальный маршрут судна для трассы морского пути в сравнении с классическими алгоритмами поиска пути на графе. Такой поход позволяет значительно сократить объем всех возможных вычислений и быстро получать возможные решения для оперативного анализа обстановки в заданном районе плавания.

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

рые разработаны на основе многолетнего опыта мореплавания и среднестатистических данных о распределении гидрометеорологических явлений по сезонам [1] - [7]. В настоящее время для автоматизированного поиска оптимального маршрута судна используются алгоритмы, основанные на теории графов.

Решение задач построения оптимального маршрута судна на основе теории графов в отличие от традиционных задач поиска кратчайших путей на графе имеет некоторые особенности. К таким особенностям относятся динамическое изменение характеристик взаимосвязей между вершинами графа [8], [9], необходимость учета гидрометеорологических факторов в процессе движения судна, изменение масштабности графов для разных судов в одной акватории и для одного судна при разных условиях загрузки, а также учет иных факторов, влияющих на безопасность мореплавания [3] - [6].

Задача поиска кратчайших путей для динамических и масштабных графов на основе точных алгоритмов не реализуется за полиномиальное время. Поэтому для решения подобных задач актуальным является поиск наиболее быстрых и эффективных методов и алгоритмов. Наиболее простыми являются методы, реализуемые на основе приближенных алгоритмов из класса NP-полных задач [9], [10], однако данные алгоритмы не всегда позволяют получить требуемое решение, и число повторных поисков может оказаться значительным по объему операций. Более гибко работают эвристические алгоритмы позволяющие, не просматривая все варианты решений, сразу проложить трассу по кратчайшему пути к целевой вершине. Использование эвристической информации основано на применении оценочной функции, которая представляет собой меру, оценивающую перспективность раскрытия вершины [11], [12].

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

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

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

РОРАБОТКА маршрута в соответствии с международными требованиями начинается с составления плана перехода от причала до причала на основе имеющейся информации. Классически маршрут формируется вдоль рекомендованных морских путей, кото-

- положение портов (пунктов), между которыми осуществляется плавание.

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

Исходя из данных условий и требований, предлагается рассмотреть трассу Северного морского пути и особенности реализации предлагаемого эвристического алгоритма построения кратчайших путей (рис. 1).

Рис. 1. Трасса Северного морского пути

Возможные варианты движения по СМП представлены в виде графа G = (V E), где V={v ..., v} — множество всех вершин графа, которые являются портами (пунктами) либо точками поворота; E={e1 ,..., em} — множество всех ребер графа (рис. 2). Каждому элементу е, l = {1, ..., m} множества E поставлена в соответствие упорядоченная пара вершин (v. ,v.) е E, и вес ребра w.. — некоторое неотрицательное значение, зависящее от времени перехода между смежными вершинами графа с учетом ледовой обстановки, глубины и течений. Ребро (v , v ) обозначено пунктиром, так как этот отрезок СМП сезонный (динамическое ребро).

Qj) c,

Рис. 2. Граф трассы Северного морского пути

Матрица весов W=(w..), в разрабатываемом алгоритме построена стандартным образом.

V

В случае, если не существует прямого пути из вершины v. в вершину v, то соответствующий вес приравнивается к бесконечности:

Выпуск 5(33) 2015.

|Выпуск 5 (33) 2015

0,если i = j

W = {

wi, j, если (Vi, Vj) e E, i Ф j. да,если (Vi, Vj) e E, i Ф j

Для быстрого поиска оптимального пути в графе предлагается использовать эвристический алгоритм А2015. В этом алгоритме совместно с исходной матрицей весов W используется вектор оценок Est(V). Элементы вектора равны сумме числа промежуточных вершин d(V), отличных от нуля и бесконечно больших значений «Inf» для выбранной строки таблицы и некоторого индекса index, пропорционального суммарному весу ребер между промежуточными вершинами:

Est (V) = d (V) + index.

Эвристический алгоритм А2015 поиска кратчайших путей включает следующие шаги.

Шаг 1. Задать целевую вершину vb и начальную вершину v

Шаг 2. Задать вектор путей Rt(V), с количеством элементов равному количеству вершин графа. Первый элемент равен номеру целевой вершины, последний — номеру начальной вершины, остальные не заданы.

Шаг 3. Номер строки i матрицы весов положить равным номеру целевой вершины v Шаг 4. Проверить для строки i выполнение условия P(v. Ji для начальной вершины va:

Г1,если w,а Ф ° w,а фда !о,если wia = 0, или wia =ю

Если P(vJ = 1, то условие выполнено, путь найден, перейти на шаг 9.

Если P(vJ = 0, то условие не выполнено, перейти на шаг 5.

Шаг 5. Просматриваются по порядку веса w.. в строке i и выбирается номер q элемента строки (соответственно номер вершины), которому соответствует наименьшее значение вектора оценок. Номер полученной вершины q внести в вектор путей Rt(v), т. е. в первую по порядку не заданную позицию.

Шаг 6. Исключить из дальнейшего выбора элементы столбца с индексом, равным i.

Шаг 7. По номеру выбранной вершины q перейти к строке i = q.

Шаг 8. Вернуться к шагу 4.

Шаг 9. Вычислить суммарный вес ребер найденного пути.

Пример результата работы алгоритма для подграфа G1(V1, E1) графа G = (V, E) приведен на рис. 3. Подграф G1 получен из G путем оставления первых пятнадцати вершин и ребер.

Рис. 3. Вывод результатов работы программы поиска кратчайших путей по алгоритму А2015

Matrix weight

1 2 3 4 5 6 7 8 ¥ 10 11 12 13 14 15

0 20 50) Inf Inf Tnf Inf Inf [nf [nf lnf lnf Inf Inf Tnf

2 20 0 Inf Inf 35 Inf Inf Jnf Lnf [nf lnf Jnf *>5 Inf Inf

3 50 Inf 0» IS Inf Inf Inf Inf [nf [nf lnf Jnf Inf Inf Inf

4 [nf Inf IS 14 Inf Inf Inf 12 [nf [nf lnf Jnf Inf Inf Inf

5 [nf Э5 Inf Inf 0 1И Inf Inf Tnf [nf lnf Jnf Inf Inf Inf

(3 [nf Inf Inf Inf 10 0 10 Inf Tnf [nf lnf lnf Inf Inf Inf

V [nf Inf Inf Inf Inf 1И 0 Inf Tnf 20 lnf lnf Inf Inf Inf

8 [nf Inf Inf 12 Inf Inf Inf d 12 [nf 30 lnf Jnf Inf Inf

7 [nf Jnf Inf Tnf Inf Inf Inf 12 14 Inf Inf lnf Inf Inf lnf

id [nf Inf Inf Inf Inf Inf 20 Inf [nf 0 Jnf 30) Inf lnf lnf

ii Inf Inf Inf Inf Inf Inf Inf 3d Inf Inf D 15 Inf Inf lnf

12 Inf Inf Inf Inf Inf Inf Inf I nf Inf 3D 15 О 40 20 35

13 Inf 65 Inf Inf Inf Inf Inf I nf Inf Inf Inf 40 0 lnf 40

14 Inf Inf Inf Inf Inf Tnf Inf Inf Inf Inf Inf ZO Inf 0 Tnf

15 Inf Inf Inf Inf Inf Tnf Inf Inf Inf Inf Inf 35 40 lnf В

Est L1

13 3 4 8 7 6 5 4 5 6 4 4 2 7 Z

purp 1—>15

Route 2 13 15

weight w<lF15>- 125

purp 1—>13

Route 2 n

ueight uCl,l3>* BS

purp 1—>11

Route 1 3 4 a 11

weight u(l,ll)a id?

purp 1—>1G

Route 2 5 6 7 10

weight w<l,10>" ¥5

purp l™->8

Route Э Л 8

weight wdF8>m TV

В качестве начальной вершины va выбрана первая вершина, в качестве целевой вершины vb выбраны вершины с номерами: v15, v13, v1p v10, v8. Матрица весов «Matrix weight» представляет собой исходную матрицу весов W для графа G1. Для каждого маршрута «purp 1--> vb» приведен вектор путей Rt и «w(v vb) = » — суммарный вес.

Для анализа эффективности работы алгоритма А2015 проведено его сравнение с алгоритмами Флойда-Уоршелла и Дейкстры. Алгоритм Флойда-Уоршелла выбран в связи с тем, что он позволяет находить оптимальные пути между всеми вершинами графа, у которого все ребра с неотрицательным весом за один цикл работы. Для алгоритма Флойда-Уоршелла важно, какие вершины используются в качестве промежуточных. Через w.jk) обозначен вес кратчайшего пути из вершины v. в вершину v c промежуточными вершинами из множества {1, 2, ..., k}. Если k = 0, то промежуточных вершин нет. В общем случае

W

(к) -

wt j ,если к = 0

min ( (1}, + wfj1), если k > j

Матрица W(n) = (w.(n)) — матрица искомых кратчайших путей. На каждом проходе добавляют по одному узлу до тех пор, пока не будут исследованы все узлы графа.

Матрица весов Wn) содержит все суммарные веса кратчайших путей. Матрица кратчайших путей R(n) = r.. позволяет получить информацию о маршруте. Исходная матрица кратчайших путей R0 задается в виде:

R j = <

v, (vi, vj )е E 0, (, Vj ) E, или i = J

Реконструкция пути осуществляется следующим образом:

г

R(k ) |' <, j ’

' ’ ' .

(к-1) Ч, к 1

v

vk ,1

'к, j

если w

(к-П (к-1) , (к-1) '

' > Щ,к +

Для алгоритма Дейкстры формируется матрица весов W= (w.), вектор меток вершин q(V), вектор значений «окраса» вершин col(V) и вектор путей Rt(V). Вектор меток вершин содержит значения меток равных весу вершины. В каждой итерации вычисляются новые значения меток вершин в процедуре «релаксации ребер». Просмотренные вершины отмечаются цветом, в простейшем случае это бинарные значения: 1 — просмотренная вершина, 0 — не просмотренная вершина. Процесс «релаксации ребер» выполняется следующим образом: если имеется ребро из вершины с номером i в вершину с номером . с весом wi., и путь из начальной вершины va в вершину v., не проходящую через вершину vi, то существует возможность улучшить значение q.:

\qj,еслиq j < wij +q t 4j = 1 ,

[qi + wij,если q j > w +qt

где j — номер очередной просматриваемой вершины пути; г — номер предыдущей вершины, смежной с вершиной v..

Результаты поиска кратчайших путей на основе эвристического алгоритма А2015 совпадают с решениями по алгоритму Флойда-Уоршела и Дейкстры, но объем вычислений для эвристического алгоритма значительно меньше.

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

Выпуск 5(33) 2015.

|Выпуск 5 (33) 2015

Анализ эффективности работы алгоритмов А2015

Число вершин графа Количество операций

Алгоритм А2015 Алгоритм Дейкстры Алгоритм Флойда-Уоршелла

5 20 121 271

8 41 288 932

10 95 440 1686

13 37 730 3777

14 139 842 4550

15 77 963 5449

16 116 1091 6396

21 166 2026 13085

22 217 2028 13860

24 93 2418 16822

25 274 2635 17753

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

Выводы

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

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

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Акмайкин Д. А. Проект системы оперативного анализа и оптимизации движения морских судов / Д. А. Акмайкин, С. Ф. Клюева, П. А. Салюк // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2015. — № 1. — С. 229-236.

2. Akmaykin D. Solaris’ information system for ship’s navigation, using operational analysis of shipboard and satellite remote sensing data of hydrosphere and atmosphere / D. Akmaykin, D. Homenko, P. Salyuk, I. Stepochkin, K. Smirko // SPIE Proceedings, Ocean Remote Sensing and Monitoring from Space. — 2014. — № 9261-41. — С. 1-10.

3. Васьков А. С. Взаимосвязь зон навигационной безопасности судна/ А. С. Васьков, В. А. Васьков,

А. А. Мироненко // Вестник Государственного морского университета имени адмирала Ф. Ф. Ушакова. — 2013. — № 2. — С. 18-21.

ВЕСТНИКД

ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

МОРСКОГО И РЕЧНОГО ФЛОТА ИМЕН И АДШГАЛА С. О. МАКАРОВА,

4. Макоско А. А. Гидрометеорологическое обеспечение плавания по трассам Северного морского пути / А. А. Макоско // Арктика: экология и экономика. — 2013. — № 3. — С. 40-49.

5. Мироненко A. A. Формирование маршрута судна в автоматизированных навигационных комплексах: автореф. дис. ... канд. техн. наук: 05.22.19. — СПб., 2002. — 24 с.

6. Некрасов С. Н. Комбинированный метод оценки навигационной безопасности при плавании по внутренним водным путям / С. Н. Некрасов, A. A. Прохоренков // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2011. — № 1. — С. 106-108.

7. Прохоренков A. A. Применение ситуационного метода оценки навигационной безопасности при плавании по внутренним водным путям / А. А. Прохоренков // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2011. — № 1. — С. 91-95.

8. Берштейн Л. С. Использование темпоральных графов как моделей сложных систем / Л. С. Берштейн, А. В. Баженюк // Известия ЮФУ Технические науки. — 2010. — № 4 (105). — С. 198-203.

9. Kostakov V. Temporal graphs / V. Kostakov // Proc. of Physica A: Statistical Mechanics and its Applications. — 2008. — V. 388. — Pp. 1007-1023.

10. Chapman W. L. System Design Is an NP-Complete problem / W. L. Chapman, J. Rozenblit, A. T. Bahill // Systems Engineernig. — 2001. — V. 4. — № 3. — Pp. 222-229.

11. Костюк Ю. Л. Приближённые алгоритмы решения сбалансированной задачи к коммивояжёров / Ю. Л. Костюк, М. С. Пожидаев // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. — 2008. — № 1. — С. 106-112.

12. Частикова В. А. Разработка и сравнительный анализ эвристических алгоритмов для поиска наименьшего гамильтонова цикла в полном графе / В. А. Частикова, К. А. Власов // Фундаментальные исследования. — 2013. — № 10-1. — С. 63-67.

HEURISTIC SEARCH FOR THE OPTIMAL ROUTE SHIP NORTHERN SEA ROUTE

This paper deals the results of the research for constructing an optimal route for the ship in accordance with route time, economical aspects and safety if navigation. The analysis of the constructing of the optimal ship’s route based on the approximation algorithms and heuristic evaluation function presented in this paper. In result of work, a heuristic algorithm A2015 was formulate and was realized n software implementation. The efficiency of algorithm shown by the example of the formation optimal ships route for the Northern Sea Route. A statement of a problem formalized. The paper describes a step-by-step guide of execution of heuristic algorithm to constructing an optimal route of the ship. Presented in the article algorithm A2015 software implementation includes comparing it with the classical Dijkstra and Floyd-Warshall algorithms. The algorithm A2015 can in some cases much faster to generate the optimal ship’s route in a sea in comparison with the classical shortest path algorithms. This approach uses is possible to significantly reduce the amount of all possible amount of calculations, and operational get possible solutions for quick analysis of the situation in a given area of navigation.

Keywords: graph, minimal path, optimal route, heuristic algorithm, Floyd algorithm, search optimization, vector estimates, safety of navigation.

REFERENCES

1. Akmaykin, D., S. Klyueva., and P. Salyuk. “Operational system design analysis and optimization of maritime traffic.” Vestnikgosudarstvennogo universiteta morskogo i rechnogoflota imeni admirala S.O. Makarova 1(29) (2015): 229-236.

2. Akmaykin, D. et al. “Solaris’ information system for ship’s navigation, using operational analysis of shipboard and satellite remote sensing data of hydrosphere and atmosphere.” SPIE Proceedings, Ocean Remote Sensing and Monitoring from Space 926114. (2014): 1-10.

3. Vaskov, A., V. Vaskov, A. Mironenko “Ships Navigation Domain relationship.” Vestnik of Admiral Ushakov State Maritime University. (2013): 18-21.

4. Makosko, A. “Hydrometeorological Support of Navigation along the Northern Sea Route.” The Artic: ecology and economy 3 (2013): 040-049.

5. Mironenko, A. Formirovanie marshruta sudna v avtomatizirovannyh navigacionnyh kompleksah: PhD dissertation thesis: 05.22.19. SPb, 2002.

Выпуск 5(33) 2015.

|Выпуск 5 (33) 2015

6. Nekrasov, S., and A. Prohorenkov. “Combined simulation while estimation of inland waterway navigation safety.” Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S.O. Makarova 1 (2011): 106-108.

7. Prohorenkov, A. “Application of situation simulation while estimation of inland waterway navigation.”

Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S.O. Makarova 1 (2011): 91-95.

8. Bershtein, L, and A. Bazhenyuk. “The using of temporal graphs as the models of complisity systems.” Izvestiya SFedU. Engineering sciences. 4(105) (2010):198-203.

9. Kostakov, V. “Temporal graphs.” Proc. of Physics A: Statistical Mechanics and its Applications 388 (2008): 1007-1023.

10. Chapman, William L., Jerzy Rozenblit, and A. Terry Bahill. “System Design Is an NP-Complete problem.” Systems Engineernig 4.3 (2001): 222-229.

11. Kostyuk, Yu., and M. Pozhidaev. “Approximate algorithms for solution the balanced problem of k travel salesman.” Tomsk State University Journal of Control and Computer Science 1 (2008): 106-112.

12. Chastikova, V., and K. Vlasov. “Development and comparative analysis of heuristic algorithms to search for the minimal Hamiltonian cycle in the complete graph.” Fundamental research 10-1 (2013): 63-67.

ИНФОРМАЦИЯ ОБ АВТОРАХ___________________

Акмайкин Денис Александрович -

кандидат физико-математических наук, доцент.

МГУ им. адм. Г. И. Невельского

akmaykin@msun. ru

Клюева Светлана Федоровна -

кандидат технических наук.

МГУ им. адм. Г.И. Невельского klsvetlkl@gmail. com Салюк Павел Анатольевич -кандидат физико-математических наук.

ТОИ ДВО РАН pavel.salyuk@gmail. com

INFORMATION ABOUT THE AUTHORS

Akmaykin Denis Aleksandrovich -

Candidate of Physical and Mathematical Sciences,

associate professor.

MSU named after adm. G.I. Nevelskoy akm aykin@msun. ru Klyueva Svetlana Fedorovna -Candidate of Engineering.

MSU named after adm. G.I. Nevelskoy

klsvetlkl@gmail. com

Salyuk Pavel Anatolievich -

Candidate of Physical and Mathematical Sciences.

V.I. Il’ichev Pacific Oceanological Institute

pavel.salyuk@gmail. com