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

Иванко Е.Е.
 pdf (353K)

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

Ключевые слова: задача коммивояжера, устойчивость
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2011, вып. 1, с. 58-66
DOI: 10.20537/vm110107

Criterion of the stability of optimal route in the Travelling Salesman Problem in case of a single vertex addition

Ivanko E.E.

The criterion for the stability of optimal travelling salesman route in case of the insertion of a new vertex between two consequent vertexes is deduced. Number of experiments demonstrating stability areas are suggested for the Euclidean plane.

Keywords: travelling salesman problem, stability
Citation in English: Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2011, issue 1, pp. 58-66
URL: http://vst.ics.org.ru/journal/article/1737/

Журнал индексируется в Web of Science (Emerging Sources Citation Index)

Журнал индексируется в Scopus

Журнал входит в базы данных zbMATH, MathSciNet

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Журнал входит в систему  Российского индекса научного цитирования.

Журнал включен в перечень ВАК.

Электронная версия журнала на Общероссийском математическом портале Math-Net.Ru.

Журнал включен в Crossref

Copyright © 2009–2024 Институт компьютерных исследований