OR_Final_Project.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "id": "__mD1CwP7OEh"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from mip import Model, xsum, minimize, BINARY"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 494
    },
    "id": "JGPdCTHm7bMU",
    "outputId": "fb2f46d7-0763-40e6-a169-c084c3c6ba54"
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "  <div id=\"df-7912322d-4e88-47d1-963e-615d26b5be40\">\n",
       "    <div class=\"colab-df-container\">\n",
       "      <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>Place index</th>\n",
       "      <th>Place Name</th>\n",
       "      <th>Latitude</th>\n",
       "      <th>Longitude</th>\n",
       "      <th>Neighbors_indice</th>\n",
       "      <th>Neighbors_weight</th>\n",
       "      <th>time</th>\n",
       "      <th>distance</th>\n",
       "      <th>traffic</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>Enghelab Square</td>\n",
       "      <td>35.701146</td>\n",
       "      <td>51.391189</td>\n",
       "      <td>2,3</td>\n",
       "      <td>1,3</td>\n",
       "      <td>2,7</td>\n",
       "      <td>0.9,3.2</td>\n",
       "      <td>1,1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>UT Enghelab campus</td>\n",
       "      <td>35.702588</td>\n",
       "      <td>51.395695</td>\n",
       "      <td>1,4</td>\n",
       "      <td>1,4</td>\n",
       "      <td>2,7</td>\n",
       "      <td>0.95,3.5</td>\n",
       "      <td>1,1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>Darvazeh Dowlat Metro Station</td>\n",
       "      <td>35.702173</td>\n",
       "      <td>51.425740</td>\n",
       "      <td>1,5</td>\n",
       "      <td>5,6</td>\n",
       "      <td>7,11</td>\n",
       "      <td>4.1,6</td>\n",
       "      <td>1,0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>UT-Fanni campus</td>\n",
       "      <td>35.724721</td>\n",
       "      <td>51.388642</td>\n",
       "      <td>2,5,6</td>\n",
       "      <td>5,8,5</td>\n",
       "      <td>8,10,5</td>\n",
       "      <td>3.9,7.8,5</td>\n",
       "      <td>1,0,0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>Kasra Hospital</td>\n",
       "      <td>35.739570</td>\n",
       "      <td>51.415285</td>\n",
       "      <td>3,4,7</td>\n",
       "      <td>6,6,6</td>\n",
       "      <td>10,10,10</td>\n",
       "      <td>6.3,5.4,6.6</td>\n",
       "      <td>0,1,0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>Baqiyatallah Hospital</td>\n",
       "      <td>35.757897</td>\n",
       "      <td>51.395250</td>\n",
       "      <td>4,7</td>\n",
       "      <td>4,7</td>\n",
       "      <td>8,10</td>\n",
       "      <td>4.5,6.2</td>\n",
       "      <td>0,1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>Mofid Children's Hospital</td>\n",
       "      <td>35.760837</td>\n",
       "      <td>51.445851</td>\n",
       "      <td>5,6,8</td>\n",
       "      <td>6,10,5</td>\n",
       "      <td>7,8,8</td>\n",
       "      <td>5.8,7.8,4.6</td>\n",
       "      <td>1,1,1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>Gholhak Subway Station</td>\n",
       "      <td>35.773169</td>\n",
       "      <td>51.437945</td>\n",
       "      <td>7,10,9</td>\n",
       "      <td>3,5,9</td>\n",
       "      <td>3,7,13</td>\n",
       "      <td>1.7,5.1,8.6</td>\n",
       "      <td>1,1,0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>Tehran International Exhibition Center</td>\n",
       "      <td>35.792741</td>\n",
       "      <td>51.402764</td>\n",
       "      <td>8</td>\n",
       "      <td>7</td>\n",
       "      <td>10</td>\n",
       "      <td>7.4</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>Ekhtiarie Square</td>\n",
       "      <td>35.787212</td>\n",
       "      <td>51.466496</td>\n",
       "      <td>8</td>\n",
       "      <td>4</td>\n",
       "      <td>9</td>\n",
       "      <td>4</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>\n",
       "      <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-7912322d-4e88-47d1-963e-615d26b5be40')\"\n",
       "              title=\"Convert this dataframe to an interactive table.\"\n",
       "              style=\"display:none;\">\n",
       "        \n",
       "  <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
       "       width=\"24px\">\n",
       "    <path d=\"M0 0h24v24H0V0z\" fill=\"none\"/>\n",
       "    <path d=\"M18.56 5.44l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94zm-11 1L8.5 8.5l.94-2.06 2.06-.94-2.06-.94L8.5 2.5l-.94 2.06-2.06.94zm10 10l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94z\"/><path d=\"M17.41 7.96l-1.37-1.37c-.4-.4-.92-.59-1.43-.59-.52 0-1.04.2-1.43.59L10.3 9.45l-7.72 7.72c-.78.78-.78 2.05 0 2.83L4 21.41c.39.39.9.59 1.41.59.51 0 1.02-.2 1.41-.59l7.78-7.78 2.81-2.81c.8-.78.8-2.07 0-2.86zM5.41 20L4 18.59l7.72-7.72 1.47 1.35L5.41 20z\"/>\n",
       "  </svg>\n",
       "      </button>\n",
       "      \n",
       "  <style>\n",
       "    .colab-df-container {\n",
       "      display:flex;\n",
       "      flex-wrap:wrap;\n",
       "      gap: 12px;\n",
       "    }\n",
       "\n",
       "    .colab-df-convert {\n",
       "      background-color: #E8F0FE;\n",
       "      border: none;\n",
       "      border-radius: 50%;\n",
       "      cursor: pointer;\n",
       "      display: none;\n",
       "      fill: #1967D2;\n",
       "      height: 32px;\n",
       "      padding: 0 0 0 0;\n",
       "      width: 32px;\n",
       "    }\n",
       "\n",
       "    .colab-df-convert:hover {\n",
       "      background-color: #E2EBFA;\n",
       "      box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
       "      fill: #174EA6;\n",
       "    }\n",
       "\n",
       "    [theme=dark] .colab-df-convert {\n",
       "      background-color: #3B4455;\n",
       "      fill: #D2E3FC;\n",
       "    }\n",
       "\n",
       "    [theme=dark] .colab-df-convert:hover {\n",
       "      background-color: #434B5C;\n",
       "      box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
       "      filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
       "      fill: #FFFFFF;\n",
       "    }\n",
       "  </style>\n",
       "\n",
       "      <script>\n",
       "        const buttonEl =\n",
       "          document.querySelector('#df-7912322d-4e88-47d1-963e-615d26b5be40 button.colab-df-convert');\n",
       "        buttonEl.style.display =\n",
       "          google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
       "\n",
       "        async function convertToInteractive(key) {\n",
       "          const element = document.querySelector('#df-7912322d-4e88-47d1-963e-615d26b5be40');\n",
       "          const dataTable =\n",
       "            await google.colab.kernel.invokeFunction('convertToInteractive',\n",
       "                                                     [key], {});\n",
       "          if (!dataTable) return;\n",
       "\n",
       "          const docLinkHtml = 'Like what you see? Visit the ' +\n",
       "            '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
       "            + ' to learn more about interactive tables.';\n",
       "          element.innerHTML = '';\n",
       "          dataTable['output_type'] = 'display_data';\n",
       "          await google.colab.output.renderOutput(dataTable, element);\n",
       "          const docLink = document.createElement('div');\n",
       "          docLink.innerHTML = docLinkHtml;\n",
       "          element.appendChild(docLink);\n",
       "        }\n",
       "      </script>\n",
       "    </div>\n",
       "  </div>\n",
       "  "
      ],
      "text/plain": [
       "   Place index                              Place Name  ...     distance  traffic\n",
       "0            1                         Enghelab Square  ...      0.9,3.2      1,1\n",
       "1            2                      UT Enghelab campus  ...     0.95,3.5      1,1\n",
       "2            3           Darvazeh Dowlat Metro Station  ...        4.1,6      1,0\n",
       "3            4                         UT-Fanni campus  ...    3.9,7.8,5    1,0,0\n",
       "4            5                          Kasra Hospital  ...  6.3,5.4,6.6    0,1,0\n",
       "5            6                   Baqiyatallah Hospital  ...      4.5,6.2      0,1\n",
       "6            7               Mofid Children's Hospital  ...  5.8,7.8,4.6    1,1,1\n",
       "7            8                  Gholhak Subway Station  ...  1.7,5.1,8.6    1,1,0\n",
       "8            9  Tehran International Exhibition Center  ...          7.4        0\n",
       "9           10                        Ekhtiarie Square  ...            4        0\n",
       "\n",
       "[10 rows x 9 columns]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df = pd.read_csv(\"Data.csv\")\n",
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "id": "fafRo-aO_iS8"
   },
   "outputs": [],
   "source": [
    "n = len(df)\n",
    "weights = np.zeros((n, n))\n",
    "for i in range(n):\n",
    "    Neighbors = df['Neighbors_indice'][i].split(\",\")\n",
    "    Neighbors = [int(x) for x in Neighbors]\n",
    "    w = df['Neighbors_weight'][i].split(\",\")\n",
    "    w = [int(x) for x in w]\n",
    "    for idx, nei in enumerate(Neighbors):\n",
    "      weights[i][nei-1] = w[idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "1enPzEozgzsR",
    "outputId": "200ac40a-71c7-49e7-f281-a5154df65abe"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.,  1.,  3.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 1.,  0.,  0.,  4.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  0.,  0.,  0.,  6.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 0.,  5.,  0.,  0.,  8.,  5.,  0.,  0.,  0.,  0.],\n",
       "       [ 0.,  0.,  6.,  6.,  0.,  0.,  6.,  0.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  4.,  0.,  0.,  7.,  0.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  0.,  6., 10.,  0.,  5.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  3.,  0.,  9.,  5.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  7.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  4.,  0.,  0.]])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "id": "FXhunOp94fc8"
   },
   "outputs": [],
   "source": [
    "def get_input(df):\n",
    "    print(\"The names of the places are:\")\n",
    "    print(\"1: Enghelab Square , 2: UT Enghelab campus , 3: Darvazeh Dowlat Metro Station\")\n",
    "    print(\"4: UT-Fanni campus , 5: Kasra Hospital , 6: Baqiyatallah Hospital\")\n",
    "    print(\"7: Mofid Children's Hospital, 8: Gholhak Subway Station\")\n",
    "    print(\"9: Tehran International Exhibition Center, 10: Ekhtiarie Square\")\n",
    "    Starting_Point = input(\"\\nPlease enter the Starting Point name just as same as above names : \")\n",
    "    Destination_Point = input(\"\\nPlease enter the Destination Point name just as same as above names : \")\n",
    "    \n",
    "    start = df[\"Place Name\"].str.find(Starting_Point)\n",
    "    start = list(start)\n",
    "    start = start.index(0)\n",
    "\n",
    "    destination = df[\"Place Name\"].str.find(Destination_Point)\n",
    "    destination = list(destination)\n",
    "    destination = destination.index(0)\n",
    "\n",
    "    print(\"\\nIndex of Starting Point is: %d, and it's coordinate is: %f, %f\" %(start + 1, df[\"Latitude\"][start], df[\"Longitude\"][start]))\n",
    "    print(\"\\nIndex of Destination Point is: %d, and it's coordinate is: %f, %f\" %(destination + 1, df[\"Latitude\"][destination], df[\"Longitude\"][destination]))\n",
    "    return start, destination"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "id": "lb3C8vEvArns"
   },
   "outputs": [],
   "source": [
    "def define_constants(model, V, weights):\n",
    "    for i in V:\n",
    "      for j in V:\n",
    "        if weights[i][j] == 0:\n",
    "          model += x[i][j] == 0\n",
    "\n",
    "    for i in V:\n",
    "        if i == start:\n",
    "          value = 1\n",
    "        elif i == destination:\n",
    "          value = -1\n",
    "        else:\n",
    "          value = 0\n",
    "        model += xsum(x[i][j] for j in V) - xsum(x[j][i] for j in V) == value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "id": "mjC7YUHhBtCE"
   },
   "outputs": [],
   "source": [
    "def print_result(x, weights):\n",
    "    COST = 0\n",
    "    place = start\n",
    "    print(\"\\nOptimal Path is:\")\n",
    "    j = 0\n",
    "    while place != destination:\n",
    "      if x[place][j].x == 1:\n",
    "        COST += weights[place][j]\n",
    "        print(str(place + 1) + \" --> \", end='')\n",
    "        place = j\n",
    "        j = 0\n",
    "      else:\n",
    "        j += 1\n",
    "    print(str(destination + 1))\n",
    "    print(\"\\nThe total cost of the optimal rout is:\", COST)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "hhvvasODkkpN",
    "outputId": "619aa185-3441-4ff8-a9ef-f885d14b0a43"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The names of the places are:\n",
      "1: Enghelab Square , 2: UT Enghelab campus , 3: Darvazeh Dowlat Metro Station\n",
      "4: UT-Fanni campus , 5: Kasra Hospital , 6: Baqiyatallah Hospital\n",
      "7: Mofid Children's Hospital, 8: Gholhak Subway Station\n",
      "9: Tehran International Exhibition Center, 10: Ekhtiarie Square\n",
      "\n",
      "Please enter the Starting Point name just as same as above names : Ekhtiarie Square\n",
      "\n",
      "Please enter the Destination Point name just as same as above names : UT-Fanni campus\n",
      "\n",
      "Index of Starting Point is: 10, and it's coordinate is: 35.787212, 51.466496\n",
      "\n",
      "Index of Destination Point is: 4, and it's coordinate is: 35.724721, 51.388642\n",
      "\n",
      "Optimal Path is:\n",
      "10 --> 8 --> 7 --> 5 --> 4\n",
      "\n",
      "The total cost of the optimal rout is: 19.0\n"
     ]
    }
   ],
   "source": [
    "start, destination = get_input(df)\n",
    "V = set(range(n))\n",
    "model = Model()\n",
    "x = [[model.add_var(var_type=BINARY) for j in V] for i in V]\n",
    "model.objective = minimize(xsum(weights[i][j]*x[i][j] for i in V for j in V))\n",
    "define_constants(model, V, weights)\n",
    "model.optimize()\n",
    "print_result(x, weights)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "OR_Final_Project.ipynb",
   "provenance": []
  },
  "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}