03-2opt.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2-opt algorithm\n",
    "\n",
    "In optimization, 2-opt is a simple local search algorithm for solving the traveling salesman problem. The 2-opt algorithm was first proposed by Croes in 1958, although the basic move had already been suggested by Flood. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm\n",
    "\n",
    "1. Randomly choice a route and set it as the best route;\n",
    "1. Randomly choice two cities that are not connected in route, and reverse the route between the two nodes to get a new route.\n",
    "1. If the new route is better than the best route, set the new route as the best route, set the counter count to 0, and return to step 2. Otherwise, increase the counter count by 1. When the count is greater than or equal to maxcount, the algorithm ends;\n",
    "\n",
    "## Step by step\n",
    "\n",
    "First, we import the python dependencies required for this section."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we define a travel graph, which include four cities a, b, c and d, and the distance between them is described by distance matrix.\n",
    "\n",
    "|  | a  | b  | c  | d  |\n",
    "|--------|----|----|----|----|\n",
    "| a      | 0  | 20 | 15 | 35 |\n",
    "| b      | 20 | 0  | 10 | 25 |\n",
    "| c      | 15 | 10 | 0  | 12 |\n",
    "| d      | 35 | 25 | 12 | 0  |\n",
    "\n",
    "Each element in the matrix represents the distance between the corresponding row and column city. For example, the distance between a and b is 15. Note that since the round-trip distance between any two points is the same, the distance matrix is a symmetric matrix.\n",
    "\n",
    "The code implementation is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "label = ['a', 'b', 'c', 'd']\n",
    "G = [\n",
    "    [0,20,15,35],\n",
    "    [20,0,10,25],\n",
    "    [15,10,0,12],\n",
    "    [35,25,12,0]\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 1. Randomly choice a route\n",
    "For example, we randomly choice a - > b - > c - > d - > e - > f - > G, and assume that this route is the best route."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calPathDist(route, G):\n",
    "    s = 0\n",
    "    for i in range(0, len(route)-1):\n",
    "        s += G[route[i]][route[i+1]]\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "best_route = list(np.arange(0, len(label)))\n",
    "random.shuffle(best_route)\n",
    "best_dist = calPathDist(best_route, G)\n",
    "print(f'route: {list(map(lambda x:label[x], best_route))}, Distance: {best_dist}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 2. Randomly choice two cities that are not connected in route, and reverse the route between the two nodes to get a new route.\n",
    "\n",
    "For example, we choice node b and node e, the new path is a - > d - > c - > b - > f - > g, and part `()` is the reverse route;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generateRandomPath(route):\n",
    "    a = np.random.randint(len(route))\n",
    "    while True:\n",
    "        b = np.random.randint(len(route))\n",
    "        if np.abs(a - b) > 0:\n",
    "            break\n",
    "    if a > b:\n",
    "        a, b = b, a\n",
    "    re_route = route[:a] + route[a:b+1][::-1] + route[b+1:]\n",
    "    return a, b, re_route\n",
    "\n",
    "node_a, node_b, repalce_route = generateRandomPath(best_route)\n",
    "\n",
    "print(f'Best route: {list(map(lambda x:label[x], best_route))}, repalce_route: {repalce_route}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 3. Compare the new route with best route\n",
    "\n",
    "If the new route is shorter than the best route, set the new route as the best route, set the counter count to 0, and return to step 2. Otherwise, add 1 to the counter count. When the count is greater than or equal to maxcount, the algorithm ends, and min is the shortest path. Otherwise, return to step 2;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "count = 0\n",
    "MAXCOUNT = 10\n",
    "while count < MAXCOUNT:\n",
    "    node_a, node_b, repalce_route = generateRandomPath(best_route)\n",
    "    repalce_dist = calPathDist(repalce_route, G)\n",
    "    if repalce_dist < best_dist:\n",
    "        count = 0\n",
    "        best_route = repalce_route\n",
    "        best_dist = repalce_dist\n",
    "    else:\n",
    "        count += 1\n",
    "print(f'Best route: {list(map(lambda x:label[x], best_route))}, Best Distance: {best_dist}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Note\n",
    "\n",
    "A complete 2-opt local search will compare every possible valid combination of the swapping mechanism. This technique can be applied to the travelling salesman problem as well as many related problems. These include the vehicle routing problem (VRP) as well as the capacitated VRP, which require minor modification of the algorithm.\n",
    "\n",
    "You can find the implementation of the nearest neighbor algorithm in pyTSP from the following location:\n",
    "\n",
    "`pyTSP/source/algorithms/local_optimization.py`\n",
    "\n",
    "## Exercises\n",
    "\n",
    " - Can this method find the best routes? Verify your idea with code (refer to the function for calculating routes distance in permutation.ipynb)\n",
    " - How to combine the nearest neighbor algorithm with 2-opt algorithm?\n",
    " - Try to understand the 3-opt algorithm. http://matejgazda.com/tsp-algorithms-2-opt-3-opt-in-python/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Environment (conda_python3)",
   "language": "python",
   "name": "conda_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.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}