{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Computing optimal road trips on a limited budget\n", "\n", "This notebook provides the methodology and code used in the blog post, [Computing optimal road trips on a limited budget](http://www.randalolson.com/2016/06/05/computing-optimal-road-trips-on-a-limited-budget/).\n", "\n", "### Notebook by [Randal S. Olson](http://www.randalolson.com)\n", "\n", "Please see the [repository README file](https://github.com/rhiever/Data-Analysis-and-Machine-Learning-Projects#license) for the licenses and usage terms for the instructional material and code in this notebook. In general, I have licensed this material so that it is as widely useable and shareable as possible.\n", "\n", "### Required Python libraries\n", "\n", "If you don't have Python on your computer, you can use the [Anaconda Python distribution](http://continuum.io/downloads) to install most of the Python packages you need. Anaconda provides a simple double-click installer for your convenience.\n", "\n", "This code uses base Python libraries except for the `googlemaps`, `pandas`, `deap`, and `tqdm` packages. You can install these packages using `pip` by typing the following commands into your command line:\n", "\n", "> pip install googlemaps pandas deap tqdm\n", "\n", "### Construct a list of road trip waypoints\n", "\n", "The first step is to decide where you want to stop on your road trip.\n", "\n", "Make sure you look all of the locations up on [Google Maps](http://maps.google.com) first so you have the correct address, city, state, etc. If the text you use to look up the location doesn't work on Google Maps, then it won't work here either.\n", "\n", "Add all of your waypoints to the list below. Make sure they're formatted the same way as in the example below.\n", "\n", "*Technical note: Due to daily usage limitations of the Google Maps API, you can only have a maximum of 70 waypoints. You will have to pay Google for an increased API limit if you want to add more waypoints.*" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# https://en.wikipedia.org/wiki/List_of_state_capitols_in_the_United_States\n", "\n", "all_waypoints = ['Alabama State Capitol, 600 Dexter Avenue, Montgomery, AL 36130',\n", " #'Alaska State Capitol, Juneau, AK',\n", " 'Arizona State Capitol, 1700 W Washington St, Phoenix, AZ 85007',\n", " 'Arkansas State Capitol, 500 Woodlane Street, Little Rock, AR 72201',\n", " 'L St & 10th St, Sacramento, CA 95814',\n", " '200 E Colfax Ave, Denver, CO 80203',\n", " 'Connecticut State Capitol, 210 Capitol Ave, Hartford, CT 06106',\n", " 'Legislative Hall: The State Capitol, Legislative Avenue, Dover, DE 19901',\n", " '402 S Monroe St, Tallahassee, FL 32301',\n", " 'Georgia State Capitol, Atlanta, GA 30334',\n", " #'Hawaii State Capitol, 415 S Beretania St, Honolulu, HI 96813'\n", " '700 W Jefferson St, Boise, ID 83720',\n", " 'Illinois State Capitol, Springfield, IL 62756',\n", " 'Indiana State Capitol, Indianapolis, IN 46204',\n", " 'Iowa State Capitol, 1007 E Grand Ave, Des Moines, IA 50319',\n", " '300 SW 10th Ave, Topeka, KS 66612',\n", " 'Kentucky State Capitol Building, 700 Capitol Avenue, Frankfort, KY 40601',\n", " 'Louisiana State Capitol, Baton Rouge, LA 70802',\n", " 'Maine State House, Augusta, ME 04330',\n", " 'Maryland State House, 100 State Cir, Annapolis, MD 21401',\n", " 'Massachusetts State House, Boston, MA 02108',\n", " 'Michigan State Capitol, Lansing, MI 48933',\n", " 'Minnesota State Capitol, St Paul, MN 55155',\n", " '400-498 N West St, Jackson, MS 39201',\n", " 'Missouri State Capitol, Jefferson City, MO 65101',\n", " 'Montana State Capitol, 1301 E 6th Ave, Helena, MT 59601',\n", " 'Nebraska State Capitol, 1445 K Street, Lincoln, NE 68509',\n", " 'Nevada State Capitol, Carson City, NV 89701',\n", " 'State House, 107 North Main Street, Concord, NH 03303',\n", " 'New Jersey State House, Trenton, NJ 08608',\n", " 'New Mexico State Capitol, Santa Fe, NM 87501',\n", " 'New York State Capitol, State St. and Washington Ave, Albany, NY 12224',\n", " 'North Carolina State Capitol, Raleigh, NC 27601',\n", " 'North Dakota State Capitol, Bismarck, ND 58501',\n", " 'Ohio State Capitol, 1 Capitol Square, Columbus, OH 43215',\n", " 'Oklahoma State Capitol, Oklahoma City, OK 73105',\n", " 'Oregon State Capitol, 900 Court St NE, Salem, OR 97301',\n", " 'Pennsylvania State Capitol Building, North 3rd Street, Harrisburg, PA 17120',\n", " 'Rhode Island State House, 82 Smith Street, Providence, RI 02903',\n", " 'South Carolina State House, 1100 Gervais Street, Columbia, SC 29201',\n", " '500 E Capitol Ave, Pierre, SD 57501',\n", " 'Tennessee State Capitol, 600 Charlotte Avenue, Nashville, TN 37243',\n", " 'Texas Capitol, 1100 Congress Avenue, Austin, TX 78701',\n", " 'Utah State Capitol, Salt Lake City, UT 84103',\n", " 'Vermont State House, 115 State Street, Montpelier, VT 05633',\n", " 'Virginia State Capitol, Richmond, VA 23219',\n", " 'Washington State Capitol Bldg, 416 Sid Snyder Ave SW, Olympia, WA 98504',\n", " 'West Virginia State Capitol, Charleston, WV 25317',\n", " '2 E Main St, Madison, WI 53703',\n", " 'Wyoming State Capitol, Cheyenne, WY 82001']\n", "\n", "len(all_waypoints)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Next you'll have to register this script with the Google Maps API so they know who's hitting their servers with hundreds of Google Maps routing requests.\n", "\n", "1) Enable the Google Maps Distance Matrix API on your Google account. Google explains how to do that [here](https://github.com/googlemaps/google-maps-services-python#api-keys).\n", "\n", "2) Copy and paste the API key they had you create into the code below." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import googlemaps\n", "\n", "gmaps = googlemaps.Client(key='ENTER YOUR GOOGLE MAPS KEY HERE')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we're going to query the Google Maps API for the shortest route between all of the waypoints.\n", "\n", "This is equivalent to doing Google Maps directions lookups on the Google Maps site, except now we're performing hundreds of lookups automatically using code.\n", "\n", "If you get an error on this part, that most likely means one of the waypoints you entered couldn't be found on Google Maps. Another possible reason for an error here is if it's not possible to drive between the points, e.g., finding the driving directions between Hawaii and Florida will return an error until we invent flying cars.\n", "\n", "### Gather the distance traveled on the shortest route between all waypoints" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from itertools import combinations\n", "\n", "waypoint_distances = {}\n", "waypoint_durations = {}\n", "\n", "for (waypoint1, waypoint2) in combinations(all_waypoints, 2):\n", " try:\n", " route = gmaps.distance_matrix(origins=[waypoint1],\n", " destinations=[waypoint2],\n", " mode='driving', # Change this to 'walking' for walking directions,\n", " # 'bicycling' for biking directions, etc.\n", " language='English',\n", " units='metric')\n", "\n", " # 'distance' is in meters\n", " distance = route['rows'][0]['elements'][0]['distance']['value']\n", "\n", " # 'duration' is in seconds\n", " duration = route['rows'][0]['elements'][0]['duration']['value']\n", "\n", " waypoint_distances[frozenset([waypoint1, waypoint2])] = distance\n", " waypoint_durations[frozenset([waypoint1, waypoint2])] = duration\n", " \n", " except Exception as e:\n", " print('Error with finding the route between {} and {}.'.format(waypoint1, waypoint2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now that we have the routes between all of our waypoints, let's save them to a text file so we don't have to bother Google about them again." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "with open('my-waypoints-dist-dur.tsv', 'w') as out_file:\n", " out_file.write('\\t'.join(['waypoint1',\n", " 'waypoint2',\n", " 'distance_m',\n", " 'duration_s']))\n", " \n", " for (waypoint1, waypoint2) in waypoint_distances.keys():\n", " out_file.write('\\n' +\n", " '\\t'.join([waypoint1,\n", " waypoint2,\n", " str(waypoint_distances[frozenset([waypoint1, waypoint2])]),\n", " str(waypoint_durations[frozenset([waypoint1, waypoint2])])]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Use a genetic algorithm to optimize the order to visit the waypoints in\n", "\n", "Instead of exhaustively looking at every possible solution, genetic algorithms start with a handful of random solutions and continually tinkers with these solutions — always trying something slightly different from the current solutions and keeping the best ones — until they can’t find a better solution any more.\n", "\n", "Below, all you need to do is make sure that the file name above matches the file name below (both currently `my-waypoints-dist-dur.tsv`) and run the code. The code will read in your route information and use a genetic algorithm to discover an optimized driving route." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import pandas as pd\n", "import numpy as np\n", "\n", "waypoint_distances = {}\n", "waypoint_durations = {}\n", "all_waypoints = set()\n", "\n", "waypoint_data = pd.read_csv('my-waypoints-dist-dur.tsv', sep='\\t')\n", "\n", "for i, row in waypoint_data.iterrows():\n", " # Distance = meters\n", " waypoint_distances[frozenset([row.waypoint1, row.waypoint2])] = row.distance_m\n", " \n", " # Duration = hours\n", " waypoint_durations[frozenset([row.waypoint1, row.waypoint2])] = row.duration_s / (60. * 60.)\n", " all_waypoints.update([row.waypoint1, row.waypoint2])" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "import random\n", "import numpy as np\n", "import copy\n", "from tqdm import tqdm\n", "\n", "from deap import algorithms\n", "from deap import base\n", "from deap import creator\n", "from deap import tools\n", "\n", "creator.create('FitnessMulti', base.Fitness, weights=(1.0, -1.0))\n", "creator.create('Individual', list, fitness=creator.FitnessMulti)\n", "\n", "toolbox = base.Toolbox()\n", "toolbox.register('waypoints', random.sample, all_waypoints, random.randint(2, 20))\n", "toolbox.register('individual', tools.initIterate, creator.Individual, toolbox.waypoints)\n", "toolbox.register('population', tools.initRepeat, list, toolbox.individual)\n", "\n", "def eval_capitol_trip(individual):\n", " \"\"\"\n", " This function returns the total distance traveled on the current road trip\n", " as well as the number of waypoints visited in the trip.\n", " \n", " The genetic algorithm will favor road trips that have shorter\n", " total distances traveled and more waypoints visited.\n", " \"\"\"\n", " trip_length = 0.\n", " individual = list(individual)\n", " \n", " # Adding the starting point to the end of the trip forces it to be a round-trip\n", " individual += [individual[0]]\n", " \n", " for index in range(1, len(individual)):\n", " waypoint1 = individual[index - 1]\n", " waypoint2 = individual[index]\n", " trip_length += waypoint_distances[frozenset([waypoint1, waypoint2])]\n", " \n", " return len(set(individual)), trip_length\n", "\n", "def pareto_selection_operator(individuals, k):\n", " \"\"\"\n", " This function chooses what road trips get copied into the next generation.\n", " \n", " The genetic algorithm will favor road trips that have shorter\n", " total distances traveled and more waypoints visited.\n", " \"\"\"\n", " return tools.selNSGA2(individuals, int(k / 5.)) * 5\n", "\n", "def mutation_operator(individual):\n", " \"\"\"\n", " This function applies a random change to one road trip:\n", " \n", " - Insert: Adds one new waypoint to the road trip\n", " - Delete: Removes one waypoint from the road trip\n", " - Point: Replaces one waypoint with another different one\n", " - Swap: Swaps the places of two waypoints in the road trip\n", " \"\"\"\n", " possible_mutations = ['swap']\n", " \n", " if len(individual) < len(all_waypoints):\n", " possible_mutations.append('insert')\n", " possible_mutations.append('point')\n", " if len(individual) > 2:\n", " possible_mutations.append('delete')\n", " \n", " mutation_type = random.sample(possible_mutations, 1)[0]\n", " \n", " # Insert mutation\n", " if mutation_type == 'insert':\n", " waypoint_to_add = individual[0]\n", " while waypoint_to_add in individual:\n", " waypoint_to_add = random.sample(all_waypoints, 1)[0]\n", " \n", " index_to_insert = random.randint(0, len(individual) - 1)\n", " individual.insert(index_to_insert, waypoint_to_add)\n", " \n", " # Delete mutation\n", " elif mutation_type == 'delete':\n", " index_to_delete = random.randint(0, len(individual) - 1)\n", " del individual[index_to_delete]\n", " \n", " # Point mutation\n", " elif mutation_type == 'point':\n", " waypoint_to_add = individual[0]\n", " while waypoint_to_add in individual:\n", " waypoint_to_add = random.sample(all_waypoints, 1)[0]\n", " \n", " index_to_replace = random.randint(0, len(individual) - 1)\n", " individual[index_to_replace] = waypoint_to_add\n", " \n", " # Swap mutation\n", " elif mutation_type == 'swap':\n", " index1 = random.randint(0, len(individual) - 1)\n", " index2 = index1\n", " while index2 == index1:\n", " index2 = random.randint(0, len(individual) - 1)\n", " \n", " individual[index1], individual[index2] = individual[index2], individual[index1]\n", " \n", " return individual,\n", "\n", "\n", "toolbox.register('evaluate', eval_capitol_trip)\n", "toolbox.register('mutate', mutation_operator)\n", "toolbox.register('select', pareto_selection_operator)\n", "\n", "def pareto_eq(ind1, ind2):\n", " return np.all(ind1.fitness.values == ind2.fitness.values)\n", "\n", "pop = toolbox.population(n=1000)\n", "hof = tools.ParetoFront(similar=pareto_eq)\n", "stats = tools.Statistics(lambda ind: (int(ind.fitness.values[0]), round(ind.fitness.values[1], 2)))\n", "stats.register('Minimum', np.min, axis=0)\n", "stats.register('Maximum', np.max, axis=0)\n", "# This stores a copy of the Pareto front for every generation of the genetic algorithm\n", "stats.register('ParetoFront', lambda x: copy.deepcopy(hof))\n", "# This is a hack to make the tqdm progress bar work\n", "stats.register('Progress', lambda x: pbar.update())\n", "\n", "# How many iterations of the genetic algorithm to run\n", "# The more iterations you allow it to run, the better the solutions it will find\n", "total_gens = 5000\n", "\n", "pbar = tqdm(total=total_gens)\n", "pop, log = algorithms.eaSimple(pop, toolbox, cxpb=0., mutpb=1.0, ngen=total_gens, \n", " stats=stats, halloffame=hof, verbose=False)\n", "pbar.close()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Animated road trip map\n", "\n", "Now that we've optimized the road trip, let's visualize it!\n", "\n", "The function below will take the results of the genetic algorithm and generate an animated map showing the Pareto optimized road trips." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def create_animated_road_trip_map(optimized_routes):\n", " \"\"\"\n", " This function takes a list of optimized road trips and generates\n", " an animated map of them using the Google Maps API.\n", " \"\"\"\n", " \n", " # This line makes the road trips round trips\n", " optimized_routes = [list(route) + [route[0]] for route in optimized_routes]\n", "\n", " Page_1 = \"\"\"\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " An optimized road trip across the U.S. according to machine learning\n", " \n", " \n", " \n", " \n", " \n", "
\n", " \n", " \n", " \"\"\"\n", "\n", " with open('us-state-capitols-animated-map.html', 'w') as output_file:\n", " output_file.write(Page_1)\n", " for route in optimized_routes:\n", " output_file.write('allRoutes.push({});'.format(str(route)))\n", " output_file.write(Page_2)\n", "\n", "create_animated_road_trip_map(reversed(hof))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "!open us-state-capitols-animated-map.html" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Individual road trip maps\n", "\n", "We can also visualize single trips at a time instead of" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def create_individual_road_trip_maps(optimized_routes):\n", " \"\"\"\n", " This function takes a list of optimized road trips and generates\n", " individual maps of them using the Google Maps API.\n", " \"\"\"\n", " \n", " # This line makes the road trips round trips\n", " optimized_routes = [list(route) + [route[0]] for route in optimized_routes]\n", "\n", " for route_num, route in enumerate(optimized_routes):\n", " Page_1 = \"\"\"\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "\n", " An optimized road trip across the U.S. according to machine learning\n", " \n", " \n", " \n", " \n", " \n", "
\n", " \n", " \n", " \"\"\"\n", "\n", " with open('optimized-us-capitol-trip-{}-states.html'.format(route_num + 2), 'w') as output_file:\n", " output_file.write(Page_1)\n", " output_file.write('optimized_route = {};'.format(str(route)))\n", " output_file.write(Page_2)\n", "\n", "create_individual_road_trip_maps(reversed(hof))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "!open optimized-us-capitol-trip-48-states.html" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Some technical notes\n", "\n", "As I mentioned in the [original article](http://www.randalolson.com/2015/03/08/computing-the-optimal-road-trip-across-the-u-s/), by the end of 5,000 generations, the genetic algorithm will very likely find a *good* but probably not the *absolute best* solution to the optimal routing problem. It is in the nature of genetic algorithms that we never know if we found the absolute best solution.\n", "\n", "However, there exist some brilliant analytical solutions to the optimal routing problem such as the [Concorde TSP solver](http://en.wikipedia.org/wiki/Concorde_TSP_Solver). If you're interested in learning more about Concorde and how it's possible to find a perfect solution to the routing problem, I advise you check out [Nathan Brixius' article](https://nathanbrixius.wordpress.com/2016/06/16/finding-optimal-state-capitol-tours-on-the-cloud-with-neos/) on the topic.\n", "\n", "### If you have any questions\n", "\n", "Please feel free to:\n", "\n", "* [Email me](http://www.randalolson.com/contact/),\n", "\n", "* [Tweet](https://twitter.com/randal_olson) at me, or\n", "\n", "* comment on the [blog post](http://www.randalolson.com/2016/06/05/computing-optimal-road-trips-on-a-limited-budget/)\n", "\n", "I'm usually pretty good about getting back to people within a day or two." ] } ], "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.6.5" } }, "nbformat": 4, "nbformat_minor": 1 }