NEW RNN_Two-Opt-Swap_TSP.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import math\n",
    "\n",
    "def calculate_distance(city1, city2):\n",
    "    \"\"\"\n",
    "    Calculates the Euclidean distance between two cities.\n",
    "\n",
    "    Parameters:\n",
    "    city1 (tuple): A tuple of two integers representing the coordinates of city1.\n",
    "    city2 (tuple): A tuple of two integers representing the coordinates of city2.\n",
    "\n",
    "    Returns:\n",
    "    float: The Euclidean distance between city1 and city2.\n",
    "    \"\"\"\n",
    "\n",
    "    # Calculate the difference between the x-coordinates of the two cities, square it,\n",
    "    # add it to the square of the difference between the y-coordinates, and take the square root.\n",
    "    return math.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)\n",
    "\n",
    "\n",
    "def calculate_distance_matrix(cities):\n",
    "    \"\"\"\n",
    "        Generates a distance matrix from a list of cities and their coordinates.\n",
    "\n",
    "        Parameters:\n",
    "        cities (list): A list of city names and their coordinates.\n",
    "\n",
    "        Returns:\n",
    "        list: A distance matrix of pairwise distances between cities.\n",
    "        \"\"\"\n",
    "    n = len(cities)  # Get the number of cities.\n",
    "\n",
    "    # Create an empty distance matrix with dimensions n x n.\n",
    "    distance_matrix = [[0] * n for _ in range(n)]\n",
    "\n",
    "    # Loop over each pair of cities and calculate their distance.\n",
    "    for i in range(n):\n",
    "        # Only calculate the distance once for each pair of cities.\n",
    "        for j in range(i+1, n):\n",
    "            # Calculate the distance between cities i and j using the calculate_distance function.\n",
    "            distance = calculate_distance(cities[i], cities[j])\n",
    "            # Set the (i, j) entry to the distance.\n",
    "            distance_matrix[i][j] = distance\n",
    "            # Set the (j, i) entry to the distance (since the distance between cities i and j is the same as the distance between cities j and i).\n",
    "            distance_matrix[j][i] = distance\n",
    "\n",
    "    return distance_matrix  # Return the distance matrix.\n",
    "\n",
    "\n",
    "def randomized_nearest_neighbor(cities, distance_matrix):\n",
    "    \"\"\"\n",
    "    Generates an initial route using the randomized nearest neighbor algorithm.\n",
    "\n",
    "    Parameters:\n",
    "    cities (list): A list of city names.\n",
    "    distance_matrix (list): A distance matrix of pairwise distances between cities.\n",
    "\n",
    "    Returns:\n",
    "    list: A route generated by the randomized nearest neighbor algorithm.\n",
    "    \"\"\"\n",
    "    n = len(cities)   # Get the number of cities\n",
    "    # Initialize visited_cities list with n number of False\n",
    "    visited_cities = [False] * n\n",
    "    route = [0] * n   # Initialize route list with n number of 0's\n",
    "\n",
    "    # Select a random starting city.\n",
    "    # Select a random city index as the starting city\n",
    "    current_city = random.randint(0, n-1)\n",
    "    visited_cities[current_city] = True   # Mark the starting city as visited\n",
    "    # Add the starting city to the first index of route\n",
    "    route[0] = current_city\n",
    "\n",
    "    # Add the remaining cities to the route.\n",
    "    for i in range(1, n):   # Iterate through the remaining cities\n",
    "        # Compute the distances from the last city added to all remaining cities.\n",
    "        distances = [(distance_matrix[current_city][j], j)\n",
    "                     for j in range(n) if not visited_cities[j]]   # Calculate the distance between the current city and all unvisited cities\n",
    "        # Select the city with the shortest distance to the last city and add it to the route.\n",
    "        # Get the city with the shortest distance from the current city\n",
    "        min_distance, nearest_city = min(distances)\n",
    "        # Mark the selected city as visited\n",
    "        visited_cities[nearest_city] = True\n",
    "        route[i] = nearest_city   # Add the selected city to the route list\n",
    "        current_city = nearest_city   # Update the current city to the selected city\n",
    "\n",
    "    return route   # Return the generated route list\n",
    "\n",
    "\n",
    "def calculate_total_distance(route, distance_matrix):\n",
    "    \"\"\"\n",
    "    Calculates the total distance of a route given its distance matrix.\n",
    "\n",
    "    Parameters:\n",
    "    route (list): A list of city indices representing the route.\n",
    "    distance_matrix (list): A distance matrix of pairwise distances between cities.\n",
    "\n",
    "    Returns:\n",
    "    float: The total distance of the given route.\n",
    "    \"\"\"\n",
    "    total_distance = 0  # initialize total distance to zero\n",
    "    n = len(route)  # get the number of cities in the route\n",
    "    for i in range(n-1):  # iterate over the cities in the route (excluding the last one)\n",
    "        # add the distance between the current city and the next city in the route to the total distance\n",
    "        total_distance += distance_matrix[route[i]][route[i+1]]\n",
    "    # add the distance between the last city in the route and the first city in the route to the total distance\n",
    "    total_distance += distance_matrix[route[-1]][route[0]]\n",
    "    return total_distance  # return the total distance\n",
    "\n",
    "\n",
    "def swap_cities(route, i, j):\n",
    "    \"\"\"\n",
    "    Swaps two cities in a route.\n",
    "\n",
    "    Parameters:\n",
    "    route (list): A list of city indices representing the route.\n",
    "    i (int): The index of the first city to be swapped.\n",
    "    j (int): The index of the second city to be swapped.\n",
    "\n",
    "    Returns:\n",
    "    list: A new list with the two cities swapped.\n",
    "    \"\"\"\n",
    "    # Make a copy of the original route list.\n",
    "    new_route = route[:]\n",
    "    # Swap the cities at indices i and j.\n",
    "    new_route[i], new_route[j] = new_route[j], new_route[i]\n",
    "    return new_route\n",
    "\n",
    "\n",
    "def apply_2opt_swap(route, i, j):\n",
    "    \"\"\"\n",
    "    Applies the 2-opt swap to a route.\n",
    "\n",
    "    Given a route and two indices i and j, this function applies a 2-opt swap to\n",
    "    the portion of the route between indices i and j. Specifically, it reverses\n",
    "    the order of the nodes between i and j (inclusive) and returns the new route.\n",
    "    This can be used in algorithms that optimize routes, such as the Traveling\n",
    "    Salesman Problem.\n",
    "\n",
    "    Parameters:\n",
    "    route (list): A list of nodes representing a route.\n",
    "    i (int): The starting index of the portion of the route to swap.\n",
    "    j (int): The ending index of the portion of the route to swap.\n",
    "\n",
    "    Returns:\n",
    "    list: A new list representing the route with the 2-opt swap applied.\n",
    "    \"\"\"\n",
    "    # create a new route by concatenating three slices of the original route:\n",
    "        # - the portion of the route before index i\n",
    "        # - the portion of the route between indices i and j, reversed\n",
    "        # - the portion of the route after index j\n",
    "    new_route = route[:i] + route[i:j+1][::-1] + route[j+1:]\n",
    "    # return the new route\n",
    "    return new_route\n",
    "\n",
    "\n",
    "def run_tsp(cities, num_iterations):\n",
    "    \"\"\"\n",
    "    Runs the Traveling Salesman Problem algorithm using RNNA and2-opt optimization.\n",
    "\n",
    "    Args:\n",
    "    cities (list): A list of cities.\n",
    "    num_iterations (int): The number of iterations to perform.\n",
    "\n",
    "    Returns:\n",
    "    None. Prints the initial route and distance, the RNNA route and distance, and the optimized route and distance.\n",
    "    \"\"\"\n",
    "\n",
    "    # Calculate the distance matrix between cities.\n",
    "    distance_matrix = calculate_distance_matrix(cities)\n",
    "\n",
    "    # Generate an initial route using random shuffling.\n",
    "    initial_route = list(range(len(cities)))\n",
    "    random.shuffle(initial_route)\n",
    "    initial_distance = calculate_total_distance(initial_route, distance_matrix)\n",
    "\n",
    "    # Generate a route using the randomized nearest neighbor algorithm.\n",
    "    rnna_route = randomized_nearest_neighbor(cities, distance_matrix)\n",
    "    rnna_distance = calculate_total_distance(rnna_route, distance_matrix)\n",
    "\n",
    "    # Apply the 2-opt algorithm to improve the route.\n",
    "    current_best_route = rnna_route\n",
    "    current_best_distance = rnna_distance\n",
    "\n",
    "    # Perform a given number of iterations and apply the 2-opt swap to improve the route.\n",
    "    for i in range(num_iterations):\n",
    "        # Select two random cities in the current best route.\n",
    "        city1, city2 = random.sample(range(len(initial_route)), 2)\n",
    "        # Apply the 2-opt swap to the current best route.\n",
    "        new_route = apply_2opt_swap(current_best_route, city1, city2)\n",
    "\n",
    "        # Calculate the total distance of the new route.\n",
    "        new_distance = calculate_total_distance(new_route, distance_matrix)\n",
    "\n",
    "        # If the new route is shorter than the current best route, update the current best route.\n",
    "        if new_distance < current_best_distance:\n",
    "            current_best_route = new_route\n",
    "            current_best_distance = new_distance\n",
    "\n",
    "    # Print the initial route and distance.\n",
    "    print(\"Route list output is limited to 15 elements only for readability.\")\n",
    "\n",
    "    print(\"\\nInitial Route: \", initial_route[0:14])\n",
    "    print(\"Initial Distance: \", initial_distance, \"km\")\n",
    "\n",
    "    # Print the RNNA route and distance, and the improvement by RNNA.\n",
    "    print(\"\\nRandomized Nearest Neighbor Route: \", rnna_route[0:14])\n",
    "    print(\"Randomized Nearest Neighbor Distance: \", rnna_distance, \"km\")\n",
    "    print(\"Improved by RNNA: -\", initial_distance - rnna_distance, \"km | In percentage: \",\n",
    "          (initial_distance - rnna_distance) / initial_distance * 100, \"%\")\n",
    "\n",
    "    # Print the optimized route and distance, and the improvement by 2-opt swaps.\n",
    "    print(\"\\nOptimized Route: \", current_best_route[0:14])\n",
    "    print(\"Optimized Distance: \", current_best_distance, \"km\")\n",
    "    print(\"Improved by 2-Opt Swap: -\", rnna_distance - current_best_distance,\n",
    "          \"km | In percentage: \", (rnna_distance - current_best_distance) / rnna_distance * 100, \"%\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial Route:  [0, 10, 14, 4, 3, 12, 9, 1, 13, 11]\n",
      "Initial Distance:  2410.8185328092045 km\n",
      "\n",
      "Randomized Nearest Neighbor Route:  [10, 11, 9, 8, 6, 7, 5, 4, 3, 2]\n",
      "Randomized Nearest Neighbor Distance:  1088.6094614124058 km\n",
      "Improved by RNNA: - 1322.2090713967987 km | In percentage:  54.844819442137585 %\n",
      "\n",
      "Optimized Route:  [14, 13, 12, 11, 10, 3, 2, 1, 0, 4]\n",
      "Optimized Distance:  961.8890229924045 km\n",
      "Improved by 2-Opt Swap: - 126.7204384200013 km | In percentage:  11.640578454608422 %\n"
     ]
    }
   ],
   "source": [
    "# TEST CASE 1 - 15 cities; 1000 iterations\n",
    "# Original proposed solution to the vaccine distribution problem\n",
    "# Carl's note: I wanted to use the real location of the cities in Quezon, but due to time constraints and conflicting priorities, I used random coordinates. I wish to implement this in the future.\n",
    "\n",
    "num_iterations = 1000\n",
    "cities = [(110.0, 225.0), (161.0, 283.0), (188.0, 293.0), (264.0, 292.0),    (280.0, 231.0), (333.0, 198.0), (340.0, 149.0),\n",
    "          (366.0, 129.0),    (382.0, 179.0), (380.0, 218.0), (394.0, 261.0), (413.0, 242.0),    (449.0, 269.0), (477.0, 246.0), (469.0, 205.0)]\n",
    "\n",
    "run_tsp(cities, num_iterations)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial Route:  [463, 844, 765, 554, 819, 826, 204, 259, 605, 255]\n",
      "Initial Distance:  531685.0307905608 km\n",
      "\n",
      "Randomized Nearest Neighbor Route:  [27, 410, 751, 517, 125, 523, 518, 622, 107, 445]\n",
      "Randomized Nearest Neighbor Distance:  29520.400486374714 km\n",
      "Improved by RNNA: - 502164.630304186 km | In percentage:  94.44776535414567 %\n",
      "\n",
      "Optimized Route:  [531, 838, 831, 115, 203, 865, 839, 619, 796, 268]\n",
      "Optimized Distance:  29364.500510001933 km\n",
      "Improved by 2-Opt Swap: - 155.89997637278066 km | In percentage:  0.5281092864737287 %\n"
     ]
    }
   ],
   "source": [
    "# TEST CASE 2 - 1000 cities; 10000 iterations\n",
    "# Scaled up version of the original proposed solution to the vaccine distribution problem.\n",
    "# Wider spread of cities.\n",
    "# More iterations to improve the route.\n",
    "\n",
    "num_iterations = 10000\n",
    "# Generate 1000 cities with random coordinates from 0 - 1000 km.\n",
    "cities = [(random.randint(0, 1000), random.randint(0, 1000))\n",
    "          for i in range(1000)]\n",
    "\n",
    "run_tsp(cities, num_iterations)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.5"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}