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

Иванко Е.Е.
 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

Ivanko E.E.

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: Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2010, issue 1, pp. 48-57
URL: http://vst.ics.org.ru/journal/article/1631/

Журнал индексируется в 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 Институт компьютерных исследований