{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "<!--NOTEBOOK_HEADER-->\n",
    "*This notebook contains course material from [CBE40455](https://jckantor.github.io/CBE40455) by\n",
    "Jeffrey Kantor (jeff at nd.edu); the content is available [on Github](https://github.com/jckantor/CBE40455.git).\n",
    "The text is released under the [CC-BY-NC-ND-4.0 license](https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode),\n",
    "and code is released under the [MIT license](https://opensource.org/licenses/MIT).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "<!--NAVIGATION-->\n",
    "< [Traveling Salesman Problem with Time Windows](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/05.05-Traveling-Salesman-Problem-with-Time-Windows.ipynb) | [Contents](toc.ipynb) | [Stock Cutting](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/05.07-Stock-Cutting.ipynb) ><p><a href=\"https://colab.research.google.com/github/jckantor/CBE40455/blob/master/notebooks/05.06-Pickup-and-Delivery.ipynb\"><img align=\"left\" src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open in Colab\" title=\"Open in Google Colaboratory\"></a><p><a href=\"https://raw.githubusercontent.com/jckantor/CBE40455/master/notebooks/05.06-Pickup-and-Delivery.ipynb\"><img align=\"left\" src=\"https://img.shields.io/badge/Github-Download-blue.svg\" alt=\"Download\" title=\"Download Notebook\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "# Pickup and Delivery"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "## Problem Description"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "This is a proof-of-concept model for a pickup and delivery service. The model describes how a set of drivers would handle a predetermined set of orders. Each order consists of a pickup location and delivery location with time windows. The drivers have home locations and commission periods during which they are available.\n",
    "\n",
    "Location data is used to compute a distance matrix among all locations.  Drivers can pickup and deliver multiple orders. The  objective is to minimize total drive time, where drive time is a  proxy for total cost. \n",
    "\n",
    "This is a proof of concept model. As such, a number of important features have not been included. Among these are\n",
    "\n",
    "* graceful handling of infeasibile solutions.  Currently the solver simply fails. The problem statement should be updated to include soft constraints for time windows.\n",
    "* car capacity constraints\n",
    "* priority weights for drivers, customers, and orders\n",
    "* time variable aggregation\n",
    "* additional modeling of subtour elimination constraints\n",
    "* allowing for multiple departures for the same car from the pickup locations. \n",
    "\n",
    "An important simplification was to model only a single departure time for each car from each location. A driver can pick up multiple packages from a location, and multiple drivers can service the pickup location, but this model provides for only a single visit for each driver to each location.\n",
    "\n",
    "The immediate priority should be handling feasibility, and performance testing for small and medium scale application.\n",
    "\\"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "## Data Set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Writing input.dat\n"
     ]
    }
   ],
   "source": [
    "%%writefile input.dat\n",
    "\n",
    "data;\n",
    "\n",
    "set P := 'Bed Bath' 'Home Depot' 'Ikea';\n",
    "set D := 'Daphne' 'Jeff' 'Tim' 'Tom';\n",
    "set S := 'Alex' 'Brian';\n",
    "\n",
    "param : lat lng :=\n",
    "    'Alex'        25.00  25.00\n",
    "    'Brian'       25.00  25.00\n",
    "    'Ikea'        20.22  20.40\n",
    "    'Bed Bath'    29.30  24.00\n",
    "    'Home Depot'  21.20  30.00\n",
    "    'Jeff'        20.34  28.00\n",
    "    'Tim'         20.34  23.00\n",
    "    'Tom'         23.03  20.00\n",
    "    'Daphne'      25.00  25.00  ;\n",
    "    \n",
    "param :  ORDERS :                   Tp1     Tp2     Td1     Td2 :=\n",
    "    'Ikea'            'Tim'         9.5    17.0    11.0    16.0\n",
    "    'Ikea'            'Daphne'      9.0    17.0    11.0    16.0\n",
    "    'Home Depot'      'Jeff'       10.0    14.0    10.5    15.5\n",
    "    'Bed Bath'        'Tom'        10.0    17.0    12.5    16.5 \n",
    "    'Bed Bath'        'Jeff'       10.5    12.0    11.5    12.5 ;\n",
    "     \n",
    "param : K :     Tk1      Tk2 :=\n",
    "     'Alex'     8.0     12.5\n",
    "     'Brian'   10.0     15.0 ;\n",
    "\n",
    "end;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "## MathProg Model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "pycharm": {}
   },
   "outputs": [],
   "source": [
    "%%script glpsol -m /dev/stdin -d input.dat -y output.txt --out output\n",
    "\n",
    "/* Pickup and Delivery */\n",
    "\n",
    "# Locations\n",
    "set P;  # pickup locations\n",
    "set D;  # delivery locations\n",
    "set S;  # car start and finish locations\n",
    "\n",
    "# Distance Matrix\n",
    "set N := P union D union S;\n",
    "param lat{N};\n",
    "param lng{N};\n",
    "param dist{i in N, j in N} := sqrt((lat[i]-lat[j])**2 + (lng[i]-lng[j])**2);\n",
    "param dur{i in N, j in N} := dist[i,j]/10;\n",
    "\n",
    "# Orders with Pickup and Delivery windows\n",
    "set ORDERS within P cross D;\n",
    "param Tp1{ORDERS};\n",
    "param Tp2{(p,d) in ORDERS} >= Tp1[p,d];\n",
    "param Td1{(p,d) in ORDERS} >= Tp1[p,d];\n",
    "param Td2{(p,d) in ORDERS} >= Td1[p,d];\n",
    "\n",
    "# Cars \n",
    "set K;  # set of cars\n",
    "param Tk1{K};\n",
    "param Tk2{k in K} >= Tk1[k];\n",
    "\n",
    "# DECISION VARIABLES\n",
    "\n",
    "# x[i,j,k] = 1 if car k travels from location i to location j\n",
    "var x{N,N,K} binary;\n",
    "\n",
    "# Arrival and Departure times for car k at location n\n",
    "var Tar{N,K};\n",
    "var Tlv{N,K};\n",
    "\n",
    "## MODEL FOR DRIVER BEHAVIORS\n",
    "\n",
    "# Each car starts at their home location and goes to a pickup\n",
    "s.t. SF01 {k in K} : sum{j in P} x[k,j,k] = 1;\n",
    "s.t. SF02 {k in K, j in D} : x[k,j,k] = 0;\n",
    "s.t. SF03 {k in K, j in S : j!=k} : x[k,j,k] = 0;\n",
    "\n",
    "# Each car finishes at their home location following a delivery\n",
    "s.t. SF04 {k in K} : sum{j in D} x[j,k,k] = 1;\n",
    "s.t. SF05 {k in K, j in P} : x[j,k,k] = 0;\n",
    "s.t. SF06 {k in K, j in S : j!= k} : x[j,k,k] = 0;\n",
    "\n",
    "# A car enters and leaves a location the same number of times\n",
    "s.t. SF07 {k in K, i in N} : sum{j in N} x[j,i,k] = sum{j in N} x[i,j,k];\n",
    "\n",
    "# A car does not return immediately to the same location\n",
    "s.t. SF08 {k in K, i in N} : x[i,i,k] = 0;\n",
    "\n",
    "# Drivers do not enter or leave home locations of other drivers\n",
    "s.t. SF09 {k in K, i in N, j in S : j!=k } : x[i,j,k] = 0;\n",
    "s.t. SF10 {k in K, i in S, j in N : i!=k } : x[i,j,k] = 0;\n",
    "\n",
    "## ORDER HANDLING\n",
    "\n",
    "# Assign one car to pickup an order and take it somewhere\n",
    "s.t. RH1 {(p,d) in ORDERS} : sum{k in K, j in P union D} x[p,j,k] = 1;\n",
    "\n",
    "# If car k picks up order (p,d) then it also visits the delivery node\n",
    "s.t. RH2 {(p,d) in ORDERS, k in K} : (sum{j in N} x[p,j,k]) = (sum{i in N} x[i,d,k]);\n",
    "\n",
    "param bigM := 10;\n",
    "\n",
    "# Cars leave home and arrive back within their commission period\n",
    "s.t. TM00 {k in K} : Tlv[k,k] >= Tk1[k];\n",
    "s.t. TM01 {k in K} : Tar[k,k] <= Tk2[k];\n",
    "\n",
    "# For all other nodes the leave time is after the arrival time\n",
    "s.t. TM02 {k in K, i in P union D} : Tlv[i,k] >= Tar[i,k];\n",
    "\n",
    "# Account for travel time\n",
    "s.t. TM03 {i in N, j in N, k in K : j!=k } : Tar[j,k] >= Tlv[i,k] + dur[i,j] - bigM*(1-x[i,j,k]);\n",
    "\n",
    "# Time window for pickup. Cannot leave until the window starts, must arrive before it ends\n",
    "s.t. TM04 {(p,d) in ORDERS, j in N, k in K} : Tlv[p,k] >= Tp1[p,d] - bigM*(1-x[p,j,k]);\n",
    "s.t. TM05 {(p,d) in ORDERS, j in N, k in K} : Tar[p,k] <= Tp2[p,d] + bigM*(1-x[p,j,k]);\n",
    "\n",
    "# Time window for delivery. Must arrive during the time window.\n",
    "s.t. TM06 {(p,d) in ORDERS, j in N, k in K} : Tar[d,k] >= Td1[p,d] - bigM*(1-x[j,d,k]);\n",
    "s.t. TM07 {(p,d) in ORDERS, j in N, k in K} : Tar[d,k] <= Td2[p,d] + bigM*(1-x[j,d,k]);\n",
    "\n",
    "## OBJECTIVE: Select routes minimizing overall drive time of all drivers\n",
    "\n",
    "var Tf{K};\n",
    "var Cost;\n",
    "\n",
    "s.t. OBJ01 {k in K, i in N, j in N} : Tf[k] >= Tar[j,k] - bigM*(1-x[i,j,k]);\n",
    "s.t. OBJ02 : Cost = sum{i in N, j in N, k in K} x[i,j,k]*dur[i,j];\n",
    "\n",
    "minimize obj: bigM*Cost + sum{k in K} Tf[k];\n",
    "\n",
    "solve;\n",
    "\n",
    "printf \"\\n\\nORDERS\\n\";\n",
    "printf \"%-12s  %6s  %6s        %-12s  %6s  %6s\\n\",\n",
    "       \"Pickup\", \"Start\", \"End\", \"Delivery\", \"Start\", \"End\";\n",
    "printf {(p,d) in ORDERS} \"%-12s  %6.2f  %6.2f        %-12s  %6.2f  %6.2f\\n\", \n",
    "    p, Tp1[p,d], Tp2[p,d], d, Td1[p,d], Td2[p,d];\n",
    "\n",
    "printf \"\\n\\nPICKUPS\\n\";\n",
    "printf \"%-12s  %-12s  %-12s  %6s  %6s  %6s\\n\", \n",
    "       \"Driver\", \"Pickup\", \"Delivery\", \"Start\", \"End\", \"Est.\";\n",
    "printf {(p,d) in ORDERS, j in N, k in K : x[p,j,k] = 1}\n",
    "    \"%-12s  %-12s  %-12s  %6.2f  %6.2f  %6.2f\\n\", \n",
    "    k, p, d, Tp1[p,d], Tp2[p,d], Tar[p,k];\n",
    "\n",
    "printf \"\\n\\nDELIVERIES\\n\"; \n",
    "printf \"%-12s  %-12s  %-12s  %6s  %6s  %6s\\n\", \n",
    "       \"Driver\", \"Pickup\", \"Delivery\", \"Start\", \"End\", \"Est.\";\n",
    "printf {(p,d) in ORDERS, j in N, k in K : x[j,d,k] = 1}\n",
    "    \"%-12s  %-12s  %-12s  %6.2f  %6.2f  %6.2f\\n\", \n",
    "    k, p, d, Td1[p,d], Td2[p,d], Tar[d,k];\n",
    "\n",
    "printf \"\\n\\nROUTING\\n\";\n",
    "printf \"%-12s  %-12s  %-12s  %6s  %6s  %6s\\n\",\n",
    "       \"Driver\", \"Start\", \"End\", \"Leave\", \"Arrive\", \"Travel\";\n",
    "printf {k in K, i in N, j in N : x[i,j,k] = 1}\n",
    "    \"%-12s  %-12s  %-12s  %6.2f  %6.2f  %6.2f\\n\",\n",
    "    k, i, j, Tlv[i,k], Tar[j,k], dur[i,j];\n",
    "printf \"\\n\";\n",
    "\n",
    "end;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "ORDERS\n",
      "Pickup         Start     End        Delivery       Start     End\n",
      "Ikea            9.50   17.00        Tim            11.00   16.00\n",
      "Ikea            9.00   17.00        Daphne         11.00   16.00\n",
      "Home Depot     10.00   14.00        Jeff           10.50   15.50\n",
      "Bed Bath       10.00   17.00        Tom            12.50   16.50\n",
      "Bed Bath       10.50   12.00        Jeff           11.50   12.50\n",
      "\n",
      "\n",
      "PICKUPS\n",
      "Driver        Pickup        Delivery       Start     End    Est.\n",
      "Brian         Ikea          Tim             9.50   17.00   10.74\n",
      "Brian         Ikea          Daphne          9.00   17.00   10.74\n",
      "Alex          Home Depot    Jeff           10.00   14.00   11.51\n",
      "Alex          Bed Bath      Tom            10.00   17.00   10.50\n",
      "Alex          Bed Bath      Jeff           10.50   12.00   10.50\n",
      "\n",
      "\n",
      "DELIVERIES\n",
      "Driver        Pickup        Delivery       Start     End    Est.\n",
      "Brian         Ikea          Tim            11.00   16.00   11.00\n",
      "Brian         Ikea          Daphne         11.00   16.00   11.51\n",
      "Alex          Home Depot    Jeff           10.50   15.50   11.73\n",
      "Alex          Bed Bath      Tom            12.50   16.50   12.57\n",
      "Alex          Bed Bath      Jeff           11.50   12.50   11.73\n",
      "\n",
      "\n",
      "ROUTING\n",
      "Driver        Start         End            Leave  Arrive  Travel\n",
      "Alex          Bed Bath      Home Depot     10.50   11.51    1.01\n",
      "Alex          Home Depot    Jeff           11.51   11.73    0.22\n",
      "Alex          Jeff          Tom            11.73   12.57    0.84\n",
      "Alex          Tom           Alex           12.57   12.50    0.54\n",
      "Alex          Alex          Bed Bath        8.00   10.50    0.44\n",
      "Brian         Ikea          Tim            10.74   11.00    0.26\n",
      "Brian         Daphne        Brian          11.51   11.51    0.00\n",
      "Brian         Tim           Daphne         11.00   11.51    0.51\n",
      "Brian         Brian         Ikea           10.08   10.74    0.66\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "f = open('output.txt')\n",
    "print(f.read())\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "pycharm": {}
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "<!--NAVIGATION-->\n",
    "< [Traveling Salesman Problem with Time Windows](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/05.05-Traveling-Salesman-Problem-with-Time-Windows.ipynb) | [Contents](toc.ipynb) | [Stock Cutting](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/05.07-Stock-Cutting.ipynb) ><p><a href=\"https://colab.research.google.com/github/jckantor/CBE40455/blob/master/notebooks/05.06-Pickup-and-Delivery.ipynb\"><img align=\"left\" src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open in Colab\" title=\"Open in Google Colaboratory\"></a><p><a href=\"https://raw.githubusercontent.com/jckantor/CBE40455/master/notebooks/05.06-Pickup-and-Delivery.ipynb\"><img align=\"left\" src=\"https://img.shields.io/badge/Github-Download-blue.svg\" alt=\"Download\" title=\"Download Notebook\"></a>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}