Recommended: Delivery Route Optimization using Python: A Step-by-Step Guide<\/a><\/em><\/strong><\/p>\n\n\n\n The problem statement is that a salesman has to travel to the Indian cities of Mumbai, Delhi, Bangalore, Hyderabad, Ahmedabad, Chennai, Kolkata, Surat, Pune, and Jaipur to sell some products.<\/p>\n\n\n\n The objective of the problem is to minimize the total distance travelled by the salesman.<\/p>\n\n\n\n This describes our problem statement. Now let’s move on to how to solve this problem using Python programming language.<\/p>\n\n\n\n We will look at two ways of solving the problem – using the Greedy algorithm and the Brute Force method ( this method is the most preferred one as it provides more optimal solutions ).<\/p>\n\n\n\n Let us look at the code of the Simple Greedy algorithm.<\/p>\n\n\n In the above example, we randomly input some coordinates and calculated the best route. Let us look at the output of this method.<\/p>\n\n\n\n Thus, according to the Greedy algorithm, we will travel to city 1 first, and cities 1,3,2 after that.<\/p>\n\n\n\n Let us look at the code of the Brute Force Method.<\/p>\n\n\n Let us look at the output of the Brute Force method.<\/p>\n\n\n\n Thus, according to the Brute force method, the minimum distance is approximately 230 units.<\/p>\n\n\n\n The difference between the Greedy algorithm and the Brute Force method is that the Greedy algorithm builds up the solution step by step whereas in the Brute Force method, all the permutations of the solution are found and then the solution with minimum distance is selected.<\/p>\n\n\n\n Here you go! Now you know the Travelling Salesman Problem and how to solve it using Python. In this article, you learned about two methods of approach i.e. Greedy algorithm and Travelling Salesman problem.<\/p>\n\n\n\n Hope you enjoyed reading it!<\/p>\n\n\n\n Recommended: Backtracking Line Search Algorithm for Unconstrained Optimization<\/a><\/em><\/strong><\/p>\n\n\n\nSolving the Traveling Salesman Problem with Python<\/h2>\n\n\n\n
Example Usage and Visualization of the Greedy Algorithm<\/h3>\n\n\n\n
\nimport matplotlib.pyplot as plt\n\ndef distance(city1, city2):\n # Replace this with your distance calculation function (e.g., Euclidean distance)\n x1, y1 = city1\n x2, y2 = city2\n return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5\n\ndef tsp(cities):\n visited = [False] * len(cities)\n current_city = 0\n\n tour = []\n total_distance = 0\n\n for _ in range(len(cities)):\n visited[current_city] = True\n tour.append(current_city)\n\n next_city = None\n min_distance = float('inf') # Represents positive infinity\n\n for i in range(len(cities)):\n if visited[i]:\n continue\n\n d = distance(cities[current_city], cities[i])\n if d < min_distance:\n min_distance = d\n next_city = i\n\n current_city = next_city\n total_distance += min_distance\n\n return tour, total_distance\n\n# Example usage\ncities = [(2, 4), (1, 8), (7, 1), (8, 5)]\n\ntour, total_distance = tsp(cities)\n\nprint("Tour:", tour)\nprint("Total Distance:", total_distance)\n\n# Plotting\nx_coords = [cities[i][0] for i in tour]\ny_coords = [cities[i][1] for i in tour]\nx_coords.append(x_coords[0]) # Close the loop for plotting\ny_coords.append(y_coords[0])\n\nplt.plot(x_coords, y_coords)\nplt.scatter(x_coords, y_coords, s=50, color='red') # Plot cities as red dots\nplt.title("Traveling Salesman Problem - Greedy Algorithm")\nplt.show()\n\n<\/pre><\/div>\n\n\n![\"Travelling](\"https:\/\/www.askpython.com\/wp-content\/uploads\/2024\/04\/Travelling-Salesman-Greedy-algorithm.png\")
![\"Travelling](\"https:\/\/www.askpython.com\/wp-content\/uploads\/2024\/04\/Travelling-Salesman-Greedy-algorithm-output.png\")
Brute Force Approach to the Traveling Salesman Problem<\/h3>\n\n\n\n
\nimport numpy as np\nimport itertools\nimport matplotlib.pyplot as plt\n\ndef calculate_distance(city1, city2):\n return np.linalg.norm(np.array(city1) - np.array(city2))\n\ndef total_distance(route, distances):\n total = 0\n for i in range(len(route) - 1):\n total += distances[route[i], route[i+1]]\n total += distances[route[-1], route[0]] # Complete the loop\n return total\n\ndef brute_force_tsp(coords, city_names):\n n = len(coords)\n distances = np.zeros((n, n))\n for i in range(n):\n for j in range(i, n):\n distances[i, j] = distances[j, i] = calculate_distance(coords[i], coords[j])\n\n min_distance = float('inf')\n min_route = None\n\n for route in itertools.permutations(range(n)):\n distance = total_distance(route, distances)\n if distance < min_distance:\n min_distance = distance\n min_route = route\n\n min_route_names = [city_names[i] for i in min_route]\n return min_route_names, min_distance\n\n# Generate random city coordinates and city names\nnp.random.seed(0)\ncity_names = ['Mumbai', 'Delhi', 'Bangalore', 'Hyderabad', 'Ahmedabad', 'Chennai', 'Kolkata', 'Surat', 'Pune', 'Jaipur']\nnum_cities = len(city_names)\ncoords_list = [(np.random.randint(1, 100), np.random.randint(1, 100)) for _ in range(num_cities)]\n\n# Solve TSP using brute force\nbest_route, best_distance = brute_force_tsp(coords_list, city_names)\n\nprint('Best Route:', best_route)\nprint('Best Distance:', best_distance)\n\n# Plot the cities and the route\nplt.figure(figsize=(8, 6))\nplt.scatter(*zip(*coords_list), color='blue')\nfor i, city in enumerate(coords_list):\n plt.text(city[0], city[1], city_names[i], fontsize=12)\nfor i in range(len(best_route) - 1):\n city1 = coords_list[city_names.index(best_route[i])]\n city2 = coords_list[city_names.index(best_route[i+1])]\n plt.plot([city1[0], city2[0]], [city1[1], city2[1]], color='red', linewidth=1)\nplt.plot([coords_list[city_names.index(best_route[-1])][0], coords_list[city_names.index(best_route[0])][0]],\n [coords_list[city_names.index(best_route[-1])][1], coords_list[city_names.index(best_route[0])][1]], color='red', linewidth=1) # Complete the loop\nplt.title('Brute Force TSP - Best Route')\nplt.xlabel('X Coordinate')\nplt.ylabel('Y Coordinate')\nplt.grid(True)\nplt.show()\n\n<\/pre><\/div>\n\n\n![\"Brute](\"https:\/\/www.askpython.com\/wp-content\/uploads\/2024\/04\/Brute-Force-method.png\")
![\"Brute](\"https:\/\/www.askpython.com\/wp-content\/uploads\/2024\/04\/Brute-Force-method-output-1024x34.png\")
Greedy Algorithm vs. Brute Force Method<\/h3>\n\n\n\n
Conclusion<\/h2>\n\n\n\n