18--des-gas-station.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CX 4230, Spring 2016: [18] Discrete event simulation of a gas station\n",
    "\n",
    "Recall the introduction to queueing models and discrete event simulators from the last class: [link](https://t-square.gatech.edu/access/content/group/gtc-59b8-dc03-5a67-a5f4-88b8e4d5b69a/cx4230-sp16--17-queueing.pdf). In this notebook, you will implement it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exponential random numbers\n",
    "\n",
    "Recall that in a queueing model, it is common to assume that customer interarrival times and service times are independent and identically distributed random variables. Classically, the most commonly assumed distribution is _exponential_.\n",
    "\n",
    "More specifically, an exponentially distributed random variable $X \\sim \\mathcal{E}(\\lambda)$ has the probability density function,\n",
    "\n",
    "$$\n",
    "  f_X(x) = \\lambda \\cdot \\exp\\left(-\\frac{x}{\\lambda}\\right),\n",
    "$$\n",
    "\n",
    "where $\\lambda$ is the mean of the distribution.\n",
    "\n",
    "Using Numpy, these are easy to generate using the function, `numpy.random.exponential()`: http://docs.scipy.org/doc/numpy-1.10.1/reference/generated/numpy.random.exponential.html.\n",
    "\n",
    "Here is a quick demo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from numpy.random import exponential\n",
    "\n",
    "X_MEAN = 10.0\n",
    "X_COUNT = 5\n",
    "x_values = exponential (X_MEAN, X_COUNT)\n",
    "\n",
    "print (\"X ~ Exp(%g):\" % X_MEAN)\n",
    "for (i, x_i) in enumerate (x_values):\n",
    "    print (\"  X_%d = %g\" % (i, x_i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a sanity check, let's generate a large number of values and compare the sample mean to the desired (true) mean."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from numpy import mean\n",
    "\n",
    "# @Demo\n",
    "N_BIG = 1000\n",
    "big_mean = mean (exponential (X_MEAN, N_BIG))\n",
    "print (\"\\nSample mean of %d values: %g\" % (N_BIG, big_mean))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Priority queues\n",
    "\n",
    "To maintain the future event list, you need some kind of priority queue data structure. One classical choice is to use a heap, for which there is a standard implementation in Python: [link](http://www.bogotobogo.com/python/python_PriorityQueue_heapq_Data_Structure.php)\n",
    "\n",
    "Here's a quick demo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from heapq import heappush, heappop, heapify"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Method 1: Convert any Python list into a heap\n",
    "h1 = list (x_values)\n",
    "print (\"Initial values:\", h1)\n",
    "\n",
    "heapify (h1)\n",
    "print (\"\\nHeapified:\", h1)\n",
    "\n",
    "print (\"\\nExtracting mins...\")\n",
    "for i in range (len (h1)):\n",
    "    print (i, \":\", heappop (h1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Method 2: Insert values into the heap one at a time\n",
    "\n",
    "print (\"Inserting...\")\n",
    "h2 = []\n",
    "for (i, x_i) in enumerate (x_values):\n",
    "    print (i, \":\", x_i)\n",
    "    heappush (h2, x_i)\n",
    "    \n",
    "print (\"\\nHeap:\", h2)\n",
    "    \n",
    "print (\"\\nExtracting minima...\")\n",
    "for i in range (len (h2)):\n",
    "    print (i, \":\", heappop (h2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A generic discrete event simulation engine\n",
    "\n",
    "We can build a simple, generic discrete event simulation engine. This engine manages the future event list, which you'll recall is a priority queue of timestamped events. It continually removes the event with the lowest timestamp and processes it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose we represent an event by a tuple, `(t, e)`, where `t` is the event's timestamp and `e` is an event handler. An event handler is simply a function. Let's suppose that this function takes two arguments, `e (t, s)`, where `t` is (again) the timestamp and `s` is the system state, encoded in an application-specific way. When `e (t, s)` executes, it may update the state `s`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise.** Complete the following function, which implements a generic discrete event simulation engine. The future events list is `events`. The initial system state is `initial_state`; the starter code below makes a copy of this state as a variable `s`, which your simulator can modify. Additionally, you should correct the last `print()` statement so that instead of a pair of `None` values it prints the timestamp and event name (name of the event handler)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from copy import deepcopy\n",
    "\n",
    "def simulate (events, initial_state):\n",
    "    s = deepcopy (initial_state)\n",
    "    \n",
    "    print (\"\\nFuture event list:\\n%s\" % str (events))\n",
    "    print (\"\\nt=0: %s\" % str (s))\n",
    "        \n",
    "    while events:\n",
    "        # @YOUSE: Get event and process it\n",
    "        \n",
    "        print (\"t=%d: event '%s' => '%s'\" % (None, None, str (s)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Instantiating the simulator\n",
    "\n",
    "For the gas station model, we asked you to assume the interarrival times, pumping times, and shopping times were exponential i.i.d. random variables. So, let's start by defining some parameters for these distributions. Let's also pre-generate some number of car arrivals."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Event parameters\n",
    "MEAN_INTERARRIVAL_TIME = 15.0 # minutes\n",
    "MEAN_PUMPING_TIME = 5.0 # minutes\n",
    "MEAN_SHOPPING_TIME = 10.0 # minutes\n",
    "\n",
    "# Number of customers (cars)\n",
    "NUM_CARS = 5\n",
    "\n",
    "# Pre-generate some interarrival times\n",
    "car_interarrival_times = exponential (MEAN_INTERARRIVAL_TIME, NUM_CARS)\n",
    "print (\"Interrival times (in minutes) of all cars:\\n\", car_interarrival_times)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that the state consists of the logical simulation time (`now`) and three state variables: `AtPump`, `AtStore`, and `PumpFree`. Let's create this state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "now = 0.0 # Current (logical) simulation time\n",
    "state = {'AtPump': 0          # no. cars at pump or waiting\n",
    "         , 'AtStore': 0       # no. cars at store\n",
    "         , 'PumpFree': True   # True <==> pump is available\n",
    "        }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's represent an _event_ as a tuple, `(t, e)`, where `t` is the timestamp of the event and `e` is an event handler, implemented as a Python function.\n",
    "\n",
    "If the future event list is stored in a global priority queue called `events`, the following function will insert an event into that queue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def schedule (t, e):\n",
    "    \"\"\"\n",
    "    Schedules a new event `e` at time `t`.\n",
    "    \"\"\"\n",
    "    global events\n",
    "    print (\"  ==> '%s' @ t=%g\" % (e.__name__, t))\n",
    "    heappush (events, (t, e))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise.** Implement an event handler to process a car arrival event. Assume that event handlers take as input the timestamp `t` of the event and the state `s` of the system at time `t`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def arrives (t, s):\n",
    "    \"\"\"\n",
    "    Processes an arrival event at time `t` for a system in state `s`.\n",
    "    Schedules a pumping event if the pump is free. Returns the new\n",
    "    system state.\n",
    "    \"\"\"\n",
    "    # @YOUSE\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise.** Implement a function to process the event for a car that finishes pumping gas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def finishes (t, s):\n",
    "    \"\"\"\n",
    "    Processes a finished-pumping event at time `t` for a system in\n",
    "    state `s`. Schedules a pumping event if any cars are waiting.\n",
    "    Returns the new system state.\n",
    "    \"\"\"\n",
    "    # @YOUSE\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise.** Implement a function to process the event for a car that leaves the store."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def departs (t, s):\n",
    "    \"\"\"\n",
    "    Processes a departure from the station event at\n",
    "    time `t` for a system in state `s`.\n",
    "    \"\"\"\n",
    "    # @YOUSE\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise.** Create an initial future events list by converting the raw interarrival times into arrival events and inserting them into the future events list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Hint: This function may prove useful\n",
    "from numpy import cumsum\n",
    "\n",
    "events = []  # Future event list, initially empty\n",
    "\n",
    "# @YOUSE: Create initial events from all car arrivals\n",
    "\n",
    "\n",
    "# Test code\n",
    "print (\"\\nContents of `events[:]`:\")\n",
    "for (i, event) in enumerate (events):\n",
    "    print (\"[%d] t=%g: %s\" % (i, event[0], event[1].__name__))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# More test code: If everything worked, so should this simulation!\n",
    "simulate (events, state)"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}