instance_01_generator.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "dedebe5e-1e12-432b-b7f9-c55ee2682634",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "import osmnx as ox\n",
    "import geopandas as gpd\n",
    "import itertools\n",
    "import time\n",
    "import random\n",
    "import ast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "f87346b9-e87f-4129-9f04-54c07495074b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Utils & Functions\n",
    "from utils import *\n",
    "from hrga import *\n",
    "from tndp import *\n",
    "from export import *\n",
    "from plot import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a256fcff-dec6-43a4-910f-c5b3c93b0107",
   "metadata": {},
   "source": [
    "### Graph Structure for Instance 1 (Toy Instance)\n",
    "\n",
    "Example taken from Guan et al. (2006). 9-node network used to test basic functioning of model and restrictions. There is only one possible path from any origin to any destination."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "bc3f7e42-e578-48b4-97ef-7b1e131e8669",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generating Mandl's Network\n",
    "\n",
    "# Create graph\n",
    "G = nx.Graph()\n",
    "\n",
    "# Node Positions\n",
    "node_positions = [(-2, 1), (-2, -1), (-1, 0), (0, 1), (0, 0), (0, -1), (1, 0), (2, 1), (2, -1)]\n",
    "\n",
    "# Add nodes\n",
    "for i in range(9):\n",
    "    G.add_node(i+1, pos=node_positions[i])\n",
    "    \n",
    "\n",
    "    \n",
    "# Add edges\n",
    "edge_list =    [(1, 3), (2, 3), (3, 5), (5, 4), (5, 6), (5, 7), (7, 8), (7, 9)]\n",
    "edge_lengths = [    10,     10,     10,     10,     10,     10,     10,     10]\n",
    "\n",
    "for i in range(len(edge_list)):\n",
    "    G.add_edge(*edge_list[i], length=edge_lengths[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "accebaf9-1864-4ca8-adf4-805882acc92c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjwAAAEeCAYAAACOg886AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAA9oUlEQVR4nO3dZ3hU1d428HvSe4L0ohRBmhQN5IiBTAoJocMIJLTQlCIBDiIPgiCItINUI1KkGISAhEOoIYS0CaAiLYkgQQkgvUgxdUIys94PHvJakjCQsqbcv+uaD8+Zvdd1x/X8k5s9ZSuEECAiIiIyZRayAxARERFVNBYeIiIiMnksPERERGTyWHiIiIjI5LHwEBERkclj4SEiIiKTZ1Xak9WqVRMNGjSopChEREREz+/UqVO/CSGqF/dcqYWnQYMGOHnyZMWkIiIiIipHCoXi15Ke40taREREZPJYeIiIiMjksfAQERGRyWPhISIiIpPHwkNEREQmj4WHiIiITB4LDxEREZk8Fh4iIiIyeSw8REREZPJYeIiIiMjklXprCWOUnZ2N5ORknDp1Cunp6dBoNLCzs0OzZs3g7u4OLy8vODk5yY5JZFY4l0SGyZxm02QKz6VLl7Bs2TJs3rwZWVlZJR7n7OyMkJAQvPfee2jUqFElJiQyP5xLIsNkjrOpEEKU+GS7du2Eod88VKfTISwsDNOnT0deXh4AwMPDA56enmjdujWcnJyQnZ2NtLQ0HDt2DD/88AMAwN7eHgsXLsSECRNgYcFX9ojKE+eSyDCZ+mwqFIpTQoh2xT4phCjx4e7uLgyZRqMRKpVKABAARHBwsEhNTS31nNTUVBEcHFx0jkqlEhqNppISE5k+ziWRYTKH2QRwUpTQaYy28Gi12qKNc3NzE1FRUc90flRUlHB1dS3aQK1WWzFBicwI55LIMJnLbJpk4VmxYkXRxp05c+a51jh9+nTRBq5cubJ8AxKZIc4lkWEyl9k0ucKTkZEh7O3tBQCxe/fufzwfFhYm3N3dhY2NjRg2bFipa0VFRQkAwt7eXmRkZFRQYiLT97S5/LOff/5Z2NraisGDBxf7POeSqPzoM5uXL18WXbt2FW5ubqJmzZpi/PjxoqCg4B/HGfpsllZ4DPedR6VYtmwZ8vLyEBwcjN69e//j+Tp16mDmzJkYOXLkU9fq06cPgoKCkJeXh+XLl1dEXCKz8LS5/LPx48ejffv2JT7PuSQqP/rM5rvvvosaNWrg1q1bSElJgVqtxhdffPGP44x5No2u8GRnZ2Pz5s0AgBkzZhR7jEqlQp8+fVC1alW91nyyTnh4OLKzs8snKJEZ0Wcun9i+fTvc3Nzg5+dX6nGcS6Ky03c2L1++jAEDBsDOzg61atVCYGAgzp07V+yxxjqbRld4kpOTkZWVBQ8PD7Rq1apc1mzdujU8PDyQlZWFI0eOlMuaROZE37nMzMzERx99hKVLlz51Tc4lUdnpO5uTJk3C9u3bkZubixs3buDgwYMIDAws9lhjnU2jKzynTp0CAHh6epbruk/We7I+EelP37mcNWsWRo0ahRdffFGvdTmXRGWj72wqlUqcO3cOLi4uqFevHtq1a4c+ffqUeLwxzqbRFZ709HQAfzTM8vRkvfPnz5frukTmQJ+5TElJQVxcHCZPnqz3upxLorLRZzZ1Oh26dOkClUqFnJwc/Pbbb3j48CGmTZtW4jnGOJtGd2sJjUYDAOV+bw9HR0cAQH5+frmuS2QO9JnLpKQkXLlyBS+99BKAP95boNVq8dNPP+H06dPFnsO5JCobfWbzwYMHuHbtGkJDQ2FrawtbW1uMGDECM2fOxOLFi4s9xxhn0+iu8NjZ2QFAqW+UKiwshEajgVarhVarhUajQWFhYanr5uTkAABsbW3LLyyRmdBnLkePHo2MjAykpKQgJSUFY8eORffu3XHo0KESz+FcEpWNPrNZrVo1NGzYEKtXr0ZhYSEePXqE8PBwtGnTpsRzjHE2ja7wNGvWDACQlpZW4jHz5s2Dvb09Fi1ahC1btsDe3h7z5s0rdd0n6zVv3rz8whKZCX3m0sHBAbVq1Sp6ODk5wc7ODtWrVy/xHM4lUdnoM5sAsGvXLsTExKB69epo3LgxrKysSv3YuTHOptG9pOXu7g4AOHbsWInHzJkzB3PmzHmmdZ+s92R9ItKfPnP5d/rMKOeSqGz0nc22bdsiKSlJ73WNcTaN7m7p2dnZqFOnDrKyspCWllYuH01PS0tDmzZt4OzsjJs3b5b7+4OITB3nksgwmdtslna3dKN7ScvJyQkhISEAgAULFpTLmk/WGTZsmEFtHJGx4FwSGSbO5p+UdM8JYST30nrWO77+naHfF4TIWHAuiQyTOc0mTO1eWo0aNcLChQsBAMOHD0dKSspzrXPmzBkMHz4cALBo0SI0atSonBISmR/OJZFhqlmzJurVqwfAzGezpCYkDPgKjxBCaLVaoVKpBADh6ur6zK01Kiqq6Db3lpaWIj4+vmKCEpmR8pxLlUoltFptxQQlMhOZmZmiU6dOAoCwtbU1+dlEKVd4jLbwCCGERqMp+uUKQAQFBYnU1NRSz0lNTRVBQUFF57z00ktFl+diY2MrKTmR6SqPuVSpVEKj0VRSYiLT9OjRI9GhQwcBQNStW1f8+OOPJj+bpRUeo/uU1t/pdDqEhYVh+vTpyMvLAwB4eHjA09MTrVu3hqOjI3JycpCWloajR4/ixIkTAFD0PT3vvvsuxo0bh/Xr18PW1ha7du1Ct27dZP5IREavrHMZGhoKCwujfMWdyCA8ePAAXbp0wcmTJ1G/fn0kJCSgUaNGJj+bpX1Ky6iv8PxZRkaGCA0NFc7OzkVNtLiHi4uLCA0N/cubrbRarXj33XcFAGFtbV3mN3UR0R/KMpdE9Hzu3bsn2rZtKwCIRo0aiStXrvzjGFOdTZjyFZ6/y87OxpEjR3Dq1CmcP38e+fn5sLW1RfPmzeHu7o5OnToV+zE6IQSmTJmC5cuXw8rKChEREejfv7+En4DI9Px5LmfNmgUAGDRo0FPnkoiezZ07d9C5c2ecPXsWr7zyChISElC3bt0Sj3/ev5mGqrQrPCZXeMpCCIHp06fjP//5DywsLPD1119j0KBBsmMRmRSFQgHgj3kjovJz8+ZN+Pn5IT09HS1atEB8fDxq1aolO1alMqkvHqxICoUCCxcuxEcffQSdTochQ4bgq6++kh2LiIioVNeuXYNSqUR6ejpatWqFxMREsys7T8PC8zcKhQIff/wx5s2bByEERowYgXXr1smORUREVKwrV65AqVTi4sWLeP3115GYmIgaNWrIjmVwWHhK8OGHH+LTTz8FAIwZMwaff/655ERERER/lZGRAS8vL1y+fBkeHh6Ij49H1apVZccySCw8pXj//fexcuVKAMCECROwbNkyyYmIiIj+cOHCBXh5eeHatWt48803cfjwYbi5ucmOZbBYeJ5i4sSJWL16NQBgypQpRV+dT0REJMu5c+egVCpx8+ZNKJVKHDp0CC4uLrJjGTQWHj2MHTsWGzZsgEKhwIwZM/Dxxx/zEyZERCRFamoqvL29iz6CHh0dbVQfHZeFhUdPI0eOxObNm2FhYYE5c+bgww8/ZOkhIqJKderUKfj4+OC3335D165dsW/fPjg4OMiOZRRYeJ7BkCFDEBERAUtLSyxcuBBTp05l6SEiokpx/Phx+Pn54eHDh+jduzeioqJgZ2cnO5bRYOF5RkFBQYiMjIS1tTWWLl2KSZMmsfQQEVGFOnr0KPz9/fH777+jX79+iIyMhK2trexYRoWF5zn07dsXu3btgo2NDcLCwjB27FjodDrZsYiIyAQlJSUhMDAQWVlZGDhwILZt2wZra2vZsYwOC89z6tGjB/bu3Qs7OzusW7cOo0aNglarlR2LiIhMyOHDh9GtWzfk5ORg2LBh+Prrr2FlZSU7llFi4SmDLl264MCBA3BwcMBXX32FkJAQFBYWyo5FREQmIDo6Gj179kReXh7eeecdbNy4EZaWlrJjGS0WnjLy9fVFTEwMnJycEBERgUGDBqGgoEB2LCIiMmJ79uxBnz59kJ+fj/Hjx2PNmjWwsOCf7LLgf71y0KlTJ8TGxsLFxQWRkZEYMGAA8vPzZcciIiIjFBkZiX79+qGgoACTJ09GWFgYy0454H/BctKhQwfExcXBzc0Nu3fvhkqlgkajkR2LiIiMSEREBIKDg1FYWIgPPvgAS5cuhUKhkB3LJLDwlKP27dsjMTERVatWRXR0NHr16oXc3FzZsYiIyAh89dVXGDJkCHQ6HWbPno0FCxaw7JQjFp5y1rZtWyQlJaFGjRo4fPgwunfvjuzsbNmxiIjIgK1btw4jRoyAEALz58/HnDlzWHbKGQtPBXj11VehVqtRu3ZtJCUloWvXrsjMzJQdi4iIDNCqVaswZswYAMCnn36KGTNmSE5kmlh4KkizZs2gVqtRr149HD16FAEBAXj06JHsWEREZECWLVuG0NBQAMDKlSvx/vvvS05kulh4KlCTJk2QnJyM+vXr4/jx4+jcuTMePHggOxYRERmAhQsXYsqUKQCANWvWYOLEiZITmTYWngrWsGFDJCcn4+WXXy66y+29e/dkxyIiIkmEEPj4448xY8YMKBQKbNy4seglLao4LDyV4KWXXoJarUbTpk2RlpYGb29v3L59W3YsIiKqZEIIzJw5E3PmzIGFhQU2b96MESNGyI5lFlh4KkndunWRlJSEFi1a4KeffoK3tzdu3LghOxYREVUSIQSmTp2KBQsWwNLSEhERERgyZIjsWGaDhacS1apVC0lJSWjdujUuXLgApVKJq1evyo5FREQVTAiBSZMmYenSpbC2tkZkZCSCgoJkxzIrLDyVrHr16khISMDrr7+OjIwMKJVKXL58WXYsIiKqIDqdDmPHjkVYWBhsbGywa9cu9O3bV3Yss8PCI0HVqlURHx+Pf/3rX7hy5Qq8vLzwyy+/yI5FRETlTKvVYtSoUVi3bh3s7Oywd+9e9OjRQ3Yss8TCI4mbmxtiY2PRsWNHXL9+HUqlEunp6bJjERFROSksLERISAi++uorODg44MCBA+jSpYvsWGaLhUciFxcXHDx4EN7e3rh16xaUSiXOnj0rOxYREZVRQUEBBg0ahIiICDg5OSEmJga+vr6yY5k1Fh7JnJyccODAAfj7++Pu3bvw9vZGSkqK7FhERPSc8vPzMWDAAERGRsLFxQWxsbHo1KmT7Fhmj4XHADg4OGDv3r3o1q0b7t+/D19fX5w8eVJ2LCIiekYajQYqlQq7d+9GlSpVEB8fjw4dOsiORWDhMRh2dnbYtWsXevfujYcPH8LPzw/fffed7FhERKSn3Nxc9OrVC9HR0ahatSoSEhLQrl072bHof1h4DIitrS0iIyPRv39/ZGZmIiAgAEeOHJEdi4iIniInJwc9evTA4cOHUaNGDSQlJaFt27ayY9GfsPAYGGtra0RERGDQoEHIzs5GYGAgEhISZMciIqISZGZmIjAwEImJiahduzbUajVeffVV2bHob1h4DJCVlRU2b96M4cOHIzc3F927d8ehQ4dkxyIior959OgRAgICcPToUdSrVw9qtRrNmjWTHYuKwcJjoCwtLbFhwwaMHj0aGo0GvXr1wv79+2XHIiKi/3nw4AE6d+6M48ePo379+khOTkaTJk1kx6ISsPAYMAsLC6xZswahoaF4/PgxVCoVoqKiZMciIjJ79+7dg6+vL06dOoWXX34ZycnJaNiwoexYVAoWHgOnUCjw2Wef4b333kNBQQH69++PHTt2yI5FRGS2bt++DR8fH6SmpqJp06ZQq9V46aWXZMeip2DhMQIKhQJLlizB9OnTodVqMXDgQGzZskV2LCIis3Pjxg14e3vj3LlzaNGiBZKSklC3bl3ZsUgPLDxGQqFQYP78+ZgzZw50Oh1CQkKwceNG2bGIiMzG1atXoVQqceHCBbRp0wZJSUmoVauW7FikJxYeI6JQKDB79mwsWLAAQgiMGjUKa9askR2LiMjkXb58GUqlEhkZGXB3d0dCQgKqV68uOxY9AxYeIzR9+nQsXboUADBu3Dh89tlnkhMREZmuixcvwsvLC1euXMG//vUvxMXF4YUXXpAdi54RC4+Reu+99xAWFgYAmDRpEpYsWSI5ERGR6UlPT4eXlxeuX7+Ojh07IjY2Fm5ubrJj0XNg4TFioaGhWLt2LQBg6tSpmD9/vuRERESm4+zZs1Aqlbh16xZ8fHxw8OBBuLi4yI5Fz4mFx8iNHj0aGzduhEKhwMyZMzF79mwIIWTHIiIyaikpKfD29sbdu3fh7++P/fv3w8nJSXYsKgMWHhMwYsQIfP3117CwsMDcuXMxY8YMlh4ioud08uRJ+Pr64v79++jWrRv27t0LBwcH2bGojFh4TMTgwYOxfft2WFlZYdGiRZgyZQpLDxHRM/r+++/h5+eHhw8fonfv3ti1axfs7Oxkx6JywMJjQvr374/IyEhYW1tj+fLlmDBhAnQ6nexYRERG4ciRI/D390dmZmbR71NbW1vZsaicsPCYmD59+iAqKgq2trZYtWoVxowZw9JDRPQUCQkJCAwMRHZ2NgYPHoyIiAhYW1vLjkXliIXHBHXv3h179+6FnZ0d1q9fj5EjR0Kr1cqORURkkA4dOoTu3bsjNzcXw4cPR3h4OKysrGTHonLGwmOiAgICEB0dDQcHB4SHh2Po0KEoLCyUHYuIyKDs378fvXr1gkajwejRo7FhwwZYWlrKjkUVgIXHhPn4+ODQoUNwcnLCtm3bMHDgQBQUFMiORURkEKKioqBSqfD48WOEhoZizZo1sLDgn0VTxZ01cR07dsThw4fh6uqKnTt3ol+/fsjPz5cdi4hIqh07dqB///4oKCjAlClT8Nlnn0GhUMiORRWIhccMvPHGG4iPj0eVKlWwd+9e9O3bF3l5ebJjERFJsWXLFgwcOBBarRbTp0/Hp59+yrJjBlh4zIS7uzsSExNRrVo1HDx4EL169UJubq7sWERElWrjxo0ICQmBTqfDnDlzMH/+fJYdM8HCY0batGmDpKQk1KxZE3FxcejWrRuys7NlxyIiqhRr167FqFGjIITAggULMHv2bJYdM8LCY2ZatmwJtVqNOnXqQK1WIzAwEJmZmbJjERFVqLCwMIwdOxYAsHTpUkyfPl1yIqpsLDxmqGnTplCr1XjxxRdx7Ngx+Pv74+HDh7JjERFViCVLlmDixIkA/ig+7733nuREJAMLj5lq3LgxkpOT0aBBA/zwww/w8/PD/fv3ZcciIipX8+fPx9SpUwH88ZJWaGio5EQkCwuPGWvQoAGSk5PRuHFjnDlzBj4+Prh7967sWEREZSaEwOzZszFz5kwoFAps3LgRo0ePlh2LJGLhMXMvvvgi1Go1mjVrhh9//BE+Pj64deuW7FhERM9NCIEZM2Zg7ty5sLCwwNdff40RI0bIjkWSsfAQ6tSpg6SkJLRs2RI//fQTvL29cePGDdmxiIiemRACU6ZMwaJFi2BlZYXt27dj8ODBsmORAWDhIQBAzZo1kZiYiDZt2uDnn3+Gl5cXfv31V9mxiIj0ptPpMGHCBCxfvhzW1taIjIxE//79ZcciA8HCQ0WqV6+OhIQEtGvXDpcuXYKXlxcuXbokOxYR0VPpdDqMGTMGq1atgq2tLaKiotCnTx/ZsciAsPDQX7zwwguIi4vDG2+8gatXr8LLywu//PKL7FhERCXSarUYOXIk1q9fDzs7O+zduxfdu3eXHYsMDAsP/YOrqytiY2PRsWNH3LhxA15eXjh//rzsWERE/1BYWIiQkBCEh4fDwcEB0dHRCAgIkB2LDBALDxXL2dkZMTEx8PHxwe3bt6FUKvHjjz/KjkVEVKSgoAADBw5EREQEnJ2dcejQIfj4+MiORQaKhYdK5OjoiP379yMgIAD37t2Dj48Pzpw5IzsWERHy8/PRr18/7Ny58y9XpYlKwsJDpXJwcMCePXvQvXt33L9/H76+vjhx4oTsWERkxjQaDfr27Yu9e/eiSpUqiI+PxxtvvCE7Fhk4Fh56Kjs7O+zatQt9+/bFo0eP0LlzZ3z77beyYxGRGcrNzUXPnj1x8OBBVKtWDYmJiXB3d5cdi4wACw/pxcbGBt988w0GDBiAzMxMBAQEIDk5WXYsIjIj2dnZ6N69O+Li4lCzZk0kJSWhTZs2smORkWDhIb1ZW1tj69atGDJkCHJychAYGIj4+HjZsYjIDGRmZiIwMBBJSUmoU6cO1Go1WrZsKTsWGREWHnomVlZW+OqrrzBixAjk5eWhR48eiImJkR2LiEzYw4cP4e/vj2PHjhXd/69p06ayY5GRYeGhZ2ZpaYn169dj7Nix0Gg06N27N/bt2yc7FhGZoPv376Nz58744Ycf0KBBAyQnJ6Nx48ayY5ERYuGh52JhYYEvvvgCEydOxOPHj6FSqbBr1y7ZsYjIhNy9exe+vr44ffo0GjdujOTkZDRo0EB2LDJSLDz03BQKBVasWIH3338fhYWFGDBgALZv3y47FhGZgFu3bsHHxwdpaWlo2rQp1Go1XnzxRdmxyIix8FCZKBQKLF68GB9++CG0Wi0GDx6MzZs3y45FREbsxo0b8Pb2xk8//YSWLVtCrVajTp06smORkWPhoTJTKBSYN28e5s6dC51Oh+HDh2PDhg2yYxGREfr111/h5eWFn3/+GW3atEFiYiJq1qwpOxaZABYeKjezZs3CokWLIITA22+/jdWrV8uORERG5NKlS1Aqlbh06RLatWuHhIQEVK9eXXYsMhEsPFSupk2bhmXLlgEA3n33XaxcuVJyIiIyBr/88guUSiV+/fVXvPHGG4iLi8MLL7wgOxaZEBYeKneTJ0/G559/DgD497//jcWLF0tORESG7Pz58/Dy8sL169fRsWNHxMbGwtXVVXYsMjEsPFQhxo8fj3Xr1kGhUGDatGn45JNPZEciIgP0448/QqlU4vbt2/Dx8UFMTAycnZ1lxyITxMJDFeadd97Bpk2bYGFhgY8++gizZs2CEEJ2LCIyEGfOnIGPjw/u3buHgIAA7N+/H46OjrJjkYli4aEKNWzYMGzZsgWWlpaYN28ePvjgA5YeIsKJEyfg6+uL+/fvo3v37tizZw8cHBxkxyITxsJDFW7gwIHYvn07rKyssHjxYkyePJmlh8iMffvtt+jcuTMePXqEvn37YteuXbCzs5Mdi0wcCw9Vin79+mHnzp2wtrbGypUrMX78eOh0OtmxiKiSJScnIyAgAJmZmRgwYAC++eYb2NjYyI5FZoCFhypN7969sWfPHtja2mL16tUYPXo0tFqt7FhEVEni4+MRGBiInJwcDBkyBFu3boW1tbXsWGQmrGQHIPPStWtX7N+/H7169cKGDRvw+PFjbNq0CZaWlv84Njs7G8nJyTh16hTS09Oh0WhgZ2eHZs2awd3dHV5eXnBycpLwU9Cz+vNePjF48GDupRF63rmMiYlB3759odFoMGLECHz55ZfFzj1RhRFClPhwd3cXRBUhKSlJODo6CgAiODhYPH78uOi5jIwMMX78eOHs7CwAlPhwdnYW48ePFxkZGRJ/EioN99J0lGUv9+7dK2xsbAQAMXbsWKHVaiX+JGTKAJwUJXQahSjlzaPt2rUTJ0+erICaRQQcO3YMXbt2RVZWFlQqFbZu3Yq1a9di+vTpyMvLAwB4eHjA09MTrVu3hpOTE7Kzs5GWloZjx47hhx9+AADY29tj4cKFmDBhAiws+CqtIdDpdAgLC+NemoCy7mXdunUxcOBAFBYWYuLEiVixYgUUCoXMH4lMmEKhOCWEaFfskyU1IcErPFQJvv/+e+Hq6ioAiFq1ahX9KzE4OFikpqaWem5qaqoIDg4uOkelUgmNRlNJyakkGo1GqFQq7qUJKI+9fPJ4//33hU6nq6TkZK5QyhUeFh6S7sSJE8La2loAEG5ubiIqKuqZzo+KiioqTSqVipfLJdJqtUV/ILmXxq0897Jp06aisLCwYoIS/QkLDxm0FStWFP1SPXPmzHOtcfr06aJfritXrizfgKQ37qXp4F6SMWLhIYOVkZEh7O3tBQCxe/fuMq0VFRUlAAh7e3u++VUC7qXp4F6SsSqt8PBdgSTVsmXLkJeXh+DgYPTu3bvYY4YMGYLatWvDxcUFr7zyCtavX1/scX369EFQUBDy8vKwfPnyioxNxdBnL729vWFnZwcnJyc4OTmhadOmxR7HvZRLn718sodPHpaWlpgwYcI/juNeksEoqQkJXuGhCpaVlVX0Ede0tLQSjzt79mzRG1jPnz8vatasKU6ePFnssampqUUfjc3KyqqQ3PRP+u6lUqkUX375pV5rci/l0Hcv/yw7O1s4OjoKtVpd7PPcS6os4BUeMkTJycnIysqCh4cHWrVqVeJxLVu2hK2tLQBAoVBAoVAgIyOj2GNbt24NDw8PZGVl4ciRIxWSm/5J3718FtxLOZ5nL3fu3IkaNWqgU6dOxT7PvSRDwMJD0jz51l1PT8+nHvvuu+/CwcEBzZo1Q+3atdGtW7cSj32y3p+/1Zcq1rPs5fTp01GtWjV4enoiKSmp1GO5l5XvWfbyifDwcISEhJT6/TrcS5KNt5YgadLT0wH88a+/p/niiy8QFhaG7777DklJSUVXfIrzZL1Zs2Zh1qxZ5ROW9PK0vfzPf/6DFi1awMbGBtu3b0fPnj2RkpKCl19+udT1uJeVT5+5BICrV69CrVZjw4YNeq13/vz5Mmcjeh68wkPSaDQaAND7HkqWlpbo2LEjrl+/jtWrV5d4nKOjY7nko2f3tL3817/+BWdnZ9ja2mLYsGHw9PREdHR0icdzL+XRdy43b96Mjh07omHDhqUe92Qv8/Pzy5yN6Hmw8JA0dnZ2AP64GeGzKCwsLPE9PACQk5MDABg0aFCpb8rno/wegwYNeq69VCgUf3w/BvfSYB7PupebN2/GsGHDnnrck70s7eosUUVi4SFpmjVrBgBIS0sr8Zi7d+9i+/btyM7OhlarxaFDh7Bt2zb4+vqWeM6T9Zo3b16+galE+uzlo0ePcOjQIWg0GhQWFmLr1q1ITk5Gly5dSjyHe1n59NnLJ7799lvcuHED/fv3f+qx3EuSje/hIWnc3d0B/HET0ZIoFAqsXr0aY8eOhU6nQ/369bFixYoSvxvkz+s9WZ8qnj57WVBQgJkzZyI9PR2WlpZo1qwZdu/eXeJ38fx5Pe5l5dFnL58IDw+HSqWCs7PzU4/lXpJsvFs6SZOdnY06deogKysLaWlp5fJx5rS0NLRp0wbOzs64efOm3u9DoLLhXpoO7iUZs9Luls6XtEgaJycnhISEAAAWLFhQLms+WWfYsGH8pVqJuJemg3tJJqu0N6/xm5apov35nj3Pejfmv+M9e+TiXpoO7iUZK/CblslQNWrUqOgNj8OHD0dKSspzrXPmzBkMHz4cALBo0SI0atSonBKSvho1aoSFCxcC4F4au4rYy3nz5nEvSa6SmpDgFR6qBOHh4UKhUAgAAoBwdXV95n9RRkVFCVdXVwFAqFQqodVqKyYsPZVWqxUqlYp7aQLKcy8BiICAAJGbm1sxYYn+B6Vc4WHhIWnWr19fVHY++uijol+uAERQUJBITU0t9fzU1FQRFBRUdI5KpSq6ySjJo9FouJcmojz20s/PT1SrVk0AEL6+viI7O7uS0pM5Kq3w8FNaJMUXX3yB8ePHA/jjZYtp06ZBp9MhLCwM06dPR15eHgDAw8MDnp6eaN26NRwdHZGTk4O0tDQcPXoUJ06cAADY29tj0aJFCA0NhYUFX6U1BNxL01Eee5meng4/Pz/cvn0bnTp1woEDB/T6KDvRsyrtU1q8wkOVbvny5UX/+lu2bNk/ns/IyBChoaHC2dm56LjiHi4uLiI0NJRvhDRg3EvTUda9vHDhgqhbt64AIDp06CAePXok6SchUwZe4SFDsXjxYkybNg0AsGrVKrz77rslHpudnY0jR47g1KlTOH/+PPLz82Fra4vmzZvD3d0dnTp14kdcjcSf9/LJTUAHDRrEvTRCZZnLjIwM+Pr64urVq2jfvj0OHTqEKlWqVPJPQKastCs8LDxUaT755BN89NFHUCgUWLduHd5++23ZkUgChUIB4I+ry2R+fv31V/j4+ODy5cto27YtDh8+jGrVqsmORSaCXzxIUgkhMGvWLHz00UewsLDApk2bWHaIzFT9+vWRnJyMJk2aICUlBT4+Prhz547sWGQGWHioQgkhMG3aNMybNw+WlpbYsmWLXndWJiLTVa9ePajVajRv3hxnz56Ft7c3bt68KTsWmTgWHqowQghMnjwZn376KaysrPDNN99g4MCBsmMRkQGoXbs2kpKS0KpVK6Snp0OpVOLatWuyY5EJY+GhCqHT6TB+/HisXLkS1tbW+O9//4u33npLdiwiMiA1atRAYmIiXnvtNVy8eBFKpRJXrlyRHYtMFAsPlTutVovRo0dj9erVsLW1xZ49e9CrVy/ZsYjIAFWtWhXx8fFo3749Ll++DKVSiYyMDNmxyASx8FC5KiwsxIgRI7BhwwbY29tj//796Nq1q+xYRGTAqlSpgsOHD+PNN9/E1atX4eXlhQsXLsiORSaGhYfKTUFBAYYMGYKvv/4ajo6OOHjwIDp37iw7FhEZAVdXV8TExMDLyws3b96EUqnEuXPnZMciE8LCQ+Xi8ePHCAoKwjfffANnZ2ccOnQISqVSdiwiMiLOzs6Ijo6Gn58f7ty5A29vb6SmpsqORSaChYfKLD8/H2+99RaioqLg6uqKuLg4eHp6yo5FREbI0dER+/btQ2BgIH777Tf4+vri9OnTsmORCWDhoTLJy8tD7969sX//frzwwgtISEiAh4eH7FhEZMTs7e2xe/du9OzZEw8ePICvry+OHz8uOxYZORYeem45OTno0aMHDh06hOrVqyMxMRGvv/667FhEZAJsbW2xc+dOvPXWW/j999/h7++Po0ePyo5FRoyFh55LVlYWunbtioSEBNSqVQtJSUlo3bq17FhEZEJsbGywfft2BAcHIysrC4GBgUhKSpIdi4wUCw89s99//x1dunTBkSNHULduXajVarRo0UJ2LCIyQVZWVtiyZQuGDh2KnJwcdOvWDXFxcbJjkRFi4aFn8vDhQ/j7++O7777DSy+9BLVajVdeeUV2LCIyYZaWlti0aRNGjRqFvLw89OjRA9HR0bJjkZFh4SG9PfnExIkTJ9CwYUMkJyfj5Zdflh2LiMyApaUl1q1bh3HjxiE/Px99+vTBnj17ZMciI8LCQ3q5c+cOfHx8kJKSgiZNmiA5ORn169eXHYuIzIiFhQVWrVqFf//73ygoKEC/fv0QGRkpOxYZCRYeeqqbN2/C29sbZ8+eRfPmzaFWq1GvXj3ZsYjIDCkUCixbtgzTpk1DYWEhgoODERERITsWGQEWHirVtWvXoFQqkZ6ejlatWiEpKQm1a9eWHYuIzJhCocDChQsxa9Ys6HQ6DBkyBOHh4bJjkYFj4aESXblyBUqlEhcvXkTbtm2RkJCAGjVqyI5FRASFQoG5c+fik08+gRACI0aMwJdffik7FhkwFh4qVkZGBpRKJS5fvoz27dsjISEB1apVkx2LiOgvZs6cicWLF0MIgdGjR2PVqlWyI5GBYuGhf7hw4QK8vLxw9epVvPnmmzh8+DCqVKkiOxYRUbGmTp2KFStWAABCQ0OxbNkyuYHIILHw0F+cO3cOSqUSN2/ehJeXF2JiYuDq6io7FhFRqSZNmoTVq1cDAKZMmYJFixZJTkSGhoWHiqSmpsLb2xt37tyBn58foqOj4ezsLDsWEZFexo4diw0bNkChUGD69OmYO3cuhBCyY5GBYOEhAMDp06fh6+uL3377DYGBgdi3bx8cHR1lxyIieiYjR45EeHg4LCwsMHv2bMycOZOlhwCw8BCA48ePw9fXFw8ePEDPnj2xe/du2Nvby45FRPRchg4dioiICFhaWmLBggWYOnUqSw+x8Ji7o0ePwt/fH7///jveeust7Ny5E7a2trJjERGVSVBQEHbs2AFra2ssXboUkyZNYukxcyw8ZiwpKQmBgYHIyspCcHAwtm/fDhsbG9mxiIjKhUqlwn//+1/Y2NggLCwM48aNg06nkx2LJGHhMVOHDx9Gt27dkJOTg6FDh2LLli2wsrKSHYuIqFz17NkTe/bsgZ2dHdauXYu3334bWq1WdiySgIXHDEVHR6Nnz57Iy8vDqFGjsGnTJlhaWsqORURUIQIDA7F//37Y29tj06ZNGDZsGAoLC2XHokrGwmNm9uzZgz59+iA/Px/jxo3DunXrWHaIyOT5+fkhJiYGTk5O2Lp1KwYNGoSCggLZsagSsfCYkcjISPTr1w8FBQX497//jVWrVsHCgv8vQETmwcvLC7GxsXBxcUFkZCQGDBiAx48fy45FlYR/7cxEREQEgoODUVhYiP/7v//DsmXLoFAoZMciIqpUHTp0QFxcHNzc3LB7926oVCpoNBrZsagSsPCYgfDwcAwZMgQ6nQ6zZs3CokWLWHaIyGw9uSFy1apVceDAAfTu3Ru5ubmyY1EFY+ExcV9++SVGjBgBIQQ++eQTzJ07l2WHiMzea6+9hsTERNSoUQOxsbHo0aMHcnJyZMeiCsTCY8JWrVqF0aNHQwiBxYsXY+bMmbIjEREZjFatWiEpKQm1a9dGYmJi0feSkWli4TFRy5YtQ2hoKABgxYoVmDp1quRERESGp3nz5lCr1ahXrx6OHj2KgIAAPHr0SHYsqgAsPCZo4cKFmDJlCgDgiy++wKRJkyQnIiIyXE2aNEFycjLq16+P77//Hp07d8aDBw9kx6JyxsJjQoQQ+PjjjzFjxgwoFAqsX78e48aNkx2LiMjgNWzYEGq1Go0aNcKpU6fg6+uLe/fuyY5F5YiFx0QIITBz5kzMmTMHFhYWCA8Px6hRo2THIiIyGvXr10dycjJeeeUVpKamwsfHB7dv35Ydi8oJC48JEEJg6tSpWLBgASwtLREREYGhQ4fKjkVEZHTq1q0LtVqNFi1a4Ny5c/D29sbNmzdlx6JywMJj5IQQmDRpEpYuXQorKyvs2LEDQUFBsmMRERmtWrVqISkpCa1bt8aFCxegVCpx7do12bGojFh4jJhOp8O4ceMQFhYGGxsb7Nq1CyqVSnYsIiKjV716dSQkJOD111/HxYsX4eXlhcuXL8uORWXAwmOktFot3n77baxduxZ2dnbYs2cPevbsKTsWEZHJqFq1KuLj4+Hh4YErV65AqVTi4sWLsmPRc2LhMUKFhYUYNmwYNm3aBHt7e+zfvx+BgYGyYxERmRw3NzccPnwYnp6euHbtGry8vJCeni47Fj0HFh4jU1BQgEGDBmHr1q1wcnJCTEwM/Pz8ZMciIjJZLi4uiImJgbe3N27dugWlUomzZ8/KjkXPiIXHiOTn52PAgAGIjIyEi4sLDh06BC8vL9mxiIhMnpOTEw4cOIDOnTvj7t278PHxQWpqquxY9AxYeIyERqPBW2+9hd27d8PNzQ1xcXF48803ZcciIjIbDg4O2LdvH7p27YrffvsNPj4+OHnypOxYpCcWHiOQm5uL3r1748CBA6hatSoSEhLQvn172bGIiMyOnZ0doqKi0Lt3bzx8+BB+fn74/vvvZcciPbDwGLicnBz06NEDsbGxqFGjBhITE/Haa6/JjkVEZLZsbW0RGRmJfv36ITMzE/7+/jh69KjsWPQULDwGLDMzE4GBgUhMTETt2rWRlJSEVq1ayY5FRGT2rK2tsW3bNgwaNAjZ2dno0qULEhMTZceiUrDwGKhHjx4hICAAR48eRb169aBWq9G8eXPZsYiI6H+srKywefNmDBs2DLm5uejWrRtiY2Nlx6ISsPAYoAcPHqBz5844fvw46tevD7VajSZNmsiORUREf2NpaYmNGzfinXfegUajQc+ePXHgwAHZsagYLDwG5t69e/D19cWpU6fQqFEjqNVqNGrUSHYsIiIqgYWFBdasWYPx48fj8ePH6Nu3L6KiomTHor9h4TEgt2/fLvpuh1deeQXJycmoX7++7FhERPQUFhYWCAsLw3vvvYeCggL0798fO3bskB2L/oSFx0DcuHED3t7eOHfuHFq0aAG1Wo26devKjkVERHpSKBRYsmQJPvjgA2i1WgwcOBBbt26VHYv+h4XHAFy9ehVKpRIXLlxAq1atkJiYiFq1asmORUREz0ihUGDBggWYPXs2dDodhg4dik2bNsmORWDhke7y5ctQKpXIyMjA66+/jsTERNSoUUN2LCIiek4KhQJz5szB/PnzIYTAyJEjsXbtWtmxzB4Lj0QXL16EUqnElStX4OHhgfj4eFStWlV2LCIiKgczZszAkiVLAABjx45FWFiY5ETmjYVHkvT0dHh5eeHatWvw9PTE4cOH4ebmJjsWERGVoylTpuCzzz4DAEycOBFLly6VnMh8sfBIcPbsWSiVSty6dQtKpRIxMTFwcXGRHYuIiCrAhAkTsGbNGgDA+++/jwULFkhOZJ5YeCpZSkoKvL29cffuXXTu3BnR0dFwcnKSHYuIiCrQmDFjsHHjRigUCnz44YeYM2cOhBCyY5kVFp5KdPLkSfj6+uL+/fvo2rUr9u3bBwcHB9mxiIioEowYMQKbN2+GhYUFPv74Y8yYMYOlpxKx8FSS77//Hn5+fnj48CF69+6NqKgo2NnZyY5FRESVaMiQIdi2bRssLS2xaNEivP/++yw9lYSFpxIcOXIE/v7+yMzMRL9+/RAZGQlbW1vZsYiISIIBAwZg586dsLa2xrJlyzBx4kTodDrZsUweC08FS0hIQGBgILKzszFo0CBs27YN1tbWsmMREZFEffr0QVRUFGxsbPD5559j7NixLD0VjIWnAh06dAjdu3dHbm4uhg0bhs2bN8PKykp2LCIiMgDdu3fHvn37YGdnhy+//BIjR46EVquVHctksfBUkP3796NXr17QaDR45513sHHjRlhaWsqORUREBiQgIAAHDhyAg4MDwsPDERISgsLCQtmxTBILTwWIioqCSqXC48ePMX78eKxZswYWFvxPTURE/+Tr64uYmBg4OTkhIiICAwcOREFBgexYJod/hcvZjh070L9/fxQUFGDy5MkICwtj2SEiolJ16tQJhw8fhouLC3bu3In+/fsjPz9fdiyTwr/E5WjLli0YOHAgtFotPvjgAyxduhQKhUJ2LCIiMgJvvPEG4uPjUaVKFezZswcqlQoajUZ2LJPBwlNONm3ahJCQEOh0OsyePRsLFixg2SEiomfSrl07JCQkoFq1aoiOjkbPnj2Rm5srO5ZJYOEpB2vXrsXIkSMhhMD8+fMxZ84clh0iInoubdu2RWJiImrWrIm4uDh0794d2dnZsmMZPRaeMgoLC8PYsWMBAEuWLMGMGTMkJyIiImP36quvIikpCbVr10ZSUhICAwORmZkpO5ZRY+EpgyVLlmDixIkAgM8++wxTpkyRnIiIiExFs2bNkJycjBdffBHHjh1DQEAAHj16JDuW0WLheU7z58/H1KlTAQBr1qzBhAkTJCciIiJT07hxY6jVajRo0ADHjx+Hn58f7t+/LzuWUWLheUZCCMyePRszZ86EQqHAxo0bMWbMGNmxiIjIRDVs2BBqtRovv/wyTp8+DV9fX9y9e1d2LKPDwvMMhBCYMWMG5s6dCwsLC2zevBkjRoyQHYuIiEzcSy+9hOTkZDRt2hRpaWnw8fHB7du3ZccyKiw8ehJCYMqUKVi0aBEsLS2xbds2DBkyRHYsIiIyE3Xq1IFarUbLli3x008/QalU4saNG7JjGQ0WHj3odDpMmDABy5cvh7W1NSIjIzFgwADZsYiIyMzUrFkTiYmJaNOmDX7++WcolUpcvXpVdiyjwMLzFDqdDmPGjMGqVatgY2ODXbt2oW/fvrJjERGRmapevToSEhLg7u6OjIwMeHl54dKlS7JjGTwWnlJotVqMHDkS69evh52dHfbt24cePXrIjkVERGbuhRdeQFxcHN544w38+uuvUCqV+OWXX2THMmgsPCUoLCxESEgIwsPD4eDggAMHDiAgIEB2LCIiIgCAm5sbYmNj0bFjR1y/fh1KpRLnz5+XHctgsfAUo6CgAAMHDkRERAScnJwQExMDX19f2bGIiIj+wtnZGTExMfDx8cGtW7fg7e2Ns2fPyo5lkFh4/iY/Px/9+vXDzp074eLigtjYWHTq1El2LCIiomI5Ojpi//798Pf3x927d+Ht7Y0zZ87IjmVwWHj+JC8vD3379sXevXtRpUoVxMfHo0OHDrJjERERlcrBwQF79+5F9+7dcf/+ffj6+uLEiROyYxkUFp7/yc3NRa9evXDw4EFUq1YNCQkJaNeunexYREREerGzs8OuXbvQp08fPHr0CJ07d8a3334rO5bBsJIdoLxlZ2cjOTkZp06dQnp6OjQaDezs7NCsWTO4u7vDy8sLTk5O/zinZ8+eSEpKQs2aNREXF4dXX31V0k9AZHr+PJdPDB48uNS5JKJnZ2Njgx07dmDIkCHYsWMHunTpggMHDsDLy6vY45/nb6bREkKU+HB3dxfGIiMjQ4wfP144OzsLACU+nJ2dxfjx40VGRoYQQojff/9deHp6CgCidu3a4vz585J/EiLT8bxzSURlU1BQIAYPHiwACAcHBxEXF/eX5011NgGcFCV0GsUfzxevXbt24uTJkxVQs8qPTqdDWFgYpk+fjry8PACAh4cHPD090bp1azg5OSE7OxtpaWk4duwYfvjhBwCAvb09Zs2ahaioKJw4cQL16tVDQkICmjRpIvPHITIJZZnLhQsXYsKECbCw4CvuRGWh1Wrx9ttv46uvvoKdnR12794Nf39/k55NhUJxSghR/PtRSmpCwgiu8Gg0GqFSqYqaaHBwsEhNTS31nNTUVBEcHPyXBlu/fn1x6dKlSkpNZNrKYy5VKpXQaDSVlJjIdGm1WjFmzBgBQFhbW4sOHTqY9GyilCs8Rlt4tFpt0S9VNzc3ERUV9UznR0VFCVdXVwFABAYGCq1WWzFBicxIec6lSqXiXBKVA51OJ0JDQ4tKiynPpkkWnhUrVhRt3JkzZ55rjdOnTxdt4MqVK8s3IJEZ4lwSGably5ebxWyaXOHJyMgQ9vb2AoDYvXt3mdaKiooSAIS9vb3RvCmLyBBxLokMkznNZmmFx3DfeVSKZcuWIS8vD8HBwejdu/c/ns/Pz8eoUaNQv359ODs747XXXsPBgweLXatPnz4ICgpCXl4eli9fXtHRiUzW0+byie3bt6N58+ZwdHTEyy+/jCNHjvzjGM4lUfnRZzbPnz8PX19fuLq6onHjxoiKiir2OKOezZKakDDQKzxZWVlFH6NLS0sr9pjs7Gwxe/ZscfnyZaHVasW+ffuEk5OTuHz5crHHp6amFn38LisrqwLTE5kmfeZSCCFiY2PFSy+9JL777juh1WrF9evXxfXr14s9lnNJVHb6zGZBQYFo0qSJWLp0qSgsLBTx8fHCwcFBXLhwodjjDXk2YUovaR04cEAAEB4eHs90XqtWrcTOnTtLfN7Dw0MAENHR0WWNSGR29J3LDh06iPXr1+u9LueSqGz0mc0ff/xRODo6Cp1OV/S/+fv7i5kzZ5Z4jqHOZmmFx+he0nryTa2enp56n3Pnzh38/PPPaNmyZYnHPFnvz98ES0T60WcutVotTp48iXv37qFx48aoV68eQkNDi74LpDicS6Ky0Wc2RTHfxyeEKPWu68Y4m0ZXeNLT0wEArVu31uv4goICDB48GMOGDUOzZs1KPO7JeufPny97SCIzo89c3rlzBwUFBdi5cyeOHDmClJQUnDlzBvPmzSvxHM4lUdnoM5vNmjVDjRo18Omnn6KgoACxsbFQq9XIzc0t8RxjnE2jKzwajQYA9Lq3h06nw9ChQ2FjY4PPP/+81GMdHR0B/PGGZyJ6NvrMpb29PQBgwoQJqF27NqpVq4b33nsP0dHRJZ7DuSQqG31m09raGrt378aBAwdQq1YtLF26FAMGDEC9evVKPMcYZ9Pobh5qZ2cH4I8bnpVGCIFRo0bhzp07iI6OhrW1danH5+TkAABsbW3LJyiRGdFnLqtUqYJ69epBoVDovS7nkqhs9P2b2bp1a6jV6qL/+80338SwYcNKPN4YZ9PorvA8eVkqLS2t1OPGjRuH8+fPY9++fUX/sizNk/WaN29e9pBEZkbfuRwxYgTCwsJw9+5dPHz4ECtWrECPHj1KPJ5zSVQ2+s5mWloaNBoNcnNzsWTJEty6dQvDhw8v9XjAuGbT6AqPu7s7AODYsWMlHvPrr79i7dq1SElJQa1ateDk5AQnJyds3bq1xHOerPdkfSLSnz5zCQCzZs1C+/bt8corr6B58+Z47bXX8OGHH5Z4POeSqGz0nc2vv/4atWvXRo0aNRAfH4/Dhw+XevXGGGfT6O6Wnp2djTp16iArKwtpaWlo1apVmddMS0tDmzZt4OzsjJs3b+r1/iAi+v84l0SGydxms7S7pRvdFR4nJyeEhIQAABYsWFAuaz5ZZ9iwYQa1cUTGgnNJZJg4m39S0hf0CAP94kEh/npfkGe94+vfGfp9QYiMBeeSyDCZ02zClL54EAAaNWqEhQsXAgCGDx+OlJSU51rnzJkzRW/KWrRoERo1alROCYnMD+eSyDBxNv+npCYkDPgKjxBCaLVaoVKpBADh6ur6zK01Kiqq6Db3KpVKaLXaiglKZEY4l0SGyVxmE6Z0L60/02g0RRsIQAQFBYnU1NRSz0lNTRVBQUFF56hUKqHRaCopMZHp41wSGSZzmM3SCo/RfUrr73Q6HcLCwjB9+vSie/J4eHjA09MTrVu3hqOjI3JycpCWloajR4/ixIkTAP741tdFixYhNDQUFhZG+coekcHiXBIZJlOfzdI+pWX0heeJS5cuYfny5QgPD0dWVlaJx7m4uCAkJASTJ082vtcfiYwM55LIMJnqbJpF4XkiOzsbR44cwalTp3D+/Hnk5+fD1tYWzZs3h7u7Ozp16mRcH6MjMgGcSyLDZGqzaVaFh4iIiMyTSX3xIBEREdGzYuEhIiIik8fCQ0RERCaPhYeIiIhMHgsPERERmTwWHiIiIjJ5LDxERERk8lh4iIiIyOSx8BAREZHJY+EhIiIik1fqrSUUCsU9AL9WXhwiIiKi51ZfCFG9uCdKLTxEREREpoAvaREREZHJY+EhIiIik8fCQ0RERCaPhYeIiIhMHgsPERERmbz/B3l+nqshDYoVAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 720x360 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Plot Graph\n",
    "f, ax = plt.subplots(figsize=(10, 5))\n",
    "\n",
    "pos = nx.get_node_attributes(G, 'pos')\n",
    "\n",
    "node_plot = nx.draw_networkx_nodes(G, pos, node_color='white', node_size=500)\n",
    "edges_plot = nx.draw_networkx_edges(G, pos, width=2)\n",
    "labels_plot = nx.draw_networkx_labels(G, pos)\n",
    "\n",
    "# Change border\n",
    "node_plot.set_edgecolor('k')\n",
    "node_plot.set_linewidth(2)\n",
    "\n",
    "# Display\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93248f10-2b87-4a2a-b821-9e6ec7f50a5a",
   "metadata": {},
   "source": [
    "#### Generating All Possible Routes\n",
    "\n",
    "Generate all possible routes by enumerating shortest paths from any origin $i$ to any destination $j$. In a more realistic set, we would consider the $k$ shortest paths. This graph, however, has only 1 possible path from any origin to any destination."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "50d26d01-3fa4-4649-b292-934b841ad6be",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize List\n",
    "routes = []\n",
    "\n",
    "# Iterate\n",
    "for origin in list(G.nodes()):\n",
    "    for destination in list(G.nodes()):\n",
    "        \n",
    "        # If origin is not destination...\n",
    "        if origin != destination:\n",
    "             routes.append(nx.shortest_path(G, origin, destination, weight='length'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "352b0148-0f6c-44f5-81e1-6f05c9afe942",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of feasible routes (after removing simetrical routes): 36\n"
     ]
    }
   ],
   "source": [
    "# Apply function\n",
    "unique = unique_routes(routes)\n",
    "print(f'Number of feasible routes (after removing simetrical routes): {len(unique)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2971ee7b-142d-49e5-abf6-df1e20597989",
   "metadata": {},
   "source": [
    "#### Generate Demand Matrix\n",
    "\n",
    "Generate a demand matrix for all OD pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a5232389-90ed-4510-a6f9-8f11800268bc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 5 5 5 5 5 5 5 5]\n",
      " [5 0 5 5 5 5 5 5 5]\n",
      " [5 5 0 5 5 5 5 5 5]\n",
      " [5 5 5 0 5 5 5 5 5]\n",
      " [5 5 5 5 0 5 5 5 5]\n",
      " [5 5 5 5 5 0 5 5 5]\n",
      " [5 5 5 5 5 5 0 5 5]\n",
      " [5 5 5 5 5 5 5 0 5]\n",
      " [5 5 5 5 5 5 5 5 0]]\n"
     ]
    }
   ],
   "source": [
    "# Initialize matrix with full demand\n",
    "demand_matrix = np.full((len(G.nodes()), len(G.nodes())), 5)\n",
    "\n",
    "# Remove diagonal\n",
    "np.fill_diagonal(demand_matrix, 0)\n",
    "\n",
    "# Print\n",
    "print(demand_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa895a30-61c8-4da1-b40b-aa72aa129114",
   "metadata": {},
   "source": [
    "#### Generate $\\Delta$ Matrix\n",
    "\n",
    "Generate $\\Delta_{er}$ matrix. This matrix tells if edge $e \\in E$ is part of route $r \\in R$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "fcdb88cd-9a07-4bf4-9fd1-2a4e11186ad1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DELTA Matrix: \n",
      "\n",
      "[[1 1 0 0 0 0 0 0]\n",
      " [1 0 0 0 0 0 0 0]\n",
      " [1 0 1 1 0 0 0 0]\n",
      " [1 0 1 0 0 0 0 0]\n",
      " [1 0 1 0 1 0 0 0]\n",
      " [1 0 1 0 0 1 0 0]\n",
      " [1 0 1 0 0 1 1 0]\n",
      " [1 0 1 0 0 1 0 1]\n",
      " [0 1 0 0 0 0 0 0]\n",
      " [0 1 1 1 0 0 0 0]\n",
      " [0 1 1 0 0 0 0 0]\n",
      " [0 1 1 0 1 0 0 0]\n",
      " [0 1 1 0 0 1 0 0]\n",
      " [0 1 1 0 0 1 1 0]\n",
      " [0 1 1 0 0 1 0 1]\n",
      " [0 0 1 1 0 0 0 0]\n",
      " [0 0 1 0 0 0 0 0]\n",
      " [0 0 1 0 1 0 0 0]\n",
      " [0 0 1 0 0 1 0 0]\n",
      " [0 0 1 0 0 1 1 0]\n",
      " [0 0 1 0 0 1 0 1]\n",
      " [0 0 0 1 0 0 0 0]\n",
      " [0 0 0 1 1 0 0 0]\n",
      " [0 0 0 1 0 1 0 0]\n",
      " [0 0 0 1 0 1 1 0]\n",
      " [0 0 0 1 0 1 0 1]\n",
      " [0 0 0 0 1 0 0 0]\n",
      " [0 0 0 0 0 1 0 0]\n",
      " [0 0 0 0 0 1 1 0]\n",
      " [0 0 0 0 0 1 0 1]\n",
      " [0 0 0 0 1 1 0 0]\n",
      " [0 0 0 0 1 1 1 0]\n",
      " [0 0 0 0 1 1 0 1]\n",
      " [0 0 0 0 0 0 1 0]\n",
      " [0 0 0 0 0 0 0 1]\n",
      " [0 0 0 0 0 0 1 1]]\n"
     ]
    }
   ],
   "source": [
    "DELTA = generate_DELTA_matrix(G, routes)\n",
    "print(f'DELTA Matrix: \\n')\n",
    "print(DELTA)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfe3790e-4bcb-4360-a177-39fffcda5c83",
   "metadata": {},
   "source": [
    "#### Enumerate Paths\n",
    "\n",
    "Since we are working with a small instance and all origin-destination pairs have only one possible path, we are going to enumerate all possible paths from all origins and all destinations. If we were working with an instance that allowed for multiple paths, we would calculate the $k$ shortest paths from any origin to any destination.\n",
    "\n",
    "Since there is only one path from any origin to any destination, the set of possible paths is identical to the set of routes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "ed210a00-c325-463a-87f4-5e14b1be381a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate OD Pairs List\n",
    "od_pairs = generate_od_pair_list(G, demand_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "5790e7bb-407d-4d10-9bda-5cac35aeaa26",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate Paths\n",
    "paths, num_paths = generate_paths(G, od_pairs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17c4f953-ac03-452c-bf37-9b6223e72762",
   "metadata": {},
   "source": [
    "#### Generate $\\delta$ Tensor\n",
    "\n",
    "The $\\delta_{ep}^{od}$ tensor indicates if the edge $e$ is used on path $p$ chosen from origin $o$ to destination $d$. It allows for the coupling of routes and paths in the optimization model.\n",
    "\n",
    "This matrix has shape $[od][k][e]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "90af4439-35bf-4712-8756-12854652097a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate Matrix\n",
    "delta = generate_delta_matrix(G, od_pairs, num_paths, paths)\n",
    "#delta"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04f206c2-2b3b-4697-90b4-6ee93a651a62",
   "metadata": {},
   "source": [
    "#### Generate Outputs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "d051a5ad-395a-43de-916a-a1da9897d567",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Nodes\n",
    "node_ids = list(G.nodes())\n",
    "node_x = [G.nodes[node]['pos'][0] for node in G.nodes()]\n",
    "node_y = [G.nodes[node]['pos'][1] for node in G.nodes()]\n",
    "\n",
    "\n",
    "# Data\n",
    "node_data = {\n",
    "    'id' : node_ids,\n",
    "    'x' : node_x,\n",
    "    'y' : node_y,\n",
    "}\n",
    "\n",
    "# Dataframe\n",
    "nodes_df = pd.DataFrame(data=node_data)\n",
    "\n",
    "# Print\n",
    "#nodes_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "8d3a4534-bee9-4f03-9b37-3ac115fffaf1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Edges\n",
    "edge_ids = [id + 1  for id in range(len(G.edges()))]\n",
    "edge_origins = [u for u, v in G.edges()]\n",
    "edge_destinations = [v for u, v in G.edges()]\n",
    "edge_lengths = [G[u][v]['length'] for u, v in G.edges()]\n",
    "edge_travel_time = [G[u][v]['length'] for u, v in G.edges()]\n",
    "edge_capacity = [10 for edge in range(len(G.edges()))]\n",
    "\n",
    "# Data\n",
    "edge_data = {\n",
    "    'id' : edge_ids,\n",
    "    'origin' : edge_origins,\n",
    "    'destination' : edge_destinations,\n",
    "    'length' : edge_lengths,\n",
    "    'travel_time' : edge_travel_time,\n",
    "    'capacity' : edge_capacity\n",
    "}\n",
    "\n",
    "# Dataframe\n",
    "edges_df = pd.DataFrame(data=edge_data)\n",
    "\n",
    "# Print\n",
    "#edges_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "7364770a-17c2-480f-bc3c-a45df69eb8bd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# OD Matrix\n",
    "od_ids = [id + 1 for id in range(len(od_pairs))]\n",
    "od_origin = [int(od.split('-')[0]) for od in od_pairs]\n",
    "od_destination = [int(od.split('-')[1]) for od in od_pairs]\n",
    "od_demand = [demand_matrix[int(od.split('-')[0]) - 1][int(od.split('-')[1]) - 1] for od in od_pairs]\n",
    "od_paths = [num_paths[od] for od in od_pairs]\n",
    "\n",
    "# Data\n",
    "od_data = {\n",
    "    'id' : od_ids,\n",
    "    'origin' : od_origin,\n",
    "    'destination' : od_destination,\n",
    "    'demand' : od_demand,\n",
    "    'paths' : od_paths\n",
    "}\n",
    "\n",
    "# Dataframe\n",
    "od_df = pd.DataFrame(data=od_data)\n",
    "#od_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "faf7bf94-a2d3-43fb-9c67-e98365f08316",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Routes\n",
    "route_ids = [id + 1 for id in range(len(routes))]\n",
    "route_sequences = [str(sequence) for sequence in routes]\n",
    "route_length = [nx.path_weight(G, route, weight='length') for route in routes]\n",
    "route_stops = [len(route) for route in routes]\n",
    "\n",
    "# Data\n",
    "route_data = {\n",
    "    'id' : route_ids,\n",
    "    'sequence' : route_sequences,\n",
    "    'length' : route_length,\n",
    "    'num_stops' : route_stops\n",
    "}\n",
    "\n",
    "route_df = pd.DataFrame(data=route_data)\n",
    "#route_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "cec231d2-0dc9-43f1-abaa-cfa724dffd59",
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 10\n",
    "\n",
    "# Paths\n",
    "paths_id = [id + 1 for id in range(len(paths) * k)]\n",
    "paths_sequence = [str(paths[od][i]) if i < len(paths[od]) else '' for od in paths for i in range(k)]\n",
    "paths_length = [nx.path_weight(G, paths[od][i], weight='length') if i < len(paths[od]) else 0 for od in paths for i in range(k)]\n",
    "paths_stops = [len(paths[od][i]) if i < len(paths[od]) else 0 for od in paths for i in range(k)]\n",
    "\n",
    "# Data\n",
    "paths_data = {\n",
    "    'id' : paths_id,\n",
    "    'sequence' : paths_sequence,\n",
    "    'length' : paths_length,\n",
    "    'num_stops' : paths_stops\n",
    "}\n",
    "\n",
    "paths_df = pd.DataFrame(data=paths_data)\n",
    "#paths_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "25a61be5-84ca-498a-b217-9a539ded182a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# DELTA Matrix\n",
    "DELTA_value = [edge for route in DELTA for edge in route]\n",
    "edge_ids = [id + 1 for id in range(len(G.edges()))] * len(routes)\n",
    "route_ids = [id + 1 for id in range(len(routes)) for i in range(len(G.edges()))]\n",
    "\n",
    "# Data\n",
    "DELTA_data = {\n",
    "    'route_id' : route_ids,\n",
    "    'edge_id' : edge_ids,    \n",
    "    'DELTA' : DELTA_value\n",
    "}\n",
    "\n",
    "# Dataframe\n",
    "DELTA_df = pd.DataFrame(data=DELTA_data)\n",
    "#DELTA_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "e991d331-c2b0-4393-ad8c-90c067df22c2",
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 10\n",
    "\n",
    "# delta Matrix\n",
    "delta_value = [edge for od in delta for path in od for edge in path]\n",
    "od_ids = [id + 1 for id in range(len(od_pairs)) for i in range(k) for j in range(len(G.edges()))]\n",
    "path_ids = [id + 1 for id in range(k) for edge in range(len(G.edges()))] * len(od_pairs)\n",
    "edge_ids = [id + 1 for id in range(len(G.edges()))] * k * len(od_pairs)\n",
    "\n",
    "od_origins = [int(od_pairs[id].split('-')[0]) for id in range(len(od_pairs)) for i in range(k) for j in range(len(G.edges()))]\n",
    "od_destinations = [int(od_pairs[id].split('-')[1]) for id in range(len(od_pairs)) for i in range(k) for j in range(len(G.edges()))]\n",
    "\n",
    "# Data\n",
    "delta_data = {\n",
    "    'od' : od_ids,\n",
    "    'path' : path_ids,\n",
    "    'edge' : edge_ids,\n",
    "    'delta' : delta_value,\n",
    "    'origin' : od_origins,\n",
    "    'destination' : od_destinations\n",
    "}\n",
    "\n",
    "# DataFrame\n",
    "delta_df = pd.DataFrame(data=delta_data)\n",
    "#delta_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "769f4529-145c-4afa-a954-81d3cbabce58",
   "metadata": {},
   "outputs": [],
   "source": [
    "# CSVs\n",
    "# nodes_df.to_csv('exports/instance_01/nodes.csv', index=False, sep=',')\n",
    "# edges_df.to_csv('exports/instance_01/edges.csv', index=False, sep=',')\n",
    "# od_df.to_csv('exports/instance_01/od_matrix.csv', index=False, sep=',')\n",
    "# DELTA_df.to_csv('exports/instance_01/big_delta.csv', index=False, sep=',')\n",
    "# delta_df.to_csv('exports/instance_01/small_delta.csv', index=False, sep=',')\n",
    "# route_df.to_csv('exports/instance_01/routes.csv', index=False, sep=',')\n",
    "# paths_df.to_csv('exports/instance_01/paths.csv', index=False, sep=',')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22ada71c-f0ec-4183-a2be-0f6fd65b9942",
   "metadata": {},
   "source": [
    "#### Preprocess Y Variable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "f22bed43-1e50-499f-bc28-6b526bd1ba4b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "y_od_r original size: 2592\n",
      "fixed_variables: 984\n",
      "y_od_r simplified size: 1608\n"
     ]
    }
   ],
   "source": [
    "# Vectors\n",
    "y_fix_od = []\n",
    "y_fix_r  = []\n",
    "\n",
    "# Iterate over OD pairs\n",
    "for i, row in od_df.iterrows():\n",
    "    \n",
    "    # Iterate over routes\n",
    "    for i, route in enumerate(routes):\n",
    "        \n",
    "        # If neither origin, nor destination in route, add do vector\n",
    "        if (row['origin'] not in route) and (row['destination'] not in route):\n",
    "            \n",
    "            y_fix_od.append(row['id'])\n",
    "            y_fix_r.append(i+1)\n",
    "            \n",
    "# Print Results\n",
    "print(f'y_od_r original size: {od_df.shape[0] * len(routes)}')\n",
    "print(f'fixed_variables: {len(y_fix_od)}')\n",
    "print(f'y_od_r simplified size: {(od_df.shape[0] * len(routes)) - len(y_fix_od)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc094916-564c-4d48-8860-10a79122aad0",
   "metadata": {},
   "source": [
    "#### Reduce Dimensionality of $\\delta$ Matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "21b6e7d7-1ae5-4887-8fa1-88549a60ed70",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iterating over od pair 1/72\n"
     ]
    }
   ],
   "source": [
    "# Initialize W Vector\n",
    "od_path_edge = []\n",
    "start_index  = []\n",
    "finish_index = []\n",
    "\n",
    "# Counter\n",
    "i = 0\n",
    "\n",
    "# Rename edges_df\n",
    "df = edges_df\n",
    "\n",
    "# Iterate over OD pairs\n",
    "for j, od in enumerate(od_pairs):\n",
    "    \n",
    "    i += 1\n",
    "    \n",
    "    if j % 100 == 0:\n",
    "        print(f'iterating over od pair {j+1}/{len(od_pairs)}' )\n",
    "    \n",
    "    # Iterate over paths\n",
    "    for k in range(10):# enumerate(paths[od]):\n",
    "\n",
    "        # If index in range\n",
    "        if k < len(paths[od]):\n",
    "           \n",
    "            # Convert path to edges\n",
    "            edges_path = path_nodes_to_edges(paths[od][k])\n",
    "\n",
    "            # Add Starting Index\n",
    "            start_index.append(i)\n",
    "\n",
    "            # I\n",
    "            i += len(edges_path) - 1\n",
    "\n",
    "            # Add Ending Index\n",
    "            finish_index.append(i)\n",
    "            \n",
    "            # I\n",
    "            #i += 1 \n",
    "\n",
    "            # Iterate over edges\n",
    "            for edge in edges_path:\n",
    "\n",
    "                # Find edge id\n",
    "                edge_id = df[((df.origin == edge[0]) & (df.destination == edge[1])) | ((df.origin == edge[1]) & (df.destination == edge[0]))].id.values[0]\n",
    "\n",
    "                # Add id to list\n",
    "                od_path_edge.append(edge_id)            \n",
    "        \n",
    "        # If out of range...\n",
    "        else:\n",
    "            \n",
    "            # Add Starting Index\n",
    "            start_index.append(i)\n",
    "\n",
    "            # Add Ending Index\n",
    "            finish_index.append(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "713e1fca-f0a8-4b32-a30a-3ee6b9864e75",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length of vector: 168\n"
     ]
    }
   ],
   "source": [
    "print(f'Length of vector: {len(od_path_edge)}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "9d07adbc-fb73-4126-91e8-a9a74a9f3609",
   "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>od</th>\n",
       "      <th>path</th>\n",
       "      <th>path_size</th>\n",
       "      <th>w_start</th>\n",
       "      <th>w_finish</th>\n",
       "      <th>origin</th>\n",
       "      <th>destination</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>4</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>715</th>\n",
       "      <td>72</td>\n",
       "      <td>6</td>\n",
       "      <td>0</td>\n",
       "      <td>168</td>\n",
       "      <td>168</td>\n",
       "      <td>9</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>716</th>\n",
       "      <td>72</td>\n",
       "      <td>7</td>\n",
       "      <td>0</td>\n",
       "      <td>168</td>\n",
       "      <td>168</td>\n",
       "      <td>9</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>717</th>\n",
       "      <td>72</td>\n",
       "      <td>8</td>\n",
       "      <td>0</td>\n",
       "      <td>168</td>\n",
       "      <td>168</td>\n",
       "      <td>9</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>718</th>\n",
       "      <td>72</td>\n",
       "      <td>9</td>\n",
       "      <td>0</td>\n",
       "      <td>168</td>\n",
       "      <td>168</td>\n",
       "      <td>9</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>719</th>\n",
       "      <td>72</td>\n",
       "      <td>10</td>\n",
       "      <td>0</td>\n",
       "      <td>168</td>\n",
       "      <td>168</td>\n",
       "      <td>9</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>720 rows × 7 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "     od  path  path_size  w_start  w_finish  origin  destination\n",
       "0     1     1          3        1         2       1            2\n",
       "1     1     2          0        2         2       1            2\n",
       "2     1     3          0        2         2       1            2\n",
       "3     1     4          0        2         2       1            2\n",
       "4     1     5          0        2         2       1            2\n",
       "..   ..   ...        ...      ...       ...     ...          ...\n",
       "715  72     6          0      168       168       9            8\n",
       "716  72     7          0      168       168       9            8\n",
       "717  72     8          0      168       168       9            8\n",
       "718  72     9          0      168       168       9            8\n",
       "719  72    10          0      168       168       9            8\n",
       "\n",
       "[720 rows x 7 columns]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k = 10\n",
    "\n",
    "# delta Matrix\n",
    "od_ids = [id + 1 for id in range(len(od_pairs)) for i in range(k)]\n",
    "path_ids = [id + 1 for id in range(k)] * len(od_pairs)\n",
    "path_size = [len(paths[od][i]) if i < len(paths[od]) else 0 for od in od_pairs for i in range(k)]\n",
    "od_origins = [int(od_pairs[id].split('-')[0]) for id in range(len(od_pairs)) for i in range(k)]\n",
    "od_destinations = [int(od_pairs[id].split('-')[1]) for id in range(len(od_pairs)) for i in range(k)]\n",
    "\n",
    "\n",
    "# Data\n",
    "reduced_delta_data = {\n",
    "    'od' : od_ids,\n",
    "    'path' : path_ids,\n",
    "    'path_size' : path_size,\n",
    "    'w_start' : start_index,\n",
    "    'w_finish' : finish_index,\n",
    "    'origin' : od_origins,\n",
    "    'destination' : od_destinations\n",
    "}\n",
    "\n",
    "# DataFrame\n",
    "reduced_delta_df = pd.DataFrame(data=reduced_delta_data)\n",
    "reduced_delta_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "bedea9a3-30c8-4368-9fe1-dd6756b34c4f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected Reduction in Dimensionality: from 5760 elements to 168 elements. A 97.08 % reduction\n"
     ]
    }
   ],
   "source": [
    "orig = delta_df.shape[0]\n",
    "redu = len(od_path_edge)\n",
    "\n",
    "print(f'Expected Reduction in Dimensionality: from {orig} elements to {redu} elements. A {((1 - (redu/orig)) * 100):.2f} % reduction')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fefce720-0e25-4dfc-9d14-c66a1a4ad37d",
   "metadata": {},
   "source": [
    "#### Reduce Dimensionality of $\\Delta$ Matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "d6959631-abeb-4372-8bbe-1ce059a58ebf",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize Vectors\n",
    "route_list = []\n",
    "\n",
    "edge_list = []\n",
    "start_pos = []\n",
    "end_pos = []\n",
    "\n",
    "# Initialize Counter\n",
    "e_start = 0\n",
    "\n",
    "# Iterate over edges\n",
    "for i, edge in enumerate(list(G.edges())):\n",
    "    \n",
    "    # Add 1\n",
    "    #e_start += 1\n",
    "    \n",
    "    # Append Data\n",
    "    edge_list.append(i+1)\n",
    "    start_pos.append(e_start+1)\n",
    "    \n",
    "    # Iterate over routes\n",
    "    for route in routes:\n",
    "    \n",
    "        # Transform route from nodes to edges\n",
    "        route_edges = path_nodes_to_edges(route)\n",
    "\n",
    "        # If edge in route\n",
    "        if (edge in route_edges) or (edge[::-1] in route_edges):\n",
    "            \n",
    "            # Add 1 to counter\n",
    "            e_start += 1\n",
    "            \n",
    "            # Find route ID\n",
    "            route_id = route_df[route_df.sequence == str(route)].id.values[0]\n",
    "\n",
    "            # Append Data\n",
    "            route_list.append(route_id)\n",
    "            \n",
    "            \n",
    "    \n",
    "    # Append Finish\n",
    "    end_pos.append(e_start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "76f51ef3-3e0b-403c-a419-efa545bbcd09",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "84"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(route_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab8c5766-53a8-4f81-b083-4a8c5a2bc069",
   "metadata": {},
   "source": [
    "### Manual Array Initialization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "e4a6482c-482e-430f-b725-957879ddce7a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OD Pairs  = 72\n",
      "Routes    = 36\n",
      "Nodes     = 9\n",
      "Edges     = 8\n",
      "Max_Paths = 10\n"
     ]
    }
   ],
   "source": [
    "sizes = [len(G.nodes()), len(G.edges()), len(od_pairs), len(routes), k, len(od_path_edge), len(route_list), len(y_fix_od)] \n",
    "\n",
    "print(f'OD Pairs  = {len(od_pairs)}')\n",
    "print(f'Routes    = {len(routes)}')\n",
    "print(f'Nodes     = {len(G.nodes())}')\n",
    "print(f'Edges     = {len(G.edges())}')\n",
    "print(f'Max_Paths = {k}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd20234f-76d2-4b1e-bd43-48d58b4fd543",
   "metadata": {},
   "outputs": [],
   "source": [
    "# return_xpress_int_txt(sizes, filename='exports/instance_01/array_sizes.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99ee9de0-5353-48e2-80eb-e37ec2a13bb7",
   "metadata": {},
   "source": [
    "**Node Data**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "20b88796-afb3-4e7e-bbb4-383259dc9730",
   "metadata": {},
   "outputs": [],
   "source": [
    "# return_xpress_int_txt(nodes_df.id, filename='exports/instance_01/node_id.txt')\n",
    "# return_xpress_str_txt(nodes_df.id, filename='exports/instance_01/node_name.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac59ab61-a6d4-4b2b-ad0c-9bf9a6902d74",
   "metadata": {},
   "source": [
    "**Edge Data**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fe824af8-1f56-4c3a-9bb3-14d54d13d12f",
   "metadata": {},
   "outputs": [],
   "source": [
    "uv = list(edges_df.origin.values) + list(edges_df.destination.values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1466d37e-1ff0-41c2-bc3c-a7d1d97a41f3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# return_xpress_int_txt(edges_df.id, filename='exports/instance_01/edge_id.txt')\n",
    "# return_xpress_int_txt(uv, filename='exports/instance_01/edge_uv.txt')\n",
    "# return_xpress_int_txt(edges_df.length, filename='exports/instance_01/edge_length.txt')\n",
    "# return_xpress_int_txt(edges_df.travel_time, filename='exports/instance_01/edge_time.txt')\n",
    "# return_xpress_int_txt(edges_df.capacity, filename='exports/instance_01/edge_capacity.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af721b52-3cfb-41b2-925c-2170f69041ca",
   "metadata": {},
   "source": [
    "**OD Matrix Data**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7a8f1479-1918-4d17-858b-f94d8a5c71a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# return_xpress_int_txt(od_df.origin, filename='exports/instance_01/origins.txt')\n",
    "# return_xpress_int_txt(od_df.destination, filename='exports/instance_01/destinations.txt')\n",
    "# return_xpress_int_txt(od_df.demand, filename='exports/instance_01/demand.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2162c396-7dba-4fc0-bbb8-8eaf23a116a7",
   "metadata": {},
   "source": [
    "**Routes**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0fac00d5-e11c-45d5-b39e-006dec4aa7ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "frequencies = [1 for route in routes]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "351779a7-328b-4094-9b1f-893dbb655f83",
   "metadata": {},
   "outputs": [],
   "source": [
    "# return_xpress_str_txt(route_df.sequence.values, filename='exports/instance_01/route_sequence.txt')\n",
    "# return_xpress_int_txt(route_df.length.values, filename='exports/instance_01/route_length.txt')\n",
    "# return_xpress_int_txt(frequencies, filename='exports/instance_01/route_frequency.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c66838e-665c-4f2a-aba8-b31314ec6fec",
   "metadata": {},
   "source": [
    "**Paths**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d089c609-5e95-42f9-953a-e1852b485691",
   "metadata": {},
   "outputs": [],
   "source": [
    "# return_xpress_str_txt(paths_df.sequence.values, filename='exports/instance_01/path_sequence.txt')\n",
    "# return_xpress_int_txt(paths_df.length, filename='exports/instance_01/path_length.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2464c276-0a5d-4cea-9a54-bea83e77b6e7",
   "metadata": {},
   "source": [
    "**Y Preprocessing**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7a08fcbd-42f6-4543-b6e8-866744387384",
   "metadata": {},
   "outputs": [],
   "source": [
    "# return_xpress_int_txt(y_fix_od, filename='exports/instance_01/yfix_origin_destination.txt')\n",
    "# return_xpress_int_txt(y_fix_r, filename='exports/instance_01/yfix_routes.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3fba8861-4ef3-4db5-a859-c7eb663a3d7c",
   "metadata": {},
   "source": [
    "**$\\delta$ Dimensionality Redux**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f23626c4-43bd-47b8-b3e3-0094f68ef179",
   "metadata": {},
   "outputs": [],
   "source": [
    "# return_xpress_int_txt(od_path_edge, filename='exports/instance_01/small_delta.txt')\n",
    "# return_xpress_int_txt(reduced_delta_df.w_start, filename='exports/instance_01/small_delta_start.txt')\n",
    "# return_xpress_int_txt(reduced_delta_df.w_finish, filename='exports/instance_01/small_delta_finish.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "332c16c5-4d55-46ef-be0c-7d6b285579c6",
   "metadata": {},
   "source": [
    "**$\\Delta $ Dimensionality Redux**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "be8176af-1847-43c5-b652-cea80e7ed06e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DONE | File exports/instance_01/big_delta.txt saved to disk.\n"
     ]
    }
   ],
   "source": [
    "# return_xpress_int_txt(route_list, filename='exports/instance_01/big_delta.txt')\n",
    "# return_xpress_int_txt(start_pos, filename='exports/instance_01/big_delta_start.txt')\n",
    "# return_xpress_int_txt(end_pos, filename='exports/instance_01/big_delta_finish.txt')"
   ]
  }
 ],
 "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.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}