Подход к решению псевдогеометрической версии задачи коммивояжера

Актуальность и цели. Задача коммивояжера является примером математической модели, которая, будучи созданной для одной предметной области, находит свое применение и во многих других областях. Псевдогеометрическая версия этой проблемы более адекватно описывает множество ее частных случаев, встречающихся в большинстве предметных областей, чем значительно более распространенная геометрическая версия. Цель работы: применить разработанные подходы для решения геометрической версии задачи коммивояжера для ее так называемой псевдогеометрической версии. Материалы и методы. Для решения псевдогеометрической задачи коммивояжера рассматривается несколько случайно сгенерированных перестановок всего множества точек, и для каждой из них применяется алгоритм псевдовосстановления их расположения. Выбор единственного варианта расположения каждой точки возможен после решения оптимизационной задачи, заключающейся в повороте сгенерированного множества точек на некоторый угол и смещении на некоторый вектор. Результат. Сформулированы различные метрики и изучены их свойства, на основании которых разработан эвристический алгоритм локального поиска. Выводы. Применение описанных в настоящей работе метрик и эвристического алгоритма локального поиска позволило повысить эффективность геометрического метода решения псевдогеометрической задачи коммивояжера.