О применении эвристических алгоритмов решения псевдогеометрической версии задачи коммивояжёра
для проектирования сетей связи

Резюме: Математические модели и алгоритмы, разрабатываемые для решения задачи коммивояжёра, разрабатываются специально для построения оптимальных маршрутов движения и выбора оптимальной траектории. При этом такие модели и алгоритмы применяются и для решения нескольких связанных между собой групп прикладных задач – например, исследование ДНК-цепочек, вычисление «похожести» длинных строк, построение алгоритмов проверки специальных грамматических структур и др. Получаемые варианты задачи коммивояжёра близки к псевдогеометрической версии.  Для нас наибольший интерес представляют вопросы, связанные с сетями связи высокой размерности. Имеются по крайней мере две различные пред­метные области, относящиеся к применению псевдогеометрической версии задачи комми­вояжёра и эвристических алгоритмов её решения. Во-первых, это расположение исходных точек при генерации исходных данных. Во-вторых, если мы заранее как-то предварительно хорошо организуем последовательность точек, то применяемые нами эвристические алгоритмы будут работать быстрее; при этом можно считать, что такое «хорошее расположение» и есть псевдооптимальное решение задачи коммивояжёра.  В статье мы также кратко описываем применяемый нами подход к классификации вариантов генерации входных данных, предназначенных в первую очередь для проверки работы и сравнения эвристических алгоритмов. Кроме того, приводится описание вспомогательного алгоритма псевдооптимального размещения точек; этот алгоритм желательно применять именно для набора точек, сгенерированного как вариант псевдогеометрической версии задачи коммивояжёра. Также в статье приводятся некоторые результаты вычислительных экспериментов, позволяющие сравнить разные алгоритмы решения псевдогеометрических вариантов проблемы.

Ключевые слова: задача коммивояжёра, псевдогеометрическая версия, эвристические алгоритмы, сети связи.

B. F. Melnikov, Yu. Yu. Terentyeva, D. A. Chaikovskii

On the application of heuristic algorithms for solving  the pseudogeometric version of the traveling  salesman problem for the design of communication networks

Summary: The Mathematical models and algorithms developed to solve the traveling salesman problem are developed specifically for constructing optimal driving routes and choosing the optimal trajectory. At the same time, such models and algorithms are also used to solve several interconnected groups of applied problems; for example, it is the study of DNA chains, the calculation of the “similarity” of long strings, the construction of algorithms for checking special grammatical structures, etc. The resulting variants of the traveling salesman problem are close to the pseudogeometric version. We are most interested in issues related to communication networks (first of all, large ones). There are at least two different subject areas related to the application of the pseudogeometric version of the traveling salesman problem and heuristic algorithms for its solution. First, it is the location of the source points when generating the source data. Secondly, if we somehow organize the sequence of points well in advance, then the heuristic algorithms we use will work faster; at the same time, we can assume that such a “good location” is a pseudo-optimal solution to the traveling salesman problem. In the article, we also briefly describe our approach to classifying input data generation options designed primarily to test the operation and compare heuristic algorithms. In addition, an auxiliary algorithm for pseudo-optimal placement of points is described; it is desirable to use this algorithm specifically for a set of points generated as a variant of the pseudo-geometric version of the traveling salesman problem. The article also presents some results of computational experiments that allow comparing different algorithms for solving pseudogeometric variants of the problem.

Keywords: traveling salesman problem, pseudogeometric version, heuristic algorithms, communication networks.

DOI: 10.34219/2078-8320-2023-14-4-7-16