GENERALIZATION OF THE TRAVELING SALESPERSON PROBLEM AND ANALYSIS OF THE EFFECTIVENESS OF METHODS FOR ITS SOLUTION

Abstract

Traveling salesperson problem (circular route problem): determining the shortest path along a closed route quite, often arises in the development of logistics programs, in particular when organizing transportation. Methods for its solution are widely enough covered in many monographs, as well as in educational literature. However, in practice, there are a number of problems that cannot be solved within the framework of classical approaches. In this paper, two classes of problems are considered that can be reduced to the classical traveling salesperson problem and proposes methods for their attention to it. Methods for solving this problem are also analyzed. The first of the classes of problems on a circular route is considered a variant when a vehicle (ship) must necessarily visit one or several points twice. It is shown that this problem splits into two or more separate problems with a circular route and its solution is the sum of solutions of the corresponding classical problems. The second class of problems is problems with priority routes: routes that, for some reason, must be passed first or last. In this case, the problem can be solved in two ways. The first of them consists in identifying priority routes and further solving the shortest-rote problem for the remaining non-priority points. The second way is to reduce the traffic matrix by introducing fictitious times or costs for priority routes. further solution is carried out according to the classical scheme for solving the traveling salesperson problem. The paper also compares three methods for solving the circular route problem. It is concluded that with a small number of points, the direct combinatorial method is the most effective. As the number of sites visited increases, the branch-and-bound method becomes more efficient. It is also shown that the effectiveness of this method decreases in the case of the presence of several optimal solutions. The method for solving a degenerate transportation model, despite its algorithmic nature, is acceptable only in the case of uniqueness or the search for one of the optimal solutions.