The Study of the Longest Non-Intersecting Route Problem Using Genetic Algorithm

Genetic algorithm contains the characteristics of global search that can be applied in solving the traveling salesman problem effectively. In this paper, we propose a novel problem of maximizing the length of a non-intersecting closed route in which each node, except for the starting point, is only visited once. The genetic algorithm of the traveling salesman problem is modified to solve the problem. In the process, some theorems regarding the intersection of two line segments are presented. Simulation results show that our proposed algorithm performs well on the optimization of the length of the route.