{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#Rugby World Cup Travelling Salesman Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####Import the required packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pn\n",
    "import numpy as np\n",
    "import nag4py.g05 as g05\n",
    "import nag4py.h03 as h03\n",
    "import nag4py.util as util\n",
    "import nag4py.x04 as x04"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####Load the data from the file created using Randy Olson's code.\n",
    "The code can be found at his Github page [here](http://nbviewer.ipython.org/github/rhiever/Data-Analysis-and-Machine-Learning-Projects/blob/master/optimal-road-trip/Computing%20the%20optimal%20road%20trip%20across%20the%20U.S..ipynb).\n",
    "\n",
    "Randy has also written a blog post which can be found here [http://www.randalolson.com/](http://www.randalolson.com/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "waypoint_data = pn.read_csv(\"my-rugby-bike-waypoints-dist-dur.tsv\", sep=\"\\t\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####Define the waypoints"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "all_waypoints = [\"brighton community stadium, UK\", \n",
    "                   \"Elland Road, UK\",\n",
    "                   \"Kingsholm Stadium, Kingsholm Road, Gloucester\",\n",
    "                  \"King Power Stadium, Filbert Way, Leicester\",\n",
    "                  \"City of Manchester Stadium, Ashton New Road, Manchester\",\n",
    "                  \"Millennium Stadium, Westgate Street, Cardiff\",\n",
    "                  \"The Stadium, Queen Elizabeth Olympic Park\",\n",
    "                  \"Sandy Park Stadium, Exeter\",\n",
    "                  \"St. James' Park, Barrack Road, Newcastle upon Tyne\",\n",
    "                  \"Stadium MK, Grafton Street, Bletchley\",\n",
    "                  \"Twickenham Stadium, Whitton Road, Twickenham\",\n",
    "                  \"Villa Park, Trinity Road, Birmingham\",\n",
    "                  \"Wembley Stadium, Wembley\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####Create the input matricies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "distance_matrix = np.zeros((len(all_waypoints),len(all_waypoints)))\n",
    "duration_matrix = np.zeros((len(all_waypoints),len(all_waypoints)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for index, row in waypoint_data.iterrows():\n",
    "    distance_matrix[all_waypoints.index(row['waypoint1'])][all_waypoints.index(row['waypoint2'])] = row['distance_m']\n",
    "    distance_matrix[all_waypoints.index(row['waypoint2'])][all_waypoints.index(row['waypoint1'])] = row['distance_m']\n",
    "    duration_matrix[all_waypoints.index(row['waypoint1'])][all_waypoints.index(row['waypoint2'])] = row['duration_s']\n",
    "    duration_matrix[all_waypoints.index(row['waypoint2'])][all_waypoints.index(row['waypoint1'])] = row['duration_s']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####Setup the NAG solver\n",
    "h03bbc requires a randomly generated state to initalise.\n",
    "\n",
    "We use nag_rand_init_repeatable to define this state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "genid = 2151\n",
    "subid = 53\n",
    "seed = np.array([304950, 889934, 209094, 23423990], dtype=np.int32)\n",
    "lseed = 4\n",
    "state = np.zeros(21, dtype=np.int32)\n",
    "lstate = np.array([21], dtype=np.int32)\n",
    "fail = util.noisy_fail()\n",
    "g05.nag_rand_init_repeatable(genid, subid, seed, lseed, state, lstate, fail)\n",
    "if fail.code != 0:\n",
    "    print(fail.message)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####Find the optimal path using nag_mip_tsp_simann (h03bbc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nc = len(distance_matrix)\n",
    "bound = -1.0\n",
    "targc = -1.0\n",
    "path = np.zeros(nc, dtype = np.int32)\n",
    "cost = np.array(0, dtype = np.float64)\n",
    "tmode = np.array(0)\n",
    "alg_stats = np.zeros(6, dtype=np.float64)\n",
    "fail = util.noisy_fail()\n",
    "h03.nag_mip_tsp_simann(nc, distance_matrix, bound, targc, path, cost, tmode, alg_stats, state, fail)\n",
    "if fail.code !=0:\n",
    "    print(fail.message)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####Convert from the path to the corresponding waypoints"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['brighton community stadium, UK',\n",
       " 'Sandy Park Stadium, Exeter',\n",
       " 'Millennium Stadium, Westgate Street, Cardiff',\n",
       " 'Kingsholm Stadium, Kingsholm Road, Gloucester',\n",
       " 'Villa Park, Trinity Road, Birmingham',\n",
       " 'City of Manchester Stadium, Ashton New Road, Manchester',\n",
       " \"St. James' Park, Barrack Road, Newcastle upon Tyne\",\n",
       " 'Elland Road, UK',\n",
       " 'King Power Stadium, Filbert Way, Leicester',\n",
       " 'Stadium MK, Grafton Street, Bletchley',\n",
       " 'Wembley Stadium, Wembley',\n",
       " 'Twickenham Stadium, Whitton Road, Twickenham',\n",
       " 'The Stadium, Queen Elizabeth Olympic Park']"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "optimal_path_distance = []\n",
    "for i in path:\n",
    "    optimal_path_distance.append(all_waypoints[i-1])\n",
    "optimal_path_distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####Randy has also produced a HTML file for putting the optimal route on to Google Maps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The HTML file can be found [here](https://github.com/rhiever/optimal-roadtrip-usa/blob/gh-pages/major-landmarks.html#L93)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}