resource_assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "406c2750",
   "metadata": {},
   "source": [
    "# Resource Assignment: Optimizing Service Vehicle Allocation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a7e7404",
   "metadata": {},
   "source": [
    "## Motivation\n",
    "\n",
    "Picture Uber Eats, DoorDash, or Grubhub, but also local mom-and-pop restaurants with their own delivery.   \n",
    "Or consider home service providers that have skilled workers like landscapers, plumbers, or electricians.  \n",
    "Or how about home healthcare providers that send licensed professionals like nurses to patients' homes.\n",
    "\n",
    "What do they all have in common?\n",
    "\n",
    "They all involve delivering goods or services. In these businesses, customers place orders and receive a delivery window from the provider (like when Amazon tells you that your overnight package will arrive between 7 am and 10 am). For service-based businesses, like needing a technician to fix something, customers might also provide an availability window (like, \"Can you come tomorrow afternoon, between 1 pm and 4 pm?\").\n",
    "\n",
    "In these diverse businesses, managing limited resources is the name of the game. Whether it's delivery vans, skilled workers, or even time itself, the challenge lies in allocating these limited resources optimally to achieve business goals."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e1e1d95",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "\n",
    "Let's delve into a specific scenario: You are consulting for a telecom company that dispatches technicians to perform various tasks for customers, ranging from equipment installations and setups to repairs. Each technician requires a service vehicle to travel to the job site. Here's what you're dealing with:\n",
    "\n",
    "- The company offers various services, and not all technicians can perform all of them, so matching the right technician to the right job is crucial.\n",
    "- Service times (also known as process times) can vary for different jobs.\n",
    "- Customers provide windows of availability, and each customer is assigned to at most one technician (due to resource constraints).\n",
    "- Technicians have their own working hours. Not all of them work an 8-hour shift, and the job can't surpass these hours (no overtime allowed).\n",
    "- Technicians leave the service centers, complete their assigned jobs, and return to the center.\n",
    "- There are a limited number of vans at the service centers, equipped with the necessary tools. These vans are in shorter supply compared to technicians, and each technician needs a van to reach customers.\n",
    "\n",
    "Currently, basic rule-of-thumb approaches are used for scheduling customers one after another and assigning them to the technicians. Each technician is dispatched with a van as soon as their schedule is known. When a technician returns, the van is up for grabs.\n",
    "\n",
    "Now, let's explore how mathematical optimization can help with the allocation of these limited resources."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f6cde92",
   "metadata": {},
   "source": [
    "## Solution Approach\n",
    "\n",
    "We solve this problem in two steps:\n",
    "\n",
    "### 1. Technician Routing\n",
    "This is a variation of the well-known vehicle routing problem (VRP) with time windows. The goal is to decide which technicians are assigned to which customers and in what sequence. This is modeled and solved in the [`technician_routing`](https://github.com/decision-spot/technician_assignment/blob/main/technician_routing.ipynb) notebook.\n",
    "\n",
    "This model yields two outputs: \n",
    "- `routes` provides some information about each technician's feasible departure window from the service center and their total occupied time.\n",
    "- `orders` provides which customers (or orders) are assigned to which technicians and in what sequence (or in what order). A bit of fun with the file name!\n",
    "\n",
    "_Note:_ The `technician_routing` notebook is almost identical to Gurobi's [`technician_routing_scheduling`](https://colab.research.google.com/github/Gurobi/modeling-examples/blob/master/technician_routing_scheduling/technician_routing_scheduling.ipynb). Since an additional post processing step was required to export the results into csv files, and also some slight modifications in the constraints and objective functions needed to be made, a slightly different file name is used to differentiate between the two. \n",
    "\n",
    "\n",
    "### 2. Resource Allocation\n",
    "Now that we know which technicians serve which customers, we can assign them to the available vans. This is the focus of this notebook.\n",
    "\n",
    "Here, we optimize the allocation of limited resources, ensuring each technician has access to a van equipped with necessary tools to reach customers in time. We're looking at the big picture, reshuffling routes as needed, and making the most of our vans. If a technician can efficiently serve multiple customers, and a service van can be used multiple times per day, we're all in.\n",
    "\n",
    "Let's roll up our sleeves and optimize! 🚚🔧"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed4f7ee5",
   "metadata": {},
   "source": [
    "# Install Required Packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "af590656",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-03T18:20:20.280290Z",
     "start_time": "2023-11-03T18:20:20.276772Z"
    }
   },
   "outputs": [],
   "source": [
    "%pip install gurobipy\n",
    "%pip install pandas"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8bd6f69",
   "metadata": {},
   "source": [
    "# Import Packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4036b5a7",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:12:51.628617Z",
     "start_time": "2023-11-06T20:12:50.874248Z"
    }
   },
   "outputs": [],
   "source": [
    "import gurobipy as gp\n",
    "import pandas as pd\n",
    "from gurobipy import GRB"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c165d441",
   "metadata": {},
   "source": [
    "# Optimization Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0816abcb",
   "metadata": {},
   "source": [
    "We want to minimize the number of resources used, while maximizing the number of customer orders that we cover (i.e., ensuring that we don't turn down a customer).\n",
    "\n",
    "Note that throughout this notebook, we will use _resource_ and _van_ interchangeably, and similarly, we'll interchange _customer_ and _order_.\n",
    "\n",
    "**Assumptions:**  \n",
    "- All the assumptions are the same as those in the `technician_routing` notebook. \n",
    "- Note: the planning horizon is from 7:00 to 17:00, or 10 hours. The time period is in minutes. So, all the times are translated into minutes starting at 0 minutes and ending at 600 minutes. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79287692",
   "metadata": {},
   "source": [
    "## Load Required Data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c63d24f5",
   "metadata": {},
   "source": [
    "**Note**:  \n",
    "If you've cloned the repo or downloaded all the files on your machine, you can simply enter the address of the file to read them (e.g., `'routes.csv'`). For consistency, we use the raw file address on GitHub."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3fd07b80",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:12:53.533340Z",
     "start_time": "2023-11-06T20:12:53.280126Z"
    }
   },
   "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>Route ID</th>\n",
       "      <th>Technician Name</th>\n",
       "      <th>Origin Location</th>\n",
       "      <th>Total Travel Time</th>\n",
       "      <th>Total Processing Time</th>\n",
       "      <th>Total Time</th>\n",
       "      <th>Earliest Start Time</th>\n",
       "      <th>Latest Start Time</th>\n",
       "      <th>Earliest End Time</th>\n",
       "      <th>Latest End Time</th>\n",
       "      <th>Num Jobs</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>Albert</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>334.0</td>\n",
       "      <td>90.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>600.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>Bob</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>100.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>100.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>230.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>Doris</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>141.0</td>\n",
       "      <td>120.0</td>\n",
       "      <td>341.0</td>\n",
       "      <td>58.0</td>\n",
       "      <td>178.0</td>\n",
       "      <td>399.0</td>\n",
       "      <td>519.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>Ed</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>134.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>194.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>113.0</td>\n",
       "      <td>194.0</td>\n",
       "      <td>307.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>Flor</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>90.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>150.0</td>\n",
       "      <td>195.0</td>\n",
       "      <td>315.0</td>\n",
       "      <td>345.0</td>\n",
       "      <td>465.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Route ID Technician Name       Origin Location  Total Travel Time  \\\n",
       "0         1          Albert            Heidelberg              334.0   \n",
       "1         2             Bob            Heidelberg              100.0   \n",
       "2         3           Doris  Freiburg im Breisgau              141.0   \n",
       "3         4              Ed            Heidelberg              134.0   \n",
       "4         5            Flor  Freiburg im Breisgau               90.0   \n",
       "\n",
       "   Total Processing Time  Total Time  Earliest Start Time  Latest Start Time  \\\n",
       "0                   90.0       570.0                  0.0                6.0   \n",
       "1                   30.0       130.0                  0.0              100.0   \n",
       "2                  120.0       341.0                 58.0              178.0   \n",
       "3                   60.0       194.0                  0.0              113.0   \n",
       "4                   60.0       150.0                195.0              315.0   \n",
       "\n",
       "   Earliest End Time  Latest End Time  Num Jobs  \n",
       "0              570.0            600.0         2  \n",
       "1              130.0            230.0         1  \n",
       "2              399.0            519.0         2  \n",
       "3              194.0            307.0         1  \n",
       "4              345.0            465.0         1  "
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "routes = pd.read_csv('https://raw.githubusercontent.com/decision-spot/technician_assignment/main/routes.csv')\n",
    "routes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92328709",
   "metadata": {},
   "source": [
    "We can visualize the lengths of the routes by examining the time span between their start and end times. Since each route has a window for the earliest and latest times, we can plot the earliest time a route can start and finish by calculating the difference between \"Earliest End Time\" and \"Earliest Start Time.\" Similarly, we can plot the latest time a route can start and finish by calculating the difference between \"Latest End Time\" and \"Latest Start Time.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "eb747fc7",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:12:56.631836Z",
     "start_time": "2023-11-06T20:12:55.807396Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA64AAAIhCAYAAABOl+fLAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8pXeV/AAAACXBIWXMAAA9hAAAPYQGoP6dpAABEEklEQVR4nO3dd3gV1d7+/3un9wYJIRAgtEivRwSVIqDUY4GvqCjNFqTIsQIqAQsRFY4ogo8goMeCnkfAdqQJCcIhGJqiWFABQYkoSgIBEpKs3x/+sh83CZBAYFaS9+u65rrYa9ae+exZQbmzZtZ2GWOMAAAAAACwlJfTBQAAAAAAcDoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAI5ZuHChXC6Xe/Px8VHNmjV1ww03aOfOnef9/FOnTtXSpUvP+3lK8tfPffI2bNiwcj1X0XXevXu3u23YsGGqV69euZ7nr5y8tqdT0rUoyeTJk+VyufTbb7+d8zmPHj2qyZMnKzU19ZyPdTr//e9/NXnyZB06dOiMfZ955hm5XC5t3LjRo72wsFBRUVFyuVz65ptvPPbl5eUpKChI1113naTSX8uySE1NlcvlOu/XCgBQ8RBcAThuwYIF2rBhg1atWqXRo0frvffe02WXXaY//vjjvJ7X6XA1cOBAbdiwodj2yCOPnPdzP/LII1qyZMl5O77T19YmR48e1ZQpUy5IcJ0yZUqpgmu3bt0kSWvWrPFo/+yzz/THH38oODi42L6NGzfq2LFj7vf27dtXGzZsUM2aNcvnAwAAcBo+ThcAAM2bN1f79u0lSV27dlVBQYGSk5O1dOlSDR8+3OHqzp8aNWrokksuOW/HP3bsmAICAkrc16BBg/N2XtivTZs2ioiIUGpqqsaPH+9uT01NVVxcnLp06aI1a9YoKSnJY5/0f6E3Ojpa0dHRF7RuAEDVxYwrAOsUhdhffvnFo/29995Tx44dFRQUpNDQUPXs2VMbNmzw6HOqW2CLbv0s4nK5lJOTo1deecV9i27Xrl3d+zMzM3XnnXeqdu3a8vPzU0JCgqZMmaL8/HyP486ZM0etWrVSSEiIQkNDddFFF2nixInneAX+z6ZNm3TDDTeoXr16CgwMVL169XTjjTdqz549Hv2KbttcsWKFRowYoejoaAUFBSk3N7fE45Z0nYwxmj17tlq3bq3AwEBFRkZq4MCB+uGHHzz6bd26Vf369VNMTIz8/f0VFxenvn37at++fZLOfG1LMmXKFHXo0EFRUVEKCwtT27Zt9fLLL8sY49GvXr166tevn5YtW6a2bdsqMDBQF110kebPn1/smOnp6br00ksVEBCguLg4TZgwQSdOnDhtHWXx66+/6q677lLTpk0VEhKimJgYXXHFFfrkk0/cfXbv3u0Od1OmTCnxdvCdO3fqpptucl/PJk2a6IUXXvA4V2FhoR5//HElJiYqMDBQERERatmypWbOnCnpz5/v+++/X5KUkJDgPs+pZnm9vLzUuXNnrV+/3uNnOjU1VV27dlWXLl2KvTc1NVXR0dFq1qyZpJJvFe7atauaN2+ujIwMXX755QoKClL9+vX15JNPqrCw0ON4X3/9tXr16qWgoCBVr15dSUlJOnz4cIn1zp8/X61atVJAQICioqJ07bXX6quvvnLv//DDD+VyuZSRkeFue+edd+RyudS3b1+PY7Vs2VIDBgxwv/73v/+tDh06KDw83F3viBEjSqwDAOAcZlwBWGfXrl2SpMaNG7vb3njjDQ0ePFhXXnml3nzzTeXm5uqpp55S165d9fHHH+uyyy4r0zk2bNigK664Qt26dXPfmhsWFibpz9B68cUXy8vLS5MmTVKDBg20YcMGPf7449q9e7cWLFggSVq0aJHuuusujRkzRs8884y8vLz03XffaceOHaWqwRhTLAhLkre3tztk7969W4mJibrhhhsUFRWl/fv3a86cOfrb3/6mHTt2qHr16h7vHTFihPr27at//etfysnJka+vb6mvyZ133qmFCxdq7NixmjZtmn7//Xc9+uij6tSpkz777DPVqFFDOTk56tmzpxISEvTCCy+oRo0ayszM1Jo1a9yh43TX9lR2796tO++8U3Xq1JH0Z+gcM2aMfvrpJ02aNMmj72effaZ7771X48ePV40aNTRv3jzdeuutatiwoTp37ixJ2rFjh7p376569epp4cKFCgoK0uzZs/XGG2+U+nqcye+//y5JSk5OVmxsrI4cOaIlS5a4fya7du2qmjVratmyZerVq5duvfVW3XbbbZLkDrM7duxQp06dVKdOHU2fPl2xsbFavny5xo4dq99++03JycmSpKeeekqTJ0/Www8/rM6dO+vEiRP6+uuv3bcF33bbbfr999/1/PPPa/Hixe7bd5s2bXrK+rt166b33ntPGRkZ6tixowoLC7V27VpNmzZNnTt31oEDB7Rjxw41bdpUeXl52rBhg/r16+fxC6CSZGZmavDgwbr33nuVnJysJUuWaMKECYqLi9OQIUMk/flLqS5dusjX11ezZ89WjRo19Prrr2v06NHFjpeSkqKJEyfqxhtvVEpKig4ePKjJkyerY8eOysjIUKNGjdzHWrVqlf72t79JklatWqXAwEClpaXpxIkT8vX11YEDB/TFF19o5MiRkv78WR00aJAGDRqkyZMnKyAgQHv27NHq1atL9TMAALiADAA4ZMGCBUaSSU9PNydOnDCHDx82y5YtM7GxsaZz587mxIkTxhhjCgoKTFxcnGnRooUpKChwv//w4cMmJibGdOrUyd02dOhQU7du3WLnSk5ONif/Jy84ONgMHTq0WN8777zThISEmD179ni0P/PMM0aS+fLLL40xxowePdpERESc1WeXdMrtX//61ynfl5+fb44cOWKCg4PNzJkz3e1F13LIkCHF3lO0b9euXe62k6/Thg0bjCQzffp0j/fu3bvXBAYGmgceeMAYY8ymTZuMJLN06dLTfr5TXdvSKCgoMCdOnDCPPvqoqVatmiksLHTvq1u3rgkICPAYm2PHjpmoqChz5513utsGDRpkAgMDTWZmprstPz/fXHTRRcWuRUmKfl5+/fXXUtedn59vTpw4Ybp3726uvfZad/uvv/5qJJnk5ORi77nqqqtM7dq1TVZWlkf76NGjTUBAgPn999+NMcb069fPtG7d+rTnf/rpp0v12Yps27bNSDJTp041xhizefNmI8l8/fXXxhhjatSoYWbNmmWMMSYtLc1IMrNnz3a/v6Sfqy5duhhJZuPGjR7natq0qbnqqqvcrx988EHjcrnMtm3bPPr17NnTSDJr1qwxxhjzxx9/mMDAQNOnTx+Pfj/++KPx9/c3N910k7vtsssuM1dccYX7dcOGDc39999vvLy8TFpamjHGmNdff91IMt9++60x5v/+Th86dKhU1wwA4BxuFQbguEsuuUS+vr4KDQ1Vr169FBkZqXfffVc+Pn/eFPLNN9/o559/1i233CIvr//7z1ZISIgGDBig9PR0HT16tNzq+eCDD9StWzfFxcUpPz/fvfXu3VuSlJaWJkm6+OKLdejQId1444169913y7wC7fXXX6+MjIxiW58+fdx9jhw5ogcffFANGzaUj4+PfHx8FBISopycHI9bJYv89RbIsn5ml8ulm2++2eMzx8bGqlWrVu7bRhs2bKjIyEg9+OCDevHFF0s9u3wmq1evVo8ePRQeHi5vb2/5+vpq0qRJOnjwoA4cOODRt3Xr1u6ZWUkKCAhQ48aNPW6fXrNmjbp3764aNWq427y9vTVo0KByqbfIiy++qLZt2yogIEA+Pj7y9fXVxx9/XOLYnOz48eP6+OOPde211yooKMjjuvfp00fHjx9Xenq6pD9/1j777DPdddddWr58ubKzs8+59pYtW6patWrusU1NTVVsbKwSExMlSZ07d3Yv0HTy862nExsbq4svvrjYuU4en2bNmqlVq1Ye/W666SaP1xs2bNCxY8eKrbQdHx+vK664Qh9//LG7rXv37lq/fr2OHTumPXv26LvvvtMNN9yg1q1ba+XKlZL+nIWtU6eOGjVqJEnu2dnrr79eb7/9tn766aczfj4AgDMIrgAc9+qrryojI0OrV6/WnXfeqa+++ko33nije//BgwclqcTVS+Pi4lRYWFiuKxD/8ssvev/99+Xr6+uxFT3bVxRQb7nlFs2fP1979uzRgAEDFBMTow4dOrj/kXwm0dHRat++fbEtKirK3eemm27SrFmzdNttt2n58uX69NNPlZGRoejoaB07dqzYMc92hddffvlFxhjVqFGj2OdOT093f+bw8HClpaWpdevWmjhxopo1a6a4uDglJyef9fOjn376qa688kpJ0ty5c7V+/XplZGTooYcekqRin7NatWrFjuHv7+/R7+DBg4qNjS3Wr6S2szVjxgyNHDlSHTp00DvvvKP09HRlZGSoV69eJY7NyQ4ePKj8/Hw9//zzxa550S8viq77hAkT9Mwzzyg9PV29e/dWtWrV1L17d23atOms63e5XOrSpYvWr1+vEydOaM2aNerSpYt7f5cuXZSWliZjjNasWaPY2FhddNFFZzxueY7Pmf7uF+2XpB49eig3N1fr1q3TypUrVb16dbVp00Y9evTQqlWrJEkff/yxevTo4X5P586dtXTpUuXn52vIkCGqXbu2mjdvrjfffPOMnxMAcGHxjCsAxzVp0sS9IFO3bt1UUFCgefPm6X//9381cOBA9z+E9+/fX+y9P//8s7y8vBQZGSnpz9m3khYkKstsaPXq1dWyZUs98cQTJe6Pi4tz/3n48OEaPny4cnJytHbtWiUnJ6tfv3769ttvVbdu3VKfsyRZWVn64IMPlJyc7LHya25urvv5ypOd6fnDU6levbpcLpc++eQT+fv7F9v/17YWLVpo0aJFMsbo888/18KFC/Xoo48qMDDQo87SWrRokXx9ffXBBx94rIJ8Ll+nU61aNWVmZhZrL6ntbL322mvq2rWr5syZ49F+qgWGThYZGSlvb2/dcsstGjVqVIl9EhISJEk+Pj665557dM899+jQoUNatWqVJk6cqKuuukp79+5VUFDQWX2Gbt26afHixdq4caM++eQTpaSkuPd16dJFv/32mzZv3qz09HRde+21Z3WOkpR2fM70d/+vz3h36NBBISEhWrVqlXbv3q3u3bvL5XKpe/fumj59ujIyMvTjjz96BFdJuvrqq3X11VcrNzdX6enpSklJ0U033aR69eqpY8eO5fFxAQDlgBlXANZ56qmnFBkZqUmTJqmwsFCJiYmqVauW3njjDY9VZnNycvTOO++4VxqW/lx19sCBAx4rEufl5Wn58uXFznPyLFCRfv366YsvvlCDBg1KnBH9a3AtEhwcrN69e+uhhx5SXl6evvzyy3O+Di6XS8aYYkFy3rx5KigoOOfj/1W/fv1kjNFPP/1U4mdu0aJFifW1atVK//znPxUREaEtW7a4953q2pbE5XLJx8dH3t7e7rZjx47pX//611l/nm7duunjjz/2+DkoKCjQW2+9ddbHPJnL5So2Np9//nmxla6L+px8PYKCgtStWzdt3bpVLVu2LPG6lzR7GRERoYEDB2rUqFH6/fff3av6nuo8p1N06+8///lPZWVleaz+3KxZM1WrVk0pKSk6fvx4qW4TLst5v/zyS3322Wce7ScvntWxY0cFBgbqtdde82jft2+fVq9ere7du7vbfH191blzZ61cuVKrV69Wz549JUmXX365fHx89PDDD7uDbEn8/f3VpUsXTZs2TdKfq2cDAOzBjCsA60RGRmrChAl64IEH9MYbb+jmm2/WU089pcGDB6tfv3668847lZubq6efflqHDh3Sk08+6X7voEGDNGnSJN1www26//77dfz4cT333HMlBr0WLVooNTVV77//vmrWrKnQ0FAlJibq0Ucf1cqVK9WpUyeNHTtWiYmJOn78uHbv3q3//Oc/evHFF1W7dm3dfvvtCgwM1KWXXqqaNWsqMzNTKSkpCg8Pdz87dzq//PKL+xnGvwoLC1PTpk0VFhamzp076+mnn1b16tVVr149paWl6eWXX1ZERMQ5XeOTXXrppbrjjjs0fPhwbdq0SZ07d1ZwcLD279+vdevWqUWLFho5cqQ++OADzZ49W9dcc43q168vY4wWL16sQ4cOuYOCdOprW5K+fftqxowZuummm3THHXfo4MGDeuaZZ0qc+S2thx9+WO+9956uuOIKTZo0SUFBQXrhhReUk5NTpuO8//77Cg0NLdY+cOBA9evXT4899piSk5PVpUsXffPNN3r00UeVkJDgsVp0aGio6tatq3fffVfdu3dXVFSUezxnzpypyy67TJdffrlGjhypevXq6fDhw/ruu+/0/vvvu1e37d+/v/v7jqOjo7Vnzx49++yzqlu3rvt5zaJfLsycOVNDhw6Vr6+vEhMTS6y/SLNmzRQTE6MlS5YoOjpaTZo0ce9zuVzq3LmzlixZIql0z7eW1rhx4zR//nz17dtXjz/+uHtV4a+//tqjX0REhB555BFNnDhRQ4YM0Y033qiDBw9qypQpCggIcK+6XKR79+669957Jck9sxoYGKhOnTppxYoVatmypWJiYtz9J02apH379ql79+6qXbu2Dh06pJkzZ8rX19fjtmkAgAUcXBgKQBVXtCppRkZGsX3Hjh0zderUMY0aNTL5+fnGGGOWLl1qOnToYAICAkxwcLDp3r27Wb9+fbH3/uc//zGtW7c2gYGBpn79+mbWrFklriq8bds2c+mll5qgoCAjyXTp0sW979dffzVjx441CQkJxtfX10RFRZl27dqZhx56yBw5csQYY8wrr7xiunXrZmrUqGH8/PxMXFycuf76683nn39+xs+u06wqfOmll7r77du3zwwYMMBERkaa0NBQ06tXL/PFF1+YunXreqzae7prWZpVhYvMnz/fdOjQwQQHB5vAwEDToEEDM2TIELNp0yZjjDFff/21ufHGG02DBg1MYGCgCQ8PNxdffLFZuHBhqa9tSebPn28SExONv7+/qV+/vklJSTEvv/xysbrr1q1r+vbtW+z9Xbp0KXaO9evXm0suucT4+/ub2NhYc//995uXXnqpTKsKn2ozxpjc3Fxz3333mVq1apmAgADTtm1bs3Tp0hKv7apVq0ybNm2Mv7+/keQxdrt27TIjRowwtWrVMr6+viY6Otp06tTJPP744+4+06dPN506dTLVq1c3fn5+pk6dOubWW281u3fv9jjPhAkTTFxcnPHy8vJYnfd0rr/+eiPJDBw4sNi+Z5991kgytWrVKrbvVKsKN2vWrFjfkq7Jjh07TM+ePU1AQICJiooyt956q3n33XdLrHvevHmmZcuWxs/Pz4SHh5urr77avbr3X3322WdGkmnUqJFH+xNPPGEkmXvuucej/YMPPjC9e/c2tWrVMn5+fiYmJsb06dPHfPLJJ8WODQBwlsuYk77dHQAAAAAAi/CMKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFjNx+kCzkVhYaF+/vlnhYaGyuVyOV0OAAAAAIcYY3T48GHFxcXJy4v5ucqmQgfXn3/+WfHx8U6XAQAAAMASe/fuVe3atZ0uA+WsQgfX0NBQSX/+cIaFhTlcDQAAAACnZGdnKz4+3p0RULlU6OBadHtwWFgYwRUAAAAAjxBWUtz8DQAAAACwGsEVAAAAAGA1gisAAAAAwGoV+hlXAAAAACgtY4zy8/NVUFDgdClVnre3t3x8fEr9TDLBFQAAAECll5eXp/379+vo0aNOl4L/X1BQkGrWrCk/P78z9iW4AgAAAKjUCgsLtWvXLnl7eysuLk5+fn6sPuwgY4zy8vL066+/ateuXWrUqJG8vE7/FCvBFQAAAECllpeXp8LCQsXHxysoKMjpciApMDBQvr6+2rNnj/Ly8hQQEHDa/izOBAAAAKBKONOsHi6ssowHIwcAAAAAsBrBFQAAAABgNYIrAAAAAFQxw4YN0zXXXON+3bVrV40bN86xes6E4AoAAAAAlho2bJhcLlexrVevXuV6nsWLF+uxxx4rl2OlpqbK5XLp0KFD5XI8iVWFAQAAAFQxa/c8pj+Of+/Y+SMDGqhz3UdK3b9Xr15asGCBR5u/v/9ZnbugoKDErwKKioo6q+NdKARXAAAAAFXKH8e/14Gc7U6XUWr+/v6KjY0tcd+MGTO0YMEC/fDDD4qKilL//v311FNPKSQkRJK0cOFCjRs3Tq+99poeeOABffvtt9q5c2ex43Tt2lWtW7fWs88+K+nPrxB6+OGH9frrr+vQoUNq3ry5pk2bpq5du0qS9uzZo9GjR2vdunXKy8tTvXr19PTTT6tp06bq1q2bJCkyMlKSNHToUC1cuPCcrgHBFQAAAAAqKC8vLz333HOqV6+edu3apbvuuksPPPCAZs+e7e5z9OhRpaSkaN68eapWrZpiYmLOeNzhw4dr9+7dWrRokeLi4rRkyRL16tVL27dvV6NGjTRq1Cjl5eVp7dq1Cg4O1o4dOxQSEqL4+Hi98847GjBggL755huFhYUpMDDwnD8nwRUAAAAALPbBBx+4Z1CLPPjgg3rkkUc8FlRKSEjQY489ppEjR3oE1xMnTmj27Nlq1apVqc73/fff680339S+ffsUFxcnSbrvvvu0bNkyLViwQFOnTtWPP/6oAQMGqEWLFpKk+vXru99fdNtxTEyMIiIizuYjF0NwBQAAAACLdevWTXPmzPFoKwqHa9as0dSpU7Vjxw5lZ2crPz9fx48fV05OjoKDgyVJfn5+atmyZanPt2XLFhlj1LhxY4/23NxcVatWTZI0duxYjRw5UitWrFCPHj00YMCAMp2jrAiuAAAAAKqUyIAGFer8wcHBatiwYbH2PXv2qE+fPkpKStJjjz2mqKgorVu3TrfeeqtOnDjh7hcYGFjigkynUlhYKG9vb23evFne3t4e+4pmfm+77TZdddVV+vDDD7VixQqlpKRo+vTpGjNmTJk+W2lViuC6cFtnBYZ4n7kjAAAAUAHd3naz0yVUKmVZ0ddmmzZtUn5+vqZPny4vrz+/6fTtt98+5+O2adNGBQUFOnDggC6//PJT9ouPj1dSUpKSkpI0YcIEzZ07V2PGjJGfn5+kP1cwLi+VIrgCAAAAQGWVm5urzMxMjzYfHx81aNBA+fn5ev7559W/f3+tX79eL7744jmfr3Hjxho8eLCGDBmi6dOnq02bNvrtt9+0evVqtWjRQn369NG4cePUu3dvNW7cWH/88YdWr16tJk2aSJLq1q0rl8ulDz74QH369FFgYGCxZ3TLyuucPxUAAAAA4LxZtmyZatas6bFddtllat26tWbMmKFp06apefPmev3115WSklIu51ywYIGGDBmie++9V4mJifr73/+ujRs3Kj4+XtKfs6mjRo1SkyZN1KtXLyUmJroXhKpVq5amTJmi8ePHq0aNGho9evQ51+MyxphzPopDsrOzFR4erplprbhVGAAAAJUWtwqfWVE2yMrKUlhYmMe+48ePa9euXUpISFBAQIBDFeJkZRkXZlwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAEsNGzZM11xzzVm9d+HChYqIiCjXelJTU+VyuXTo0KFyPe6Z+FzQswEAAACAw46+954Kf/3VsfN7RUcr6O9/d+z8FREzrgAAAACqlMJff1XBvn2ObeUVmmfMmKEWLVooODhY8fHxuuuuu3TkyBFJf86MDh8+XFlZWXK5XHK5XJo8ebIkKS8vTw888IBq1aql4OBgdejQQampqe7j7tmzR/3791dkZKSCg4PVrFkz/ec//9Hu3bvVrVs3SVJkZKRcLpeGDRtWLp/lTJhxBQAAAIAKyMvLS88995zq1aunXbt26a677tIDDzyg2bNnq1OnTnr22Wc1adIkffPNN5KkkJAQSdLw4cO1e/duLVq0SHFxcVqyZIl69eql7du3q1GjRho1apTy8vK0du1aBQcHa8eOHQoJCVF8fLzeeecdDRgwQN98843CwsIUGBh4QT4rwRUAAAAAKqBx48a5/5yQkKDHHntMI0eO1OzZs+Xn56fw8HC5XC7Fxsa6+33//fd68803tW/fPsXFxUmS7rvvPi1btkwLFizQ1KlT9eOPP2rAgAFq0aKFJKl+/fru90dFRUmSYmJiyv352dMhuAIAAABABbRmzRpNnTpVO3bsUHZ2tvLz83X8+HHl5OQoODi4xPds2bJFxhg1btzYoz03N1fVqlWTJI0dO1YjR47UihUr1KNHDw0YMEAtW7Y875/ndAiuAAAAAKoUr+joCn/+PXv2qE+fPkpKStJjjz2mqKgorVu3TrfeeqtOnDhxyvcVFhbK29tbmzdvlre3t8e+oluJb7vtNl111VX68MMPtWLFCqWkpGj69OkaM2bMOdd9tgiuAAAAAKqUyrCi76ZNm5Sfn6/p06fLy+vPNXfffvttjz5+fn4qKCjwaGvTpo0KCgp04MABXX755ac8fnx8vJKSkpSUlKQJEyZo7ty5GjNmjPz8/CSp2HHPN4IrAAAAAFgsKytL27Zt82iLjo5Wfn6+nn/+efXv31/r16/Xiy++6NGnXr16OnLkiD7++GO1atVKQUFBaty4sQYPHqwhQ4Zo+vTpatOmjX777TetXr1aLVq0UJ8+fTRu3Dj17t1bjRs31h9//KHVq1erSZMmkqS6devK5XLpgw8+UJ8+fRQYGOieqT2f+DocAAAAALBYamqq2rRp47HNnz9fM2bM0LRp09S8eXO9/vrrSklJ8Xhfp06dlJSUpEGDBik6OlpPPfWUJGnBggUaMmSI7r33XiUmJurvf/+7Nm7cqPj4eEl/zqaOGjVKTZo0Ua9evZSYmKjZs2dLkmrVqqUpU6Zo/PjxqlGjhkaPHn1BroHLGGMuyJnOg+zsbIWHh2tmWisFhnif+Q0AAABABXR7281Ol2C9omyQlZWlsLAwj33Hjx/Xrl27lJCQoICAAIcqxMnKMi7MuAIAAAAArFYpnnEd1nptsd+qAAAAAAAqB2ZcAQAAAABWI7gCAAAAAKxGcAUAAABQJVTgdWkrpbKMB8EVAAAAQKXm6+srSTp69KjDleCvisajaHxOp1IszgQAAAAAp+Lt7a2IiAgdOHBAkhQUFCSXy+VwVVWXMUZHjx7VgQMHFBERIW/vM3+1KcEVAAAAQKUXGxsrSe7wCudFRES4x+VMCK4AAAAAKj2Xy6WaNWsqJiZGJ06ccLqcKs/X17dUM61FCK4AAAAAqgxvb+8yBSbYgcWZAAAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACr+ThdwPmWNWWK0yUAAAAAlU54crLTJaAKcXTGde3aterfv7/i4uLkcrm0dOlSJ8sBAAAAAFjI0eCak5OjVq1aadasWU6WAQAAAACwmKO3Cvfu3Vu9e/d2sgQAAAAAgOUq1DOuubm5ys3Ndb/Ozs52sBoAAAAAwIVQoVYVTklJUXh4uHuLj493uiQAAAAAwHlWoYLrhAkTlJWV5d727t3rdEkAAAAAgPOsQt0q7O/vL39/f6fLAAAAAABcQBVqxhUAAAAAUPU4OuN65MgRfffdd+7Xu3bt0rZt2xQVFaU6deo4WBkAAAAAwBaOBtdNmzapW7du7tf33HOPJGno0KFauHChQ1UBAAAAAGziaHDt2rWrjDFOlgAAAAAAsBzPuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAq/k4XcD5Fp6c7HQJAAAAAIBzwIwrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDUfpwsoDwu3dVZgiLfTZaAKur3tZqdLAAAAACo9ZlwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFbzcbqA8jCs9VqFhYU5XQYAAAAA4DxgxhUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1HydPnpKSosWLF+vrr79WYGCgOnXqpGnTpikxMdHJsmCprClTnC4BVVh4crLTJQAAAFRZjs64pqWladSoUUpPT9fKlSuVn5+vK6+8Ujk5OU6WBQAAAACwiKMzrsuWLfN4vWDBAsXExGjz5s3q3LmzQ1UBAAAAAGziaHA9WVZWliQpKiqqxP25ubnKzc11v87Ozr4gdQEAAAAAnGPN4kzGGN1zzz267LLL1Lx58xL7pKSkKDw83L3Fx8df4CoBAAAAABeaNcF19OjR+vzzz/Xmm2+ess+ECROUlZXl3vbu3XsBKwQAAAAAOMGKW4XHjBmj9957T2vXrlXt2rVP2c/f31/+/v4XsDIAAAAAgNMcDa7GGI0ZM0ZLlixRamqqEhISnCwHAAAAAGAhR4PrqFGj9MYbb+jdd99VaGioMjMzJUnh4eEKDAx0sjQAAAAAgCUcfcZ1zpw5ysrKUteuXVWzZk339tZbbzlZFgAAAADAIo7fKgwAAAAAwOlYs6owAAAAAAAlIbgCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVfJwuACit8ORkp0sAAAAA4ABmXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFbzcboAnF9zt7RzugQAQBV3e9vNTpcAAKjgmHEFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAq5X563B27typd999V7t375bL5VJCQoKuueYa1a9f/3zUBwAAAACo4soUXFNSUjRp0iQVFhYqJiZGxhj9+uuvGj9+vKZOnar77rvvfNUJAAAAAKiiSn2r8Jo1a/Twww/roYce0m+//ab9+/crMzPTHVzHjx+vtWvXns9aAQAAAABVkMsYY0rTcdCgQYqIiND//M//lLj/jjvu0OHDh/Xmm2+Wa4Gnk52drfDwcGVlZSksLOyCnbcimbulndMlAACquNvbbna6BABVANmgciv1jOunn36qW2655ZT7b7nlFqWnp5dLUQAAAAAAFCl1cP3ll19Ur169U+5PSEhQZmZmedQEAAAAAIBbqYPr8ePH5efnd8r9vr6+ysvLK5eiAAAAAAAoUqZVhefNm6eQkJAS9x0+fLhcCgIAAAAA4K9KHVzr1KmjuXPnnrEPAAAAAADlqdTBdffu3eexDAAAAAAASlbqZ1wBAAAAAHBCqWdcn3vuuVL1Gzt27FkXAwAAAADAyUodXP/5z3+esY/L5SK4AgAAAADKVamD665du85nHQAAAAAAlIhnXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgtVKvKvxX33//vRYsWKDvv/9eM2fOVExMjJYtW6b4+Hg1a9asvGvEObi97WanSwAAAACAc1LmGde0tDS1aNFCGzdu1OLFi3XkyBFJ0ueff67k5ORyLxAAAAAAULWVObiOHz9ejz/+uFauXCk/Pz93e7du3bRhw4ZyLQ4AAAAAgDIH1+3bt+vaa68t1h4dHa2DBw+WS1EAAAAAABQpc3CNiIjQ/v37i7Vv3bpVtWrVKpeiAAAAAAAoUubgetNNN+nBBx9UZmamXC6XCgsLtX79et13330aMmTI+agRAAAAAFCFlTm4PvHEE6pTp45q1aqlI0eOqGnTpurcubM6deqkhx9++HzUCAAAAACowlzGGHM2b/zhhx+0ZcsWFRYWqk2bNmrUqFF513ZG2dnZCg8PV1ZWlsLCwi74+QEAAADYgWxQuZV5xvXRRx/V0aNHVb9+fQ0cOFDXX3+9GjVqpGPHjunRRx89HzUCAAAAAKqwMs+4ent7a//+/YqJifFoP3jwoGJiYlRQUFCuBZ4Ov1UBAAAAIJENKrsyz7gaY+RyuYq1f/bZZ4qKiiqXogAAAAAAKOJT2o6RkZFyuVxyuVxq3LixR3gtKCjQkSNHlJSUdF6KBAAAAABUXaUOrs8++6yMMRoxYoSmTJmi8PBw9z4/Pz/Vq1dPHTt2PC9FAgAAAACqrlIH16FDh0qSEhIS1KlTJ/n6+p63ogAAAAAAKFLq4FokISFB+/fvP+X+OnXqnFNBAAAAAAD8VZmDa7169UpcnKnIhVxVGAAAAABQ+ZU5uG7dutXj9YkTJ7R161bNmDFDTzzxRLkVBgAAAACAdBbBtVWrVsXa2rdvr7i4OD399NO67rrryqUwAHbJmjLF6RIAAFB4crLTJQBwQJm/x/VUGjdurIyMjDK9Z86cOWrZsqXCwsIUFhamjh076qOPPiqvkgAAAAAAlUCZZ1yzs7M9XhtjtH//fk2ePFmNGjUq07Fq166tJ598Ug0bNpQkvfLKK7r66qu1detWNWvWrKylAQAAAAAqoTIH14iIiGKLMxljFB8fr0WLFpXpWP379/d4/cQTT2jOnDlKT08nuAIAAAAAJJ1FcF2zZo3Hay8vL0VHR6thw4by8Snz4dwKCgr073//Wzk5OerYsWOJfXJzc5Wbm+t+ffLsLwAAAACg8ilz0uzSpUu5FrB9+3Z17NhRx48fV0hIiJYsWaKmTZuW2DclJUVTWCAGAAAAAKqUs1qc6fvvv9eYMWPUo0cP9ezZU2PHjtX3339/VgUkJiZq27ZtSk9P18iRIzV06FDt2LGjxL4TJkxQVlaWe9u7d+9ZnRMAAAAAUHGUObguX75cTZs21aeffqqWLVuqefPm2rhxo5o1a6aVK1eWuQA/Pz81bNhQ7du3V0pKilq1aqWZM2eW2Nff39+9AnHRBgAAAACo3Mp8q/D48eP1j3/8Q08++WSx9gcffFA9e/Y8p4KMMR7PsQIAAAAAqrYyB9evvvpKb7/9drH2ESNG6Nlnny3TsSZOnKjevXsrPj5ehw8f1qJFi5Samqply5aVtSwAAAAAQCVV5uAaHR2tbdu2FfvO1m3btikmJqZMx/rll190yy23aP/+/QoPD1fLli21bNmyc561BQAAAABUHmUOrrfffrvuuOMO/fDDD+rUqZNcLpfWrVunadOm6d577y3TsV5++eWynh4AAAAAUMWUObg+8sgjCg0N1fTp0zVhwgRJUlxcnCZPnqyxY8eWe4EAAAAAgKqtzMHV5XLpH//4h/7xj3/o8OHDkqTQ0FBJ0k8//aRatWqVb4UAAAAAgCrtrL7HtUhoaKhCQ0OVmZmpMWPGqGHDhuVVFwAAAAAAksoQXA8dOqTBgwcrOjpacXFxeu6551RYWKhJkyapfv36Sk9P1/z5889nrQAAAACAKqjUtwpPnDhRa9eu1dChQ7Vs2TL94x//0LJly3T8+HF99NFH6tKly/msEwAAAABQRZU6uH744YdasGCBevToobvuuksNGzZU48aNy/zdrQAAAAAAlEWpbxX++eef1bRpU0lS/fr1FRAQoNtuu+28FQYAAAAAgFSG4FpYWChfX1/3a29vbwUHB5+XogAAAAAAKFLqW4WNMRo2bJj8/f0lScePH1dSUlKx8Lp48eLyrRAAAAAAUKWVOrgOHTrU4/XNN99c7sUAAAAAAHCyUgfXBQsWnM86AAAAAAAoUamfcQUAAAAAwAkEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYr9eJMAKq28ORkp0sAAABAFcWMKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1H6cLKA8Lt3VWYIi302UAKIPb2252ugQAAABUEMy4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACs5uN0AeVhWOu1CgsLc7oMAAAAAMB5wIwrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAaj5OF1AkJSVFEydO1N13361nn33W6XJQCWVNmeJ0CQDOQnhystMlAAAAh1kx45qRkaGXXnpJLVu2dLoUAAAAAIBlHA+uR44c0eDBgzV37lxFRkY6XQ4AAAAAwDKOB9dRo0apb9++6tGjxxn75ubmKjs722MDAAAAAFRujj7jumjRIm3ZskUZGRml6p+SkqIpPKcIAAAAAFWKYzOue/fu1d13363XXntNAQEBpXrPhAkTlJWV5d727t17nqsEAAAAADjNsRnXzZs368CBA2rXrp27raCgQGvXrtWsWbOUm5srb29vj/f4+/vL39//QpcKAAAAAHCQY8G1e/fu2r59u0fb8OHDddFFF+nBBx8sFloBAAAAAFWTY8E1NDRUzZs392gLDg5WtWrVirUDAAAAAKoux1cVBgAAAADgdBxdVfhkqampTpcAAAAAALAMM64AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGo+ThcAXCjhyclOlwAAAADgLDDjCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsJqP0wUAqLrmbmnndAnAeXV7281OlwAAQKXAjCsAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGo+ThcAoOq6ve1mp0sAAABABcCMKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1H6cLAACgPGRNmeJ0CcB5E56c7HQJAOAoR2dcJ0+eLJfL5bHFxsY6WRIAAAAAwDKOz7g2a9ZMq1atcr/29vZ2sBoAAAAAgG0cD64+Pj7MsgIAAAAATsnxxZl27typuLg4JSQk6IYbbtAPP/xwyr65ubnKzs722AAAAAAAlZujwbVDhw569dVXtXz5cs2dO1eZmZnq1KmTDh48WGL/lJQUhYeHu7f4+PgLXDEAAAAA4EJzGWOM00UUycnJUYMGDfTAAw/onnvuKbY/NzdXubm57tfZ2dmKj49XVlaWwsLCLmSpAADLsKowKjNWFQbOLDs7W+Hh4WSDSsrxZ1z/Kjg4WC1atNDOnTtL3O/v7y9/f/8LXBUAAAAAwEmOP+P6V7m5ufrqq69Us2ZNp0sBAAAAAFjC0eB63333KS0tTbt27dLGjRs1cOBAZWdna+jQoU6WBQAAAACwiKO3Cu/bt0833nijfvvtN0VHR+uSSy5Renq66tat62RZAAAAAACLOBpcFy1a5OTpAQAAAAAVgFXPuAIAAAAAcDKCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWM3H6QIAACgP4cnJTpcAAADOE2ZcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFjNx+kCzoUxRpKUnZ3tcCUAAAAAnFSUCYoyAiqXCh1cDx48KEmKj493uBIAAAAANjh8+LDCw8OdLgPlrEIH16ioKEnSjz/+yA9nJZedna34+Hjt3btXYWFhTpeD84ixrjoY66qDsa46GOuqw8axNsbo8OHDiouLc7oUnAcVOrh6ef35iG54eLg1f2FwfoWFhTHWVQRjXXUw1lUHY111MNZVh21jzWRW5cXiTAAAAAAAqxFcAQAAAABWq9DB1d/fX8nJyfL393e6FJxnjHXVwVhXHYx11cFYVx2MddXBWONCcxnWiwYAAAAAWKxCz7gCAAAAACo/gisAAAAAwGoEVwAAAACA1QiuAAAAAACrVejgOnv2bCUkJCggIEDt2rXTJ5984nRJKIO1a9eqf//+iouLk8vl0tKlSz32G2M0efJkxcXFKTAwUF27dtWXX37p0Sc3N1djxoxR9erVFRwcrL///e/at2/fBfwUKI2UlBT97W9/U2hoqGJiYnTNNdfom2++8ejDeFcOc+bMUcuWLd1fSN+xY0d99NFH7v2Mc+WVkpIil8ulcePGudsY78ph8uTJcrlcHltsbKx7P+Ncufz000+6+eabVa1aNQUFBal169bavHmzez/jDadU2OD61ltvady4cXrooYe0detWXX755erdu7d+/PFHp0tDKeXk5KhVq1aaNWtWifufeuopzZgxQ7NmzVJGRoZiY2PVs2dPHT582N1n3LhxWrJkiRYtWqR169bpyJEj6tevnwoKCi7Ux0AppKWladSoUUpPT9fKlSuVn5+vK6+8Ujk5Oe4+jHflULt2bT355JPatGmTNm3apCuuuEJXX321+x81jHPllJGRoZdeekktW7b0aGe8K49mzZpp//797m379u3ufYxz5fHHH3/o0ksvla+vrz766CPt2LFD06dPV0REhLsP4w3HmArq4osvNklJSR5tF110kRk/frxDFeFcSDJLlixxvy4sLDSxsbHmySefdLcdP37chIeHmxdffNEYY8yhQ4eMr6+vWbRokbvPTz/9ZLy8vMyyZcsuWO0ouwMHDhhJJi0tzRjDeFd2kZGRZt68eYxzJXX48GHTqFEjs3LlStOlSxdz9913G2P4e12ZJCcnm1atWpW4j3GuXB588EFz2WWXnXI/4w0nVcgZ17y8PG3evFlXXnmlR/uVV16p//73vw5VhfK0a9cuZWZmeoyxv7+/unTp4h7jzZs368SJEx594uLi1Lx5c34OLJeVlSVJioqKksR4V1YFBQVatGiRcnJy1LFjR8a5kho1apT69u2rHj16eLQz3pXLzp07FRcXp4SEBN1www364YcfJDHOlc17772n9u3b6//9v/+nmJgYtWnTRnPnznXvZ7zhpAoZXH/77TcVFBSoRo0aHu01atRQZmamQ1WhPBWN4+nGODMzU35+foqMjDxlH9jHGKN77rlHl112mZo3by6J8a5stm/frpCQEPn7+yspKUlLlixR06ZNGedKaNGiRdqyZYtSUlKK7WO8K48OHTro1Vdf1fLlyzV37lxlZmaqU6dOOnjwIONcyfzwww+aM2eOGjVqpOXLlyspKUljx47Vq6++Kom/13CWj9MFnAuXy+Xx2hhTrA0V29mMMT8Hdhs9erQ+//xzrVu3rtg+xrtySExM1LZt23To0CG98847Gjp0qNLS0tz7GefKYe/evbr77ru1YsUKBQQEnLIf413x9e7d2/3nFi1aqGPHjmrQoIFeeeUVXXLJJZIY58qisLBQ7du319SpUyVJbdq00Zdffqk5c+ZoyJAh7n6MN5xQIWdcq1evLm9v72K/tTlw4ECx3wChYiparfB0YxwbG6u8vDz98ccfp+wDu4wZM0bvvfee1qxZo9q1a7vbGe/Kxc/PTw0bNlT79u2VkpKiVq1aaebMmYxzJbN582YdOHBA7dq1k4+Pj3x8fJSWlqbnnntOPj4+7vFivCuf4OBgtWjRQjt37uTvdSVTs2ZNNW3a1KOtSZMm7sVPGW84qUIGVz8/P7Vr104rV670aF+5cqU6derkUFUoTwkJCYqNjfUY47y8PKWlpbnHuF27dvL19fXos3//fn3xxRf8HFjGGKPRo0dr8eLFWr16tRISEjz2M96VmzFGubm5jHMl0717d23fvl3btm1zb+3bt9fgwYO1bds21a9fn/GupHJzc/XVV1+pZs2a/L2uZC699NJiX1f37bffqm7dupL4/zUcduHXgyofixYtMr6+vubll182O3bsMOPGjTPBwcFm9+7dTpeGUjp8+LDZunWr2bp1q5FkZsyYYbZu3Wr27NljjDHmySefNOHh4Wbx4sVm+/bt5sYbbzQ1a9Y02dnZ7mMkJSWZ2rVrm1WrVpktW7aYK664wrRq1crk5+c79bFQgpEjR5rw8HCTmppq9u/f796OHj3q7sN4Vw4TJkwwa9euNbt27TKff/65mThxovHy8jIrVqwwxjDOld1fVxU2hvGuLO69916TmppqfvjhB5Oenm769etnQkND3f/mYpwrj08//dT4+PiYJ554wuzcudO8/vrrJigoyLz22mvuPow3nFJhg6sxxrzwwgumbt26xs/Pz7Rt29b91RqoGNasWWMkFduGDh1qjPlzyfXk5GQTGxtr/P39TefOnc327ds9jnHs2DEzevRoExUVZQIDA02/fv3Mjz/+6MCnwemUNM6SzIIFC9x9GO/KYcSIEe7/LkdHR5vu3bu7Q6sxjHNld3JwZbwrh0GDBpmaNWsaX19fExcXZ6677jrz5ZdfuvczzpXL+++/b5o3b278/f3NRRddZF566SWP/Yw3nOIyxhhn5noBAAAAADizCvmMKwAAAACg6iC4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAVwuTJk9W6dWunywAAAA5wGWOM00UAAKo2l8t12v1Dhw7VrFmzlJubq2rVql2gqgAAgC0IrgAAx2VmZrr//NZbb2nSpEn65ptv3G2BgYEKDw93ojQAAGABbhUGADguNjbWvYWHh8vlchVrO/lW4WHDhumaa67R1KlTVaNGDUVERGjKlCnKz8/X/fffr6ioKNWuXVvz58/3ONdPP/2kQYMGKTIyUtWqVdPVV1+t3bt3X9gPDAAAyoTgCgCosFavXq2ff/5Za9eu1YwZMzR58mT169dPkZGR2rhxo5KSkpSUlKS9e/dKko4ePapu3bopJCREa9eu1bp16xQSEqJevXopLy/P4U8DAABOheAKAKiwoqKi9NxzzykxMVEjRoxQYmKijh49qokTJ6pRo0aaMGGC/Pz8tH79eknSokWL5OXlpXnz5qlFixZq0qSJFixYoB9//FGpqanOfhgAAHBKPk4XAADA2WrWrJm8vP7vd7A1atRQ8+bN3a+9vb1VrVo1HThwQJK0efNmfffddwoNDfU4zvHjx/X9999fmKIBAECZEVwBABWWr6+vx2uXy1ViW2FhoSSpsLBQ7dq10+uvv17sWNHR0eevUAAAcE4IrgCAKqNt27Z66623FBMTo7CwMKfLAQAApcQzrgCAKmPw4MGqXr26rr76an3yySfatWuX0tLSdPfdd2vfvn1OlwcAAE6B4AoAqDKCgoK0du1a1alTR9ddd52aNGmiESNG6NixY8zAAgBgMZcxxjhdBAAAAAAAp8KMKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAq/1/3Mvgl3TffakAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 1000x600 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(10, 6))\n",
    "row_height = 0.3\n",
    "row_space = 0.2\n",
    "\n",
    "for _, row in routes.iterrows():\n",
    "    route_id = row[\"Route ID\"]\n",
    "    earliest_start = row[\"Earliest Start Time\"]\n",
    "    earliest_end = row[\"Earliest End Time\"]\n",
    "    latest_start = row[\"Latest Start Time\"]\n",
    "    latest_end = row[\"Latest End Time\"]\n",
    "\n",
    "    # Plot the bars for earliest start to earliest end\n",
    "    ax.barh(route_id - row_space / 2 - row_height, earliest_end - earliest_start, \n",
    "            left=earliest_start, height=row_height, color=\"yellowgreen\")\n",
    "\n",
    "    # Plot the bars for latest start to latest end on a separate line\n",
    "    ax.barh(route_id + row_space / 2, latest_end - latest_start, \n",
    "            left=latest_start, height=row_height, color=\"lightcoral\")\n",
    "\n",
    "# Labels\n",
    "ax.set_xlabel(\"Time\")\n",
    "ax.set_ylabel(\"Route ID\")\n",
    "ax.set_title(\"Routes Earliest and Latest Windows\")\n",
    "ax.invert_yaxis()  # Invert the y-axis to have Route ID 1 at the top\n",
    "# Set y-ticks to ensure integer values\n",
    "ax.set_yticks(range(1, len(routes) + 1))\n",
    "# Create a single legend entry \n",
    "earliest_legend = plt.Line2D([0], [0], color=\"yellowgreen\", lw=4, label=\"Earliest\")\n",
    "latest_legend = plt.Line2D([0], [0], color=\"lightcoral\", lw=4, label=\"Latest\")\n",
    "ax.legend(handles=[earliest_legend, latest_legend], loc=\"upper left\", bbox_to_anchor=(1, 1))\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e294c161",
   "metadata": {},
   "source": [
    "The length of each bar represents the duration from the start to the completion of a route. Because we have time windows (both earliest and latest times) for both the start and finish, each route is represented by two bars. One bar illustrates the route's duration if everything starts at the earliest times, and the other shows the duration if everything is delayed until the latest times. By comparing the starting points of these bars for each route, we can assess the schedule flexibility for each route.\n",
    "\n",
    "We can see that some routes, like route 1, have a very tight schedule, while routes like 3 and 4, have more room for their start times. Our goal is now more clear. Is it possible to take advantage of the extra rooms in the routes' schedules and assign multiple routes to the same van, thus, reducing the number of resources?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2d6872ea",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:12:58.376921Z",
     "start_time": "2023-11-06T20:12:58.205635Z"
    }
   },
   "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>Route ID</th>\n",
       "      <th>Stop Number</th>\n",
       "      <th>Customer Name</th>\n",
       "      <th>Technician Name</th>\n",
       "      <th>Location Name</th>\n",
       "      <th>Job type</th>\n",
       "      <th>Processing Time</th>\n",
       "      <th>Customer Time Window Start</th>\n",
       "      <th>Customer Time Window End</th>\n",
       "      <th>Earliest Start</th>\n",
       "      <th>Latest Start</th>\n",
       "      <th>Earliest End</th>\n",
       "      <th>Latest End</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>Customer1</td>\n",
       "      <td>Albert</td>\n",
       "      <td>Mannheim</td>\n",
       "      <td>Equipment Setup</td>\n",
       "      <td>30.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>24.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>54.0</td>\n",
       "      <td>60.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>Customer7</td>\n",
       "      <td>Albert</td>\n",
       "      <td>Loerrach</td>\n",
       "      <td>Inspect/Service Equipment</td>\n",
       "      <td>60.0</td>\n",
       "      <td>360.0</td>\n",
       "      <td>480.0</td>\n",
       "      <td>360.0</td>\n",
       "      <td>390.0</td>\n",
       "      <td>420.0</td>\n",
       "      <td>450.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>Customer2</td>\n",
       "      <td>Bob</td>\n",
       "      <td>Karlsruhe</td>\n",
       "      <td>Equipment Setup</td>\n",
       "      <td>30.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>150.0</td>\n",
       "      <td>50.0</td>\n",
       "      <td>150.0</td>\n",
       "      <td>80.0</td>\n",
       "      <td>180.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>Customer4</td>\n",
       "      <td>Doris</td>\n",
       "      <td>Buehl</td>\n",
       "      <td>Equipment Installation</td>\n",
       "      <td>60.0</td>\n",
       "      <td>120.0</td>\n",
       "      <td>240.0</td>\n",
       "      <td>120.0</td>\n",
       "      <td>240.0</td>\n",
       "      <td>180.0</td>\n",
       "      <td>300.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>Customer6</td>\n",
       "      <td>Doris</td>\n",
       "      <td>Lahr/Schwarzwald</td>\n",
       "      <td>Repair - Critical</td>\n",
       "      <td>60.0</td>\n",
       "      <td>300.0</td>\n",
       "      <td>420.0</td>\n",
       "      <td>300.0</td>\n",
       "      <td>420.0</td>\n",
       "      <td>360.0</td>\n",
       "      <td>480.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>Customer3</td>\n",
       "      <td>Ed</td>\n",
       "      <td>Baden-Baden</td>\n",
       "      <td>Repair - Regular</td>\n",
       "      <td>60.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>180.0</td>\n",
       "      <td>67.0</td>\n",
       "      <td>180.0</td>\n",
       "      <td>127.0</td>\n",
       "      <td>240.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>5</td>\n",
       "      <td>1</td>\n",
       "      <td>Customer5</td>\n",
       "      <td>Flor</td>\n",
       "      <td>Offenburg</td>\n",
       "      <td>Equipment Installation</td>\n",
       "      <td>60.0</td>\n",
       "      <td>240.0</td>\n",
       "      <td>360.0</td>\n",
       "      <td>240.0</td>\n",
       "      <td>360.0</td>\n",
       "      <td>300.0</td>\n",
       "      <td>420.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Route ID  Stop Number Customer Name Technician Name     Location Name  \\\n",
       "0         1            1     Customer1          Albert          Mannheim   \n",
       "1         1            2     Customer7          Albert          Loerrach   \n",
       "2         2            1     Customer2             Bob         Karlsruhe   \n",
       "3         3            1     Customer4           Doris             Buehl   \n",
       "4         3            2     Customer6           Doris  Lahr/Schwarzwald   \n",
       "5         4            1     Customer3              Ed       Baden-Baden   \n",
       "6         5            1     Customer5            Flor         Offenburg   \n",
       "\n",
       "                    Job type  Processing Time  Customer Time Window Start  \\\n",
       "0            Equipment Setup             30.0                         0.0   \n",
       "1  Inspect/Service Equipment             60.0                       360.0   \n",
       "2            Equipment Setup             30.0                        30.0   \n",
       "3     Equipment Installation             60.0                       120.0   \n",
       "4          Repair - Critical             60.0                       300.0   \n",
       "5           Repair - Regular             60.0                        60.0   \n",
       "6     Equipment Installation             60.0                       240.0   \n",
       "\n",
       "   Customer Time Window End  Earliest Start  Latest Start  Earliest End  \\\n",
       "0                      30.0            24.0          30.0          54.0   \n",
       "1                     480.0           360.0         390.0         420.0   \n",
       "2                     150.0            50.0         150.0          80.0   \n",
       "3                     240.0           120.0         240.0         180.0   \n",
       "4                     420.0           300.0         420.0         360.0   \n",
       "5                     180.0            67.0         180.0         127.0   \n",
       "6                     360.0           240.0         360.0         300.0   \n",
       "\n",
       "   Latest End  \n",
       "0        60.0  \n",
       "1       450.0  \n",
       "2       180.0  \n",
       "3       300.0  \n",
       "4       480.0  \n",
       "5       240.0  \n",
       "6       420.0  "
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order_routes = pd.read_csv('https://raw.githubusercontent.com/decision-spot/technician_assignment/main/orders.csv')\n",
    "order_routes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b8e9dc1",
   "metadata": {},
   "source": [
    "Note that \"Earliest Start\" and \"Latest Start\" consider the travel time from the Depot to the Customer. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "190b9bce",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:13:02.596360Z",
     "start_time": "2023-11-06T20:13:02.591288Z"
    }
   },
   "outputs": [],
   "source": [
    "earliest_time = 0  # this is the reference for start time. Assume 7:00 AM is minute 0\n",
    "latest_time = 600  # 10 hours later, 5:00 PM is minute 600\n",
    "resource_limit = 3  # number of available resources"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75881443",
   "metadata": {},
   "source": [
    "## Problem Formulation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b8229be",
   "metadata": {},
   "source": [
    "Let's define our notations for the MO model.\n",
    "\n",
    "**Sets**\n",
    "- $O\\quad$: Set of orders\n",
    "- $R\\quad$: Set of routes\n",
    "- $V\\quad$: Set of resources/vans\n",
    "\n",
    "We also have the following information from `routes` and `order_routes` dataframes:\n",
    "\n",
    "**Parameters**\n",
    "- $b^{E}_{r}\\quad$: earliest start (beginning) time of route $r \\in R$\n",
    "- $b^{L}_{r}\\quad$: latest start (beginning) time of route $r \\in R$\n",
    "- $f^{E}_{r}\\quad$: earliest end (finish) time of route $r \\in R$\n",
    "- $f^{L}_{r}\\quad$: latest end (finish) time of route $r \\in R$\n",
    "- $t_{r}\\quad$: total duration of time on route $r \\in R$\n",
    "- $a_{o,r}\\quad$: 1 if order $o \\in O$ is covered by route $r \\in R$\n",
    "\n",
    "Total time ($t_{r}$) includes all the transit time, processing time, and any waiting time from the start (leaving the depot) to the end (returning to the depot) for each route.\n",
    "\n",
    "Note that superscript $E$ is used to indicate earliest and $L$ is used to indicate latest time. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fcf3cf8",
   "metadata": {},
   "source": [
    "## Decision Variables"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d21f6f93",
   "metadata": {},
   "source": [
    "First of all, we know that due to resource limitation, we may not be able to use every route, and consequently, cover every order. So, we want to have variables that track the order coverage and route usage: \n",
    "- $u_{o}\\quad$: 1 if order $o \\in O$ is covered; 0 otherwise\n",
    "- $x_{r}\\quad$: 1 if route $r \\in R$ is used; 0 otherwise\n",
    "\n",
    "Next, we want to know which of the available vans are used and track which route is assigned to which van:\n",
    "- $y_{r,v}\\quad$: 1 if route $r \\in R$ is assigned to van $v \\in V$; 0 otherwise\n",
    "- $z_{v}\\quad$: 1 if van $v \\in V$ is used; 0 otherwise\n",
    "\n",
    "As explained before, we want to see if it's possible to take advantage of the route's start time flexibility and shift the routes around as needed. That way, more routes can be assigned to a single van. That means, the start time of a route (and by extension its end time) are decision variables too:\n",
    "- $s_{r}\\quad$: start time of route $r \\in R$\n",
    "- $e_{r}\\quad$: end time of route $r \\in R$\n",
    "\n",
    "With these initial decision variables, we can start the MO model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e8140631",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:13:04.985957Z",
     "start_time": "2023-11-06T20:13:04.968032Z"
    }
   },
   "outputs": [],
   "source": [
    "order_route_dict = dict(zip(order_routes['Customer Name'], order_routes['Route ID']))  # a(o,r)\n",
    "routes_dict = routes.set_index('Route ID').to_dict(orient='index')  # this will help us in creating the constraints\n",
    "r_set = routes_dict.keys()  # R\n",
    "v_set = set(range(resource_limit))  # V\n",
    "rv_set = {(r, v) for r in r_set for v in range(resource_limit)}  # pair of (r,v) index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "18f9b67f",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:13:08.868021Z",
     "start_time": "2023-11-06T20:13:08.855572Z"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "mdl = gp.Model('resource_assignment')\n",
    "\n",
    "# Variables\n",
    "u = mdl.addVars(order_route_dict.keys(), vtype=GRB.BINARY, name='u')  # tracks whether order o is covered\n",
    "x = mdl.addVars(r_set, vtype=GRB.BINARY, name='x')  # tracks whether route r is used\n",
    "y = mdl.addVars(rv_set, vtype=GRB.BINARY, name='y')  # tracks whether route r is assigned to van v\n",
    "z = mdl.addVars(v_set, vtype=GRB.BINARY, name='z')  # tracks whether van v is used\n",
    "s = mdl.addVars(r_set, lb=earliest_time, ub=latest_time, vtype=GRB.CONTINUOUS, name='s')  # tracks start time of route r\n",
    "e = mdl.addVars(r_set, lb=earliest_time, ub=latest_time, vtype=GRB.CONTINUOUS, name='e')  # tracks end time of route r"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53a33172",
   "metadata": {},
   "source": [
    "## Constraints"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "225d8693",
   "metadata": {},
   "source": [
    "We know that each order is covered by one route and each route can have multiple orders. So, we first establish this relationship, ensuring that when an order is covered, the route that it belongs to should be used.\n",
    "\n",
    "\\begin{align}\n",
    "&???\\\\\n",
    "\\end{align}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fe03af94-b72d-440c-b81d-e1de82eed7c6",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-05T14:32:28.532217Z",
     "start_time": "2023-11-05T14:32:28.528496Z"
    }
   },
   "outputs": [],
   "source": [
    "# Relation between x and u\n",
    "... # ???"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db534a31",
   "metadata": {},
   "source": [
    "Similarly, we know that if a route is used, it should be assigned to only one van:\n",
    "\n",
    "\\begin{align}\n",
    "&???\\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e0b73d5f",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-05T14:32:55.346186Z",
     "start_time": "2023-11-05T14:32:55.343292Z"
    }
   },
   "outputs": [],
   "source": [
    "# Relation between y and x\n",
    "... # ???"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28688fc6",
   "metadata": {},
   "source": [
    "Next, we focus on van usage, i.e., $z_{v}$.\n",
    "If a van is not used, no routes can be assigned to it. On the other hand, if a van is used, then at least one route should be assigned to it.\n",
    "\n",
    "\\begin{align}\n",
    "???\\\\\n",
    "\\end{align}\n",
    "\n",
    "\\begin{align}\n",
    "???\\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba4e366d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-05T14:33:40.924896Z",
     "start_time": "2023-11-05T14:33:40.920916Z"
    }
   },
   "outputs": [],
   "source": [
    "# LB relation between y and z\n",
    "... # ???\n",
    "\n",
    "# UB relation between y and z\n",
    "... # ???"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "718a8ac0",
   "metadata": {},
   "source": [
    "Next, we establish the logical constraints for the route's start and end time.\n",
    "\n",
    "\n",
    "\\begin{align}\n",
    "&??? \\\\\n",
    "&??? \\\\\n",
    "&???\n",
    "\\end{align}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d1a3c0a",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-05T14:54:12.599506Z",
     "start_time": "2023-11-05T14:54:12.595902Z"
    }
   },
   "outputs": [],
   "source": [
    "# Logical constraints for the route's start and end time\n",
    "... # ???"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cc5f120",
   "metadata": {},
   "source": [
    "We need another set of constraints to establish the relationship between different routes assigned to a van. \n",
    "\n",
    "If you look at the constraints that we have written so far, you'll notice that nothing stops the model from assigning all the routes to one van.\n",
    "\n",
    "For any two routes, if one of them is assigned to a van, the other route can only be assigned to the same van if either its start time occurs after the end time of the first route or its end time occurs before the start time of the first route.\n",
    "\n",
    "Using indexes of $r \\in R$ and $h \\in R$ to refer to any two routes ($r \\ne h$), we need a way to say:\n",
    "\n",
    "For all $r \\in R$ and $h \\in R$ ($r \\neq h$), if there exists $v \\in V$ such that $y_{r,v} = 1$ and $y_{h,v} = 1$, then either $s_h \\geq e_r$ or $s_r \\geq e_h$.\n",
    "\n",
    "In other words, we want to say:\n",
    "- If two routes $r$ and $h$ are both assigned to the same van, then only one of the two constraints should be active\n",
    "- If neither route $r$ nor route $h$ are assigned to the same van, the constraints should be inactive\n",
    "\n",
    "Because we have an \"Either-Or\" structure between the two constraints, we use an indicator variable that when takes a value of 1, activates the first constraints and if it takes a value of 0, activates the second constraint. Let's call this indicator variable $\\delta_{r,h}$ and define it as follows:\n",
    "\n",
    "- $\\delta_{r,h}\\quad$: A binary variable equal to 1 if route $r \\in R$ and $h \\in R$ are served by the same van **and route $r$ comes before route $h$**\n",
    "\n",
    "<font color=red>**How should we write the constraints?**</font>  \n",
    "_Hint_: What you learned about building logical constraints using binary variables will be handy here!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f3fc4ec8",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-05T16:05:34.902133Z",
     "start_time": "2023-11-05T16:05:34.896090Z"
    }
   },
   "outputs": [],
   "source": [
    "rh_set = set((r1, r2) for r1 in r_set for r2 in r_set if r1 != r2)  # pair of (r,h) index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "db331279",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-05T16:05:36.447162Z",
     "start_time": "2023-11-05T16:05:36.444367Z"
    }
   },
   "outputs": [],
   "source": [
    "delta = mdl.addVars(rh_set, vtype=GRB.BINARY, name='d')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8c0a3030",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-05T16:00:23.982130Z",
     "start_time": "2023-11-05T16:00:23.978717Z"
    }
   },
   "outputs": [],
   "source": [
    "# Relation between any pair of routes assigned to a van\n",
    "... # ???"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "455b4685",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a9e0d5df",
   "metadata": {},
   "source": [
    "## Objectives"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cafeb700",
   "metadata": {},
   "source": [
    "In this model, we have two objectives:\n",
    "1. Maximize order coverage\n",
    "2. Minimize resource/van usage\n",
    "\n",
    "\\begin{align}\n",
    "\\max \\sum_{o} u_{o}\\\\\n",
    "\\min \\sum_{v} z_{v}\\\\\n",
    "\\end{align}\n",
    "\n",
    "We want to give a higher priority to the first objective. To use gurobi's multi-objective syntax, we can have one sense (i.e., minimize or maximize). This is easy since $\\max f(x) = \\min - f(x)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a7352d11",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-05T16:05:39.375861Z",
     "start_time": "2023-11-05T16:05:39.360519Z"
    }
   },
   "outputs": [],
   "source": [
    "mdl.ModelSense = GRB.MINIMIZE\n",
    "# weight=1: minimize, -1: maximize\n",
    "mdl.setObjectiveN(u.sum(), index=0, priority=2, name='order_coverage', weight=-1)\n",
    "mdl.setObjectiveN(z.sum(), index=1, priority=1, name='resource_usage', weight=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93782ff9",
   "metadata": {},
   "source": [
    "We can now tell Gurobi that the model is complete and it can solve the problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9b4669ff",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-05T16:05:44.539911Z",
     "start_time": "2023-11-05T16:05:44.491089Z"
    }
   },
   "outputs": [],
   "source": [
    "mdl.optimize()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9a1a8f4",
   "metadata": {},
   "source": [
    "## Post Processing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1f1b8fd1",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-05T16:05:47.134575Z",
     "start_time": "2023-11-05T16:05:47.076518Z"
    }
   },
   "outputs": [],
   "source": [
    "res_df = pd.DataFrame()\n",
    "status = mdl.status\n",
    "if status == GRB.OPTIMAL:\n",
    "    res_list = []\n",
    "    for k, val in y.items():\n",
    "        if val.x > 0.5:\n",
    "            rid, n = k  # route id, resource number\n",
    "            r = routes_dict[rid]\n",
    "            st = s[rid].x  # start time\n",
    "            rows = {'Resource Number': n, 'Route Number': rid, 'Start Time': st}\n",
    "            rows.update(r)\n",
    "            res_list.append(rows)\n",
    "    res_df = pd.DataFrame(res_list)\n",
    "    res_df = res_df.sort_values(by=['Resource Number', 'Start Time', 'Route Number'])\n",
    "    uncovered_orders = {o for o in order_route_dict if u[o].x < 0.5}\n",
    "    print(f'Number of uncovered orders:\\n {len(uncovered_orders)}')\n",
    "elif status in (GRB.INF_OR_UNBD, GRB.INFEASIBLE):\n",
    "    print('Model is either infeasible or unbounded.')\n",
    "else:\n",
    "    print(f'Status is {status} which is unexpected.')\n",
    "res_df"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1863587a",
   "metadata": {},
   "source": [
    "# Further Practice: Model Enhancement\n",
    "Make the following changes to the model:\n",
    "- Considering the input files, the output dataframe is not correct. Can you spot what's wrong about it?\n",
    "  - _Hint_: The fix is very easy and you don't need to change the mathematical model! In fact, we already talked about it.\n",
    "  - **Answer**: \n",
    "- Some orders are more important (maybe they are from the premium users) and should be favored.\n",
    "  - **Answer**: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f6ce465-db8c-4bc0-87a6-570058d7801c",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.18"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}