VRPPD and CVRPPD.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "677e9e06",
   "metadata": {},
   "source": [
    "# Curso Optativo: Enrutamiento de Vehículos. Trabajo Final\n",
    "\n",
    "- Carmen Irene Cabrera Rodríguez\n",
    "- David Guaty Domínguez\n",
    "- Enrique Martínez González\n",
    "- Richard García de la Osa\n",
    "\n",
    "C-512"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8e294ea",
   "metadata": {},
   "source": [
    "# Ejemplos de solución mediante Or-Tools de variantes de VRP de la tesis:\n",
    "## \"Validación Automática de Modelos para Problemas de Enrutamiento de Vehículos\", de Gabriela Argüelles Terrón\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc4d0406",
   "metadata": {},
   "source": [
    "El problema de enrutamiento de vehículos (VRP por sus siglas en inglés) es un problema concerniente a la distribución de mercancías entre un conjunto de almacenes y clientes. El objetivo del VRP es diseñar rutas de costo mínimo desde un almacén a un conjunto de clientes geográficamente dispersos sujeto a un conjunto de restricciones [1]."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4068b561",
   "metadata": {},
   "source": [
    "### Modelación general\n",
    "\n",
    "Los VRP se modelan como un grafo completo $G = ( V, A )$ donde $V = \\{ 0, 1, ..., n \\}$ es el conjunto de vértices y $A = \\{( i, j ) | i, j ∈ V \\}$ el conjunto de aristas que conectan vértices. Los vértices $\\{ 1, 2, ..., n \\}$ representan a los clientes y $0$ representa al almacén. A cada arista $( i, j )$ $\\in$ $A$ se le asocia un costo $c_{ij}$ representado en una matriz. Como no se permiten aristas $( i, i )$ el costo asociado a las mismas es $c_{ii} = +\\infty$ $\\forall i \\in V$. Si el grafo fuera dirigido, entonces se tiene una matriz de costo asimétrica, que define un problema de enrutamiento de vehículos asimétrico (ACVRP). Cada cliente tiene asociado una demanda $d_i \\ge 0$ $\\forall i \\in V/\\{ 0 \\}$ y el almacén tiene una demanda ficticia $d_0 = 0.$ Se tienen $K$ vehículos en el almacén con capacidad $C$ y se asume que $d_i \\le C$ $\\forall i \\in V$. Además, se asume que $K$ es mayor o igual que $K_{min}$ (cantidad mínima de vehículos necesarios para satisfacer a todos los clientes) [1]."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2bcee9f",
   "metadata": {},
   "source": [
    "Una de las variantes del problema es VRP con Entrega y Recogida (VRPPD):\n",
    "\n",
    "#### VRP con Entrega y Recogida (VRPPD)\n",
    "En el VRP con entrega y recogida (VRPPD por sus siglas en inglés) a cada cliente se le asocian dos cantidades que representan las demandas de mercancías para entregar y recoger. Cada cliente conoce el vértice del que proviene su entrega, y el vértice al que va destinada su recogida. Para cada cliente el proceso de entrega siempre debe ocurrir antes que el de recogida [1].\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d1ceaf2",
   "metadata": {},
   "source": [
    "**En el presente trabajo se resuelve un ejemplo de cada variante mediante la herramienta Or-Tools**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b02bf7ac",
   "metadata": {},
   "source": [
    "### Or-Tools\n",
    "\n",
    "Or-Tools es un software desarrollado por Google, especializado en problemas de optimización combinatorios. Uno de estos problemas es el VRP. Or-Tools ofrece herramientas para muchas de las variantes de dicho problema.\n",
    "\n",
    "Para cada problema de VRP, Or-Tools sigue un patrón en general [3]:\n",
    "- Importar las bibliotecas necesarias\n",
    "- Declarar el *solver*\n",
    "- Crear las variables\n",
    "- Definir las restricciones\n",
    "- Definir la función objetivo\n",
    "- Invocar al *solver* y obtener la solución\n",
    "\n",
    "Para instalar Or-Tools para python se puede ejecutar:\n",
    "`python -m pip install --upgrade --user ortools`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c264846f",
   "metadata": {},
   "source": [
    "A continuación se explica cómo utilizar Or-Tools para resolver las dos variantes de VRP que se proponen siguiendo este patrón"
   ]
  },
  {
   "attachments": {
    "vprppd_locations-2.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAAtoAAAI0CAYAAAAjoI7BAAAABHNCSVQICAgIfAhkiAAAABl0RVh0U29mdHdhcmUAZ25vbWUtc2NyZWVuc2hvdO8Dvz4AACAASURBVHic7N15lCN3fe/9T01JrV2abrV683T3eMUrHoOXMWCMMcEYwmICA0+CyUMgwMFAEnDgJpdrknDDdTbIiVniGwKXJYTVsfOEEA6+GMc2SwAbbGNmjMeebnerW91SaymVqkpqqZ8/xjPJMGbG0P0rjaffr3N8ji3V1Oc7Mz+rPiqVqq21tbU1HcHs7KwmJydlWdaRNtsQYWZ96lOf0q5duxSPx41nzc3NaXx8XLZtG8+an5/X6OioIpGI8axisahCoaBoNGo8a2FhQfl8XgMDA8azbr75Zl188cUaHR01nlUqlZTL5UJZh0tLS8pkMkokEsazlpeXlUqllEwmj6ust7/97XJdV+985zt15plnGs2qVCqKxWJKp9NGcw5YWVlRNBpVJpMxnlWtVmXbtrLZrPGsWq0my7KUy+WMZ919993q9Xo6//zzjWc1Gg11u10NDg4az3IcR51OR0NDQ8azms2mgiBQPp8PJcv3fQ0PDxvP2rt3r/bt26fLL7/ceFar1ZLruioUCsazPM+T4zgaGRkxnuX7vur1eijH5iAIVK1WNTY2tu59bdmAeQAAAAD8DIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGRGZmZo64QbFYVK/Xk2VZxocJM6tcLmt2dlaxWMx41uLiotrttmzbNp5VKpXk+74ikUgoWZ7nhZK1tLQk13UVjUaNZy0vL2tubk6+7xvPKpfLqtfroazDcrmsdDqteDxuPKtSqSiVSoWStbKyokQioUQiYTyr0WjI8zwVi0WlUimjWbVaTdFo1HhOP/Lq9bps21Y6nTae1Wg0ZFmWarWa8ayFhQX1ej0d7bi6EZrNprrdrhqNRmhZjuMYz3JdV51OR81m03hWq9VSEARyXdd41vz8vEqlUihrw/M8tVottVot41m+78t1XXmeZzwrCAI5jhPKsbndbqterysIgnXvKzI9PX3EDSzL0uTkZCjlN8ys4eFhTU1NhVIEbNvW+Ph4KEU7EolodHQ0lPIbjUZVKBRCKb8DAwPK5/MaGBgwnlUoFLRt2zaNjo4az4rH48rlcqGsw0QioUwmE0ohTSaTSqVSSiaTx1VWNpuVbduamJjQ0V471yudTisWi4VSRiUpk8koGo0qk8kYz6pWq7JtW9ls1nhWrVaTZVnK5XLGsyqVinq9nvG1Ie1/A9HtdjU4OGg8y3EcdTodDQ0NGc9qNpsKgkD5fD6ULN/3NTw8bDxrdXVVnU4nlLXRarXkuq4KhYLxLM/z5DiORkZGjGf5vq96vR7KsTkIAlWrVY2Nja17X1w6AgAAABhA0QYAAAAMoGgDAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMICiDQAAABgQmZmZOeIGxWJRvV5PlmUZHybMrHK5rNnZWcViMeNZi4uLarfbsm3beFapVJLv+4pEIqFkeZ4XStbS0pJc11U0GjWetby8rLm5Ofm+bzyrXC6rXq+Hsg7L5bLS6bTi8bjxrEqlolQqFUrWysqKEomEEomE8axGoyHP81QsFpVKpYxm1Wo1RaNR4zn9yKvX67JtW+l02nhWo9GQZVmq1WrGsxYWFtTr9XS04+pGaDab6na7ajQaoWU5jmM8y3VddTodNZtN41mtVktBEMh1XeNZ8/PzKpVKoawNz/PUarXUarWMZ/m+L9d15Xme8awgCOQ4TijH5na7rXq9riAI1r2vyPT09BE3sCxLk5OToZTfMLOGh4c1NTUVShGwbVvj4+OhFO1IJKLR0dFQym80GlWhUAil/A4MDCifz2tgYMB4VqFQ0LZt2zQ6Omo8Kx6PK5fLhbIOE4mEMplMKIU0mUwqlUopmUweV1nZbFa2bWtiYkJHe+1cr3Q6rVgsFkoZlaRMJqNoNKpMJmM8q1qtyrZtZbNZ41m1Wk2WZSmXyxnPqlQq6vV6xteGtP8NRLfb1eDgoPEsx3HU6XQ0NDRkPKvZbCoIAuXz+VCyfN/X8PCw8azV1VV1Op1Q1kar1ZLruioUCsazPM+T4zgaGRkxnuX7vur1eijH5iAIVK1WNTY2tu59cekIAAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMICiDQAAABhA0QYAAAAMoGgDAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYEBkZmbmiBsUi0X1ej1ZlmV8mDCzyuWyZmdnFYvFjGctLi6q3W7Ltm3jWaVSSb7vKxKJhJLleV4oWUtLS3JdV9Fo1HjW8vKy5ubm5Pu+8axyuax6vR7KOiyXy0qn04rH48azKpWKUqlUKFkrKytKJBJKJBLGsxqNhjzPU7FYVCqVMppVq9UUjUaN5/Qjr16vy7ZtpdNp41mNRkOWZalWqxnPWlhYUK/X09GOqxuh2Wyq2+2q0WiEluU4jvEs13XV6XTUbDaNZ7VaLQVBINd1jWfNz8+rVCqFsjY8z1Or1VKr1TKe5fu+XNeV53nGs4IgkOM4oRyb2+226vW6giBY974i09PTR9zAsixNTk6GUn7DzBoeHtbU1FQoRcC2bY2Pj4dStCORiEZHR0Mpv9FoVIVCIZTyOzAwoHw+r4GBAeNZhUJB27Zt0+joqPGseDyuXC4XyjpMJBLKZDKhFNJkMqlUKqVkMnlcZWWzWdm2rYmJCR3ttXO90um0YrFYKGVUkjKZjKLRqDKZjPGsarUq27aVzWaNZ9VqNVmWpVwuZzyrUqmo1+sZXxvS/jcQ3W5Xg4ODxrMcx1Gn09HQ0JDxrGazqSAIlM/nQ8nyfV/Dw8PGs1ZXV9XpdEJZG61WS67rqlAoGM/yPE+O42hkZMR4lu/7qtfroRybgyBQtVrV2NjYuvfFpSMAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMICiDQAAABhA0QYAAAAMoGgDAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2gE3jtttu0xvf+Ebddttthzz+L//yL7rssss0NDSk5z//+brjjjvU7Xb7NCUA4HhB0QawKdx77726/vrr9f3vf/+Qx++44w79zd/8jZ71rGfplltu0eTkpG644Qbdc889fZoUAHC8oGgDOO59/vOf12tf+1rt2bNHmUzmkOe++tWv6uSTT9arX/1qXXLJJbr22mvluq4eeOABzmoDANYl0u8BAMC03bt3601vepPW1tZ05513Hny83W7rkUce0emnn66RkRFJ0qmnnqqtW7fqkUceUbVa1fDwcL/GBgA8yVG0ARz33vve90qSvvCFLxzyeKPRkOd52rp1q5LJpCQpEokok8nIdV15nhf6rACA4weXjgDYtIIg0OrqqiKRiLZs+c+Xw2g0ql6vx6UjAIB1iezevfuIGxSLRbmuK8uyjA8TdtaePXsUi8WMZy0uLqper8u2beNZpVJJ1WpVkYj5DytKpZJWVlZCyVpaWlK5XFY0GjWeNT8/r4ceekjVatV4VrlcViaTCWUdlstlpdNpxeNx41mVSkWpVCqUrJWVFSUSCSUSiZ+7TTQa1fDwsHq93sHHgiCQbduybVurq6tyXVe+7yuZTKrT6SidTqvX66lYLMpxHK2trWllZUWe5+nhhx8+pJibUKvVFI1GlUqljOb817xIJKJ0Om0868DrYRhZjUZDlmUddm2+Cfv27VOv1wvl99VsNtXtdpXL5Y6rLNd11el0tLy8bDyr1WopCAKVy2XjWbOzsyoWizpa59oInuep1WqpUqkYz/J9X67ramVlxXhWEARyHCeUY3O73Va9XletVlv3viLz8/NH3GBpaUlra2vrDnoilpeX1ev1QinatVpNxWJRAwMDxrPK5bI6nY7xA7O0v+AcKBCmraysyPf9UIr2gYITRlalUtHCwoJ83zeeVa1W1Ww2Q3kDUavV5DhOKGu+Xq8rHo+H8gbiiWTFYjElk8mDr2Vra2sKgkDpdFqpZEr1el2u6yqRSKjdbstxHJ1wwgnasmWLlpeXValUtLa2drCMLy0tHbHYbwTHcRSJRIzn9COv2Wxqy5YtBy/XMcl1XUn7C7dpB46XRzuuboRWq6Ver6dms2k8y/M8ra6uhpp14O/NJN/31W631Wq1jGeVSiWVy+VQ1kYQBPJ9P5Rj2IE/vzCzgiAwntXpdNRsNtVut9e9r8jll19+xA1mZ2c1OTkZSvkNM2t+fl6XXXZZKGfc5ubmND4+Hkr5nZ+f1+joaCiFtFgsqlAohFISFxYWlM/nQymJjuPo4osv1ujoqPGsUqmkXC4XyjpcWlpSJpMJpUgtLy8rlUqFUqR+kawD/w9alqVsNitJOunkk7S8vKxWq6Xp6Wk98MADqtfrOnH7iZqanNKW7f/5BvmWW26R67rauXOnzjzzTDO/ocdUKhXFYrFQzo5K+9/MRqPRUM78VqtV2bZ98O/ApFqtJsuyQjkbOzg4qF6vp/PPP994VqPRULfb1eDgoPEsx3HU6XQ0NDRkPKvZbCoIAuXz+VCyfN8P5QvPe/fu1b59+3S0zrURWq2WXNdVoVAwnuV5nhzHOfhlcpN831e9Xg/l2BwEgarVqsbGxta9L67RBrCp/cqv/IoeeOABfeYzn9Edd9yhv/qrv1I6ndYZZ56hLTYvkQCAXx5HEQCb2qWXXqq3vvWtuv322/XSl75Uc3Nzeutb36rzdpzX79EAAE9y3N4PwKaxa9cu7dq167DHr7rqKl111VV9mAgAcDzjjDYAAABgAEUbAAAAMICiDQAAABhA0QYAAAAMoGgDAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyIzMzNH3KBYLKrX68myLOPDhJlVLpc1OzurWCxmPGtxcVHtdlu2bRvPKpVK8n1fkUgklCzP80LJWlpakuu6ikajxrOWl5c1Nzcn3/eNZ5XLZdXr9VDWYblcVjqdVjweN55VqVSUSqVCyVpZWVEikVAikTCe1Wg05HmeisWiUqmU0axaraZoNGo8px959Xpdtm0rnU4bz2o0GrIsS7VazXjWwsKCer2ejnZc3QjNZlPdbleNRiO0LMdxjGe5rqtOp6Nms2k8q9VqKQgCua5rPGt+fl6lUimUteF5nlqtllqtlvEs3/fluq48zzOeFQSBHMcJ5djcbrdVr9cVBMG69xWZnp4+4gaWZWlycjKU8htm1vDwsKampkIpArZta3x8PJSiHYlENDo6Gkr5jUajKhQKoZTfgYEB5fN5DQwMGM8qFAratm2bRkdHjWfF43HlcrlQ1mEikVAmkwmlkCaTSaVSKSWTyeMqK5vNyrZtTUxM6GivneuVTqcVi8VCKaOSlMlkFI1GlclkjGdVq1XZtq1sNms8q1arybIs5XI541mVSkW9Xs/42pD2v4HodrsaHBw0nuU4jjqdjoaGhoxnNZtNBUGgfD4fSpbv+xoeHjaetbq6qk6nE8raaLVacl1XhULBeJbneXIcRyMjI8azfN9XvV4P5dgcBIGq1arGxsbWvS8uHQEAAAAMMH/aE9gEgtaqvvGRPfrJRxbkBW1tPTWhp7/5RO189fZ+jwYAAPqEog2sU7fT06de8y1Vv+vp8g+frtxYUrtvX9TX3nmfVoNVPes3T+n3iAAAoA8o2sA6/eDmGS18t6E33HqJJs7Yfx3oKTsLatdWtfebyxRtAAA2KYo2sE733TSv7S8YPliyV4OuIjFbL/9f5/V5MgAA0E8UbWAd1tak0r83dMG7T9S3/uFhfeddD8lRoJRiuvgvTtEz/p+TFMJNdAAAwDGIog2sQ9tbVUdd3f/BOSlt6dKPnK7U4IB+9E+P6tbf/7E6rVU95w2n9XtMAADQBxRtYB26nZ4kyWt39JavXaatE/vvUX36s8f0fyrf0l3vfUjPfM1Jisb5Xw0AgM2G+2gD6zCQ3F+gxy/ferBkH3D6Cye0qq6WZ8z/1DEAAHDsoWgD6xCJblFuNKG1oHfYc2tra5Kkgbj5nwgKAACOPRRtYJ2e8htjmruzpuV9zUMe/8m/FpXZElN+KtWnyQAAQD9RtIF1uuS3TlVaA/r0c7+je74yq4e+s6wv/v4P9Og3VvQrHz9LFrcdAQBgU+IbWsA6pQdj+u17LtGtH9qjr7/xJ+qoq8IFae367AU649Kxfo8HAAD6hKINbIDMSEJX/ckO6U/6PQkAADhWcOkIAAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADuL0f0Ccr+1ztubWi2EBT008vaPiUtCIx3vsCAHC8oGgDIXv0+1X98Auz+slXFtSs+NpibZFlWbrgt7brWdecoux4ot8jAgCADUDRBkLklgPd/oE9euTOsnqra4c8972P71PtUU9XXHem8ien+zQhAADYKHxODYRo978tavmnzmEl+4Cffr2kxR83tBr0Qp4MAABsNIo2ECKn5GvVP3KJXn7QUeB0QpoIAACYEpmZmTniBsViUb1eT5ZlGR8mzKxyuazZ2VnFYjHjWYuLi2q327Jt23hWqVSS7/uKRMxfFVQqleR5XihZS0tLcl1X0WjUeNby8rLm5ubk+/6G77u8uKJ20Fa325UkdXtdrVlrh6z50qNlzeyzlXI39vdaLpeVTqcVj8c3dL+Pp1KpKJVKhZK1srKiRCKhRML8te2NRkOe56lYLCqVShnNqtVqikajxnP6kVev12XbttJp85dINRoNWZalWq1mPGthYUG9Xk9HO65uhGazqW63q0ajEVqW4zjGs1zXVafTUbPZNJ7VarUUBIFc1zWeNT8/r1KpFMra8DxPrVZLrVbLeJbv+3JdV57nGc8KgkCO4xg5Nv+sdruter2uIAjWva/I9PT0ETewLEuTk5OhlN8ws4aHhzU1NRVKEbBtW+Pj46EU7UgkotHR0VDKbzQaVaFQCKX8DgwMKJ/Pa2BgwHhWoVDQtm3bNDo6uuH7Lp3Z0+w3mlptPvZCYenglyEPeMozpnTqmROKJjd2vSQSCWUymVAKaTKZVCqVUjKZPK6ystmsbNvWxMSEjvbauV7pdFqxWCyUMipJmUxG0WhUmUzGeFa1WpVt28pms8azarWaLMtSLpcznlWpVNTr9YyvDWn/G4hut6vBwUHjWY7jqNPpaGhoyHhWs9lUEATK5/OhZPm+r+HhYeNZq6ur6nQ6oayNVqsl13VVKBSMZ3meJ8dxNDIyYjzL933V63Ujx+afFQSBqtWqxsbG1r0vLh0BQjR+zlbFcz//jcm2pw9q/Km5DS/ZAAAgfBRtIEST5w/qGW86Wblth59VTo3EdMUfnaXRM8yf5QMAAOZxez8gZDteNanJ8wf14/+vqIe/V1LUjmpoKq2dv32iBqfDuR4XAACYR9EG+iB/clrP/t3T9JRSTrlcLpTvCgAAgHBx6QgAAABgAEUbAAAAMICiDQAAABhA0QYAAAAMoGgDAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGRGZmZo64QbFYVK/Xk2VZxocJM6tcLmt2dlaxWMx41uLiotrttmzbNp5VKpXk+74ikUgoWZ7nhZK1tLQk13UVjUaNZy0vL2tubk6+7xvPKpfLqtfroazDcrmsdDqteDxuPKtSqSiVSoWStbKyokQioUQiYTyr0WjI8zwVi0WlUimjWbVaTdFo1HhOP/Lq9bps21Y6nTae1Wg0ZFmWarWa8ayFhQX1ej0d7bi6EZrNprrdrhqNRmhZjuMYz3JdV51OR81m03hWq9VSEARyXdd41vz8vEqlUihrw/M8tVottVot41m+78t1XXmeZzwrCAI5jhPKsbndbqterysIgnXvKzI9PX3EDSzL0uTkZCjlN8ys4eFhTU1NhVIEbNvW+Ph4KEU7EolodHQ0lPIbjUZVKBRCKb8DAwPK5/MaGBgwnlUoFLRt2zaNjo4az4rH48rlcqGsw0QioUwmE0ohTSaTSqVSSiaTx1VWNpuVbduamJjQ0V471yudTisWi4VSRiUpk8koGo0qk8kYz6pWq7JtW9ls1nhWrVaTZVnK5XLGsyqVinq9nvG1Ie1/A9HtdjU4OGg8y3EcdTodDQ0NGc9qNpsKgkD5fD6ULN/3NTw8bDxrdXVVnU4nlLXRarXkuq4KhYLxLM/z5DiORkZGjGf5vq96vR7KsTkIAlWrVY2Nja17X1w6AgAAABhg/rQnACB0P/32kj77iu/q3btfoHjG/KdOwAEVr6q/vfcL+sbCvVoMmroov12vP+uleub40/o9GhA6zmgDwHHmoe8u64uv+EG/x8Am1Fr19du3/anuWLxf7zx3lz7+7N/TRDKvXbf9pf59/nv9Hg8IHWe0AeA44dYC3f53P9X3/3qf4oqq0++BsOl8/dG79N36vP7t+X+kc/JPkSRdMHau7l15RJ/6yVf07BMu6POEQLgo2gBwnPj3v3tIuz+6qJf83blqLPi67brd/R4Jm8ylExfolueOHizZkrTFspSMDMhbbfdxMqA/uHQEAI4T579ySm/f81zteOFkv0fBJrU1ltX5o2cf/O9a0NBHf/SPuqM6q6vPeGEfJwP6gzPaAHCcKGw3f2s+4Im6/gd/pxse/IYk6c0nXaLnbdvZ54mA8FG0AQDAhnvlyVfoqpOep3vLu/W+e76oR5yS/u6518neYv5nSgDHCoo2AADYcCdvnZIkPWXwRA1EBvSW73xMdyx8T885gTPb2Dy4RhsAAGyIH5Z/on995PbDHj8tt12StNCshDwR0F8UbQAAsCG+Xfyhfvs7f6uH648e8vhdxXskSacNbu/DVED/cOkIAADYELtOu1JffPgOXXP7X+ht5/ya8vGcvl26V3/xk6/pddMX6+kjZ/V7RCBUFG0AALAh8vGt+uwVf6wb7/2iPvijL2qvX9PTsuP6y6f9ul512pX9Hg8IHUUbAI5Dz379qXr260/t9xjYhMYSBb33orf0ewzgmMA12gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADOD2fgCwiXnVtor31bU0s6KRU7KKPTWhgRSHBoSrterrp/Wi7lt6SHFrQJckd2g0sbXfYwHrxqspAGxSs99d0Tf+fLdmvl1Rr9eTLGn6wrwue9fpOvGZw/0eD5vEj1Ye1l/d+yXdWrxba701rUma3F3QW858sV532hX9Hg9YF4o2AGxCP/iHGd35oYdUm2kd8vij36vqWx/dq2jS1rbzBvs0HTaLhdaKvvzInbq1ePchj8+3yvrzH31RFd/RtU99RZ+mA9aPa7QBYJMpP9TUT28tHVayD3joG0v60RfmVJ/3Qp4Mm0m7t6pvLtyrm2fuetzn652mbi3era/P3/24zwNPBhRtANhkWittBc7qEbdxy768WjukibAZzbtlfW95j8p+/eduUw2aWmithDgVsLEiMzMzR9ygWCyq1+vJsizjw4SZVS6XNTs7q1gsZjxrcXFR7XZbtm0bzyqVSvJ9X5GI+auCSqWSPM8LJWtpaUmu6yoajRrPWl5e1tzcnHzfN55VLpdVr9dDWYflclnpdFrxeNx4VqVSUSqVCiVrZWVFiURCiUTCeFaj0ZDneSoWi0qlUkazarWaotGokZz5GUdO3VW32z342IFrtNesNUlSo+po/tGignRtw/Pr9bps21Y6nd7wff+sRqMhy7JUq2387+NnLSwsqNfr6WjH1Y3QbDbV7XbVaDRCy3IcZ0P3+4i7qFJt+ZB1eOAa7bW1/T3ACzwtLpc0M7Dxf6atVktBEMh13Q3f98+an59XqVQKZW14nifP89RqPf4nVhvJ9325rivPM//pVxAEchwnlGNzu91WvV5XEATr3ldkenr6iBtYlqXJyclQym+YWcPDw5qamgqlCNi2rfHx8VCKdiQS0ejoaCjlNxqNqlAohFJ+BwYGlM/nNTAwYDyrUCho27ZtGh0dNZ4Vj8eVy+VCWYeJREKZTCaUQppMJpVKpZRMJo+rrGw2K9u2NTExoaO9dq5XOp1WLBYzUkZjzboeGWmqYv/nAcuyLMmStlj7P+gc3jao7adNKj+98fnValW2bSubzW74vn9WrVaTZVnK5XLGsyqV/V8qNb02pP1vILrdrgYHzV9H7ziOOp2OhoaGNnS/2WBIT13dp9tW7j/42Jq1v2hv2bK/B+RTOZ12wnYjf6bNZlO+72t42PwXf1dXV9XpdEJZG61WS67rqlAoGM/yPE+O42hkZMR4lu/7qtfroRybgyBQtVrV2NjYuvfFpSMAsMkUTs1o5PSsosnHf/OfGolp+zPyGpw2e9Yem9tgLKPLJ87Ts0bP/rnbnJSZ0PnDp4U4vBA0egAAIABJREFUFbCxKNoAsMnYA1t0/m9u1ymXPf5ZqPNePaWnPH9cW2zzny5iczt/+DS94qRLlIoc/qneU4dO0qtPfo62pcyfmQVM4fZ+ALAJDU4lddUN5+msF0/ooW8sqVFpKj2S0DkvntT0RXlFE+YvdQMkadeJl+qU7An60sP/rnlnWVEroqePnaZLx8/VmVun+j0esC4UbQDYpKJxW2e9ZEJnvWRCKysrikajymQy/R4Lm9DT8qfoaflT1Gw2FQSB8vl8v0cCNgSXjgAAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMICiDQAAABhA0QYAAAAMoGgDAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog1gU3NdV7t27ZJlWYf885nPfKbfowEAnuQi/R4AAPppfn5enufpPe95jy699NKDj5999tl9nAoAcDygaAPY1Obn55VKpfSMZzxDz3ve8/o9DgDgOMKlIwA2tWKxqGQyqWw22+9RAADHGYo2gE1tfn5es7Ozesc73qHJyUldeOGF+tznPifHcfo9GgDgSY6iDWBTm5+fV7FY1Mtf/nJ98pOf1M6dO/Wnf/qn+upXv6rV1dV+jwcAeBKL7N69+4gbFItFua4ry7KMDxN21p49exSLxYxnLS4uql6vy7Zt41mlUknValWRiPnL70ulklZWVkLJWlpaUrlcVjQaNZ41Pz+vhx56SNVq1XhWuVxWJpMJZR2Wy2Wl02nF43HjWZVKRalUKpSslZUVJRIJJRKJX+jXJZNJFQoFvf/979f73vc+xeNx2batCy+8UG9+85v1ne98R+eff74SiYQcx1Gv19PKyoo8z9PDDz+sLVvMnqeo1WqKRqNKpVJGc/5rXiQSUTqdNp514PUwjKxGoyHLspTJZIxn7du3T71eL5TfV7PZVLfbVS6XO66yXNdVp9PR8vKy8axWq6UgCFQul41nzc7Oqlgs6midayN4nifP81SpVIxn+b4v13W1srJiPCsIAjmOE8qxud1uq16vq1arrXtfkfn5+SNusLS0pLW1tXUHPRHLy8vq9XqhFO1araZisaiBgQHjWeVyWZ1Ox/iBWdpfcIIgCKXUr6ysyPf9UIr2gYITRlalUtHCwoJ83zeeVa1W1Ww2Q3kDUavV5DhOKGu+Xq8rHo+H8gbil8myLEuFQkFDQ0MHS1GlUlG9VtdwYViFQkFBEKjZbCoIApVKJXW7XbmuK9/3tbS09AsX+1+U4ziKRCLGc/qR12w2tWXLFiWTSeNZrutK2l+4TTtwvDzacXUjtFot9Xo9NZtN41me52l1dTXUrAN/byb5vq92u61Wq2U8q1QqqVwuh7I2giCQ7/vyPM941oE/vzCOlweygiAwntXpdNRsNtVut9e9r8jll19+xA1mZ2c1OTkZSvkNM2t+fl6XXXZZKGfc5ubmND4+Hkr5nZ+f1+joaCiFtFgsqlAohFISFxYWlM/nQymJjuPo4osv1ujoqPGsUqmkXC4XyjpcWlpSJpMJpUgtLy8rlUqFUqTWk+V5nl73utdpenpab37zm3XSySfJcRwtLCzo5JNP1sjIiMbGxnTGGWdIkm655Ra5rqudO3fqzDPP3OjfyiEqlYpisVgoZ0el/W9mo9FoKGd+q9WqbNsO5QuotVpNlmWFcjZ2cHBQvV5P559/vvGsRqOhbrerwcFB41mO46jT6WhoaMh41oE3t/l8PpQs3/c1PDxsPGvv3r3at2+fjta5NkKr1ZLruioUCsazPM+T4zgaGRkxnuX7vur1eijH5iAIVK1WNTY2tu59cXs/AJtWIpHQ2WefrS996UsaGhrSM5/5TH3uc5/TzMyMXvva127IiywAYPPiy5AI1Q9/+ENdffXV2rFjh04//XS96EUv0s0339zvsbCJvfnNb9ZrXvMafeITn9Dll1+ub33rW/rDP/xDXXbZZf0eDQDwJMcZbYTm3nvv1VVXXaWzzz5b73vf+5RIJHTzzTfrmmuu0ezsrN7+9rf3e0RsQqlUStdcc42uueaafo8CADjOULQRmhtuuEFbt27V5z73uYN3Unje856n5eVlfehDH9Jb3vKWUK4tBwAACAOXjiA0F1xwgd7+9rcfdruyM844Q67rhvINaQAAgLBw+hCheeMb33jYY51OR1//+td18sknh3K3AwAAgLBQtNE3a2tres973qOZmRl96lOf6vc4AAAAG4qijb5ot9u69tprddNNN+n973+/nvvc5/Z7JAAAgA1F0UboFhcX9frXv167d+/WRz/6Ub34xS/u90gAAAAbjqKNUP34xz/W1VdfrS1btujLX/6yduzY0e+RAAAAjOCuIwjN3r17tWvXLo2MjOhf//VfKdkAAOC4xhlthOZ3f/d3VavV9Bu/8Ru65ZZbDnv+13/91w+79R8AAMCTFUUboXj00Ud19913S5I+/OEPP+42v/qrv0rRBgAAxw2KNkIxOTmp+fn5fo8BAAAQGq7RBgAAAAygaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAI/jd37nd3TCCScc9s+rXvWqfo8G4EmC2/vhmLeysqLdu3dreHhY09PTSqfT2rKF94gAfr4gCLS8vKzZ2Vml02mdcsopSiaTv9A+7rvvPp1zzjmHFeuJiYmNHBXAcYyijWPaRz/6UX3kIx/R8vKyLMvS8PCwfvM3f1O/9Vu/paGhoX6PB+AY9G//9m/6wAc+oPvvv1+9Xk+WZenMM8/UtddeqyuvvPIJ7cP3fT300EN6xzveode97nWGJwZwvKJo45j16le/Wt/61re0urp68LFKpaIPfOADGhkZ0ctf/nKl0+k+TgjgWHPnnXfqxhtv1P3333/I4z/5yU/08Y9/XIODg9q5c+dR9/PAAw+o2+3q3HPPlbT/DHksFjMyM4DjF5+/45j06U9/Wrt37z6kZP9XN9xwgx588EF1u92QJwNwrNq3b58++9nP6rvf/e7jPn/XXXfpH//xH7Vv376j7uu+++6TtP/s+LnnnquTTjpJ5513nm644Qb1er2NHBvAcYyijWPS4uKi2u32z31+fn5e3/ve9+S6bohTATiWVatV1ev1I27zyCOPaGZm5qj7OlC05+bmdP311+vGG2/Ujh07dP311+u6667bkHkBHP8iR3vBKRaLB69xMy3MrHK5rNnZ2VA+CjxQGm3bNp5VKpXk+74iEfNXBZVKJXmeZyRrdnZWvu8fPGN9YF3817Xx4IMPau/evRt+rfby8rLm5ubk+/6G7vfxlMtl1ev1UNZhuVxWOp1WPB43nlWpVJRKpULJWllZUSKRUCKRMJ7VaDTkeZ6KxaJSqZTRrFqtpmg0ajynH3n1el22bW/4pV8zMzOq1WqHfNL1s68d5XJZDz/8sLZv3/5z95PP5/Wa17xGl1xyiV74whcePIN95ZVX6uqrr9bHP/5xvelNb1I8Hler1Tr46xYWFtTr9Z5QkV+vZrOpbrerRqMRWpbjOMazXNdVp9NRs9k0ntVqtRQEQSgnbObn51UqlUJZG57nyfO8Q9amKb7vy3VdeZ5nPCsIAjmOE8qxud1uq16vKwiCde8rMj09fcQNLMvS5ORkKOU3zKzh4WFNTU2FUgRs29b4+HgoRTsSiWh0dDSUoh2NRlUoFBSNRjd832eeeaa++c1vHvwf6sCB8r+ujUsuuUSnn376hhesQqGgbdu2aXR0dEP3+3ji8bhyuVwo6zCRSCiTyYRSSJPJpFKp1C98l4djPSubzcq2bU1MTOhor53rlU6nFYvFQvseQiaTUTQaVSaTMZ5VrVZl27ay2eyG7tf3/cNea3/2teOMM87QhRdeeNS/vx07dmjHjh2HPf6Sl7xEt99+ux588EFdfvnlhzxXqVTU6/WMrw1p/5u+brerwcFB41mO46jT6YTyBfRms6kgCJTP50PJ8n1fw8PDxrNWV1fV6XRCWRutVkuu66pQKBjP8jxPjuNoZGTEeJbv+6rX66Ecm4MgULVa1djY2Lr3xaUjOCadd955RzyzdtVVV+miiy4KpTQCeHI46aSTdNZZZ/3c1450Oq3zzz9fp5122lH39c///M+6/fbbD3v8wBmuMMoZgCc/ijaOSTt37tQ111zzuO+S8/m83va2t2l8fLwPkwE4VkWjUe3atUsvetGLHvf5l73sZXrZy172hD6Fu/HGG/V7v/d7h3z8vra2pptuukkjIyM6/fTTN2xuAMcvbu+HY9bVV1+tiy66SLfccot+8IMfKJvNavv27XrDG94QysdUAJ58TjjhBP3Zn/2ZrrzySn3ta1/TwsKCMpmMnv/85+u5z33uE7784d3vfrde85rX6Oqrr9ab3vQmSdInP/lJ3X333frbv/1bbvUH4AmhaOOYdtppp+n3f//3tbCwoHw+r4GBgX6PBOAYF4vFdMUVV+iKK65QrVaTZVnK5XK/0D6e/exn6wtf+II++MEP6h3veId839c555yjT3/603rOc55jZnAAxx2KNgAAj2Pnzp36/Oc/3+8xADyJcY02AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMICiDQAAABhA0QYAAAAMiMzMzBxxg2KxqF6vJ8uyjA8TZla5XNbs7KxisZjxrMXFRbXbbdm2bTyrVCrJ931FIpFQsjzPCyVraWlJrusqGo0az1peXtbc3Jx83zeeVS6XVa/XQ1mH5XJZ6XRa8XjceFalUlEqlQola2VlRYlEQolEwnhWo9GQ53kqFotKpVJGs2q1mqLRqPGcfuTV63XZtq10Om08q9FoyLIs1Wo141kLCwvq9Xo62nF1IzSbTXW7XTUajdCyHMcxnuW6rjqdjprNpvGsVqulIAjkuq7xrPn5eZVKpVDWhud58jxPrVbLeJbv+3JdV57nGc8KgkCO44RybG6326rX6wqCYN37ikxPTx9xA8uyNDk5GUr5DTNreHhYU1NToRQB27Y1Pj4eStGORCIaHR0NpfxGo1EVCoVQyu/AwIDy+bwGBgaMZxUKBW3btk2jo6PGs+LxuHK5XCjrMJFIKJPJhFJIk8mkUqmUksnkcZWVzWZl27YmJiZ0tNfO9Uqn04rFYqGUUUnKZDKKRqPKZDLGs6rVqmzbVjabNZ5Vq9VkWZZyuZzxrEqlol6vZ3xtSPvfQHS7XQ0ODhrPchxHnU5HQ0NDxrOazaaCIFA+nw8ly/d9DQ8PG89aXV1Vp9MJZW20Wi25rqtCoWA8y/M8OY6jkZER41m+76ter4dybA6CQNVqVWNjY+veF5eOAAAAAAZQtAEATxpeN9BVX3mn3vrN9/d7FAA4Koo2AOBJ469+8An9R6PY7zEA4AmhaAMAnhRuffRb+od939YpcfPXWwPARqBoAwCOeQutZb37Ox/T9Re8Vickt/Z7HAB4QijaAIBjWq/X0x/edYOeN362Xnri5f0eBwCeMIo2AOCYduP9n9esW9F/v+iN/R4FAH4h5m+2DADAL+n7pfv1P3/8L/rny/9A2Wg49xQHgI1C0QYAHJPqbUfv+vZHdM3Jl+rE7KRW/Lokqdvrqd3raMWvKxVNKGab/0FWAPDLoGgDAI5Je1Ye1h6vqj17b9OH99522PNf+ac366+f/lq98rQr+zAdABwdRRsAcEx6ytBJ+qfL/tthj//P731CmWhCv7Pj1ZrKnNCHyQDgiaFoAwCOSbmBjC4cO/ewx9MDcQ3GHv85ADiWcNcRAMCTi2VJVr+HAICj44w2AOBJ5bPP/1/9HgEAnhDOaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMIDb+wEAjjtBt6Mlv6aZelHpaEKnpmJKReL9HgvAJkPRBgAcV+6pPKS/vPdLum3hh+r11mRJetb4OXrnOa/QzpHT+z0egE2Eog0AOG7ctO9OffC+m7TXKR7y+F2l+7Xs1XTtU1+pX526qE/TAdhsuEYbAHBc2OeU9H/n7zmsZB/wYGNOt87frZlmKeTJAGxWFG0AwHGh0XHldLwjbjPfqmihtRLSRAA2u8jMzMwRNygWi+r1erIsy/gwYWaVy2XNzs4qFosZz1pcXFS73ZZt28azSqWSfN9XJGL+qqBSqSTP80LJWlpakuu6ikajxrOWl5c1Nzcn3/eNZ5XLZdXr9VDWYblcVjqdVjxu/gthlUpFqVQqlKyVlRUlEgklEgnjWY1GQ57nqVgsKpVKGc2q1WqKRqPGc/qRV6/XZdu20un0hu73wdojKtUr6na7Bx87cI22tbb/uPLQyqO6Z98DGveSG5otSQsLC+r1ejracXUjNJtNdbtdNRqN0LIcxzGe5bquOp2Oms2m8axWq6UgCOS6rvGs+fl5lUqlUNaG53nyPE+tVst4lu/7cl1XnnfkN7gbIQgCOY4TyrG53W6rXq8rCIJ17ysyPT19xA0sy9Lk5GQo5TfMrOHhYU1NTYVSBGzb1vj4eChFOxKJaHR0NJTyG41GVSgUQim/AwMDyufzGhgYMJ5VKBS0bds2jY6OGs+Kx+PK5XKhrMNEIqFMJhNKIU0mk0qlUkomN77M9DMrm83Ktm1NTEzoaK+d65VOpxWLxTa8jP48mUxG0WhUmUzGeFa1WpVt28pmsxu6XzcnTdTv0X3uf5YZy3qsaG/Zf1w5q3CiLjrpXE0Pb/zfX6VSUa/XM742pP1v+rrdrgYHB41nOY6jTqejoaEh41nNZlNBECifz4eS5fu+hoeHjWetrq6q0+mEsjZarZZc11WhUDCe5XmeHMfRyMiI8Szf91Wv10M5NgdBoGq1qrGxsXXvi0tHAADHhXwsq5H4oCLW459oiFoRnZSZ0GTKfLECAImiDQA4TowmBnXNWS/WS7df/LjPv+KkZ+uNZ7xQhcTWkCcDsFlxez8AwHFjKjWiv7zwjXrBCRfos3u/oR9X9mkilddvnHq5rpy8QEMx85fGAMABFG0AwHElZkf1oqkL9aKpC1Wr1WRZlnK5XL/HArAJcekIAAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMICiDQAAABhA0QYAAAAMoGgDAAAABkRmZmaOuEGxWFSv15NlWcaHCTOrXC5rdnZWsVjMeNbi4qLa7bZs2zaeVSqV5Pu+IpFIKFme54WStbS0JNd1FY1GjWctLy9rbm5Ovu8bzyqXy6rX66Gsw3K5rHQ6rXg8bjyrUqkolUqFkrWysqJEIqFEImE8q9FoyPM8FYtFpVIpo1m1Wk3RaNR4Tj/y6vW6bNtWOp02ntVoNGRZlmq1mvGshYUF9Xo9He24uhGazaa63a4ajUZoWY7jGM9yXVedTkfNZtN4VqvVUhAEcl3XeNb8/LxKpVIoa8PzPHmep1arZTzL9325rivP84xnBUEgx3FCOTa3223V63UFQbDufUWmp6ePuIFlWZqcnAyl/IaZNTw8rKmpqVCKgG3bGh8fD6VoRyIRjY6OhlJ+o9GoCoVCKOV3YGBA+XxeAwMDxrMKhYK2bdum0dFR41nxeFy5XC6UdZhIJJTJZEIppMlkUqlUSslk8rjKymazsm1bExMTOtpr53ql02nFYrFQyqgkZTIZRaNRZTIZ41nValW2bSubzRrPqtVqsixLuVzOeFalUlGv1zO+NqT9byC63a4GBweNZzmOo06no6GhIeNZzWZTQRAon8+HkuX7voaHh41nra6uqtPphLI2Wq2WXNdVoVAwnuV5nhzH0cjIiPEs3/dVr9dDOTYHQaBqtaqxsbF174tLRwAAAAADzJ/2BHDM2/3a16izWPrPByxLW2JxDYyPKfvMizX88lfKDunMamdpSXte9/8qde4ObX/f+2T9Ap8EOXfdpX1//Ec65UMfUuK0p2it19PS5z+nSDKl/EtfanBqAAAOR9EGIEka2Dah4Zf92v7/WFtTz/PkPrhHS5/5rGq336GT//wvFAnh49zlL39J0ZFRTf23P/iFSrYk2YNDyjzjYm157Drjnudp6ROf0Ngb3mBiVAAAjoiiDUCSFBnMK/+SlxzyWEGPnSX+kz/W3Ic/pO3XvfcJ7++XvXY/c8H5Krz812Rnn9i1wlu3blWv15MkJc88Q9v/6E9+qVwAADYaRRvAEWWe+UzlLn+u6rf+X3VKJUUf+yJKz2lq8R8+rcadd2m1uqLYtm0aesmLlX/Ri5VMJmVvsVX86EfUeuABDV75ApVvukmri8samDxB+ZddpaErrjgkx/mP72r5y1+St3ev1FtTascOjV59tRInnnRwm+Y9d2vpc5+V99O9UndNidNP0dDLXq7czov37+O/XDqigQE99MY3SpIWP/YxLX7sYzrrK/+qLdGogn37tPgPn1brgd3q1RuKn3aKCq94hbLPeGZIf6oAgM2AL0MCOKrczmdIktz775MkdT1Pe991raq3fl2FV75SJ/7pnyp78cUq/s0NWvzEJ5RIJA7ePch78CFVvnyzpv/gD3XGTV9W/mVXqfjBD6py8z8d3P/yF7+gfe95j6KFgqbe9W5te/vb1Vlc0MNv+x219uzev599j2jfe67TwOi4tl93nabfe522JJKaue46eQ/99LCZY9smdcpHPiJJGt61S6d94hPaEonIve8+/fSat2p1eVkTb3qTJv/Hf1dk65Bm/uiPVLnlFqN/jgCAzYUz2gCOKvLY7a861aokaeUr/yJ/716deP31Sj/t6ZKk1I7zZMXjKn3ik9p6xRWKjY/v/8VrXW279p2Kn3yKJGnoiivk7dmtxU99SoO/+mKtuS2V/s+nlHvOZZq89l0HM9MXXKgH3/B6Lf79x3TSn/+lWj95QGudQIVXvUqxE7ZJkpKnn67Ff/iMtLZ22MxbIhENjE/snz+bPfhrFv73jYrkt+rEP/9LbXnsdpHZi3bqkff+Dy3+/d8r97zLFUmF88VPAMDxjTPaAH5hze99X3Zuq1Ln7tBat3vwn9zOi6W1rpr33H1wWzu3Vckzzjjk16d3nKdesyn/pz9V6/77tNYJNPgrzztkGzuVUu7SS+X+6F51fV/ps5+qLbGYHr72WhVv/Kga3/m21tbWNPb6Nyh+yqlPaO5uw5G3Z4+2PueygyX7gPyvvEA935O/Z88v+acCAMChOKMN4KhWl/bf+m/gsTPbq7WquvWa7r/yBY+7fadSPvjv0aHDf6DGgVsFdl1Hncd+Alz0cX4YxsDg0P6z1X5LsclJnfzXf63lf7pJtVtvVeXLN8mKRJS6eKe2veVt2pI/+g/TWHUaPzcr8ticqy3zPyUOALA5ULQBHFXju/8hWbZSZ58tSbJzWcWmpjT1B3/wuNtvyfznT/zrrFQOe/5AEY9kB6Wg89h2K4qffOh27crK/nt6p/fvL37yKfsvL1lbk//II2p8+y4tfvozmu9Z2v7e6476+4g8NldnZeWw51b///buPkiOs7Dz+K+35/1lR7szsy/SvuCV5JdYMrZ5MZgcwi84V1w4A0eEcQ6DeREvdq6OlyKxSUziC8R3McWducIXRIgKDLFJwjkJVakYO4aTDTYQgylsjB0s7bI7u7M7s/Pa093ztveHzBJdsEROenql1fdTpT802+rfs7uP5vl1T0/Pc4+FU+Y/GREAcGbg0hEAx9T47ndU/YcHlbl8j0K5Ix/pm7zoYrXnF6RQSLHtO9b/9BoNLf7p5+Qv//zDb3q1upqPPXbUPisPPKBQNqvY9hklzt8lKxxV5Wv3H7VNz3VVO/gNJS98oaxQSCt/8WX96M3XqOd5kmUpNjOjkd98i2LnnatOcfEXD37gyFOc9dwl3PZgWvFzz1b16w+q324ftenq/fdpIBJT7JxzT+THBQDAOs5oA5AkdStllf/mb478ZW1NPbel1tM/VuPhRxSdmNC2d79vfdvca/+9qvffr0M3f0Qjb75GsclJeT+d09KBA4qMjCj+3BsfJUmWpbn/dptG3/pWRfJ5Ve6/X85jj2nq5ptl2bbsLRmNvuU/aulzf6qfRkLasudV6rdcrfzVl9WrNzX2trdLktIverGKBw5o9vc/qvzVV2sgHlfzB9+X+4Mfaut73/MLvyc7FpMVjqr28MMaGExry6uv0vg73qVDN92kQx/+kLJvfKPsSFSVf3hAjW9+S+Pvfa/seNzYzxgAcGahaAOQJLXnCyr8z0+t/30gnlR0eptG3nad8le/TgOJxPrX7FRKOz7xSS196S4t//k96lVXFc7nNPzqqzT65t9ULxTS2nN3AhmIJTTx/g9o6TOfVadYVOzcHXrBxz+m9Itfur6//DXXKDySV/nev9bcrbfKisWVfOEF2vb+D67fRzs2M6OzbvuvKt795/rp//jvWnNaik5Naet//k/K/bvX/uJvyrI0vu9dKt71eS3e+b+U2LVbyRdeqJlPfFLFu7+ohU98UuqvKX7ODk3//u9zH20AwElF0Qagcz9/17/639hbMtr2vhu07X03/IuvrZZKGv5nbzgcvORlGrzkZcfc35bLr9CWy6845jbJ3bs1s3v3UY91u111ul1FIhGlX/EK7b7va0d9PXv11cpeffVRjyXOO1dn/cF/OWYWAAAnimu0AZx0a7/gvtamVCoVdbvdwPIAAPhlUbQBmBFc1wYA4JRE0QZgRK/f09b3vk/n//W9Gz0UAAA2BEUbgBGdTmejhwAAwIaiaAMAAAAGULQBAAAAA7i9HwD8Evqup1y/r5jnaaDR0Fq3Kysh+u/7AAAgAElEQVTEUygA4PmxSgDAcTQf+56WPvc5Xf7t72htbU2t3/4dzb/mNRp58zWKTk5u9PAAAKcoijYAHEPpf39FK3/xV+osLx/1eOW+++QdPqTxd+9T6oUXbtDoAACnMq7RBoDn4R06pPo3H/kXJftn3KefUfPb31G3XA54ZACA04E1Pj5+zI+V6PV6sm07kMEEmeW6rmKxmCzLMp61WX+GQWb1+31ZlhXI78vzPEUiEQ0MmD8ODfL7Iutf78WxmF4Xj2vSPvLi31q/L0lHsp7L+z+ep696roon+dMpg/wZBp23WbN+dkvLcDhsPGttbU1ra2uBPE+RdeJ6vZ663a6i0ajxrM36Mzxds6zbb7/9mEW7UqloaGjohIN+GdVqVZlMJpAnxO9+97u68MILFQrgzUy1Wk3pdDqQyRFkVr1eVzKZDKRsB5n1wx/+UC94wQuUSqWMZzUaDcXj8UDmYbPZVDQaDaQEBJnlOI7C4bAikchJ3/fEj5/S+DM/UdjzJUme50rScwdiR+bi6sRW/fRXzpMzmDmp2a1WS7ZtB7IwB53nuq4sy1IsFttUWQsLC+r3+5oM4Lp9z/O0trameDxuPMv3ffV6PSUSiU2V1W631el0lEwmjWeVy2Wtrq5q586dxrM6nY583w9kDQsyq9vtynVdpdPp0yrLWltbO2bRnpub0+TkZCDlN8isz3/+89q7d28gT77z8/MaHx8PpCQuLCxodHQ0kOJWKBSUz+cDKVOLi4vKZrNGytT/695779XLX/5yjY6OGs8qFovKZDKBzMPl5WWl0+lAFuaVlRUlk8lAFkuTWY1vf0fFAwfUevppSUcO+NbW1pRMJtf/j2Vf++vKv2mvImPjJzW7XC4rGo0GsoBJ0urqqsLhcCCLWKVSkW3bGhwcNJ5VrVZlWZYymZN7IPSLPPbYY+r3+3rxi19sPKter6vX6wVyIqzRaKjT6Wh4eNh4VrPZlO/7ymazgWR5nqdcLmc86yc/+YkOHz6sK664wnhWq9WS4zjK5/PGs1zXVaPR0MjIiPEsz/NUq9UCWZt931elUtHY2NgJ74trtAHgecSmpxQZGZH1PAfJA+GwIiMjspPBlGEAwOmFu44A/4/zf+X8wM4i4tQWHh3V0K+/Ru2VZbV+/PS/+Hrmlf9Gg6+4VHYAZ4Fx6tu2bZv6z13HDwDSGVy0g3oTH04/O882fw0dTh/pF79E0Ykp1R9+WLUv3qXWyrLyL79E4//2NUpddKHsAC5/wOkhiJe0cXoaGBgI5DJLnHrOmEtHPM/TS1/6Ut1///3qdrvK5XIaGBjQs88+q9e+9rXKZDI677zzdO+996rdbm/0cLEBvvGNb+icc85Zv0OBZVm6+OKL9cQPn9joocGwr371q7rssss0PDysq666SgcPHlSv11v/emRsVLn/8Ab9xcSEvnz2Oeq/5Tpl9rySkg15nqebb775qOcNy7L0e7/3exs9NGygZ599Vh/96Ed12223SZKGhoY0PT2tH/3oR3rnO9+pfD6vXbt26c4776RzbHJnxBlt13X19re/XY8//vj64jk9Pa21tTVde+212rlzpx588EE98MAD2rdvn+6//37t2rUrkDt34NRx+PBh7dixQzfddJMmJiYkSel0WtMvmN7gkcGkgwcP6o477tCv/uqv6tZbb9WBAwf0qU99SvF4PJA3teH0trKyomq1quuvv17XXnvt+uNnnXXWBo4KG2lxcVGf+9zn9IUvfEHvfe97JUmpVEpLS0v6zGc+o8XFRd1zzz164okn9OUvf1nxeFxve9vbNnbQMGbTF+0nnnhC73znO+W67lFnqPL5vB544AEtLCzoK1/5isbHx3XxxRfr4Ycf1j333KPt27cHcssfnDoOHTqkmZkZXXbZZZqeplyfKf7u7/5O27dv1zXXXKPzzz9fuVxOH/rQh/Tkk0/qoosu4jIzHFOpVFK/39dLXvISXXnllRs9HGywxx9/XH/wB3+ggwcPHnWwZdu2Dh8+rEOHDmnfvn26/PLLtWvXLlUqFd1333269tprA7mrFoK36U/ZPvzww7riiiv0tfu+dtTtnRKJhB577DHt3r1bqWRq/ZaCl1xyiR5//PH1Dx7AmePw4cMaGRlRPGb+9nc4NbTbbR06dEhjY2Prt6fauXOntmzZokOHDqlSqWzwCHGq+1nRDuIWcTj1raysaGJiQnfeeedRr4j1+32VVkpyXVfnnXeeJCmXy2nHjh1aWVnR7OzsRg0Zhm36or1v3z794R/+oYaGh466P7dt2yoWixoZGTnqEpF8Pq/l5WXeOX6GWVtb0+zsrB566CFdceUV2rZtm970pjfpiSeeOOqVEGwu9Xpdrutqy5Yt6/fhDoVCSqfTchxHrutu8AhxqltZWdHhw4f1yU9+UjMzM9q9e7fuuOMOra6ubvTQsAGuvPJK3XHHHTr77LOPetzzPFVrVUWj0fV7nw8MDCgej2tgYICD+k1s0xTtdrutcrmsUqmkUqmkVqulY30WjyVLruseeanmn30+TiQSUbvdPua/xemt0+moUqmszxXHcbS4uKharaZer6dbb71Vd955p5aWlvThD39YP/nJTzZ6yDDE9311u12FQqGjDrjD4bD6/T4HWTiuUqmkubk5XXrppdq/f79+442/oQMHDmj//v28Mop1vV5Pvu8fuftI6Od3H7FtWwMDA8yVTWzTXKP9ta99TW9605vkOI4k6ZZbbtFNN930vJ+4t6Y1xWIxNZtN6Z916na7rUQiEcinU2JjfPOb39S73vUuPfPMM5Kk973vffrIRz6i++67b/1T8cLhsPL5vN7xjnfo2Wef1czMTCCftolgRSIR2batbrd71KtYnU5HqVSK3zmOa9++fXrbW9+mWDwm27Z1ySWXqNfv6Xvf+56efvppnX/++Rs9RJwCbNtWJBJRv99Xp/vzUt3r9bS2tqZoNLqBo4NJm2YVueSSS/S3f/u362egtm/ffsw3FnS7XY2Pj+tb3/qW+ms/X2CXl5eVz+e548gmdsEFF+jAgQNqtVqSpMnJSWWz2fUnuu9///uamZnRzMyM4vG4SqWS2u02pWsTGtoypGQiqVqtJtd1lUwm1e121Wg0tG3btkA+rh6nt1gstn5CZ35+Xmtra8rn83r66afVaDQ2eHQ4VcTjcQ0NDcn3fVWrVeXzefX7fbmuq36/v345CTafTdMccrmcLrvssl96e9d19aIXvUj79+9Xq9XS4HP3w3300Ud1wQUXcGP5TWxoaEiXXnrpUY89+uij+q3f+i3dfvvtuuiii5RIJNbfFLtt27bnfWUEp7dQOKSZ7TNaWVnRysqKcrmcnn76adVqNZ31grM0tIXFD8/P93398R//sebm5vQ7v/07mpyaVKvV0uLi4vqrYoAkWZalfD6vZDKpp556Sjt37lSpVNI//dM/KZ/Pa2pqaqOHCEPO2NO2KysretWrXqWRkRG9//3v1z/+4z/q9ttv16OPPqq9e/dyJusMs3v3buXzed1222369re/rYceekgf/ehHdfHFF+uss87iFY5N7NWvfrWefPJJ3XXXXTp48KA+8YlPKJVK6bxfOU8DNr93PL9oNKodO3boqaee0mf/9LN6/PHH9Sd/8if6+te/rpe97GXaPrN9o4eIU0Sv19PU1JQmJib06U9/Wvfff7/uueceff3rX9ev/dqvcXJvEztjV5HZ2VkNDAzoi1/8olZXV7Vnzx792Z/9mfbv369zzz2XYnWGSSQS+tSnPqVt27bpLW95i974xjdqenpat9xyC/fU3uT27NmjG2+8Ud/4xjd09dVXa35+XjfeeKMuuvCijR4aTgOve93rdOONN+rgwYO66qqr9KUvfUlvf/vbdd111x31Rnuc2ZrNphKJhN797ncrl8vpmmuu0f79+7V37169+c1v3ujhwaBNc+nI8YRCIZVKpfW/l8tl9ft97dy5U3//93+/gSPDqWJmZkb79+/f6GFgA7z+9a/X61//+o0eBk5DsVhMe/fu1d69ezd6KDiFXHDBBfr0pz+9/vdqtaq5uTm98pWv1Be+8IUNHBmCdsaetu12uxs9BJyifvSjHx25Gw0A/CssLS2pUChs9DBwCur1etzC7wx1xhZt4Pn8+Mc/Xr9NJAD8sgqFAkUbwFEo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADQrOzs8fcoFAoqN/vy7Is44MJMqtUKmlubk7RaNR41tLSktrttmzbNp5VLBbleZ5CoVAgWa7rBpK1vLwsx3EUDoeNZ62srGh+fl6e5xnPKpVKqtVqgczDUqmkVCqlWCxmPKtcLiuZTAaStbq6qng8rng8bjyrXq/LdV0VCgUlk0mjWdVqVeFw2HjORuTVajXZtq1UKmU8q16vy7IsVatV41mLi4vq9/s63rp6MjSbTfV6PdXr9cCyGo2G8SzHcdTpdAL5dN5WqyXf9wP5gLKFhQUVi8VA5obrunJdV61Wy3iW53lyHEeu6xrP8n1fjUYjkLW53W6rVqvJ9/0T3ldoenr6mBtYlqXJyclAym+QWblcTlNTU4EUAdu2NT4+HkjRDoVCGh0dDaT8hsNh5fP5QMpvJBJRNptVJBIxnpXP5zUxMaHR0VHjWbFYTJlMJpB5GI/HlU6nAymkiURCyWRSiURiU2UNDg7Ktm1t3bpVx3vuPFGpVErRaDSQMipJ6XRa4XBY6XTaeFalUpFt2xocHDSeVa1WZVmWMpmM8axyuax+v298bkhHDiB6vZ6GhoaMZzUaDXU6HQ0PDxvPajab8n1f2Ww2kCzP85TL5YxndbtddTqdQOZGq9WS4zjK5/PGs1zXVaPR0MjIiPEsz/NUq9UCWZt931elUtHY2NgJ74tLRwAAAAADKNoAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMICiDQAAABhA0QYAAAAMoGgDAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADQrOzs8fcoFAoqN/vy7Is44MJMqtUKmlubk7RaNR41tLSktrttmzbNp5VLBbleZ5CoVAgWa7rBpK1vLwsx3EUDoeNZ62srGh+fl6e5xnPKpVKqtVqgczDUqmkVCqlWCxmPKtcLiuZTAaStbq6qng8rng8bjyrXq/LdV0VCgUlk0mjWdVqVeFw2HjORuTVajXZtq1UKmU8q16vy7IsVatV41mLi4vq9/s63rp6MjSbTfV6PdXr9cCyGo2G8SzHcdTpdNRsNo1ntVot+b4vx3GMZy0sLKhYLAYyN1zXleu6arVaxrM8z5PjOHJd13iW7/tqNBqBrM3tdlu1Wk2+75/wvkLT09PH3MCyLE1OTgZSfoPMyuVympqaCqQI2Lat8fHxQIp2KBTS6OhoIOU3HA4rn88HUn4jkYiy2awikYjxrHw+r4mJCY2OjhrPisViymQygczDeDyudDodSCFNJBJKJpNKJBKbKmtwcFC2bWvr1q063nPniUqlUopGo4GUUUlKp9MKh8NKp9PGsyqVimzb1uDgoPGsarUqy7KUyWSMZ5XLZfX7feNzQzpyANHr9TQ0NGQ8q9FoqNPpaHh42HhWs9mU7/vKZrOBZHmep1wuZzyr2+2q0+kEMjdarZYcx1E+nzee5bquGo2GRkZGjGd5nqdarRbI2uz7viqVisbGxk54X1w6AgAAABhA0QYAAAAMoGgDAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMICiDQAAABgQmp2dPeYGhUJB/X5flmUZH0yQWaVSSXNzc4pGo8azlpaW1G63Zdu28axisSjP8xQKhQLJcl03kKzl5WU5jqNwOGw8a2VlRfPz8/I8z3hWqVRSrVYLZB6WSiWlUinFYjHjWeVyWclkMpCs1dVVxeNxxeNx41n1el2u66pQKCiZTBrNqlarCofDxnM2Iq9Wq8m2baVSKeNZ9XpdlmWpWq0az1pcXFS/39fx1tWTodlsqtfrqV6vB5bVaDSMZzmOo06no2azaTyr1WrJ9305jmM8a2FhQcViMZC54bquXNdVq9UynuV5nhzHkeu6xrN831ej0QhkbW6326rVavJ9/4T3FZqenj7mBpZlaXJyMpDyG2RWLpfT1NRUIEXAtm2Nj48HUrRDoZBGR0cDKb/hcFj5fD6Q8huJRJTNZhWJRIxn5fN5TUxMaHR01HhWLBZTJpMJZB7G43Gl0+lACmkikVAymVQikdhUWYODg7JtW1u3btXxnjtPVCqVUjQaDaSMSlI6nVY4HFY6nTaeValUZNu2BgcHjWdVq1VZlqVMJmM8q1wuq9/vG58b0pEDiF6vp6GhIeNZjUZDnU5Hw8PDxrOazaZ831c2mw0ky/M85XI541ndbledTieQudFqteQ4jvL5vPEs13XVaDQ0MjJiPMvzPNVqtUDWZt/3ValUNDY2dsL74tIRAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMICiDQAAABhA0QYAAAAMoGgDAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAARRtAAAAwIDQ7OzsMTcoFArq9/uyLMv4YILMKpVKmpubUzQaNZ61tLSkdrst27aNZxWLRXmep1AoFEiW67qBZC0vL8txHIXDYeNZKysrmp+fl+d5xrNKpZJqtVog87BUKimVSikWixnPKpfLSiaTgWStrq4qHo8rHo8bz6rX63JdV4VCQclk0mhWtVpVOBw2nrMRebVaTbZtK5VKGc+q1+uyLEvVatV41uLiovr9vo63rp4MzWZTvV5P9Xo9sKxGo2E8y3EcdTodNZtN41mtVku+78txHONZCwsLKhaLgcwN13Xluq5arZbxLM/z5DiOXNc1nuX7vhqNRiBrc7vdVq1Wk+/7J7yv0PT09DE3sCxLk5OTgZTfILNyuZympqYCKQK2bWt8fDyQoh0KhTQ6OhpI+Q2Hw8rn84GU30gkomw2q0gkYjwrn89rYmJCo6OjxrNisZgymUwg8zAejyudTgdSSBOJhJLJpBKJxKbKGhwclG3b2rp1q4733HmiUqmUotFoIGVUktLptMLhsNLptPGsSqUi27Y1ODhoPKtarcqyLGUyGeNZ5XJZ/X7f+NyQjhxA9Ho9DQ0NGc9qNBrqdDoaHh42ntVsNuX7vrLZbCBZnucpl8sZz+p2u+p0OoHMjVarJcdxlM/njWe5rqtGo6GRkRHjWZ7nqVarBbI2+76vSqWisbGxE94Xl44AAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyjaAM5ojuNo7969sizrqD933XXXRg8NAHCaC230AABgIy0sLMh1Xf3u7/6u9uzZs/74rl27NnBUAIDNgKIN4Iy2sLCgZDKpSy+9VFdeeeVGDwcAsIlw6QiAM1qhUFAikdDg4OBGDwUAsMlQtAGc0RYWFjQ3N6cPfOADmpyc1Etf+lLdfffdajQaGz00AMBpjktHAJwR1tbW1Gw25fu+JCkUCimZTGphYUGFQkFvfetb9ZKXvET33nuvPvaxj2lgYEBveMMbFArxNAkA+P/DGW0AZwTXdXX99dcrn88rn89rz549euihh/Txj39cjzzyiD74wQ/q8ssv1x/90R/phS98oR555BEVCoWNHjYA4DQWeuCBB465wfLyskZGRgIZzMrKinK5nCzLMp715JNP6sEHH1QkEjGeVSqVNDw8rIEB88c15XJZW7ZskW3bxrNWV1c1ODgYyBm/ILN+8IMfqNvtamhoyHhWpVJRKpVSOBw2nlWtVpVIJAKZ87VaTbFYTNFodMOzLMvS6OiopqamdMstt+g973mPJCmdTuvss89WMpmUdOT/Tq1aUy6fUz6fl+/7qlarchxHxWJRvV5PP/3pT+V5nh555BEtLi4a/b4ajYZCoZDi8bjRnI3IazabGhgYUCKRMJ7lOI4krf+eTXrmmWe0tramWq1mPKvVaqnf7yuVShnPcl1X3W5X6XR6U2V5nqd2ux3I+zMKhYKKxaLxHEnyfV+e5ymTyRjParfbarVa2rJly6bK6nQ6ajabJ6UHhLZt23bMDSzL0vj4eCDlN8isLVu2aOvWrYEUAdu2lc/nAym/oVBI2Ww2kEIaZFY4HNbQ0FAghTSbzWp8fFzZbNZ4VjQaVTqdDmQeRqNRpVIpxWIx41mxWEzJZDKQrHg8vv7n+YRCIXmepx07dujss8+WdOT/ZafT0fXXX6/p6Wnt27dPU9NTchxHi4uL2r59u7Zs2aJQKKSBgQGtra0pmUxqYGBAIyMjOt5z54mqVqsKh8OBFMSf5YVCoUCKW61Wk23bgWTV63VZlhVIcavVaur3+8bnhnTkYKXX6wVSpoLMchxHnU4nkDLVarXk+34gJ1V6vZ56vV4gc8N1Xbmuq+HhYeNZnufJcZxA1kvf99VoNJTL5Yxntdtt1Wo15fP5E95X6Nxzzz3mBolEQpOTk4GU3yCztm7dqnPOOSeQIpBKpTQ+Ph5I0U6n0xodHQ2k/A4ODiqfzwdSfjOZjLLZbCBnY5966int2LFDo6OjxrOKxaIymUwg83B5eVnpdDqQM5YrKytKJpOBnLE8kaxwOKxdu3bpL//yLzU8PKxXvOIVuvvuuzU7O6vrrrtOU1NTR20/PDwsx3E0MzOj4z13nqhyubx+cBSE1dVVhcPhQApppVKRbduBnEmsVquyLCuQkvizs8ym54Z05ACi1+sFUhIbjYY6nU4gxe1n76MIorg1m015nhdIcQuHw7JtO5C50Wq15DjOSSmJx+O6rhqNRiBXPniep1qtFsja7Pu+KpWKxsbGTnhfvMsHwBntPe95j2KxmD772c/qlltu0fnnn6+bb75Zl1122UYPDQBwmqNoAzijJZNJ3XDDDbrhhhs2eigAgE2Gu44AAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMCA0Ozt7zA0KhYL6/b4syzI+mCCzSqWS5ubmFI1GjWctLS2p3W7Ltm3jWcViUZ7nKRQKBZLlum4gWcvLy3IcR+Fw2HjWysqK5ufn5Xme8axSqaRarRbIPCyVSkqlUorFYsazyuWykslkIFmrq6uKx+OKx+PGs+r1ulzXVaFQUDKZNJpVrVYVDoeN52xEXq1Wk23bSqVSxrPq9bosy1K1WjWetbi4qH6/r+OtqydDs9lUr9dTvV4PLKvRaBjPchxHnU5HzWbTeFar1ZLv+3Icx3jWwsKCisViIHPDdV25rqtWq2U8y/M8OY4j13WNZ/m+r0ajEcja3G63VavV5Pv+Ce8rND09fcwNLMvS5ORkIOU3yKxcLqepqalAioBt2xofHw+kaIdCIY2OjgZSfsPhsPL5fCDlNxKJKJvNKhKJGM/K5/OamJjQ6Oio8axYLKZMJhPIPIzH40qn04EU0kQioWQyqUQisamyBgcHZdu2tm7dquM9d56oVCqlaDQaSBmVpHQ6rXA4rHQ6bTyrUqnItm0NDg4az6pWq7IsS5lMxnhWuVxWv983PjekIwcQvV5PQ0NDxrMajYY6nY6Gh4eNZzWbTfm+r2w2G0iW53nK5XLGs7rdrjqdTiBzo9VqyXEc5fN541mu66rRaGhkZMR4lud5qtVqgazNvu+rUqlobGzshPfFpSMAAACAARRtAAAAwACKNgAAAGAARRsAAAAwgKINAAAAGEDRBgAAAAygaAMAAAAGULQBAAAAAyjaAAAAgAEUbQAAAMAAijYAAABgAEUbAAAAMICiDQAAABhA0QYAAAAMoGgDAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADCAog0AAAAYQNEGAAAADKBoAwAAAAZQtAEAAAADKNoAAACAAaHZ2dljblAoFNTv92VZlvHBBJlVKpU0NzenaDRqPGtpaUntdlu2bRvPKhaL8jxPoVAokCzXdQPJWl5eluM4CofDxrNWVlY0Pz8vz/OMZ5VKJdVqtUDmYalUUiqVUiwWM55VLpeVTCYDyVpdXVU8Hlc8HjeeVa/X5bquCoWCksmk0axqtapwOGw8ZyPyarWabNtWKpUynlWv12VZlqrVqvGsxcVF9ft9HW9dPRmazaZ6vZ7q9XpgWY1Gw3iW4zjqdDpqNpvGs1qtlnzfl+M4xrMWFhZULBYDmRuu68p1XbVaLeNZnufJcRy5rms8y/d9NRqNQNbmdrutWq0m3/dPeF+h6enpY25gWZYmJycDKb9BZuVyOU1NTQVSBGzb1vj4eCBFO+75LtkAAAEWSURBVBQKaXR0NJDyGw6Hlc/nAym/kUhE2WxWkUjEeFY+n9fExIRGR0eNZ8ViMWUymUDmYTweVzqdDqSQJhIJJZNJJRKJTZU1ODgo27a1detWHe+580SlUilFo9FAyqgkpdNphcNhpdNp41mVSkW2bWtwcNB4VrValWVZymQyxrPK5bL6/b7xuSEdOYDo9XoaGhoyntVoNNTpdDQ8PGw8q9lsyvd9ZbPZQLI8z1MulzOe1e121el0ApkbrVZLjuMon88bz3JdV41GQyMjI8azPM9TrVYLZG32fV+VSkVjY2MnvC8uHQEAAAAMoGgDAAAABlC0AQAAAAMo2gAAAIABFG0AAADAAIo2AAAAYABFGwAAADDg/wLgVTFF28sRmAAAAABJRU5ErkJggg=="
    }
   },
   "cell_type": "markdown",
   "id": "3b67bf1a",
   "metadata": {},
   "source": [
    "## VRP con Entrega y Recogida (VRPPD)\n",
    "\n",
    "Para ejemplicar esta variante, se considera un VRP en el que cada vehículo recoge artículos en varios lugares y los deja en otros. El problema es asignar rutas para que los vehículos recojan y entreguen todos los artículos, minimizando la longitud de la ruta más larga. Se analiza un ejemplo con 6 ubicaciones y un depósito en $(0,0)$. Además, existen artículos en las posiciones $1,2,3$ que deben ser recogidos y entregados en las posiciones $4,5$ y $6$. \n",
    "\n",
    "Se deben recoger artículos en la ubicación $1$ y ser entregados en la ubicación $6$.\n",
    "\n",
    "Se deben recoger artículos en la ubicación $2$ y ser entregados en la ubicación $5$.\n",
    "\n",
    "Se deben recoger artículos en la ubicación $3$ y ser entregados en la ubicación $4$.\n",
    "\n",
    "En  una ruta, 1 se visita antes que $6$, $2$ antes que $5$ y $3$ antes que $4$.\n",
    "\n",
    "Las ubicaciones tiene las siguientes coordenadas:\n",
    "- Depósito: $(0,0)$\n",
    "- 1: $(2,6)$\n",
    "- 2: $(-6,4)$\n",
    "- 3: $(8,6)$\n",
    "- 4: $(4,2)$\n",
    "- 5: $(4,4)$\n",
    "- 6: $(-4,8)$\n",
    "\n",
    "Se tienen dos vehículos.\n",
    "\n",
    "Para enfocarse en el tipo de restricción de esta variante de VRP no se tiene en cuanta las capacidades de los vehículos; o sea, se asume que siempre tienen capacidad.\n",
    "\n",
    "En la siguiente figura se ilustra la situación:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a517625c",
   "metadata": {},
   "source": [
    "<img src=\"vprppd_locations.png\" width=500 height=400 />"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f9b1114",
   "metadata": {},
   "source": [
    "### Solución mediante Or-Tools\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f3a58cf",
   "metadata": {},
   "source": [
    "**Creando los datos**\n",
    "\n",
    "Las distancias entre ubicaciones son números reales. Sin embargo, Or-Tools trabaja con pesos enteros en las aristas del grafo del modelo. Por esto, en la función de distancia a continuación se redondean las distancias hasta 2 lugares después de la coma y se escalan por un factor de 100.\n",
    "\n",
    "Precalcular la matriz de distancias entre ubicaciones es útil porque es más eficiente que calcular las distancias varias veces en tiempo de ejecución por el *solver*.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "488d395f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'distance_matrix': [[0, 632, 721, 1000, 447, 566, 894],\n",
       "  [632, 0, 825, 600, 447, 283, 632],\n",
       "  [721, 825, 0, 1414, 1019, 1000, 447],\n",
       "  [1000, 600, 1414, 0, 566, 447, 1217],\n",
       "  [447, 447, 1019, 566, 0, 200, 1000],\n",
       "  [566, 283, 1000, 447, 200, 0, 894],\n",
       "  [894, 632, 447, 1217, 1000, 894, 0]],\n",
       " 'num_vehicles': 2,\n",
       " 'depot': 0,\n",
       " 'pickups_deliveries': [[1, 6], [2, 5], [3, 4]]}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "def create_data():\n",
    "    data = {}\n",
    "    locations = [(0,0), (2,6), (-6,4), (8,6), (4,2), (4,4), (-4,8)]\n",
    "    def distance(i, j):\n",
    "        x1,y1 = locations[i]\n",
    "        x2,y2 = locations[j]\n",
    "        d = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)\n",
    "        d = (round(d, 2))\n",
    "        return int(d * 100)\n",
    "    data['distance_matrix'] = [[distance(i, j) for i in range(len(locations))] for j in range(len(locations))]\n",
    "    data['num_vehicles'] = 2\n",
    "    data['depot'] = 0\n",
    "    data['pickups_deliveries'] = [\n",
    "        [1,6],\n",
    "        [2,5],\n",
    "        [3,4]\n",
    "    ]\n",
    "    return data\n",
    "\n",
    "create_data()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad6472a6",
   "metadata": {},
   "source": [
    "**Importando las librerías**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "86e24fd8",
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.constraint_solver import routing_enums_pb2\n",
    "from ortools.constraint_solver import pywrapcp"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4293a0e4",
   "metadata": {},
   "source": [
    "**Definiendo el solver y las variables**\n",
    "\n",
    "Con los datos creados se puede definir un modelo de Or-Tools para ser resuelto.\n",
    "\n",
    "El *solver* se declara con la línea `routing = pywrapcp.RoutingModel(manager)`\n",
    "\n",
    "El Manager en Or-Tools se encarga de la administración de los índices de las ubicaciones, variables internas del *solver*. Convierte los índices internos del *solver* a índices en ubicaciones de la matriz de distancias.\n",
    "\n",
    "Las entradas del método `RoutingIndexManager` son: \n",
    "- La cantidad de ubicaciones\n",
    "- El número de vehículos\n",
    "- La ubicación del depósito"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "3480fd11",
   "metadata": {},
   "outputs": [],
   "source": [
    "data = create_data()\n",
    "number_of_locations = len(data['distance_matrix'])\n",
    "manager = pywrapcp.RoutingIndexManager(\n",
    "    number_of_locations,\n",
    "    data['num_vehicles'],\n",
    "    data['depot']\n",
    ")\n",
    "routing = pywrapcp.RoutingModel(manager)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66460a9b",
   "metadata": {},
   "source": [
    "Hasta aquí se han definido los nodos del grafo, la cantidad de vehículos y el nodo que representa el depósito. Ahora se define el costo de las aristas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9b1856e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance_callback(from_index, to_index):\n",
    "    from_node = manager.IndexToNode(from_index)\n",
    "    to_node = manager.IndexToNode(to_index)\n",
    "    return data['distance_matrix'][from_node][to_node]\n",
    "\n",
    "transit_callback_index = routing.RegisterTransitCallback(distance_callback)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "104175ab",
   "metadata": {},
   "source": [
    "El método `RegisterTransitCallback` registra en el *solver* una función que relaciona dos ubicaciones $(i,j)$. Esta relación entre $(i,j)$ puede ser la distancia entre $i$ y $j$, el tiempo de viaje de $i$ a $j$ o cualquier otra medida de interés. En general, registra una función de la forma $(int,int) \\rightarrow (int)$. En este caso se registró la función distancia entre nodos.\n",
    "\n",
    "En la función `distance_callback` se usa el `manager` para convertir los índices internos del *solver* a los índices respectivos que representan las ubicaciones.\n",
    "\n",
    "Pero solo se ha registrado la función. Para definir el costo de un viaje se puede usar la función registrada `transit_callback_index` en la siguiente línea:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "e17f044f",
   "metadata": {},
   "outputs": [],
   "source": [
    "routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b948dda9",
   "metadata": {},
   "source": [
    "Ahora para todos los vehículos el costo de ir de la ubicación $i$ a la ubicación $j$ está dado por la distancia de $i$ a $j$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "09d00621",
   "metadata": {},
   "source": [
    "Entonces, se tiene un grafo con las ubicaciones y el costo de ir de una ubicación a otra, por lo que se tiene el problema de encontrar las rutas con la mínima distancia total. Sin embargo, la solución óptima para este tipo de problema es asignar un solo vehículo para visitar todas las ubicaciones y encontrar la ruta más corta para ese vehículo. Este es esencialmente el mismo problema que el TSP.  Una mejor manera de definir rutas óptimas es minimizar la longitud de la ruta más larga entre todos los vehículos. Generalmente se utiliza esta vía ya que, en la práctica, muchas veces el objetivo es completar todas las entregas lo antes posible.\n",
    "\n",
    "Para transformar el problema a uno de minimizar la longitud da la ruta más larga es necesario, para cada ruta tomada por los vehículos, saber cuánta distancia el vehículo recorrió en esa ruta específica. Esto se diferencia del problema de minimizar la distancia total de todas las rutas, en el que no importa la distancia de una ruta específica, sino del conjunto en total.\n",
    "\n",
    "Para lograr esto Or-Tools posee una característica llamada **dimensiones**. \n",
    "\n",
    "El *solver* utiliza un objeto llamado `dimensión` para realizar un seguimiento de las cantidades que se acumulan a lo largo de la ruta de un vehículo, como el tiempo de viaje o, si el vehículo realiza recolecciones y entregas, el peso total que transporta. Si un problema de enrutamiento involucra tal cantidad, ya sea en las restricciones o en la función objetivo, debe definir una dimensión para especificarlas [4].\n",
    "\n",
    "En este caso nos interesa saber la distancia acumulada de una ruta específica."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e43357f7",
   "metadata": {},
   "source": [
    "**Definiendo las restricciones y función objetivo**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d502f608",
   "metadata": {},
   "source": [
    "Se modifica la función objetivo para minimizar la longitud de la ruta más larga, añadiendo una dimensión:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "354ba9be",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dimension_name = 'Distance'\n",
    "INFINITE = 100000\n",
    "routing.AddDimension(\n",
    "    transit_callback_index,\n",
    "    0,  \n",
    "    INFINITE, \n",
    "    True, \n",
    "    dimension_name)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e849417",
   "metadata": {},
   "source": [
    "El método `AddDimension` recibe:\n",
    "- Una función `TransitCallback` de la forma $(int,int) \\rightarrow (int)$ anteriormente descrita\n",
    "- *slack*: Una variable que representa el tiempo de espera de un vehículo cuando visita una ubicación, en este caso no se considera por lo que su valor es $0$\n",
    "- *capacity*: El máximo de la cantidad acumulada en la ruta. Por ejemplo, si se está midiendo distancia sería la máxima distancia posible en una ruta. Si se estuviese contando la carga del vehículo, la carga máxima que puede llevar el vehículo en una ruta. Si es tiempo, el tiempo máximo que puede demorar una ruta, etcétera\n",
    "- *fix_start_cumulative_to_zero*: Si es `True`, la cantidad acumulada se inicializa en $0$\n",
    "- El nombre de la dimensión definida\n",
    "\n",
    "La dimensión definida **Distance** cuenta la distancia recorrida en una ruta. Por ejemplo, si un vehículo toma la ruta $1 \\rightarrow 2 \\rightarrow 3$, la dimensión **Distance** será: \n",
    "$$\n",
    "transit\\_callback\\_index(1,2) + transit\\_callback\\_index(2,3)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfcf6da7",
   "metadata": {},
   "source": [
    "Para cada ruta escogida de los vehículos, se calcula la distancia recorrida. Por cada distancia calculada se modifica la función objetivo sumándole tal distancia multiplicada por un coeficiente alto. De esta manera, la función objetivo cambia de forma que se pueda minimizar la mayor distancia entre todas las rutas.\n",
    "\n",
    "Para dos vehículos, si $d_1$ es la distancia recorrida por el vehículo 1 y $d_2$ es la distancia recorrida por el vehículo 2 en sus respectivas rutas, entonces se modifica la función objetivo:\n",
    "$$\n",
    "    F'(x) = F(x) + cd_1 + cd_2 \n",
    "$$\n",
    "Donde $c$ es un coeficiente muy alto relativo al problema que se esté tratando.\n",
    "\n",
    "Esta idea se implementa de la siguiente forma:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "38d3079d",
   "metadata": {},
   "outputs": [],
   "source": [
    "distance_dimension = routing.GetDimensionOrDie(dimension_name)\n",
    "distance_dimension.SetGlobalSpanCostCoefficient(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "930674f2",
   "metadata": {},
   "source": [
    "\n",
    "El método `GetDimensionOrDie` retorna la dimensión buscada o lanza excepción en caso de no encontrarla.\n",
    "\n",
    "El método `SetGlobalSpanCostCoefficient` implementa la idea mencionada de los coeficientes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76e0efc1",
   "metadata": {},
   "source": [
    "Ahora solo falta definir la restricción:  **En  una ruta, $1$ se visita antes que $6$, $2$ antes que $5$ y $3$ antes que $4$.**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a4bd70d2",
   "metadata": {},
   "source": [
    "En este caso es díficil usar dimensiones, puesto que esta restricción no tiene forma acumulativa en la ruta. Para ello, Or-Tools tiene el método `AddPickupAndDelivery(i, j)`. Este método notifica al *solver* que las ubicaciones $i$ y $j$ deben estar siempre en la misma ruta. Luego, hay que asegurar que la ubicación $i$ sea visitada antes que la $j$ y además, por el mismo vehículo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "970b4a8e",
   "metadata": {},
   "outputs": [],
   "source": [
    "for request in data['pickups_deliveries']:\n",
    "    pickup_index = manager.NodeToIndex(request[0])\n",
    "    delivery_index = manager.NodeToIndex(request[1])\n",
    "    routing.AddPickupAndDelivery(pickup_index, delivery_index)\n",
    "    routing.solver().Add(\n",
    "        routing.VehicleVar(pickup_index) == routing.VehicleVar(\n",
    "                delivery_index))\n",
    "    routing.solver().Add(\n",
    "            distance_dimension.CumulVar(pickup_index) <=\n",
    "            distance_dimension.CumulVar(delivery_index))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0647e9c1",
   "metadata": {},
   "source": [
    "```\n",
    "routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))\n",
    "```\n",
    "La ubicación de recogida y entrega para un artículo es hecha por el mismo vehículo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f09203ba",
   "metadata": {},
   "source": [
    "```\n",
    "routing.solver().Add(distance_dimension.CumulVar(pickup_index) <= distance_dimension.CumulVar(delivery_index))\n",
    "```\n",
    "\n",
    "La ubicación de recogida se visita antes que la ubicación de entrega."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "060467e4",
   "metadata": {},
   "source": [
    "Solo resta llamar al método `SolveWithParameters` del *solver* para resolver el problema. Para ello es necesario:\n",
    "- Definir los parámetros: Se seleccionan los parámetros por defecto\n",
    "- Definir una heurística para encontrar una primera solución: Se selecciona una estrategia Greedy que construya la ruta seleccionando la arista con menor costo de forma iterativa\n",
    "\n",
    "Diferentes métodos heurísticos para encontrar la primera solución pueden influir en el tiempo de ejecución."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "2a21e4c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "search_parameters = pywrapcp.DefaultRoutingSearchParameters()\n",
    "search_parameters.first_solution_strategy = (\n",
    "    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4862e14",
   "metadata": {},
   "source": [
    "**Obteniendo la solución**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "f3d12c28",
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = routing.SolveWithParameters(search_parameters)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "deccea62",
   "metadata": {},
   "source": [
    "**Imprimiendo la solución**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "5b8421bd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Objective: 3186339\n",
      "Route for vehicle 0:\n",
      " 0 ->  2 ->  5 ->  3 ->  4 -> 0\n",
      "Distance of the route: 3181m\n",
      "\n",
      "Route for vehicle 1:\n",
      " 0 ->  1 ->  6 -> 0\n",
      "Distance of the route: 2158m\n",
      "\n",
      "Total Distance of all routes: 5339m\n"
     ]
    }
   ],
   "source": [
    "def print_solution(data, manager, routing, solution):\n",
    "    \"\"\"Prints solution on console.\"\"\"\n",
    "    print(f'Objective: {solution.ObjectiveValue()}')\n",
    "    total_distance = 0\n",
    "    for vehicle_id in range(data['num_vehicles']):\n",
    "        index = routing.Start(vehicle_id)\n",
    "        plan_output = 'Route for vehicle {}:\\n'.format(vehicle_id)\n",
    "        route_distance = 0\n",
    "        while not routing.IsEnd(index):\n",
    "            plan_output += ' {} -> '.format(manager.IndexToNode(index))\n",
    "            previous_index = index\n",
    "            index = solution.Value(routing.NextVar(index))\n",
    "            route_distance += routing.GetArcCostForVehicle(\n",
    "                previous_index, index, vehicle_id)\n",
    "        plan_output += '{}\\n'.format(manager.IndexToNode(index))\n",
    "        plan_output += 'Distance of the route: {}m\\n'.format(route_distance)\n",
    "        print(plan_output)\n",
    "        total_distance += route_distance\n",
    "    print('Total Distance of all routes: {}m'.format(total_distance))\n",
    "\n",
    "print_solution(data, manager, routing, solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54667df0",
   "metadata": {},
   "source": [
    "### Añadiendo capacidad al problema"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6087064a",
   "metadata": {},
   "source": [
    "Se supone ahora que en las ubicaciones $1,2$ y $3$ se recogen artículos con una capacidad de $c_1$, $c_2$ y $c_3$ respectivamente. Las ubicaciones $6,5$ y $4$ tendrán capacidades $c_6 = - c_1$, $c_5 = - c_2$ y $c_4 = - c_3$. O sea, todo lo recogido en una ubicación se entrega en su ubicación correspondiente. Los vehículos tienen una capacidad máxima $v_1$ y $v_2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "79b239a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def create_data():\n",
    "    data = {}\n",
    "    locations = [(0,0), (2,6), (-6,4), (8,6), (4,2), (4,4), (-4,8)]\n",
    "    def distance(i, j):\n",
    "        x1,y1 = locations[i]\n",
    "        x2,y2 = locations[j]\n",
    "        d = math.sqrt((x1- x2) **2 + (y1-y2)**2)\n",
    "        d = (round(d,2))\n",
    "        return int(d * 100)\n",
    "    data[\"distance_matrix\"] = [[distance(i,j) for i in range(len(locations))] for j in range(len(locations))]\n",
    "    data['num_vehicles'] = 2\n",
    "    data['depot'] = 0\n",
    "    data['pickups_deliveries'] = [\n",
    "        [1,6],\n",
    "        [2,5],\n",
    "        [3,4]\n",
    "    ]\n",
    "    data['demands'] = [0, 2,5,10,-10,-5,-2] # [c0,c1,c2,c3,c4,c5,c6]\n",
    "    data['vehicle_capacities'] = [5, 10] # [v1, v2]\n",
    "    return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "47e38fc7",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "data = create_data()\n",
    "number_of_locations = len(data['distance_matrix'])\n",
    "manager = pywrapcp.RoutingIndexManager( number_of_locations,\n",
    "                                       data['num_vehicles'], data['depot'])\n",
    "routing = pywrapcp.RoutingModel(manager)\n",
    "\n",
    "def distance_callback(from_index, to_index):\n",
    "    from_node = manager.IndexToNode(from_index)\n",
    "    to_node = manager.IndexToNode(to_index)\n",
    "    return data['distance_matrix'][from_node][to_node]\n",
    "\n",
    "transit_callback_index = routing.RegisterTransitCallback(distance_callback)\n",
    "routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)\n",
    "\n",
    "dimension_name = 'Distance'\n",
    "INFINITE = 100000\n",
    "routing.AddDimension(\n",
    "    transit_callback_index,\n",
    "    0,  \n",
    "    INFINITE, \n",
    "    True, \n",
    "    dimension_name)\n",
    "\n",
    "distance_dimension = routing.GetDimensionOrDie(dimension_name)\n",
    "distance_dimension.SetGlobalSpanCostCoefficient(1000)\n",
    "\n",
    "for request in data['pickups_deliveries']:\n",
    "    pickup_index = manager.NodeToIndex(request[0])\n",
    "    delivery_index = manager.NodeToIndex(request[1])\n",
    "    routing.AddPickupAndDelivery(pickup_index, delivery_index)\n",
    "    routing.solver().Add(\n",
    "        routing.VehicleVar(pickup_index) == routing.VehicleVar(\n",
    "                delivery_index))\n",
    "    routing.solver().Add(\n",
    "            distance_dimension.CumulVar(pickup_index) <=\n",
    "            distance_dimension.CumulVar(delivery_index))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f449af6",
   "metadata": {},
   "source": [
    "En este caso hay que añadir otra dimensión correspondiente a la demanda de cada ubicación. Con esta dimensión se pueden comprobar las restricciones de capacidad sobre los vehículos dada una ruta."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "ea7bc803",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def demand_callback(from_index):\n",
    "    from_node = manager.IndexToNode(from_index)\n",
    "    return data['demands'][from_node]\n",
    "\n",
    "demand_callback_index = routing.RegisterUnaryTransitCallback(\n",
    "    demand_callback)\n",
    "routing.AddDimensionWithVehicleCapacity(\n",
    "    demand_callback_index,\n",
    "    0,  # null capacity slack\n",
    "    data['vehicle_capacities'], \n",
    "    True,  \n",
    "    'Capacity')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb443163",
   "metadata": {},
   "source": [
    "El método `AddDimensionWithVehicleCapacity` es análogo al método `AddDimension`. La única diferencia es que puede recibir un array de capacidades para definir la capacidad máxima para cada vehículo por separado."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "21e322df",
   "metadata": {},
   "outputs": [],
   "source": [
    "search_parameters = pywrapcp.DefaultRoutingSearchParameters()\n",
    "search_parameters.first_solution_strategy = (\n",
    "    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "dbe77485",
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = routing.SolveWithParameters(search_parameters)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "f732daf3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Objective: 3186339\n",
      "Route for vehicle 0:\n",
      " 0 Load(0) ->  1 Load(2) ->  6 Load(0) ->  0 Load(0)\n",
      "Distance of the route: 2158m\n",
      "Load of the route: 0\n",
      "\n",
      "Route for vehicle 1:\n",
      " 0 Load(0) ->  2 Load(5) ->  5 Load(0) ->  3 Load(10) ->  4 Load(0) ->  0 Load(0)\n",
      "Distance of the route: 3181m\n",
      "Load of the route: 0\n",
      "\n",
      "Total distance of all routes: 5339m\n",
      "Total load of all routes: 0\n"
     ]
    }
   ],
   "source": [
    "def print_solution(data, manager, routing, solution):\n",
    "    \"\"\"Prints solution on console.\"\"\"\n",
    "    print(f'Objective: {solution.ObjectiveValue()}')\n",
    "    total_distance = 0\n",
    "    total_load = 0\n",
    "    for vehicle_id in range(data['num_vehicles']):\n",
    "        index = routing.Start(vehicle_id)\n",
    "        plan_output = 'Route for vehicle {}:\\n'.format(vehicle_id)\n",
    "        route_distance = 0\n",
    "        route_load = 0\n",
    "        while not routing.IsEnd(index):\n",
    "            node_index = manager.IndexToNode(index)\n",
    "            route_load += data['demands'][node_index]\n",
    "            plan_output += ' {0} Load({1}) -> '.format(node_index, route_load)\n",
    "            previous_index = index\n",
    "            index = solution.Value(routing.NextVar(index))\n",
    "            route_distance += routing.GetArcCostForVehicle(\n",
    "                previous_index, index, vehicle_id)\n",
    "        plan_output += ' {0} Load({1})\\n'.format(manager.IndexToNode(index),\n",
    "                                                 route_load)\n",
    "        plan_output += 'Distance of the route: {}m\\n'.format(route_distance)\n",
    "        plan_output += 'Load of the route: {}\\n'.format(route_load)\n",
    "        print(plan_output)\n",
    "        total_distance += route_distance\n",
    "        total_load += route_load\n",
    "    print('Total distance of all routes: {}m'.format(total_distance))\n",
    "    print('Total load of all routes: {}'.format(total_load))\n",
    "\n",
    "print_solution(data, manager, routing, solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0bc9de6",
   "metadata": {},
   "source": [
    "Note como el vehículo 1 solo puede ir ahora por la ruta $0 \\rightarrow 1 \\rightarrow 6 \\rightarrow 0$, a diferencia del caso anterior."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bb9ecd9",
   "metadata": {},
   "source": [
    "## Referencias"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0bc08f72",
   "metadata": {},
   "source": [
    "[1] Argüelles Terrón G.(2020). Validación Automática de Modelos para Problemas de Enrutamiento de Vehículos. Trabajo de Diploma\n",
    "presentado en opción al título de Licenciado en Ciencia de la Computación. 1-7. \n",
    "\n",
    "[2] https://developers.google.com/optimization/routing\n",
    "\n",
    "[3] https://developers.google.com/optimization/introduction/get_started\n",
    "\n",
    "[4] https://developers.google.com/optimization/routing/dimensions\n",
    "\n",
    "[5] https://developers.google.com/optimization/routing/cvrp"
   ]
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}