COMBINING A GREEDY ALGORITHM WITH THE MONTE CARLO METHOD TO SOLVE LOGISTICS PROBLEMS BASED ON THE TSP

Abstract

One of the urgent problems of existing logistics systems is transportation on optimal (ideally the shortest) routes. As a rule, the solution of this problem is reduced to solving the problem of the salesman (TSP-problem) and requires the development of algorithms that would ensure its solution in the shortest time. The fastest algorithm for solving the problem of a salesman is a greedy algorithm, because it involves only one iteration to find the route by determining the minimum lengths of sections at each step. However, its results are far from optimal. The aim of the article is to evaluate the possibility of combining a greedy algorithm to solve practical logistical problems, which are based on the task of a salesman. The article proposes a combined algorithm for solving the problem of a salesman based on the simultaneous use of a greedy algorithm and an algorithm based on the application of the Monte Carlo method. The proposed combination involves the use of a greedy algorithm at the initial stage of the algorithm due to the fact that it is at this stage that it has high performance. At the final stage, it is proposed to use the Monte Carlo method to select sections of the route - search using random values. The advantage of the combined algorithm over the greedy one has been proved by computer modeling, which will allow to use it effectively for solving logistics problems. The adequacy of the model was verified by calculating the average result for 50 random variants of the salesman problem containing ten cities. The performed calculations also allowed to make assumptions about the insufficient performance of metaheuristic algorithms to solve the problem of the salesman with minimal time, because they all contain long computational procedures that slow down the calculations. As an example, the formulaic dependences of two metaheuristic algorithms - the annealing simulation algorithm and the ant colony algorithm - were given in the article. Further research will confirm or refute this statement.