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

 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

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: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2011, issue 1, pp. 58-66

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

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

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

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

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

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

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