COMPUTER PROGRAM FOR SOLVING VARIOUS VERSIONS OF THE TRAVELING SALESMAN PROBLEM USING A GENETIC ALGORITHM

Abstract

Currently, transport logistics is developing intensively. Optimal routes for vehicles for a certain set of communication points: transit, initial and final points, can be found by solving various versions of the traveling salesman problem.The traveling salesman problem is a classical optimization problem. In the case of its closed version, the traveling salesman, moving from the initial point (IP), visits all transit points once and returns to the IP. In the case of an open version, the traveling salesman moves from the IP, visits all transit points once and arrives at the final point.The routes for the closed and open versions of the problem can be determined using computer programs that use a genetic algorithm (GA) for solving.When using GA to solve the traveling salesman problem, with a large number of transit points, a possible situation is choosing the optimal route from several obtained with different parameters of the genetic algorithm. In this case, prompt interactive interaction with the program is necessary to change the GA parameters. As is known, computer programs with a graphical user interface have interactivity.In this work, a cross-platform computer program for solving various versions of the traveling salesman problem using a genetic algorithm was developed in the Java programming language. It has a graphical user interface and allows you to determine the optimal route for both closed and open versions of the traveling salesman problem. At the same time, the graphical interface makes it possible to change the GA parameters in the process of working with the application and display the found routes in graphical form.Previously, data on the location of the traffic points, in the form of their names and corresponding values of geographic coordinates of latitude and longitude, are entered into the program from a *.csv file.The program uses a genetic algorithm based on methods that implemented crossover, chromosome mutation, elitism and tournament selection mechanisms, and population fitness assessment for each version of the traveling salesman problem (the methods for implementing crossover and chromosome mutation of the population differed for different versions of the problem). The application uses the haversine formula to estimate the distance between cities and the length of the route.