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.

Задача комівояжера (задача про кільцевий маршрут): визначення найкоротшого шляху по замкненому маршруту досить часто виникає при розробці логістичних програм, зокрема при організації транспортних перевезень. Методи її розв’язання досить широко висвітлені в багатьох монографіях та в навчальній літературі. Однак, на практиці зустрічається ряд задач, які не можуть бути розв’язані в межах класичних підходів.

У даній роботі розглянуто два класи задач, які можуть бути зведені до класичної задачі комівояжера і запропоновані методи зведення до неї. Також проаналізовано методи розв’язання запропонованих задач.

У першому з класів задач про кільцевий маршрут розглянуто варіант, коли транспортний засіб (судно) за необхідністю має відвідати один або кілька пунктів двічі. Показано, що дана задача розпадається на дві або більше окремих задач про кільцевий маршрут і її розв’язання є сумою  розв’язків відповідних класичних задач.

Другий клас задач - це задачі з пріоритетними маршрутами: маршрутами, які в силу певних причин повинні бути пройдені першими або останніми. У даному випадку вихідна задача може бути розв’язана двома способами. Перший з них полягає у виділенні пріоритетних ділянок і подальшому розв’язанні задачі про найкоротший шлях для решти непріоритетних ділянок. Другий спосіб полягає в редукції матриці перевезень за допомогою введення фіктивних часу або витрат для пріоритетних ділянок. Подальше розв’язання проводиться за класичною схемою розв'язання задачі комівояжера.

У статті також проведено порівняння трьох методів розв’язання задачі про кільцевий маршрут. Зроблено висновок про те, що при невеликій кількості пунктів найбільш ефективним є прямий комбінаторний метод. При збільшенні кількості відвідуваних пунктів ефективнішим стає метод розгалужень і меж. Зауважено, що ефективність даного методу знижується в разі наявності декількох оптимальних розв’язків. Метод розв’язання виродженої транспортної задачі, незважаючи на свою алгоритмічність, є прийнятним тільки в разі єдиності або пошуку одного з оптимальних розв’язків.