{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Computing The Really Optimal Tour Across The USA On The Cloud With Python\n", "\n", "## Author: [Jean-François Puget](https://www.ibm.com/developerworks/community/blogs/jfp/?lang=en)\n", "\n", "This is a follow up on Randy Olson work on solving TSPs in Python: [Computing the optimal road trip across the U.S.](http://www.randalolson.com/2015/03/08/computing-the-optimal-road-trip-across-the-u-s/). The code below is commented at length in my blog entry on [Computing The Really Optimal Tour Across The USA On The Cloud With Python](https://www.ibm.com/developerworks/community/blogs/jfp/entry/computing_the_really_optimal_tour_acrosss_the_usa_on_the_cloud_with_python)\n", "\n", "Some of the code is a derivative work of Randy Olson's code, namely the list of points to visits, and the html template used for rendering the tour on Google Map.\n", "\n", "Can we do better than Randy, i.e. can we compute the shortest tour visiting each one of the 50 landmarks he has selected? \n", "\n", "The answer is yes. I will use these tools to compute it.\n", " \n", "### Google Maps\n", "No need to present this, is it? We will use it for gathering data and rendering the result on a map.\n", " \n", "### Concorde\n", "[Concorde](http://www.math.uwaterloo.ca/tsp/concorde.html) is the best known algorithm to solve TSPs, see my [post](http://www.randalolson.com/2015/03/08/computing-the-optimal-road-trip-across-the-u-s/) for more background on it.\n", " \n", "### CPLEX\n", "We use [CPLEX](http://www.ibm.com/software/commerce/optimization/cplex-optimizer/) indirectly as Concorde is built on top of it. In all fairness, Concorde can also be used with an alternative solver called QSopt. Using CPLEX is faster, but the difference becomes noticeable only for very large TSPs. For a 50 city TSP lke Randy Olson's tour, using CPLEX or QSopt is similar. Let's admit that I have a strong bias towards CPLEX in general!\n", " \n", "### NEOS\n", "This is what makes Concorde and CPLEX easy to consume in Python. NEOS is a server delivering Software as a Service (SaaS). Actually, we could say that NEOS delivers Solvers as a Service because it provides quite a few optimization solvers. In particular, Concorde on NEOS is available at: http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Enough discussion, let's start.\n", "\n", "## Python Setup\n", "\n", "Let's first import packages we'll use in this notebook. We use Python 2.7 here. if you use Python 3 then you should rename xmlrpclib into xmlrpc.client ." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import googlemaps\n", "import time\n", "import xmlrpclib\n", "import re\n", "from jinja2 import Template" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "For ease of reuse, let's state the versions of what we are using here. We will use the convenient [watermark package](https://pypi.python.org/pypi/watermark). It can be installed with ```pip install ipyext```. Note that the package name is not watermark, for some reason.\n", "\n", "Once installed, it is used as a magic function." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [], "source": [ "%load_ext watermark" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "JFPuget Sat Mar 12 2016 \n", "\n", "CPython 2.7.11\n", "IPython 4.0.3\n", "\n", "googlemaps 2.4.2\n", "jinja2 2.8\n", "requests 2.6.0\n", "\n", "compiler : MSC v.1500 64 bit (AMD64)\n", "system : Windows\n", "release : 7\n", "machine : AMD64\n", "processor : Intel64 Family 6 Model 42 Stepping 7, GenuineIntel\n", "CPU cores : 8\n", "interpreter: 64bit\n" ] } ], "source": [ "%watermark -a 'JFPuget' -nmv --packages googlemaps,jinja2,requests" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Data\n", "\n", "We are set, let's start real work. We start with the list of cities to be visited. The list below is from Randy Olson [article](http://www.randalolson.com/2015/03/08/computing-the-optimal-road-trip-across-the-u-s/). You can paste your own list to get another tour. Note that all points must be understandable by Google Maps, hence you should try to locate each of those points on it before running the script." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": true }, "outputs": [], "source": [ "USA_50_points = [\"USS Alabama, Battleship Parkway, Mobile, AL\",\n", " \"Grand Canyon National Park, Arizona\",\n", " \"Toltec Mounds, Scott, AR\",\n", " \"San Andreas Fault, San Benito County, CA\",\n", " \"Cable Car Museum, 94108, 1201 Mason St, San Francisco, CA 94108\",\n", " \"Pikes Peak, Colorado\",\n", " \"The Mark Twain House & Museum, Farmington Avenue, Hartford, CT\",\n", " \"New Castle Historic District, Delaware\",\n", " \"White House, Pennsylvania Avenue Northwest, Washington, DC\",\n", " \"Cape Canaveral, FL\",\n", " \"Okefenokee Swamp Park, Okefenokee Swamp Park Road, Waycross, GA\",\n", " \"Craters of the Moon National Monument & Preserve, Arco, ID\",\n", " \"Lincoln Home National Historic Site Visitor Center, 426 South 7th Street, Springfield, IL\",\n", " \"West Baden Springs Hotel, West Baden Avenue, West Baden Springs, IN\",\n", " \"Terrace Hill, Grand Avenue, Des Moines, IA\",\n", " \"C. W. Parker Carousel Museum, South Esplanade Street, Leavenworth, KS\",\n", " \"Mammoth Cave National Park, Mammoth Cave Pkwy, Mammoth Cave, KY\",\n", " \"French Quarter, New Orleans, LA\",\n", " \"Acadia National Park, Maine\",\n", " \"Maryland State House, 100 State Cir, Annapolis, MD 21401\",\n", " \"USS Constitution, Boston, MA\",\n", " \"Olympia Entertainment, Woodward Avenue, Detroit, MI\",\n", " \"Fort Snelling, Tower Avenue, Saint Paul, MN\",\n", " \"Vicksburg National Military Park, Clay Street, Vicksburg, MS\",\n", " \"Gateway Arch, Washington Avenue, St Louis, MO\",\n", " \"Glacier National Park, West Glacier, MT\",\n", " \"Ashfall Fossil Bed, Royal, NE\",\n", " \"Hoover Dam, NV\",\n", " \"Omni Mount Washington Resort, Mount Washington Hotel Road, Bretton Woods, NH\",\n", " \"Congress Hall, Congress Place, Cape May, NJ 08204\",\n", " \"Carlsbad Caverns National Park, Carlsbad, NM\",\n", " \"Statue of Liberty, Liberty Island, NYC, NY\",\n", " \"Wright Brothers National Memorial Visitor Center, Manteo, NC\",\n", " \"Fort Union Trading Post National Historic Site, Williston, North Dakota 1804, ND\",\n", " \"Spring Grove Cemetery, Spring Grove Avenue, Cincinnati, OH\",\n", " \"Chickasaw National Recreation Area, 1008 W 2nd St, Sulphur, OK 73086\",\n", " \"Columbia River Gorge National Scenic Area, Oregon\",\n", " \"Liberty Bell, 6th Street, Philadelphia, PA\",\n", " \"The Breakers, Ochre Point Avenue, Newport, RI\",\n", " \"Fort Sumter National Monument, Sullivan's Island, SC\",\n", " \"Mount Rushmore National Memorial, South Dakota 244, Keystone, SD\",\n", " \"Graceland, Elvis Presley Boulevard, Memphis, TN\",\n", " \"The Alamo, Alamo Plaza, San Antonio, TX\",\n", " \"Bryce Canyon National Park, Hwy 63, Bryce, UT\",\n", " \"Shelburne Farms, Harbor Road, Shelburne, VT\",\n", " \"Mount Vernon, Fairfax County, Virginia\",\n", " \"Hanford Site, Benton County, WA\",\n", " \"Lost World Caverns, Lewisburg, WV\",\n", " \"Taliesin, County Road C, Spring Green, Wisconsin\",\n", " \"Yellowstone National Park, WY 82190\"]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Google Maps Setup\n", "\n", "We need the distance between each pair of cities we want to visit. We will use Google map distance matrix API here, but we could provide the distance matrix in any way that suits us. We will see later than we can import an existing [TSPLIB](http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/) file for instance.\n", "\n", "We must enable the Google map distance matrix API on the [developer console](https://console.developers.google.com/). We will use the Python client library([documentation](https://googlemaps.github.io/google-maps-services-python/docs/2.2/)). We imported it above via ```import googlemaps```.\n", "\n", "First step is to get a google maps API key, see [instructions](https://github.com/googlemaps/google-maps-services-python#api-keys). Once we have a key we paste it below. I removed my actual key and you should paste yours if you want to reuse this code. We initiailize the client connection to the service with the key." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [], "source": [ "google_key = \"paste your key here\"\n", "\n", "gmaps = googlemaps.Client(key=google_key)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We are using the free version of the service. The free API is limited to 2500 pairwise distances per 24 hours. Given we have 50 points to visit, we need 50x49/2 = 1225 pairwise distances, hence we can call this only twice a day or so. The free API is also limited to 100 pairwise distances per 10 seconds. We therefore have to wait about 123 seconds for getting all our distances.\n", "\n", "We use the default parameters for the distance matrix api: units=metric, mode=driving, departure_time=now.\n", "\n", "We return the result as a string in the [TSPLIB](http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/) format. The string must represent the distance matrix in lower triangular form. If the cities are numbered from 0 to 49, this distance matrix must look like the following (I only show the first few lines):\n", "```\n", "0\n", "1-0 0\n", "2-0 2-1 0\n", "3-0 3-1 3-2 0\n", "4-0 4-1 4-2 4-3 0\n", "```\n", "where `i-j` represents the distance from city `i` to city `j`. \n" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def get_tsp_data(points):\n", " distances = ''\n", " try:\n", " for i in range(0, len(points)):\n", " for j in range(0,i+1):\n", " if i == j: \n", " distances += '0\\n'\n", " else: \n", " result1 = gmaps.distance_matrix(origins=points[i],destinations=points[j])\n", " d = result1['rows'][0]['elements'][0]['distance']['value']\n", " distances += '%d ' % d\n", " except Exception as e:\n", " print 'Error in getting distance between %s and %s' % (points[i], points[j])\n", " return distances" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's try it!" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": true }, "outputs": [], "source": [ "distances = get_tsp_data(USA_50_points)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Does it look good?" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\n", "2677783 0\n", "708032 2066041 0\n", "3679695 1086596 3007532 0\n", "3854200 1261100 3182037 213466 0\n", "2223711 9742\n" ] } ], "source": [ "print(distances[:100])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Seems it is correct. \n", "\n", "## NEOS Data Preparation\n", "\n", "We can now prepare data for [NEOS](http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html). We will use the NEOS API for Concorde. It is not a REST API as is now customary for web services, because NEOS was developed before REST APIs were invented! NEOS API uses XML-RPC. All we need to provide is a XML file that contains the data of the problem plus few parameters for Concorde. \n", "\n", "We first need to wrap data to get a valid [TSPLIB format](http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/). This format has few fixed input lines describing the problem before the distance matrix. The string below contains the template for files containing a lower triangular distance matrix" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": true }, "outputs": [], "source": [ "tsp_template = \"\"\"\n", "TYPE : TSP\n", "DIMENSION : %i\n", "EDGE_WEIGHT_TYPE : EXPLICIT\n", "EDGE_WEIGHT_FORMAT : LOWER_DIAG_ROW \n", "EDGE_WEIGHT_SECTION\n", "%s\n", "EOF\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We insert the distance matrix we computed via the % operator." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": true }, "outputs": [], "source": [ "tsp_data = tsp_template % (50, distances)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We save it in case we ned to rerun it. This will avoids waiting 5 minutes to get the distance matrix from Google map next time" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": true }, "outputs": [], "source": [ "with open('usa_50.tsp','wb') as file:\n", " file.write(tsp_data)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If for some reason we lost our Python kernel, or if we restart it, we can get the data back from the file." ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "```\n", "with open('usa_50.tsp','rb') as file:\n", " tsp_data = file.read()\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We now have to insert that data in the right xml file to submit it to NEOS. As explained in [my post](https://www.ibm.com/developerworks/community/blogs/jfp/entry/computing_the_really_optimal_tour_acrosss_the_usa_on_the_cloud_with_python), I could have carefully read the documentation. I preferred to use another nice way NEOS offers: it is possible to generate the xml file using the dry run option on the NEOS [submission page for Concorde](http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html). For that, I created a file named fake.tsp with the two character string '%s' as content. This content is only there for helping processing with Python later. I then entered the path to that file on the submission page, and I checked the dry run option before submitting. This does not run the job. It produces an xml content that I stored in the string below. I removed my actual email and you should put yours instead if you want to reuse it." ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "collapsed": true }, "outputs": [], "source": [ "base_xml = \"\"\"\n", "\n", "co\n", "concorde\n", "TSP\n", "long\n", " *** insert your email here ***\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can now insert the tsp data, again via the % operator" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": true }, "outputs": [], "source": [ "tsp_xml = base_xml % tsp_data" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Computing Shortest Tour on NEOS\n", "\n", "We are now ready to log into NEOS, submit the job, and get the result." ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [], "source": [ "NEOS_HOST=\"www.neos-server.org\"\n", "NEOS_PORT=3332\n", "\n", "neos = xmlrpclib.ServerProxy(\"http://%s:%d\" % (NEOS_HOST, NEOS_PORT))\n", "\n", "(jobNumber,password) = neos.submitJob(tsp_xml)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We now wait until NEOS has computed the shortest tour. It shouldn't be long." ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [], "source": [ "status=\"Waiting\"\n", "while status == \"Running\" or status==\"Waiting\":\n", " time.sleep(1)\n", " status = neos.getJobStatus(jobNumber, password)\n", " \n", "msg = neos.getFinalResults(jobNumber, password).data" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What does the result look like?" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "/home/neos5/bin/concorde.cplex -s 99 -f sample.tsp\n", "Host: thales Current process id: 21793\n", "Using random seed 99\n", "Problem Type: TSP\n", "Number of Nodes: 50\n", "Explicit Lengths (CC_MATRIXNORM)\n", "Set initial upperbound to 22243542 (from tour)\n", " LP Value 1: 21512609.000000 (0.00 seconds)\n", " LP Value 2: 22243542.000000 (0.00 seconds)\n", "New lower bound: 22243542.000000\n", "Final lower bound 22243542.000000, upper bound 22243542.000000\n", "Exact lower bound: 22243542.000000\n", "DIFF: 0.000000\n", "Final LP has 66 rows, 164 columns, 518 nonzeros\n", "Optimal Solution: 22243542.00\n", "Number of bbnodes: 1\n", "Total Running Time: 0.03 (seconds)\n", "\n", "\n", "*** ***\n", "\n", "\n", "\n", "*** You chose the Concorde(CPLEX) solver ***\n", "\n", "\n", "\n", "*** Cities are numbered 0..n-1 and each line shows a leg from one city to the next \n", " followed by the distance rounded to integers***\n", "\n", "50 50\n", "0 17 232538\n", "17 23 332001\n", "23 41 382077\n", "41 2 223579\n", "2 35 599175\n", "35 42 645010\n", "42 30 732619\n", "30 5 906931\n", "5 49 1012309\n", "49 11 479311\n", "11 43 886721\n", "43 1 420685\n", "1 27 390501\n", "27 3 762531\n", "3 4 213466\n", "4 36 1046462\n", "36 46 169763\n", "46 25 693577\n", "25 33 755032\n", "33 40 582428\n", "40 26 599792\n", "26 15 549197\n", "15 14 332988\n", "14 22 393573\n", "22 48 401354\n", "48 12 490113\n", "12 24 168248\n", "24 13 390955\n", "13 16 194584\n", "16 34 307293\n", "34 21 419167\n", "21 44 1077780\n", "44 28 191765\n", "28 18 369946\n", "18 20 441365\n", "20 38 119309\n", "38 6 144579\n", "6 31 191481\n", "31 37 150785\n", "37 29 147965\n", "29 7 84693\n", "7 19 99052\n", "19 8 57073\n", "8 45 29759\n", "45 47 418990\n", "47 32 633579\n", "32 39 727874\n", "39 10 378291\n", "10 9 384913\n", "9 0 880363\n", "\n" ] } ], "source": [ "print(msg)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "By searching for the string \"Optimal Solution: \" we see that we find a tour of length 22,313.083 kilometers. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Printing Results\n", "\n", "We must now parse the results in order to print it with city names. We first look for the start of the section where each leg of the tour is printed. We then parse the tour using Python regular expressions, which gives us the list of the cities visited by the tour. However, what we get are the indices of the cities, because this is all we provided to Concorde. We need to translate these indices back to the original location names. We finally need to close the loop, i.e. add the starting point at the end." ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimal Length (m) : 22243542\n", "['USS Alabama, Battleship Parkway, Mobile, AL', 'French Quarter, New Orleans, LA', 'Vicksburg National Military Park, Clay Street, Vicksburg, MS', 'Graceland, Elvis Presley Boulevard, Memphis, TN', 'Toltec Mounds, Scott, AR', 'Chickasaw National Recreation Area, 1008 W 2nd St, Sulphur, OK 73086', 'The Alamo, Alamo Plaza, San Antonio, TX', 'Carlsbad Caverns National Park, Carlsbad, NM', 'Pikes Peak, Colorado', 'Yellowstone National Park, WY 82190', 'Craters of the Moon National Monument & Preserve, Arco, ID', 'Bryce Canyon National Park, Hwy 63, Bryce, UT', 'Grand Canyon National Park, Arizona', 'Hoover Dam, NV', 'San Andreas Fault, San Benito County, CA', 'Cable Car Museum, 94108, 1201 Mason St, San Francisco, CA 94108', 'Columbia River Gorge National Scenic Area, Oregon', 'Hanford Site, Benton County, WA', 'Glacier National Park, West Glacier, MT', 'Fort Union Trading Post National Historic Site, Williston, North Dakota 1804, ND', 'Mount Rushmore National Memorial, South Dakota 244, Keystone, SD', 'Ashfall Fossil Bed, Royal, NE', 'C. W. Parker Carousel Museum, South Esplanade Street, Leavenworth, KS', 'Terrace Hill, Grand Avenue, Des Moines, IA', 'Fort Snelling, Tower Avenue, Saint Paul, MN', 'Taliesin, County Road C, Spring Green, Wisconsin', 'Lincoln Home National Historic Site Visitor Center, 426 South 7th Street, Springfield, IL', 'Gateway Arch, Washington Avenue, St Louis, MO', 'West Baden Springs Hotel, West Baden Avenue, West Baden Springs, IN', 'Mammoth Cave National Park, Mammoth Cave Pkwy, Mammoth Cave, KY', 'Spring Grove Cemetery, Spring Grove Avenue, Cincinnati, OH', 'Olympia Entertainment, Woodward Avenue, Detroit, MI', 'Shelburne Farms, Harbor Road, Shelburne, VT', 'Omni Mount Washington Resort, Mount Washington Hotel Road, Bretton Woods, NH', 'Acadia National Park, Maine', 'USS Constitution, Boston, MA', 'The Breakers, Ochre Point Avenue, Newport, RI', 'The Mark Twain House & Museum, Farmington Avenue, Hartford, CT', 'Statue of Liberty, Liberty Island, NYC, NY', 'Liberty Bell, 6th Street, Philadelphia, PA', 'Congress Hall, Congress Place, Cape May, NJ 08204', 'New Castle Historic District, Delaware', 'Maryland State House, 100 State Cir, Annapolis, MD 21401', 'White House, Pennsylvania Avenue Northwest, Washington, DC', 'Mount Vernon, Fairfax County, Virginia', 'Lost World Caverns, Lewisburg, WV', 'Wright Brothers National Memorial Visitor Center, Manteo, NC', \"Fort Sumter National Monument, Sullivan's Island, SC\", 'Okefenokee Swamp Park, Okefenokee Swamp Park Road, Waycross, GA', 'Cape Canaveral, FL', 'USS Alabama, Battleship Parkway, Mobile, AL']\n" ] } ], "source": [ "def get_tour (num_points, msg):\n", " num_points = 50\n", " optimal_length_mention = re.findall(r'Optimal Solution: (\\d+)',msg)\n", " optimal_length = int(optimal_length_mention[0])\n", " indices = re.findall(r'(\\d+) \\d+ \\d+', msg)\n", " tour = [USA_50_points[int(i)] for i in indices]\n", " tour.append(tour[0])\n", " return (optimal_length,tour)\n", "\n", "(optimal_length,tour) = get_tour(50, msg)\n", "print(\"Optimal Length (m) : %s\" % optimal_length)\n", "print(tour)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Result Display\n", "\n", "\n", "\n", "We can now display the result. I started from Randal Olson [code](https://github.com/rhiever/optimal-roadtrip-usa/blob/gh-pages/major-landmarks.html). However, his code must be be edited manually each time one wants to display a different tour. Python ecosystem includes a evry convenient package for this: the jinja2 package. We will use this package to parameterize Randy's html code.\n", "\n", "The parameter we need to pass is a split of the tour in subtours of length at most 10 because of Google map API limit. For each subtour we will need its index, its starting point, its ending point, and all the intermediate waypoints in a list. We can construct this information via a simple utility function." ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def create_routes(tour):\n", " routes = []\n", " length = len(tour)\n", " i = 1\n", " while length >= 2:\n", " rlength = min(8,length - 2)\n", " start = tour[0]\n", " end = tour[rlength+1]\n", " route = tour[1:rlength+1]\n", " routes.append( (i, start, end, route) )\n", " i += 1\n", " tour = tour[rlength+1:]\n", " length = len(tour)\n", " return routes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can now create the html template. i started from randy Olson's template, and I replaced all input parts with Jinja2 loops. These loops look like the following:\n", "```\n", "{% for n in routes %}\n", "some Javascript code here\n", "{% endfor %}\n", "```" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "collapsed": false }, "outputs": [], "source": [ "tsp_html = \"\"\"\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "The correct optimal road trip across the U.S.\n", "\n", "\n", "\n", "\n", "\n", "
\n", "\n", "\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can now create the html file via rendering the above template with the actual tour we computed." ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": false }, "outputs": [], "source": [ "tsp_template = Template(tsp_html)\n", "r = tsp_template.render(routes = create_routes(tour))\n", "with open('tsp.html','wb') as file:\n", " file.write(r)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We leverage Jupyter `%%HTML` magic function to display the result inside the notebook. We may have to use the zoom/unzoom buttons on the lower left corner to adjust the image to the actual cell size. " ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%%HTML\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This looks nice, isn't it?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## A Shorter Tour?\n", "\n", "The tour we computed is different from the one Bill Cook published. The difference is due to the fact that Google Maps returned a distance matrix that was a bit different from the one Bill used. Let us check that our code is correct by using the same distance matrix as Bill.\n", "\n", "We will repeat the above steps, starting this time from the europe50 file Bill created.\n", "\n", "In order to do that, let's wrap everything into a simple to use function that expects a file containing a distance matrix in TSPLIB format with extension `tsp`." ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def tsp(file_name):\n", " with open(file_name+'.tsp', 'rb') as file:\n", " tsp_xml = base_xml % file.read()\n", "\n", " (jobNumber,password) = neos.submitJob(tsp_xml)\n", "\n", " status=\"Waiting\"\n", " \n", " while status == \"Running\" or status==\"Waiting\":\n", " print(status)\n", " time.sleep(1)\n", " status = neos.getJobStatus(jobNumber, password)\n", " \n", " msg = neos.getFinalResults(jobNumber, password).data\n", " (optimal_length,tour) = get_tour(50, msg)\n", " print(\"Optimal Length (m) : %s\" % optimal_length)\n", " \n", " tsp_template = Template(tsp_html)\n", " r = tsp_template.render(routes = create_routes(tour))\n", " with open(file_name+'.html','wb') as file:\n", " file.write(r)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that this function isn't safe at all. It does not check for any formatting error in the input file for instance. But it is good enough when we are using files from the TSPLIB as these files are well formated. For some reason Bill named his file 'europe50' ..." ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Waiting\n", "Running\n", "Running\n", "Running\n", "Running\n", "Optimal Length (m) : 22015038\n" ] } ], "source": [ "tsp('europe50')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We get the same length as Bill, which is good. How does this tour looks like?" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%%HTML\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Main difference with the one we found is around Virginia.\n", "\n", "Let us try out function with the distance matrix we just got from Google Maps." ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Waiting\n", "Running\n", "Running\n", "Running\n", "Running\n", "Optimal Length (m) : 22243542\n" ] } ], "source": [ "tsp('usa_50')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How does it look like?" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%%HTML\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "I hope you enjoyed this. If you want to learn more then my blog entry on [Computing The Really Optimal Tour Across The USA On The Cloud With Python](https://www.ibm.com/developerworks/community/blogs/jfp/entry/computing_the_really_optimal_tour_acrosss_the_usa_on_the_cloud_with_python) contains useful links." ] } ], "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.11" } }, "nbformat": 4, "nbformat_minor": 0 }