ОБ ЭФФЕКТИВНОСТИ НЕКОТОРЫХ ПОДХОДОВ К РЕШЕНИЮ ЗАДАЧИ КОММИВОЯЖЁРА

Димитриев А.П., ORCID: 0000-0002-7345-9790, канд. техн. наук, Чувашский государственный университет им. И.Н. Ульянова, г. Чебоксары, Россия

ОБ ЭФФЕКТИВНОСТИ НЕКОТОРЫХ ПОДХОДОВ К РЕШЕНИЮ ЗАДАЧИ КОММИВОЯЖЁРА

Аннотация. Исследуются возможности программного решения задачи коммивояжёра без использования библиотеки Concorde, которая включает более 700 функций. Предложен ряд способов сокращения маршрута: устранение пересечений, локальная оптимизация методом ближайшего соседа и др. Разработан комплекс программ, реализующий эти способы и выводящий графическое изображение маршрута. Используются общедоступные файлы с данными о городах в формате TSPLIB. Полученный маршрут для 423 городов на 5% длиннее оптимального маршрута.

Ключевые слова: задача коммивояжёра; глобальный оптимум; Concorde.

 

Dimitriev A.P., ORCID: 0000-0002-7345-9790, Ph.D., Chuvash State University named after I.N. Ulyanov, Cheboksary, Russia

ON THE EFFICIENCY OF SOME APPROACHES TO SOLUTION OF THE TRAVELLING SALESMAN'S PROBLEM

Abstract. Possibilities of software solution of the traveling salesman problem without using the Concorde library, which includes more than 700 functions, are investigated. A number of ways to shorten the route are proposed: elimination of intersections, local optimization by the nearest neighbor method, etc. A complex of programs has been developed that implements these methods and displays a graphical image of the route. Publicly available city data files in TSPLIB format are used. The resulting route for 423 cities is 5% longer than the optimal route.

Keywords: traveling salesman problem; global optimum; Concorde.