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

 pdf (620K)

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

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

Sufficient conditions of the stability of optimal route in the Travelling Salesman Problem in cases of a single vertex addition or substraction

The sufficient conditions for the stability of optimal travelling salesman route in case of the insertion of a new vertex between two consequent vertices and in case of the substraction of one vertex are deduced. Number of experiments, demonstrating stability areas and vertices are suggested for the Euclideanplane.

Keywords: travelling salesman problem, stability
Citation in English: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2010, issue 1, pp. 48-57

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

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

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

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

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

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

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