Rugby World Cup Travelling Salesman Problem

Import the required packages

In [10]:
import pandas as pn
import numpy as np
import nag4py.g05 as g05
import nag4py.h03 as h03
import nag4py.util as util
import nag4py.x04 as x04

Load the data from the file created using Randy Olson's code.

The code can be found at his Github page here.

Randy has also written a blog post which can be found here http://www.randalolson.com/

In [11]:
waypoint_data = pn.read_csv("my-rugby-bike-waypoints-dist-dur.tsv", sep="\t")

Define the waypoints

In [4]:
all_waypoints = ["brighton community stadium, UK", 
                   "Elland Road, UK",
                   "Kingsholm Stadium, Kingsholm Road, Gloucester",
                  "King Power Stadium, Filbert Way, Leicester",
                  "City of Manchester Stadium, Ashton New Road, Manchester",
                  "Millennium Stadium, Westgate Street, Cardiff",
                  "The Stadium, Queen Elizabeth Olympic Park",
                  "Sandy Park Stadium, Exeter",
                  "St. James' Park, Barrack Road, Newcastle upon Tyne",
                  "Stadium MK, Grafton Street, Bletchley",
                  "Twickenham Stadium, Whitton Road, Twickenham",
                  "Villa Park, Trinity Road, Birmingham",
                  "Wembley Stadium, Wembley"]

Create the input matricies

In [5]:
distance_matrix = np.zeros((len(all_waypoints),len(all_waypoints)))
duration_matrix = np.zeros((len(all_waypoints),len(all_waypoints)))
In [6]:
for index, row in waypoint_data.iterrows():
    distance_matrix[all_waypoints.index(row['waypoint1'])][all_waypoints.index(row['waypoint2'])] = row['distance_m']
    distance_matrix[all_waypoints.index(row['waypoint2'])][all_waypoints.index(row['waypoint1'])] = row['distance_m']
    duration_matrix[all_waypoints.index(row['waypoint1'])][all_waypoints.index(row['waypoint2'])] = row['duration_s']
    duration_matrix[all_waypoints.index(row['waypoint2'])][all_waypoints.index(row['waypoint1'])] = row['duration_s']

Setup the NAG solver

h03bbc requires a randomly generated state to initalise.

We use nag_rand_init_repeatable to define this state.

In [7]:
genid = 2151
subid = 53
seed = np.array([304950, 889934, 209094, 23423990], dtype=np.int32)
lseed = 4
state = np.zeros(21, dtype=np.int32)
lstate = np.array([21], dtype=np.int32)
fail = util.noisy_fail()
g05.nag_rand_init_repeatable(genid, subid, seed, lseed, state, lstate, fail)
if fail.code != 0:
    print(fail.message)

Find the optimal path using nag_mip_tsp_simann (h03bbc)

In [8]:
nc = len(distance_matrix)
bound = -1.0
targc = -1.0
path = np.zeros(nc, dtype = np.int32)
cost = np.array(0, dtype = np.float64)
tmode = np.array(0)
alg_stats = np.zeros(6, dtype=np.float64)
fail = util.noisy_fail()
h03.nag_mip_tsp_simann(nc, distance_matrix, bound, targc, path, cost, tmode, alg_stats, state, fail)
if fail.code !=0:
    print(fail.message)

Convert from the path to the corresponding waypoints

In [9]:
optimal_path_distance = []
for i in path:
    optimal_path_distance.append(all_waypoints[i-1])
optimal_path_distance
Out[9]:
['brighton community stadium, UK',
 'Sandy Park Stadium, Exeter',
 'Millennium Stadium, Westgate Street, Cardiff',
 'Kingsholm Stadium, Kingsholm Road, Gloucester',
 'Villa Park, Trinity Road, Birmingham',
 'City of Manchester Stadium, Ashton New Road, Manchester',
 "St. James' Park, Barrack Road, Newcastle upon Tyne",
 'Elland Road, UK',
 'King Power Stadium, Filbert Way, Leicester',
 'Stadium MK, Grafton Street, Bletchley',
 'Wembley Stadium, Wembley',
 'Twickenham Stadium, Whitton Road, Twickenham',
 'The Stadium, Queen Elizabeth Olympic Park']

Randy has also produced a HTML file for putting the optimal route on to Google Maps

The HTML file can be found here