technician_routing_scheduling/technician_routing_scheduling.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Technician Routing and Scheduling Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective and Prerequisites\n",
    "\n",
    "Try this modeling example to discover how mathematical optimization can help telecommunications firms automate and improve their technician assignment, scheduling, and routing decisions in order to ensure the highest levels of customer satisfaction.\n",
    "\n",
    "This modeling example is at the intermediate level, where we assume that you know Python and are familiar with the Gurobi Python API. In addition, you have some knowledge about building mathematical optimization models. To fully understand the content of this notebook, you should be familiar with object-oriented-programming.\n",
    "\n",
    "**Download the Repository** <br /> \n",
    "You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Motivation\n",
    "The Technician Routing and Scheduling (TRS) is a common problem faced by telecommunication firms, which must be able to provide services for a large number of customers. With its limited resources, these firms must try to deliver timely, affordable and reliable services to maximize customer satisfaction. The TRS problem involves assignment, scheduling, and routing of multi-skilled technicians to serve customers with unique priorities, service time windows, processing times, skills requirements, and geographical locations. \n",
    "In the current practice, these decisions are often being made by operators via heuristics, sometimes manually -and this method\n",
    "can not only be time-consuming, \n",
    "but may also deviate from optima significantly. \n",
    "Using mathematical optimization to solve the\n",
    "TRS problem  will\n",
    "enable \n",
    "telecom operators and dispatchers to automate and improve their assignment, scheduling, and routing decisions, while achieving high customer satisfaction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "A telecom firm operates multiple service centers to serve its customers. \n",
    "Each service center has \n",
    "its technicians who are dispatched from the service center to work on their assigned jobs, and return to the center after all the jobs are completed. \n",
    "A technician has multiple skills and available working capacity that cannot be exceeded during the scheduling horizon. \n",
    "A service order/job has \n",
    "a known processing time, \n",
    "a customer-specified time window for starting the service, \n",
    "a deadline of completing the service, \n",
    "and its skill requirements. \n",
    "Depending on the nature of the job (routine maintenance or emergency), and relationship with the customer (existing, new), the firm assesses the importance of the job and assigns a priority score to it. \n",
    "A job is assigned to at most one technician who possesses the required \n",
    "skills, \n",
    "but the technician's available capacity during the scheduling horizon cannot be exceeded.\n",
    "To solve the  TRS problem, telecommunications companies must be able to\n",
    "simultaneously makes three types of decisions: (i) the assignment of jobs to a technician at all the service centers; \n",
    "(ii) the routing of each technician, i.e. the sequence/order of customers for a technician to visit; \n",
    "(iii) and the scheduling of jobs, i.e. the timing for a technician to arrive at a customer location and complete the corresponding job. \n",
    "The firm’s goal is to minimize the total weighted lateness of all  jobs, with their priority being the weights. \n",
    "\n",
    "The following constraints must be satisfied:\n",
    "* A technician, if utilized, departs from the service center where he/she is based and returns to the same service center after his/her assigned jobs are completed.\n",
    "* A technician’s available capacity during the scheduling horizon cannot be exceeded.\n",
    "* A job, if selected, is assigned to at most one technician who  possesses the required skills.\n",
    "* A technician must arrive at a customer location during an interval (time window) specified by the customer, and must complete a job before the deadline required by the customer. This an important constraint for guaranteeing customer satisfaction. \n",
    "\n",
    "The above basic TRS is a variant of the multi-depot vehicle routing problem with time windows, known as the MDVRPTW in the literature [1]. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution Approach\n",
    "\n",
    "Mathematical programming is a declarative approach where the modeler formulates a mathematical optimization model that captures the key aspects of a complex decision problem. The Gurobi Optimizer solves such models using state-of-the-art mathematics and computer science.\n",
    "\n",
    "A mathematical optimization model has five components, namely:\n",
    "\n",
    "* Sets and indices.\n",
    "* Parameters.\n",
    "* Decision variables.\n",
    "* Objective function(s).\n",
    "* Constraints.\n",
    "\n",
    "To simplify the MIP formulation, we consider that for each job's skill requirements, we can determine the subset of technicians that are qualified to perform the job based on the skills that the technicians have.\n",
    "\n",
    "We now present a MIP formulation for the basic TRS problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Formulation\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sets and Indices\n",
    "$j \\in J = \\{1,2,...,n\\}$: Index and set of jobs.\n",
    "\n",
    "$k \\in K$: Index and set of technicians.\n",
    "\n",
    "$K(j) \\subset K$: Subset of technicians qualified to perform job $j \\in J$ \n",
    "\n",
    "$d \\in D = \\{n+1, n+2, ...,n+m \\}$: Index and set of depots (service centers), where $m$ is the number of depots.\n",
    "\n",
    "$l, i, j \\in L = J \\cup D = \\{1,2,..., n+m \\}$: index and set of locations to visit.\n",
    "\n",
    "### Parameters\n",
    "$\\beta_{k,d} \\in \\{0,1\\}$: This parameter is equal 1 if technician $k \\in K$ must depart from and return to depot \n",
    "$d \\in D$; and 0 otherwise.\n",
    "\n",
    "$p_{j} \\in \\mathbb{R^{+}}$; Processing time (duration) of job $j \\in J$.\n",
    "\n",
    "$\\tau_{i,j} \\in \\mathbb{R^{+}}$: Travel time, in minutes, from location $i \\in L$ to location $j \\in L$.\n",
    "\n",
    "$W_{k} \\in \\mathbb{N}$: Workload limit of technician $k \\in K$ during the planning horizon. That is, the number of hours, in minutes, that the technician is available for the next work day.\n",
    "\n",
    "$\\pi_{j} \\in \\{1,2,3,4\\}$: Priority weight of job $j \\in J$, a larger number means higher priority.\n",
    "\n",
    "$a_{j} \\in \\mathbb{R^{+}} $: Earliest time to start the service at location of job $j \\in J$.\n",
    "\n",
    "$b_{j} \\in \\mathbb{R^{+}} $: Latest time to start the service at location of job $j \\in J$.\n",
    "\n",
    "$dd_{j} \\in \\mathbb{R^{+}} $: Due date of job $j \\in J$, i.e. the latest time to complete the service for job $j \\in J$.\n",
    "\n",
    "$M \\in \\mathbb{N}$: This is a very large number. This number is determined as follows: the planning horizon is of 10 working hours (i.e. 600 min). We want the value of $M$ to be an order of magnitude larger than the planning horizon. Therefore, we set M = 6100.\n",
    "\n",
    "### Decision Variables\n",
    "\n",
    "$x_{j,k} \\in \\{0,1\\}$: This variable is equal 1 if job $j \\in J$ is assigned to technician $k \\in K$, and 0 otherwise.\n",
    "\n",
    "$u_{k} \\in \\{0,1\\}$: This variable is equal 1 if technician $k \\in K$  is used to perform a job, and 0 otherwise.\n",
    "\n",
    "$y_{i,j,k} \\in \\{0,1\\}$: This variable is equal 1 if technician $k \\in K$  travels from location $i \\in L$ to location \n",
    "$j \\in L$; and 0 otherwise.\n",
    "\n",
    "$t_{j} \\geq 0$: This variable determines the time to arrive or start the service at location $j \\in J$.\n",
    "\n",
    "$z_{j} \\geq 0$: This variable determines the lateness of completing job $j \\in J$.\n",
    "\n",
    "$xa_{j}, xb_{j} \\geq 0$: Correction to earliest and latest time to start the service for job $j \\in J$.\n",
    "\n",
    "$g_{j}$: This variable is equal 1 if job $j \\in J$ cannot be filled, and 0 otherwise. \n",
    "\n",
    "### Objective Function\n",
    "\n",
    "- **Minimize lateness:** The Objective function is to minimize the total weighted lateness of all the jobs. \n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j \\in J} \\pi_{j} \\cdot z_{j} + \\sum_{j \\in J} 0.01 \\cdot \\pi_{j} \\cdot M(xa_{j} + xb_{j}) + \n",
    "\\sum_{j \\in J} \\pi_{j} \\cdot M \\cdot g_{j}\n",
    "\\tag{0}\n",
    "\\end{equation}\n",
    "\n",
    "**Note**: We want to treat the constraints of filling the jobs demand and the constraints about starting the jobs within a time window as soft constraints. Soft constraints can be violated, but the violation will incur in a huge penalty. To consider that each job has different priority, we use the priority penalty for the calculation of the penalty associated with a violation of soft constraints. We assume that not filling jobs demand greatly deteriorate customer satisfaction, consequently should incur the largest penalties associated with the soft constraints. Recall that the value of the paramter $M$ is a large number, then the penalty associated with not filling a job is determined as follows: $\\pi_{j} \\cdot M$. The time windows constraints violation also deteriorates customer satisfaction but to a lesser degree than the penalty associated with violating the time windows constraints. The time window constraints are determined as follows: $0.01 \\cdot \\pi_{j} \\cdot M$.\n",
    "\n",
    "### Constraints\n",
    "\n",
    "- **Assign qualified technicians:** For each job, we  assign one technician who is qualified for the job, or a gap is declared. \n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{k \\in K(j)} x_{j,k} + g_{j} = 1 \\quad \\forall j \\in J\n",
    "\\tag{1}\n",
    "\\end{equation}\n",
    "\n",
    "**Note**: The penalty of the gap variable $g_{j}$ is ($0.1 \\cdot \\pi_{j} \\cdot M$) which is a large number to discourage \n",
    "not being able to satisfy demand.\n",
    "\n",
    "- **Only one technician:** For each job, we only allow one technician to be assigned.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{k \\in K} x_{j,k} \\leq 1 \\quad \\forall j \\in J\n",
    "\\tag{2}\n",
    "\\end{equation}\n",
    "\n",
    "- **Technician capacity:** For each technician, we ensure that the available capacity of the technician is not exceeded. \n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j \\in J}  p_{j} \\cdot x_{j,k} + \\sum_{i \\in L} \\sum_{j \\in L} \\tau_{i,j} \\cdot y_{i,j,k} \\leq W_{k} \\cdot u_{k} \\quad \\forall k \\in K\n",
    "\\tag{3}\n",
    "\\end{equation}\n",
    "\n",
    "- **Technician tour:** For each technician and job, we ensure that if the technician is assigned to the job, then the technician must travel to another location (to form a tour). \n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j \\in L}  y_{i,j,k} = x_{i,k} \\quad \\forall i \\in J, k \\in K\n",
    "\\tag{4}\n",
    "\\end{equation}\n",
    "\n",
    "- For each technician and job, we ensure that if a technician is assigned to the job, then the technician must travel from another location to the location of the job (to form a tour). \n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{i \\in L}  y_{i,j,k} = x_{j,k} \\quad \\forall j \\in J, k \\in K\n",
    "\\tag{5}\n",
    "\\end{equation}\n",
    "\n",
    "- **Same depot:** For each technician and depot, we ensure that a technician, if assigned to any job, must depart from and return to the service center (depot) where the technician is based. \n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j \\in J}  y_{d,j,k} = \\beta_{k,d} \\cdot u_{k} \\quad \\forall  k \\in K, d \\in D\n",
    "\\tag{6}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{i \\in J}  y_{i,d,k} = \\beta_{k,d} \\cdot u_{k} \\quad \\forall  k \\in K, d \\in D\n",
    "\\tag{7}\n",
    "\\end{equation}\n",
    "\n",
    "- **Temporal relationship:** For each location and job, we ensure the temporal relationship between two consecutive jobs served by the same technician. That is, if a technician $k$ travels from job $i$ to job $j$, then the start of the service time at job $j$ must be no less than the completion time of job $i$ plus the travel time from job $i$ to job $j$. \n",
    "\n",
    "\\begin{equation}\n",
    "t_{j} \\geq t_{i} + p_{i} + \\tau_{i,j} - M \\cdot (1 - \\sum_{k \\in K}  y_{i,j,k}) \\quad \\forall i \\in L, j \\in J\n",
    "\\tag{8}\n",
    "\\end{equation}\n",
    "\n",
    "**Note**: Observe that if the technician $k$ travels from the location of job $i$ to the location of job $j$, then\n",
    "$\\sum_{k \\in K}  y_{i,j,k} = 1$. Therefore, $M \\cdot (1 - \\sum_{k \\in K}  y_{i,j,k}) = 0$, and the constraint \n",
    "$t_{j} \\geq t_{i} + p_{i} + \\tau_{i,j}$ would be properly enforced. Now consider the case where the technician $k$ does not travel  from the location of job $i$ to the location of job $j$. Hence, $\\sum_{k \\in K}  y_{i,j,k} = 0$ and \n",
    "$M \\cdot (1 - \\sum_{k \\in K}  y_{i,j,k}) = M$. In this case, this constraint becomes \n",
    "$t_{j} \\geq t_{i} + p_{i} + \\tau_{i,j} - M$. But $M$ is a very large number, then $t_{i} + p_{i} + \\tau_{i,j} - M < 0$ and \n",
    "since $t_{j} \\geq 0$, this constraint is redundant.\n",
    "\n",
    "- **Time window:** For each job $j \\in J$ ensure that the time window for the job is satisfied.\n",
    "\n",
    "\\begin{equation}\n",
    "t_{j} \\geq a_{j} - xa_{j} \\quad \\forall j \\in J\n",
    "\\tag{9}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "t_{j} \\leq b_{j} + xb_{j} \\quad \\forall j \\in J\n",
    "\\tag{10}\n",
    "\\end{equation}\n",
    "\n",
    "**Note**: To discourage that the time window of a job is violated, we associate the  penalty of \n",
    "($0.01 \\cdot \\pi_{j} \\cdot M$) to the correction variables $xa_{j}, xb_{j}$.\n",
    "\n",
    "- **Lateness constraint:** For each job $j \\in J$ calculate the lateness of the job.\n",
    "\n",
    "\\begin{equation}\n",
    "z_{j} \\geq t_{j} + p_{j} - dd_{j} \\quad \\forall j \\in J\n",
    "\\tag{11}\n",
    "\\end{equation}\n",
    "\n",
    "- Note that since the lateness decision variable $z_{j}$ is non-negative, there is no benefit to complete a job before its due date; on the other hand, since the objective function minimizes the total weighted lateness, Constraint (11) should always be binding."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Instance\n",
    "\n",
    "In this scenario, we consider the problem of routing and scheduling technicians for the next work-day in such a way that the delay of customer appointments is minimized. The telecom firm has seven technicians: Albert, Bob, Carlos, Doris, Ed, Flor, and Gina. There are two service centers: Heidelberg and Freiburg im Breisgau. Technicians are based at only one of these service centers. The number of hours available and the service center base (depot) for each technician is described in the following table.\n",
    "\n",
    "| <i></i> | Albert | Bob | Carlos | Doris | Ed | Flor | Gina |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- |\n",
    "| Minutes | 480 | 480 | 480 | 480 | 480 | 360 | 360 |\n",
    "| Depot | Heidelberg | Heidelberg | Freiburg im Breisgau | Freiburg im Breisgau | Heidelberg | Freiburg im Breisgau | Heidelberg |\n",
    "\n",
    "The telecom company has different type of jobs. \n",
    "The following table shows the priority (4 for the highest priority and 1 for the least important) and duration (in hours) of a job type.\n",
    "\n",
    "| <i></i> | Priority | Duration (min) |\n",
    "| --- | --- | --- | \n",
    "| Equipment Installation | 2 | 60 |\n",
    "| Equipment Setup | 3 | 30 |\n",
    "| Inspect/Service Equipment | 1 | 60 |\n",
    "| Repair - Regular | 1 | 60 |\n",
    "| Repair - Important | 2 | 120 |\n",
    "| Repair - Urgent | 3 | 90 |\n",
    "| Repair - Critical | 4 | 60 |\n",
    "\n",
    "The following table shows the jobs that each technician is qualified for.\n",
    "\n",
    "| <i></i> | Albert | Bob | Carlos | Doris | Ed | Flor | Gina |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- |\n",
    "| Equipment Installation | - | - | - | 1 | - | 1 | 1 |\n",
    "| Equipment Setup | 1 | 1 | 1 | 1 | - | - | 1 |\n",
    "| Inspect/Service Equipment | 1 | - | 1 | - | 1 | - | - |\n",
    "| Repair - Regular | - | 1 | 1 | - | 1 | 1 | 1 |\n",
    "| Repair - Important | - | - | - | 1 | - | 1 | 1 |\n",
    "| Repair - Urgent | - | 1 | 1 | - | 1 | 1 | 1 |\n",
    "| Repair - Critical | - | - | - | 1 | - | - | 1 |\n",
    "\n",
    "The telecom company receives customers' requests for a specific job type, appointment (due) time, and the service time window where the technician can arrive. The following table shows the customers' orders and their requirements. For each customer, the location is specified.\n",
    "\n",
    "| <i></i> | C1:Mannheim  | C2: Karlsruhe  | C3: Baden-Baden  | C4: Bühl  | C5: Offenburg | C6: Lahr/Schwarzwald | C7: Lörrach |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- |\n",
    "| Job type | Equipment Setup | Equipment Setup | Repair - Regular | Equipment Installation | Equipment Installation | Repair - Critical | Inspect/Service Equipment |\n",
    "| Due time | 8:00 | 10:00 | 11:00  | 12:00 | 14:00 | 15:00 | 16:00 |\n",
    "| Time Window | 7:00-7:30 | 7:30-9:30 | 8:00-10:00 | 9:00-11:00 | 11:00-13:00 | 12:00-14:00 | 13:00-15:00 |\n",
    "\n",
    "The planning horizon is from 7:00 to 17:00, or 10 hours. The time period is in minutes, then the due time and time windows will be translated into minutes starting at 0 minutes and ending at 600 minutes. For example, for customer C2 the due time is at 10:00  (180 min), and the time window is from 7:30 to 9:30  (30 min to  150 min). \n",
    "\n",
    "The following table shows the travel time (in minutes) from any depot or customer location to any depot or customer location.\n",
    "\n",
    "| <i></i> | Heidelberg | Freiburg im Breisgau | Mannheim  | Karlsruhe  | Baden-Baden  | Bühl  | Offenburg | Lahr/Schwarzwald | Lörrach |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- |--- |--- |\n",
    "| Heidelberg | - | 120 | 24 | 50 | 67 | 71 | 88 | 98 | 150 |\n",
    "| Freiburg im Breisgau | - | - | 125 | 85 | 68 | 62 | 45 | 39 | 48 |\n",
    "| Mannheim | - | - | - | 53 | 74 | 77 | 95 | 106 | 160 |\n",
    "| Karlsruhe | - | - | - | - | 31 | 35 | 51 | 61 | 115 |\n",
    "| Baden-Baden | - | - | - | - | - | 16 | 36 | 46 | 98 |\n",
    "| Bühl | - | - | - | - | - | - | 30 | 40 | 92 |\n",
    "| Offenburg | - | - | - | - | - | - | - | 26 | 80 |\n",
    "| Lahr/Schwarzwald | - | - | - | - | - | - | - | - | 70 |\n",
    "| Lörrach | - | - | - | - | - | - | - | - | - |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python Implementation\n",
    "\n",
    "In this Jupyter Notebook, we use the following libraries:\n",
    "\n",
    "* `sys` to access system-specific parameters and functions.\n",
    "* `pandas` to read data from Excel files.\n",
    "* `gurobipy` Gurobi Optimizer library.\n",
    "\n",
    "This implementation is based on object-oriented-programming.\n",
    "\n",
    "### Helper Classes\n",
    "\n",
    "The following classes properly organize the input data of the MIP model.\n",
    "\n",
    "* `Technician`.\n",
    "* `Job`.\n",
    "* `Customer`.\n",
    "\n",
    "### Helper Functions\n",
    "\n",
    "* `solve_trs0` builds and solves MIP model.\n",
    "* `printScen` prints headings for output reports.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Defaulting to user installation because normal site-packages is not writeable\n",
      "Requirement already satisfied: gurobipy in c:\\users\\marika.karbstein\\appdata\\roaming\\python\\python39\\site-packages (10.0.2)\n",
      "Note: you may need to restart the kernel to use updated packages.\n"
     ]
    }
   ],
   "source": [
    "%pip install gurobipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "import pandas as pd\n",
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "\n",
    "# tested with Gurobi v10.0.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Technician():\n",
    "    def __init__(self, name, cap, depot):\n",
    "        self.name = name\n",
    "        self.cap = cap\n",
    "        self.depot = depot\n",
    "\n",
    "    def __str__(self):\n",
    "        return f\"Technician: {self.name}\\n  Capacity: {self.cap}\\n  Depot: {self.depot}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Job():\n",
    "    def __init__(self, name, priority, duration, coveredBy):\n",
    "        self.name = name\n",
    "        self.priority = priority\n",
    "        self.duration = duration\n",
    "        self.coveredBy = coveredBy\n",
    "\n",
    "    def __str__(self):\n",
    "        about = f\"Job: {self.name}\\n  Priority: {self.priority}\\n  Duration: {self.duration}\\n  Covered by: \"\n",
    "        about += \", \".join([t.name for t in self.coveredBy])\n",
    "        return about"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Customer():\n",
    "    def __init__(self, name, loc, job, tStart, tEnd, tDue):\n",
    "        self.name = name\n",
    "        self.loc = loc\n",
    "        self.job = job\n",
    "        self.tStart = tStart\n",
    "        self.tEnd = tEnd\n",
    "        self.tDue = tDue\n",
    "\n",
    "    def __str__(self):\n",
    "        coveredBy = \", \".join([t.name for t in self.job.coveredBy])\n",
    "        return f\"Customer: {self.name}\\n  Location: {self.loc}\\n  Job: {self.job.name}\\n  Priority: {self.job.priority}\\n  Duration: {self.job.duration}\\n  Covered by: {coveredBy}\\n  Start time: {self.tStart}\\n  End time: {self.tEnd}\\n  Due time: {self.tDue}\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Base Scenario\n",
    "\n",
    "For the base scenario, there is enough technician capacity to fill all customers demand. To run the base scenario, consider the spreadsheet file `data-Sce0.xlsx` and insert this name when you open the Excel workbook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read Excel workbook\n",
    "excel_file = 'https://raw.githubusercontent.com/Gurobi/modeling-examples/master/technician_routing_scheduling/data-Sce0.xlsx'\n",
    "df = pd.read_excel(excel_file, sheet_name='Technicians')\n",
    "df = df.rename(columns={df.columns[0]: \"name\", df.columns[1]: \"cap\", df.columns[2]: \"depot\"})\n",
    "\n",
    "df1 = df.drop(df.columns[3:], axis=1).drop(df.index[[0,1]])\n",
    "# Create Technician objects\n",
    "technicians = [Technician(*row) for row in df1.itertuples(index=False, name=None)]\n",
    "# print(df1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read job data\n",
    "jobs=[]\n",
    "for j in range(3, len(df.columns)):\n",
    "    coveredBy = [t for i, t in enumerate(technicians) if df.iloc[2+i,j]==1]\n",
    "    thisJob = Job(df.iloc[2:,j].name, df.iloc[0,j], df.iloc[1,j], coveredBy)\n",
    "    jobs.append(thisJob)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read location data\n",
    "df_locations = pd.read_excel(excel_file, sheet_name='Locations', index_col=0) #, skiprows=1, index_col=0)\n",
    "\n",
    "# Extract locations and initialize distance dictionary\n",
    "locations = df_locations.index\n",
    "dist = {(l, l): 0 for l in locations}\n",
    "\n",
    "# Populate distance dictionary\n",
    "for i, l1 in enumerate(locations):\n",
    "    for j, l2 in enumerate(locations):\n",
    "        if i < j:\n",
    "            dist[l1, l2] = df_locations.iloc[i, j]\n",
    "            dist[l2, l1] = dist[l1, l2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read customer data\n",
    "df_customers = pd.read_excel(excel_file, sheet_name='Customers')\n",
    "\n",
    "customers = []\n",
    "for i, c in enumerate(df_customers.iloc[:, 0]):\n",
    "    job_name = df_customers.iloc[i, 2]\n",
    "    \n",
    "    # Find the corresponding Job object\n",
    "    matching_job = next((job for job in jobs if job.name == job_name), None)\n",
    "    \n",
    "    if matching_job is not None:\n",
    "        # Create Customer object using corresponding Job object\n",
    "        this_customer = Customer(c, df_customers.iloc[i, 1], matching_job, *df_customers.iloc[i, 3:])\n",
    "        customers.append(this_customer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_trs0(technicians, customers, dist):\n",
    "    # Build useful data structures\n",
    "    K = [k.name for k in technicians]\n",
    "    C = [j.name for j in customers]\n",
    "    J = [j.loc for j in customers]\n",
    "    L = list(set([l[0] for l in dist.keys()]))\n",
    "    D = list(set([t.depot for t in technicians]))\n",
    "    cap = {k.name : k.cap for k in technicians}\n",
    "    loc = {j.name : j.loc for j in customers}\n",
    "    depot = {k.name : k.depot for k in technicians}\n",
    "    canCover = {j.name : [k.name for k in j.job.coveredBy] for j in customers}\n",
    "    dur = {j.name : j.job.duration for j in customers}\n",
    "    tStart = {j.name : j.tStart for j in customers}\n",
    "    tEnd = {j.name : j.tEnd for j in customers}\n",
    "    tDue = {j.name : j.tDue for j in customers}\n",
    "    priority = {j.name : j.job.priority for j in customers}\n",
    "    \n",
    "        ### Create model\n",
    "    m = gp.Model(\"trs0\")\n",
    "    \n",
    "    ### Decision variables\n",
    "    # Customer-technician assignment\n",
    "    x = m.addVars(C, K, vtype=GRB.BINARY, name=\"x\")\n",
    "    \n",
    "    # Technician assignment\n",
    "    u = m.addVars(K, vtype=GRB.BINARY, name=\"u\")\n",
    "    \n",
    "    # Edge-route assignment to technician\n",
    "    y = m.addVars(L, L, K, vtype=GRB.BINARY, name=\"y\")\n",
    "   \n",
    "    # Technician cannot leave or return to a depot that is not its base\n",
    "    for k in technicians:\n",
    "        for d in D:\n",
    "            if k.depot != d:\n",
    "                for i in L:\n",
    "                    y[i,d,k.name].ub = 0\n",
    "                    y[d,i,k.name].ub = 0\n",
    "    \n",
    "    # Start time of service\n",
    "    t = m.addVars(L, ub=600, name=\"t\")\n",
    "    \n",
    "    # Lateness of service\n",
    "    z = m.addVars(C, name=\"z\")\n",
    "    \n",
    "    # Artificial variables to correct time window upper and lower limits\n",
    "    xa = m.addVars(C, name=\"xa\")\n",
    "    xb = m.addVars(C, name=\"xb\")\n",
    "    \n",
    "    # Unfilled jobs\n",
    "    g = m.addVars(C, vtype=GRB.BINARY, name=\"g\")\n",
    "    \n",
    "        ### Constraints\n",
    "\n",
    "    # A technician must be assigned to a job, or a gap is declared (1)\n",
    "    m.addConstrs((gp.quicksum(x[j, k] for k in canCover[j]) + g[j] == 1 for j in C), name=\"assignToJob\")\n",
    "    \n",
    "    # At most one technician can be assigned to a job (2)\n",
    "    m.addConstrs((x.sum(j, '*') <= 1 for j in C), name=\"assignOne\")\n",
    "\n",
    "    # Technician capacity constraints (3)\n",
    "    capLHS = {k : gp.quicksum(dur[j]*x[j,k] for j in C) +\\\n",
    "        gp.quicksum(dist[i,j]*y[i,j,k] for i in L for j in L) for k in K}\n",
    "    m.addConstrs((capLHS[k] <= cap[k]*u[k] for k in K), name=\"techCapacity\")\n",
    "\n",
    "    # Technician tour constraints (4 and 5)\n",
    "    m.addConstrs((y.sum('*', loc[j], k) == x[j,k] for k in K for j in C),\\\n",
    "        name=\"techTour1\")\n",
    "    m.addConstrs((y.sum(loc[j], '*', k) == x[j,k] for k in K for j in C),\\\n",
    "        name=\"techTour2\")\n",
    "\n",
    "    # Same depot constraints (6 and 7)\n",
    "    m.addConstrs((gp.quicksum(y[j,depot[k],k] for j in J) == u[k] for k in K),\\\n",
    "        name=\"sameDepot1\")\n",
    "    m.addConstrs((gp.quicksum(y[depot[k],j,k] for j in J) == u[k] for k in K),\\\n",
    "        name=\"sameDepot2\")\n",
    "\n",
    "    # Temporal constraints (8) for customer locations\n",
    "    M = {(i,j) : 600 + dur[i] + dist[loc[i], loc[j]] for i in C for j in C}\n",
    "    m.addConstrs((t[loc[j]] >= t[loc[i]] + dur[i] + dist[loc[i], loc[j]]\\\n",
    "        - M[i,j]*(1 - gp.quicksum(y[loc[i],loc[j],k] for k in K))\\\n",
    "        for i in C for j in C), name=\"tempoCustomer\")\n",
    "\n",
    "    # Temporal constraints (8) for depot locations\n",
    "    M = {(i,j) : 600 + dist[i, loc[j]] for i in D for j in C}\n",
    "    m.addConstrs((t[loc[j]] >= t[i] + dist[i, loc[j]]\\\n",
    "        - M[i,j]*(1 - y.sum(i,loc[j],'*')) for i in D for j in C),\\\n",
    "        name=\"tempoDepot\")\n",
    "\n",
    "    # Time window constraints (9 and 10)\n",
    "    m.addConstrs((t[loc[j]] + xa[j] >= tStart[j] for j in C), name=\"timeWinA\")\n",
    "    m.addConstrs((t[loc[j]] - xb[j] <= tEnd[j] for j in C), name=\"timeWinB\")\n",
    "\n",
    "    # Lateness constraint (11)\n",
    "    m.addConstrs((z[j] >= t[loc[j]] + dur[j] - tDue[j] for j in C),\\\n",
    "        name=\"lateness\")\n",
    "\n",
    "    ### Objective function\n",
    "    M = 6100\n",
    "    \n",
    "    m.setObjective(z.prod(priority) + gp.quicksum( 0.01 * M * priority[j] * (xa[j] + xb[j]) for j in C) +\n",
    "                   gp.quicksum( M * priority[j] * g[j] for j in C) , GRB.MINIMIZE)\n",
    "    \n",
    "    m.write(\"TRS0.lp\")\n",
    "    m.optimize()\n",
    "\n",
    "    status = m.Status\n",
    "    if status in [GRB.INF_OR_UNBD, GRB.INFEASIBLE, GRB.UNBOUNDED]:\n",
    "        print(\"Model is either infeasible or unbounded.\")\n",
    "        sys.exit(0)\n",
    "    elif status != GRB.OPTIMAL:\n",
    "        print(\"Optimization terminated with status {}\".format(status))\n",
    "        sys.exit(0)\n",
    "        \n",
    "    ### Print results\n",
    "    # Assignments\n",
    "    print(\"\")\n",
    "    for j in customers:\n",
    "        if g[j.name].X > 0.5:\n",
    "            jobStr = \"Nobody assigned to {} ({}) in {}\".format(j.name,j.job.name,j.loc)\n",
    "        else:\n",
    "            for k in K:\n",
    "                if x[j.name,k].X > 0.5:\n",
    "                    jobStr = \"{} assigned to {} ({}) in {}. Start at t={:.2f}.\".format(k,j.name,j.job.name,j.loc,t[j.loc].X)\n",
    "                    if z[j.name].X > 1e-6:\n",
    "                        jobStr += \" {:.2f} minutes late.\".format(z[j.name].X)\n",
    "                    if xa[j.name].X > 1e-6:\n",
    "                        jobStr += \" Start time corrected by {:.2f} minutes.\".format(xa[j.name].X)\n",
    "                    if xb[j.name].X > 1e-6:\n",
    "                        jobStr += \" End time corrected by {:.2f} minutes.\".format(xb[j.name].X)\n",
    "        print(jobStr)\n",
    "\n",
    "    # Technicians\n",
    "    print(\"\")\n",
    "    for k in technicians:\n",
    "        if u[k.name].X > 0.5:\n",
    "            cur = k.depot\n",
    "            route = k.depot\n",
    "            while True:\n",
    "                for j in customers:\n",
    "                    if y[cur,j.loc,k.name].X > 0.5:\n",
    "                        route += \" -> {} (dist={}, t={:.2f}, proc={})\".format(j.loc, dist[cur,j.loc], t[j.loc].X, j.job.duration)\n",
    "                        cur = j.loc\n",
    "                for i in D:\n",
    "                    if y[cur,i,k.name].X > 0.5:\n",
    "                        route += \" -> {} (dist={})\".format(i, dist[cur,i])\n",
    "                        cur = i\n",
    "                        break\n",
    "                if cur == k.depot:\n",
    "                    break\n",
    "            print(\"{}'s route: {}\".format(k.name, route))\n",
    "        else:\n",
    "            print(\"{} is not used\".format(k.name)) \n",
    "            \n",
    "    \n",
    "    # Utilization\n",
    "    print(\"\")\n",
    "    for k in K:\n",
    "        used = capLHS[k].getValue()\n",
    "        total = cap[k]\n",
    "        util = used / cap[k] if cap[k] > 0 else 0\n",
    "        print(\"{}'s utilization is {:.2%} ({:.2f}/{:.2f})\".format(k, util,\\\n",
    "            used, cap[k]))\n",
    "    totUsed = sum(capLHS[k].getValue() for k in K)\n",
    "    totCap = sum(cap[k] for k in K)\n",
    "    totUtil = totUsed / totCap if totCap > 0 else 0\n",
    "    print(\"Total technician utilization is {:.2%} ({:.2f}/{:.2f})\".format(totUtil, totUsed, totCap))\n",
    "    \n",
    "    m.dispose()\n",
    "    gp.disposeDefaultEnv()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def printScen(scenStr):\n",
    "    sLen = len(scenStr)\n",
    "    print(\"\\n\" + \"*\"*sLen + \"\\n\" + scenStr + \"\\n\" + \"*\"*sLen + \"\\n\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "***************************\n",
      "Solving base scenario model\n",
      "***************************\n",
      "\n",
      "Restricted license - for non-production use only - expires 2024-10-28\n",
      "Warning: variable name \"y[Karlsruhe,Freiburg im Breisgau,Albert]\" has a space\n",
      "Warning: constraint name \"tempoDepot[Freiburg im Breisgau,Customer1]\" has a space\n",
      "Warning: to let Gurobi read it back, use rlp format\n",
      "Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (win64)\n",
      "\n",
      "CPU model: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz, instruction set [SSE2|AVX|AVX2|AVX512]\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "\n",
      "Optimize a model with 217 rows, 660 columns and 2329 nonzeros\n",
      "Model fingerprint: 0x8bfebb74\n",
      "Variable types: 30 continuous, 630 integer (630 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 8e+02]\n",
      "  Objective range  [1e+00, 2e+04]\n",
      "  Bounds range     [1e+00, 6e+02]\n",
      "  RHS range        [1e+00, 6e+02]\n",
      "Found heuristic solution: objective 245830.00000\n",
      "Presolve removed 28 rows and 188 columns\n",
      "Presolve time: 0.01s\n",
      "Presolved: 189 rows, 472 columns, 2129 nonzeros\n",
      "Variable types: 26 continuous, 446 integer (446 binary)\n",
      "\n",
      "Root relaxation: objective 0.000000e+00, 103 iterations, 0.00 seconds (0.00 work units)\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "H    0     0                       0.0000000 -256200.00      -     -    0s\n",
      "     0     0          -    0         0.00000    0.00000  0.00%     -    0s\n",
      "\n",
      "Explored 1 nodes (294 simplex iterations) in 0.03 seconds (0.01 work units)\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 2: 0 245830 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%\n",
      "\n",
      "Gina assigned to Customer1 (Equipment Setup) in Mannheim. Start at t=30.00.\n",
      "Carlos assigned to Customer2 (Equipment Setup) in Karlsruhe. Start at t=113.00.\n",
      "Carlos assigned to Customer3 (Repair - Regular) in Baden-Baden. Start at t=174.00.\n",
      "Doris assigned to Customer4 (Equipment Installation) in Buehl. Start at t=120.00.\n",
      "Doris assigned to Customer5 (Equipment Installation) in Offenburg. Start at t=360.00.\n",
      "Gina assigned to Customer6 (Repair - Critical) in Lahr/Schwarzwald. Start at t=420.00.\n",
      "Carlos assigned to Customer7 (Inspect/Service Equipment) in Loerrach. Start at t=360.00.\n",
      "\n",
      "Albert is not used\n",
      "Bob is not used\n",
      "Carlos's route: Freiburg im Breisgau -> Karlsruhe (dist=85.0, t=113.00, proc=30.0) -> Baden-Baden (dist=31.0, t=174.00, proc=60.0) -> Loerrach (dist=98.0, t=360.00, proc=60.0) -> Freiburg im Breisgau (dist=48.0)\n",
      "Doris's route: Freiburg im Breisgau -> Buehl (dist=62.0, t=120.00, proc=60.0) -> Offenburg (dist=30.0, t=360.00, proc=60.0) -> Freiburg im Breisgau (dist=45.0)\n",
      "Ed is not used\n",
      "Flor is not used\n",
      "Gina's route: Heidelberg -> Mannheim (dist=24.0, t=30.00, proc=30.0) -> Lahr/Schwarzwald (dist=106.0, t=420.00, proc=60.0) -> Heidelberg (dist=98.0)\n",
      "\n",
      "Albert's utilization is 0.00% (0.00/480.00)\n",
      "Bob's utilization is 0.00% (0.00/480.00)\n",
      "Carlos's utilization is 85.83% (412.00/480.00)\n",
      "Doris's utilization is 53.54% (257.00/480.00)\n",
      "Ed's utilization is 0.00% (0.00/480.00)\n",
      "Flor's utilization is 0.00% (0.00/360.00)\n",
      "Gina's utilization is 88.33% (318.00/360.00)\n",
      "Total technician utilization is 31.63% (987.00/3120.00)\n",
      "Freeing default Gurobi environment\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    # Base model\n",
    "    printScen(\"Solving base scenario model\")\n",
    "    solve_trs0(technicians, customers, dist)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Base Scenario Analysis\n",
    "For the base scenario, we have enough technician capacity to satisfy customers demand. Notice that the optimal objective function value is 0.00, this means that all jobs were completed, they were completed on time, and there were no corrections to the time window limits.\n",
    "\n",
    "The first report describes which technician was assigned to each customer, the location of the customer, and the start time of the job. The second report describes the route of each assigned technician. The route defines the *from-location* and the \n",
    "*to-location*. The parameter *dist*  defines the number of minutes that it takes to drive from the *from-location* to the *to-location*. The parameter t determines the *start-time* of the job at the *to-location*. The parameter *proc*  shows the number of minutes that it takes the technician to complete the job. \n",
    "The third report describes the capacity utilization of each technician and the overall capacity utilization of all technicians. The technician capacity utilization is the number of minutes the technician spends driving or serving customers, divided by the technician capacity. The overall capacity utilization of all technicians is the total number of minutes that all technicians spend driving or serving customers, divided by the total capacity of all the technicians available. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scenario 1\n",
    "\n",
    "We assume that technicians are working at half of their capacity. Also, we assume that customer 5 requires an urgent service and its due time is at 00 min. Since the due time has changed, we remove the time window limits, that is the time window is any time within the planning horizon. The new time window is [0, 600].\n",
    "\n",
    "To run this scenario, consider the spreadsheet file `data-Sce3.xlsx` and insert this name when you open the Excel workbook.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Open Excel workbook\n",
    "excel_file = 'https://raw.githubusercontent.com/Gurobi/modeling-examples/master/technician_routing_scheduling/data-Sce3.xlsx'\n",
    "\n",
    "# Read technician data\n",
    "df = pd.read_excel(excel_file, sheet_name='Technicians')\n",
    "df = df.rename(columns={df.columns[0]: \"name\", df.columns[1]: \"cap\", df.columns[2]: \"depot\"})\n",
    "\n",
    "df1 = df.drop(df.columns[3:], axis=1).drop(df.index[[0,1]])\n",
    "# Create Technician objects\n",
    "technicians = [Technician(*row) for row in df1.itertuples(index=False, name=None)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read job data\n",
    "jobs=[]\n",
    "for j in range(3, len(df.columns)):\n",
    "    coveredBy = [t for i, t in enumerate(technicians) if df.iloc[2+i,j]==1]\n",
    "    thisJob = Job(df.iloc[2:,j].name, df.iloc[0,j], df.iloc[1,j], coveredBy)\n",
    "    jobs.append(thisJob)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read location data\n",
    "df_locations = pd.read_excel(excel_file, sheet_name='Locations', index_col=0) #, skiprows=1, index_col=0)\n",
    "\n",
    "# Extract locations and initialize distance dictionary\n",
    "locations = df_locations.index\n",
    "dist = {(l, l): 0 for l in locations}\n",
    "\n",
    "# Populate distance dictionary\n",
    "for i, l1 in enumerate(locations):\n",
    "    for j, l2 in enumerate(locations):\n",
    "        if i < j:\n",
    "            dist[l1, l2] = df_locations.iloc[i, j]\n",
    "            dist[l2, l1] = dist[l1, l2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read customer data\n",
    "df_customers = pd.read_excel(excel_file, sheet_name='Customers')\n",
    "\n",
    "customers = []\n",
    "for i, c in enumerate(df_customers.iloc[:, 0]):\n",
    "    job_name = df_customers.iloc[i, 2]\n",
    "    \n",
    "    # Find the corresponding Job object\n",
    "    matching_job = next((job for job in jobs if job.name == job_name), None)\n",
    "    \n",
    "    if matching_job is not None:\n",
    "        # Create Customer object using corresponding Job object\n",
    "        this_customer = Customer(c, df_customers.iloc[i, 1], matching_job, *df_customers.iloc[i, 3:])\n",
    "        customers.append(this_customer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "************************\n",
      "Solving scenario 1 model\n",
      "************************\n",
      "\n",
      "Restricted license - for non-production use only - expires 2024-10-28\n",
      "Warning: variable name \"y[Karlsruhe,Freiburg im Breisgau,Albert]\" has a space\n",
      "Warning: constraint name \"tempoDepot[Freiburg im Breisgau,Customer1]\" has a space\n",
      "Warning: to let Gurobi read it back, use rlp format\n",
      "Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (win64)\n",
      "\n",
      "CPU model: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz, instruction set [SSE2|AVX|AVX2|AVX512]\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "\n",
      "Optimize a model with 217 rows, 660 columns and 2329 nonzeros\n",
      "Model fingerprint: 0x10d7b4f8\n",
      "Variable types: 30 continuous, 630 integer (630 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 8e+02]\n",
      "  Objective range  [1e+00, 2e+04]\n",
      "  Bounds range     [1e+00, 6e+02]\n",
      "  RHS range        [1e+00, 6e+02]\n",
      "Found heuristic solution: objective 216670.00000\n",
      "Presolve removed 168 rows and 593 columns\n",
      "Presolve time: 0.02s\n",
      "Presolved: 49 rows, 67 columns, 279 nonzeros\n",
      "Found heuristic solution: objective 24610.000000\n",
      "Variable types: 15 continuous, 52 integer (52 binary)\n",
      "\n",
      "Root relaxation: objective 8.214242e+03, 14 iterations, 0.00 seconds (0.00 work units)\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0 8214.24242    0    6 24610.0000 8214.24242  66.6%     -    0s\n",
      "*    0     0               0    12410.000000 12410.0000  0.00%     -    0s\n",
      "\n",
      "Explored 1 nodes (15 simplex iterations) in 0.04 seconds (0.01 work units)\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 3: 12410 24610 216670 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 1.241000000000e+04, best bound 1.241000000000e+04, gap 0.0000%\n",
      "\n",
      "Gina assigned to Customer1 (Equipment Setup) in Mannheim. Start at t=24.00.\n",
      "Bob assigned to Customer2 (Equipment Setup) in Karlsruhe. Start at t=50.00.\n",
      "Bob assigned to Customer3 (Repair - Regular) in Baden-Baden. Start at t=111.00.\n",
      "Nobody assigned to Customer4 (Equipment Installation) in Buehl\n",
      "Flor assigned to Customer5 (Equipment Installation) in Offenburg. Start at t=45.00. 105.00 minutes late.\n",
      "Doris assigned to Customer6 (Repair - Critical) in Lahr/Schwarzwald. Start at t=300.00.\n",
      "Carlos assigned to Customer7 (Inspect/Service Equipment) in Loerrach. Start at t=480.00.\n",
      "\n",
      "Albert is not used\n",
      "Bob's route: Heidelberg -> Karlsruhe (dist=50.0, t=50.00, proc=30.0) -> Baden-Baden (dist=31.0, t=111.00, proc=60.0) -> Heidelberg (dist=67.0)\n",
      "Carlos's route: Freiburg im Breisgau -> Loerrach (dist=48.0, t=480.00, proc=60.0) -> Freiburg im Breisgau (dist=48.0)\n",
      "Doris's route: Freiburg im Breisgau -> Lahr/Schwarzwald (dist=39.0, t=300.00, proc=60.0) -> Freiburg im Breisgau (dist=39.0)\n",
      "Ed is not used\n",
      "Flor's route: Freiburg im Breisgau -> Offenburg (dist=45.0, t=45.00, proc=60.0) -> Freiburg im Breisgau (dist=45.0)\n",
      "Gina's route: Heidelberg -> Mannheim (dist=24.0, t=24.00, proc=30.0) -> Heidelberg (dist=24.0)\n",
      "\n",
      "Albert's utilization is 0.00% (0.00/240.00)\n",
      "Bob's utilization is 99.17% (238.00/240.00)\n",
      "Carlos's utilization is 65.00% (156.00/240.00)\n",
      "Doris's utilization is 57.50% (138.00/240.00)\n",
      "Ed's utilization is 0.00% (0.00/240.00)\n",
      "Flor's utilization is 83.33% (150.00/180.00)\n",
      "Gina's utilization is 43.33% (78.00/180.00)\n",
      "Total technician utilization is 48.72% (760.00/1560.00)\n",
      "Freeing default Gurobi environment\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    # Base model\n",
    "    printScen(\"Solving scenario 1 model\")\n",
    "    solve_trs0(technicians, customers, dist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scenario 1 Analysis\n",
    "\n",
    "We assume that technicians are working at half of their capacity. Also, we assume that customer 5 requires an urgent service and its due time is at 00 min. Since the due time has changed, we remove the time window limits, that is the time window is any time within the planning horizon. The new time window is [0, 600].\n",
    "\n",
    "* Six jobs out of seven are filled.\n",
    "  * The service of customer 5 will be 105 min late. \n",
    "  * The start time is at min 45 which is within the time window of [0, 600].\n",
    "* Service requirement of Customer 4 could not be filled. \n",
    "  * Observe that the priority of this customer is low.\n",
    "* Six technicians were assigned to fill the requirements of 6 customers.\n",
    "* Ed was not assigned to any customer. \n",
    "  * Notice that Ed is not qualified for the job of Customer 4 (Equipment Installation).\n",
    "* The overall technician utilization is 54.23%."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "In this Jupyter Notebook, we formulated and solved a multi-depot vehicle routing problem with time windows constraints using the Gurobi Python API. This MIP formulation is an optimization application for the telecommunication industry; however, the formulation is quite general and can easily be adapted to any kind of vehicle routing problems in the transportation and logistics industries.\n",
    "\n",
    "The routing and scheduling problem that we tackled considers a telecom firm that operates multiple service centers to serve its customers. We solved this routing and scheduling problem by simultaneously making three types of decisions: \n",
    "- (i) the assignment of jobs to a technician at all the service centers\n",
    "- (ii) the routing of each technician, i.e. the sequence/order of customers for a technician to visit\n",
    "- (iii) the scheduling of jobs, i.e. the timing for a technician to arrive at a customer location and complete the corresponding job. \n",
    "\n",
    "The objective of the telecom firm is to minimize the total weighted lateness of all the jobs.\n",
    "\n",
    "In this notebook, we discussed two scenarios, the base scenario has enough technicians' capacity to fill all customers demand on time. In scenario 1, we reduced the capacity of all technicians by half, and one customer has an emergency that requires service first thing in the morning. The scenario captures various trade-offs that the MIP model needs to consider given the limited technician capacity and customers' job priority and requirements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "[1] S. Salhi, A. Imran, N. A. Wassan. *The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation*. Computers & Operations Research 52 (2014) 315-325."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copyright © 2020 Gurobi Optimization, LLC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}