Effective Solution for the Traveling Salesman Problem on Randomly Distributed Data

Abstract

In this study, we present a method and its implementations for the traveling salesman problem considering matrices with a uniform random distribution of path costs. The method is a modification of the branch-and-bound method with specific heuristics. Data generation and validation used for this study are discussed. The mathematical study of the problem being solved can probably be considered complete as early as the 1970s; even earlier, an approach to its solution in the form of the branch- and-bound method was described. The purpose of this paper is to describe such a heuristic implementation of the branch-and-bound method, which with almost a single probability gives the optimal solution to a random problem in an acceptable time. We call random variants of the problem, in which each cell of the traveling salesman matrix for a problem instance represents a realization of a uniformly distributed random variable. It is important to note that approaches to the heuristic solution of a random variant differ significantly from approaches to geometric and pseudogeometric variants. In our opinion, we have achieved our goal: thus, the maximum time to obtain a solution for 100 random problem instances of dimension 99 did not exceed 2 minutes, while the exact solution was always found; the last thing was verified by the fact that the branch-and-bound method was always counted to completion. In the paper, we provide a brief description of the heuristics used for this purpose, the most important of which is the construction of the so-called sequence of right-hand subproblems.