Optimization Techniques for the Traveling Salesman Problem: A Study of Conglomerate of Algorithmic Approaches
Yamini Niharika, Thirumalaraju Akhila, V. Vaishnavi, Apurvanand Sahay · 2024
This project investigates Python to study the Traveling Salesman Problem (TSP) and looks at five different algorithms that can be implemented: Brute Force, Greedy, Genetic, Dynamic Programming, and Divide and Conquer. Locating the shortest path that makes accurate stops in each city before returning to the origin city is the task assigned to the TSP. In order to identify the best solution, the Brute Force algorithm thoroughly looks through every combination of city sequences. The nearest unexplored city is chosen at each stage via the Greedy Algorithm, in contrast, which makes locally optimal decisions. By applying genetic operators like crossover and mutation, genetic algorithms generate new generations of possible paths by iteratively improving existing ones, mimicking the principles of natural selection. To cut down on unnecessary computations, dynamic programming divides the problem into smaller subproblems and stores the answers.