script_81_cities.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9a5fd2f0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import Required Libraries\n",
    "\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "from pulp import *\n",
    "from itertools import product\n",
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "195a24b6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>ADANA</th>\n",
       "      <th>ADIYAMAN</th>\n",
       "      <th>AFYON</th>\n",
       "      <th>AĞRI</th>\n",
       "      <th>AMASYA</th>\n",
       "      <th>ANKARA</th>\n",
       "      <th>ANTALYA</th>\n",
       "      <th>ARTVİN</th>\n",
       "      <th>AYDIN</th>\n",
       "      <th>BALIKESİR</th>\n",
       "      <th>...</th>\n",
       "      <th>BATMAN</th>\n",
       "      <th>ŞIRNAK</th>\n",
       "      <th>BARTIN</th>\n",
       "      <th>ARDAHAN</th>\n",
       "      <th>IĞDIR</th>\n",
       "      <th>YALOVA</th>\n",
       "      <th>KARABÜK</th>\n",
       "      <th>KİLİS</th>\n",
       "      <th>OSMANİYE</th>\n",
       "      <th>DÜZCE</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>İL ADI</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>ADANA</th>\n",
       "      <td>NaN</td>\n",
       "      <td>333.0</td>\n",
       "      <td>573.0</td>\n",
       "      <td>965.0</td>\n",
       "      <td>611.0</td>\n",
       "      <td>490.0</td>\n",
       "      <td>558.0</td>\n",
       "      <td>1034.0</td>\n",
       "      <td>883.0</td>\n",
       "      <td>897.0</td>\n",
       "      <td>...</td>\n",
       "      <td>618.0</td>\n",
       "      <td>717.0</td>\n",
       "      <td>769.0</td>\n",
       "      <td>1038.0</td>\n",
       "      <td>1068.0</td>\n",
       "      <td>893.0</td>\n",
       "      <td>701.0</td>\n",
       "      <td>246.0</td>\n",
       "      <td>87.0</td>\n",
       "      <td>722.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>ADIYAMAN</th>\n",
       "      <td>333.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>906.0</td>\n",
       "      <td>648.0</td>\n",
       "      <td>634.0</td>\n",
       "      <td>755.0</td>\n",
       "      <td>891.0</td>\n",
       "      <td>755.0</td>\n",
       "      <td>1216.0</td>\n",
       "      <td>1230.0</td>\n",
       "      <td>...</td>\n",
       "      <td>301.0</td>\n",
       "      <td>480.0</td>\n",
       "      <td>1038.0</td>\n",
       "      <td>759.0</td>\n",
       "      <td>751.0</td>\n",
       "      <td>1162.0</td>\n",
       "      <td>970.0</td>\n",
       "      <td>209.0</td>\n",
       "      <td>246.0</td>\n",
       "      <td>991.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>AFYON</th>\n",
       "      <td>573.0</td>\n",
       "      <td>906.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>1311.0</td>\n",
       "      <td>590.0</td>\n",
       "      <td>256.0</td>\n",
       "      <td>292.0</td>\n",
       "      <td>1237.0</td>\n",
       "      <td>346.0</td>\n",
       "      <td>324.0</td>\n",
       "      <td>...</td>\n",
       "      <td>1191.0</td>\n",
       "      <td>1290.0</td>\n",
       "      <td>515.0</td>\n",
       "      <td>1346.0</td>\n",
       "      <td>1421.0</td>\n",
       "      <td>341.0</td>\n",
       "      <td>447.0</td>\n",
       "      <td>819.0</td>\n",
       "      <td>660.0</td>\n",
       "      <td>375.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>AĞRI</th>\n",
       "      <td>965.0</td>\n",
       "      <td>648.0</td>\n",
       "      <td>1311.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>738.0</td>\n",
       "      <td>1055.0</td>\n",
       "      <td>1432.0</td>\n",
       "      <td>397.0</td>\n",
       "      <td>1645.0</td>\n",
       "      <td>1571.0</td>\n",
       "      <td>...</td>\n",
       "      <td>369.0</td>\n",
       "      <td>426.0</td>\n",
       "      <td>1173.0</td>\n",
       "      <td>310.0</td>\n",
       "      <td>143.0</td>\n",
       "      <td>1363.0</td>\n",
       "      <td>1104.0</td>\n",
       "      <td>815.0</td>\n",
       "      <td>878.0</td>\n",
       "      <td>1192.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>AMASYA</th>\n",
       "      <td>611.0</td>\n",
       "      <td>634.0</td>\n",
       "      <td>590.0</td>\n",
       "      <td>738.0</td>\n",
       "      <td>NaN</td>\n",
       "      <td>334.0</td>\n",
       "      <td>826.0</td>\n",
       "      <td>695.0</td>\n",
       "      <td>932.0</td>\n",
       "      <td>833.0</td>\n",
       "      <td>...</td>\n",
       "      <td>800.0</td>\n",
       "      <td>982.0</td>\n",
       "      <td>435.0</td>\n",
       "      <td>779.0</td>\n",
       "      <td>848.0</td>\n",
       "      <td>625.0</td>\n",
       "      <td>366.0</td>\n",
       "      <td>666.0</td>\n",
       "      <td>629.0</td>\n",
       "      <td>454.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>5 rows × 81 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "          ADANA  ADIYAMAN   AFYON    AĞRI  AMASYA  ANKARA  ANTALYA  ARTVİN  \\\n",
       "İL ADI                                                                       \n",
       "ADANA       NaN     333.0   573.0   965.0   611.0   490.0    558.0  1034.0   \n",
       "ADIYAMAN  333.0       NaN   906.0   648.0   634.0   755.0    891.0   755.0   \n",
       "AFYON     573.0     906.0     NaN  1311.0   590.0   256.0    292.0  1237.0   \n",
       "AĞRI      965.0     648.0  1311.0     NaN   738.0  1055.0   1432.0   397.0   \n",
       "AMASYA    611.0     634.0   590.0   738.0     NaN   334.0    826.0   695.0   \n",
       "\n",
       "           AYDIN  BALIKESİR  ...  BATMAN  ŞIRNAK  BARTIN  ARDAHAN   IĞDIR  \\\n",
       "İL ADI                       ...                                            \n",
       "ADANA      883.0      897.0  ...   618.0   717.0   769.0   1038.0  1068.0   \n",
       "ADIYAMAN  1216.0     1230.0  ...   301.0   480.0  1038.0    759.0   751.0   \n",
       "AFYON      346.0      324.0  ...  1191.0  1290.0   515.0   1346.0  1421.0   \n",
       "AĞRI      1645.0     1571.0  ...   369.0   426.0  1173.0    310.0   143.0   \n",
       "AMASYA     932.0      833.0  ...   800.0   982.0   435.0    779.0   848.0   \n",
       "\n",
       "          YALOVA  KARABÜK  KİLİS  OSMANİYE   DÜZCE  \n",
       "İL ADI                                              \n",
       "ADANA      893.0    701.0  246.0      87.0   722.0  \n",
       "ADIYAMAN  1162.0    970.0  209.0     246.0   991.0  \n",
       "AFYON      341.0    447.0  819.0     660.0   375.0  \n",
       "AĞRI      1363.0   1104.0  815.0     878.0  1192.0  \n",
       "AMASYA     625.0    366.0  666.0     629.0   454.0  \n",
       "\n",
       "[5 rows x 81 columns]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Read the distance matrix from the excel\n",
    "\n",
    "karayollari = pd.read_excel('TR81_KGM.xls', index_col=1)\n",
    "df = karayollari.copy()\n",
    "city_df = df.iloc[:,1:-2]\n",
    "city_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "93938fd8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Check if the matrix is symmetric\n",
    "\n",
    "def check_symmetric(a, rtol=1e-05, atol=1e-08):\n",
    "    import numpy\n",
    "    return numpy.allclose(a, a.T, rtol=rtol, atol=atol)\n",
    "\n",
    "check_symmetric(city_df.values) # False\n",
    "\n",
    "# Matrix is not symmetric"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "140f5a19",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Change city names with city codes.\n",
    "\n",
    "city_names = df.index\n",
    "\n",
    "city_df.index = np.arange(1,82)\n",
    "city_df.columns = np.arange(1,82)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ae7a1873",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Keep record of city_code - city_name pairs\n",
    "\n",
    "city_code_dict = dict(zip(np.arange(1,len(city_names)+1),city_names))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "b2833f53",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Select 82 cities\n",
    "\n",
    "cities = np.arange(1,82)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "4207de79",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "cost = city_df.copy()\n",
    "max_cost = cost.max().max()\n",
    "cost = cost.fillna(100*max_cost)\n",
    "n = len(cities)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "cee0f8e5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "      <th>6</th>\n",
       "      <th>7</th>\n",
       "      <th>8</th>\n",
       "      <th>9</th>\n",
       "      <th>10</th>\n",
       "      <th>...</th>\n",
       "      <th>72</th>\n",
       "      <th>73</th>\n",
       "      <th>74</th>\n",
       "      <th>75</th>\n",
       "      <th>76</th>\n",
       "      <th>77</th>\n",
       "      <th>78</th>\n",
       "      <th>79</th>\n",
       "      <th>80</th>\n",
       "      <th>81</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>204600.0</td>\n",
       "      <td>333.0</td>\n",
       "      <td>573.0</td>\n",
       "      <td>965.0</td>\n",
       "      <td>611.0</td>\n",
       "      <td>490.0</td>\n",
       "      <td>558.0</td>\n",
       "      <td>1034.0</td>\n",
       "      <td>883.0</td>\n",
       "      <td>897.0</td>\n",
       "      <td>...</td>\n",
       "      <td>618.0</td>\n",
       "      <td>717.0</td>\n",
       "      <td>769.0</td>\n",
       "      <td>1038.0</td>\n",
       "      <td>1068.0</td>\n",
       "      <td>893.0</td>\n",
       "      <td>701.0</td>\n",
       "      <td>246.0</td>\n",
       "      <td>87.0</td>\n",
       "      <td>722.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>333.0</td>\n",
       "      <td>204600.0</td>\n",
       "      <td>906.0</td>\n",
       "      <td>648.0</td>\n",
       "      <td>634.0</td>\n",
       "      <td>755.0</td>\n",
       "      <td>891.0</td>\n",
       "      <td>755.0</td>\n",
       "      <td>1216.0</td>\n",
       "      <td>1230.0</td>\n",
       "      <td>...</td>\n",
       "      <td>301.0</td>\n",
       "      <td>480.0</td>\n",
       "      <td>1038.0</td>\n",
       "      <td>759.0</td>\n",
       "      <td>751.0</td>\n",
       "      <td>1162.0</td>\n",
       "      <td>970.0</td>\n",
       "      <td>209.0</td>\n",
       "      <td>246.0</td>\n",
       "      <td>991.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>573.0</td>\n",
       "      <td>906.0</td>\n",
       "      <td>204600.0</td>\n",
       "      <td>1311.0</td>\n",
       "      <td>590.0</td>\n",
       "      <td>256.0</td>\n",
       "      <td>292.0</td>\n",
       "      <td>1237.0</td>\n",
       "      <td>346.0</td>\n",
       "      <td>324.0</td>\n",
       "      <td>...</td>\n",
       "      <td>1191.0</td>\n",
       "      <td>1290.0</td>\n",
       "      <td>515.0</td>\n",
       "      <td>1346.0</td>\n",
       "      <td>1421.0</td>\n",
       "      <td>341.0</td>\n",
       "      <td>447.0</td>\n",
       "      <td>819.0</td>\n",
       "      <td>660.0</td>\n",
       "      <td>375.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>965.0</td>\n",
       "      <td>648.0</td>\n",
       "      <td>1311.0</td>\n",
       "      <td>204600.0</td>\n",
       "      <td>738.0</td>\n",
       "      <td>1055.0</td>\n",
       "      <td>1432.0</td>\n",
       "      <td>397.0</td>\n",
       "      <td>1645.0</td>\n",
       "      <td>1571.0</td>\n",
       "      <td>...</td>\n",
       "      <td>369.0</td>\n",
       "      <td>426.0</td>\n",
       "      <td>1173.0</td>\n",
       "      <td>310.0</td>\n",
       "      <td>143.0</td>\n",
       "      <td>1363.0</td>\n",
       "      <td>1104.0</td>\n",
       "      <td>815.0</td>\n",
       "      <td>878.0</td>\n",
       "      <td>1192.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>611.0</td>\n",
       "      <td>634.0</td>\n",
       "      <td>590.0</td>\n",
       "      <td>738.0</td>\n",
       "      <td>204600.0</td>\n",
       "      <td>334.0</td>\n",
       "      <td>826.0</td>\n",
       "      <td>695.0</td>\n",
       "      <td>932.0</td>\n",
       "      <td>833.0</td>\n",
       "      <td>...</td>\n",
       "      <td>800.0</td>\n",
       "      <td>982.0</td>\n",
       "      <td>435.0</td>\n",
       "      <td>779.0</td>\n",
       "      <td>848.0</td>\n",
       "      <td>625.0</td>\n",
       "      <td>366.0</td>\n",
       "      <td>666.0</td>\n",
       "      <td>629.0</td>\n",
       "      <td>454.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>5 rows × 81 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "         1         2         3         4         5       6       7       8   \\\n",
       "1  204600.0     333.0     573.0     965.0     611.0   490.0   558.0  1034.0   \n",
       "2     333.0  204600.0     906.0     648.0     634.0   755.0   891.0   755.0   \n",
       "3     573.0     906.0  204600.0    1311.0     590.0   256.0   292.0  1237.0   \n",
       "4     965.0     648.0    1311.0  204600.0     738.0  1055.0  1432.0   397.0   \n",
       "5     611.0     634.0     590.0     738.0  204600.0   334.0   826.0   695.0   \n",
       "\n",
       "       9       10  ...      72      73      74      75      76      77  \\\n",
       "1   883.0   897.0  ...   618.0   717.0   769.0  1038.0  1068.0   893.0   \n",
       "2  1216.0  1230.0  ...   301.0   480.0  1038.0   759.0   751.0  1162.0   \n",
       "3   346.0   324.0  ...  1191.0  1290.0   515.0  1346.0  1421.0   341.0   \n",
       "4  1645.0  1571.0  ...   369.0   426.0  1173.0   310.0   143.0  1363.0   \n",
       "5   932.0   833.0  ...   800.0   982.0   435.0   779.0   848.0   625.0   \n",
       "\n",
       "       78     79     80      81  \n",
       "1   701.0  246.0   87.0   722.0  \n",
       "2   970.0  209.0  246.0   991.0  \n",
       "3   447.0  819.0  660.0   375.0  \n",
       "4  1104.0  815.0  878.0  1192.0  \n",
       "5   366.0  666.0  629.0   454.0  \n",
       "\n",
       "[5 rows x 81 columns]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cost.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "id": "3eb66c2d",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Define model objective, variables and constraints\n",
    "\n",
    "prob = LpProblem(name=\"TSP_TR_Problem\", sense=LpMinimize) # It is a minimization problem\n",
    "\n",
    "\n",
    "roads = [(i,j) for i in cities for j in cities] # Arcs (roads) are defined\n",
    "\n",
    "variables = LpVariable.dicts(\"Road\", (cities, cities), 0, 1, LpInteger) # Arc Variables are created\n",
    "\n",
    "nodes = {}\n",
    "\n",
    "for i in cities:  # Order Variables used for DL constraints are created\n",
    "    nodes[i] = LpVariable(f'u{i}', 1, len(cities), LpInteger)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "id": "08579b6b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# The objective function is added to 'prob' first\n",
    "prob += (\n",
    "    lpSum([variables[i][j] * cost.loc[i,j] for (i, j) in roads]),\n",
    "    \"Sum_of_Transporting_Costs\",\n",
    ")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 227,
   "id": "2ced09e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Vehicles should exit from the city exactly once\n",
    "for i in cities:\n",
    "    prob += (lpSum([variables[i][j] for j in cities]) >= 1,\n",
    "             \"Exit_From_City_%s\" %i\n",
    "            )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "id": "c1f0570f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Vehicles should enter the city exactly once\n",
    "for i in cities:\n",
    "    prob += (\n",
    "        lpSum([variables[j][i] for j in cities]) >= 1,\n",
    "        \"Enter_To_City_%s\" % i,\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "id": "23b9384f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# No paired subtours allowed\n",
    "for i in cities:\n",
    "    for j in cities:\n",
    "        prob+= (variables[i][j]+variables[j][i]<=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "id": "552aee90",
   "metadata": {},
   "outputs": [],
   "source": [
    "# # Subtour Constraints\n",
    "# for (i,j) in product(cities, cities):\n",
    "#     if (i!=cities[0]) and (j!=cities[0]):\n",
    "#         prob+=(\n",
    "#         nodes[i] - nodes[j] + (n-1)*variables[i][j] + (n-3)*variables[j][i] <= n-2, f\"{i}_{j}_subtour_constraint\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 231,
   "id": "1d25e05b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Subtours encountered\n",
    "# subtour1=[10,17,22,39,59,34,41,54,77,16,11,26,43,3,64,20,48,9,35,45]\n",
    "#subtour2=[10,17,22,39,59,34,41,14,81,54,77,16,11,26,43,3,64,20,48,9,35,45]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 232,
   "id": "a85bcdc2",
   "metadata": {},
   "outputs": [],
   "source": [
    "subtour1=[10,17,22,39,59,34,41,54,77,16,11,26,43,3,64,20,48,9,35,45]\n",
    "subtour2=[10,17,22,39,59,34,41,14,81,54,77,16,11,26,43,3,64,20,48,9,35,45]\n",
    "subtour3=[10,45,35,9,48,20,7,15,32,64,3,43,26,11,16,77,41,54,34,59,39,22,17]\n",
    "subtour4=[10, 17, 22, 39, 59, 34, 41, 67, 74, 78, 14, 81, 54, 77, 16, 11, 26, 43, 3, 64, 32, 15, 7, 20, 48, 9, 35, 45]\n",
    "subtour_log = [] # Keep the codes of the cities that were previously in a subtour\n",
    "\n",
    "subtours = [subtour1, subtour2, subtour3, subtour4]\n",
    "\n",
    "for subtour in subtours:\n",
    "    for i in subtour:\n",
    "        for j in subtour:      \n",
    "            if i!=j and not ((i in subtour_log) and (j in subtour_log)):\n",
    "                prob += (nodes[i] - nodes[j] + (n-1)*variables[i][j] + (n-3)*variables[j][i] <= n-2, f\"{i}_{j}_subtour_constraint\")\n",
    "    subtour_log.extend(subtour)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cb3b6a23",
   "metadata": {},
   "outputs": [],
   "source": [
    "start = time.time()\n",
    "\n",
    "prob.solve()\n",
    "\n",
    "print(time.time()-start, \"seconds passed\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "74b3d357",
   "metadata": {},
   "outputs": [],
   "source": [
    "LpStatus[prob.status]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 212,
   "id": "c72e2e9e",
   "metadata": {},
   "outputs": [],
   "source": [
    "final_result = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "id": "3f5a0e35",
   "metadata": {},
   "outputs": [],
   "source": [
    "t=0\n",
    "for v in prob.variables():\n",
    "    if v.varValue==1:\n",
    "        final_result.append(v.name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 214,
   "id": "6e0ca7a8",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Road_10_17',\n",
       " 'Road_11_26',\n",
       " 'Road_12_49',\n",
       " 'Road_13_65',\n",
       " 'Road_14_81',\n",
       " 'Road_15_7',\n",
       " 'Road_16_11',\n",
       " 'Road_17_22',\n",
       " 'Road_18_37',\n",
       " 'Road_19_66',\n",
       " 'Road_1_33',\n",
       " 'Road_20_48',\n",
       " 'Road_21_47',\n",
       " 'Road_22_39',\n",
       " 'Road_23_62',\n",
       " 'Road_24_58',\n",
       " 'Road_25_69',\n",
       " 'Road_26_43',\n",
       " 'Road_27_46',\n",
       " 'Road_28_61',\n",
       " 'Road_29_24',\n",
       " 'Road_2_44',\n",
       " 'Road_30_73',\n",
       " 'Road_31_79',\n",
       " 'Road_32_15',\n",
       " 'Road_33_80',\n",
       " 'Road_34_41',\n",
       " 'Road_35_45',\n",
       " 'Road_36_76',\n",
       " 'Road_37_57',\n",
       " 'Road_38_50',\n",
       " 'Road_39_59',\n",
       " 'Road_3_64',\n",
       " 'Road_40_71',\n",
       " 'Road_41_67',\n",
       " 'Road_42_70',\n",
       " 'Road_43_3',\n",
       " 'Road_44_23',\n",
       " 'Road_45_10',\n",
       " 'Road_46_31',\n",
       " 'Road_47_63',\n",
       " 'Road_48_9',\n",
       " 'Road_49_13',\n",
       " 'Road_4_25',\n",
       " 'Road_50_68',\n",
       " 'Road_51_38',\n",
       " 'Road_52_28',\n",
       " 'Road_53_8',\n",
       " 'Road_54_77',\n",
       " 'Road_55_52',\n",
       " 'Road_56_72',\n",
       " 'Road_57_55',\n",
       " 'Road_58_60',\n",
       " 'Road_59_34',\n",
       " 'Road_5_19',\n",
       " 'Road_60_5',\n",
       " 'Road_61_53',\n",
       " 'Road_62_12',\n",
       " 'Road_63_2',\n",
       " 'Road_64_32',\n",
       " 'Road_65_30',\n",
       " 'Road_66_40',\n",
       " 'Road_67_74',\n",
       " 'Road_68_42',\n",
       " 'Road_69_29',\n",
       " 'Road_6_18',\n",
       " 'Road_70_51',\n",
       " 'Road_71_6',\n",
       " 'Road_72_21',\n",
       " 'Road_73_56',\n",
       " 'Road_74_78',\n",
       " 'Road_75_36',\n",
       " 'Road_76_4',\n",
       " 'Road_77_16',\n",
       " 'Road_78_14',\n",
       " 'Road_79_27',\n",
       " 'Road_7_20',\n",
       " 'Road_80_1',\n",
       " 'Road_81_54',\n",
       " 'Road_8_75',\n",
       " 'Road_9_35']"
      ]
     },
     "execution_count": 214,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "final_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 215,
   "id": "022dea4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "source = []\n",
    "destination = []\n",
    "final_pairs = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 216,
   "id": "189f3853",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in final_result:\n",
    "    if len(i)>5:\n",
    "        a, b, c = i.split('_')\n",
    "        source.append(b)\n",
    "        destination.append(c)\n",
    "        \n",
    "for i in final_result:\n",
    "    if len(i)>5:\n",
    "        a, b, c = i.split('_')\n",
    "        final_pairs.append([b,c])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 217,
   "id": "74732fff",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Check if there exist a loop arc\n",
    "\n",
    "for i in range(0,len(source)):\n",
    "    if source[i]==destination[i]:\n",
    "        print('Loop arc exists')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 218,
   "id": "4097dd2a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# of source cities:  81\n",
      "# of destination cities:  81\n"
     ]
    }
   ],
   "source": [
    "print(\"# of source cities: \", len(set(source)))\n",
    "print(\"# of destination cities: \", len(set(destination)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "id": "1683611d",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['10', '17'],\n",
       " ['11', '26'],\n",
       " ['12', '49'],\n",
       " ['13', '65'],\n",
       " ['14', '81'],\n",
       " ['15', '7'],\n",
       " ['16', '11'],\n",
       " ['17', '22'],\n",
       " ['18', '37'],\n",
       " ['19', '66'],\n",
       " ['1', '33'],\n",
       " ['20', '48'],\n",
       " ['21', '47'],\n",
       " ['22', '39'],\n",
       " ['23', '62'],\n",
       " ['24', '58'],\n",
       " ['25', '69'],\n",
       " ['26', '43'],\n",
       " ['27', '46'],\n",
       " ['28', '61'],\n",
       " ['29', '24'],\n",
       " ['2', '44'],\n",
       " ['30', '73'],\n",
       " ['31', '79'],\n",
       " ['32', '15'],\n",
       " ['33', '80'],\n",
       " ['34', '41'],\n",
       " ['35', '45'],\n",
       " ['36', '76'],\n",
       " ['37', '57'],\n",
       " ['38', '50'],\n",
       " ['39', '59'],\n",
       " ['3', '64'],\n",
       " ['40', '71'],\n",
       " ['41', '67'],\n",
       " ['42', '70'],\n",
       " ['43', '3'],\n",
       " ['44', '23'],\n",
       " ['45', '10'],\n",
       " ['46', '31'],\n",
       " ['47', '63'],\n",
       " ['48', '9'],\n",
       " ['49', '13'],\n",
       " ['4', '25'],\n",
       " ['50', '68'],\n",
       " ['51', '38'],\n",
       " ['52', '28'],\n",
       " ['53', '8'],\n",
       " ['54', '77'],\n",
       " ['55', '52'],\n",
       " ['56', '72'],\n",
       " ['57', '55'],\n",
       " ['58', '60'],\n",
       " ['59', '34'],\n",
       " ['5', '19'],\n",
       " ['60', '5'],\n",
       " ['61', '53'],\n",
       " ['62', '12'],\n",
       " ['63', '2'],\n",
       " ['64', '32'],\n",
       " ['65', '30'],\n",
       " ['66', '40'],\n",
       " ['67', '74'],\n",
       " ['68', '42'],\n",
       " ['69', '29'],\n",
       " ['6', '18'],\n",
       " ['70', '51'],\n",
       " ['71', '6'],\n",
       " ['72', '21'],\n",
       " ['73', '56'],\n",
       " ['74', '78'],\n",
       " ['75', '36'],\n",
       " ['76', '4'],\n",
       " ['77', '16'],\n",
       " ['78', '14'],\n",
       " ['79', '27'],\n",
       " ['7', '20'],\n",
       " ['80', '1'],\n",
       " ['81', '54'],\n",
       " ['8', '75'],\n",
       " ['9', '35']]"
      ]
     },
     "execution_count": 219,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "final_pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 220,
   "id": "24de218b",
   "metadata": {},
   "outputs": [],
   "source": [
    "route = ['10']\n",
    "\n",
    "for i in range(0,80):\n",
    "    for j in final_pairs:\n",
    "        if j[0]==route[-1]:\n",
    "            route.append(j[1])\n",
    "            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "id": "cad524d7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "28"
      ]
     },
     "execution_count": 221,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(np.unique(np.array(route))) # Check if len==81. If not, subtour exists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "id": "01b03361",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(['10', '17', '22', '39', '59', '34', '41', '67', '74', '78', '14',\n",
       "       '81', '54', '77', '16', '11', '26', '43', '3', '64', '32', '15',\n",
       "       '7', '20', '48', '9', '35', '45', '10', '17', '22', '39', '59',\n",
       "       '34', '41', '67', '74', '78', '14', '81', '54', '77', '16', '11',\n",
       "       '26', '43', '3', '64', '32', '15', '7', '20', '48', '9', '35',\n",
       "       '45', '10', '17', '22', '39', '59', '34', '41', '67', '74', '78',\n",
       "       '14', '81', '54', '77', '16', '11', '26', '43', '3', '64', '32',\n",
       "       '15', '7', '20', '48'], dtype='<U2')"
      ]
     },
     "execution_count": 222,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.array(route)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "id": "f0f3eaa6",
   "metadata": {},
   "outputs": [],
   "source": [
    "subtour4=[10, 17, 22, 39, 59, 34, 41, 67, 74, 78, 14, 81, 54, 77, 16, 11, 26, 43, 3, 64, 32, 15, 7, 20, 48, 9, 35, 45]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f48fe33c",
   "metadata": {},
   "source": [
    "# Visualization on the map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 252,
   "id": "409d77ea",
   "metadata": {},
   "outputs": [],
   "source": [
    "# api_key\n",
    "api_key = 'AIzaSyAsvARN081dfw2VDq2MaTBPb8PgAc3jiB8'\n",
    "\n",
    "html = 'https://roads.googleapis.com/v1/snapToRoads?path=-35.27801,149.12958|-35.28032,149.12907|-35.28099,149.12929|-35.28144,149.12984|-35.28194,149.13003|-35.28282,149.12956|-35.28302,149.12881|-35.28473,149.12836 &interpolate=true &key=AIzaSyAsvARN081dfw2VDq2MaTBPb8PgAc3jiB8'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 251,
   "id": "cc0fb029",
   "metadata": {},
   "outputs": [],
   "source": [
    "import urllib.request"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1562cb67",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5dbdd3d9",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4202469f",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}