TY - JOUR
AU - Colak, Recep
PY - 2024/06/30
TI - Solving the Traveling Salesman Problem with Greedy Genetic Algorithm
JF - Journal of Multidisciplinary Developments; Vol 9 No 1 (2024): "Union": Volume: 9, Issue: 1
KW -
N2 - The traveling salesman problem (TSP) is an NP-hard problem that is difficult to solve. TSP is a general problem with many sub-branches such as vehicle routing, cargo distribution, circuit element placement for electronic cards, school busses. The problem can be solved in N! time by trying all possibilities. When the number of points to be visited is small, precise methods can be used, while when the number of points is high, a solution in an acceptable time is not possible with precise methods. When the number of points is large, the problem is solved with heuristic algorithms that give solutions close to the optimum solution. Genetic Algorithm (GA), which is an heuristic method, is a frequently used method in solving the TSP problem. In this study, the effect of assigning the initial chromosomes of GA with Greedy Heuristic (GH) on the solution was investigated. In the Greedy approach, the first point is randomly selected, the next visit point is selected, and the closest point to the last selected point is selected and the tours are completed. The obtained results showed that the initial routes were assigned with GH instead of random assignment, giving better solutions. In addition, fewer chromosomes were needed in the solutions obtained with GH, thus shortening the runtime.
UR - http://jomude.com/index.php/jomude/article/view/111