{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Routing, speed imputation, and travel times\n",
    "\n",
    "Including parallelized shortest-path solving via built-in multiprocessing in OSMnx.\n",
    "\n",
    "Author: [Geoff Boeing](https://geoffboeing.com/)\n",
    "\n",
    "  - [Documentation](https://osmnx.readthedocs.io/)\n",
    "  - [Journal article and citation info](https://geoffboeing.com/publications/osmnx-paper/)\n",
    "  - [Code repository](https://github.com/gboeing/osmnx)\n",
    "  - [Examples gallery](https://github.com/gboeing/osmnx-examples)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import multiprocessing as mp\n",
    "\n",
    "import numpy as np\n",
    "import osmnx as ox\n",
    "\n",
    "np.random.seed(0)\n",
    "ox.__version__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "place = \"Piedmont, California, USA\"\n",
    "G = ox.graph_from_place(place, network_type=\"drive\")\n",
    "Gp = ox.project_graph(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Fast nearest node/edge search with OSMnx\n",
    "\n",
    "The nearest_nodes and nearest_edges functions take arrays of x and y (or lng/lat) coordinates and return the nearest node/edge to each."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# randomly sample n points spatially-constrained to the network's geometry\n",
    "points = ox.utils_geo.sample_points(ox.convert.to_undirected(Gp), n=100)\n",
    "X = points.x.values\n",
    "Y = points.y.values\n",
    "X0 = X.mean()\n",
    "Y0 = Y.mean()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find each nearest node to several points, and optionally return distance\n",
    "nodes, dists = ox.nearest_nodes(Gp, X, Y, return_dist=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# or, find the nearest node to a single point\n",
    "node = ox.nearest_nodes(Gp, X0, Y0)\n",
    "node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find each nearest edge to several points, and optionally return distance\n",
    "edges, dists = ox.nearest_edges(Gp, X, Y, return_dist=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find the nearest edge to a single point\n",
    "edge = ox.nearest_edges(Gp, X0, Y0)\n",
    "edge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Basic routing by distance\n",
    "\n",
    "Pick two nodes. Then find the shortest path between origin and destination, using weight='length' to find the shortest path by minimizing distance traveled (otherwise it treats each edge as weight=1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find the shortest path (by distance) between these nodes then plot it\n",
    "orig = list(G)[0]\n",
    "dest = list(G)[120]\n",
    "route = ox.shortest_path(G, orig, dest, weight=\"length\")\n",
    "fig, ax = ox.plot_graph_route(G, route, route_color=\"y\", route_linewidth=6, node_size=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or get *k* shortest paths, weighted by some attribute:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "routes = ox.k_shortest_paths(G, orig, dest, k=30, weight=\"length\")\n",
    "fig, ax = ox.plot_graph_routes(G, list(routes), route_colors=\"y\", route_linewidth=4, node_size=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Imputing travel speeds and times\n",
    "\n",
    "The `add_edge_speeds` function add edge speeds (km per hour) to graph as new `speed_kph` edge attributes. Imputes free-flow travel speeds for all edges based on mean `maxspeed` value of edges, per highway type. This mean-imputation can obviously be imprecise, and the caller can override it by passing in `hwy_speeds` and/or `fallback` arguments that correspond to local speed limit standards. See docstring for details."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# impute speed on all edges missing data\n",
    "G = ox.add_edge_speeds(G)\n",
    "\n",
    "# calculate travel time (seconds) for all edges\n",
    "G = ox.add_edge_travel_times(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# see mean speed/time values by road type\n",
    "edges = ox.graph_to_gdfs(G, nodes=False)\n",
    "edges[\"highway\"] = edges[\"highway\"].astype(str)\n",
    "edges.groupby(\"highway\")[[\"length\", \"speed_kph\", \"travel_time\"]].mean().round(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# same thing again, but this time pass in a few default speed values (km/hour)\n",
    "# to fill in edges with missing `maxspeed` from OSM\n",
    "hwy_speeds = {\"residential\": 35, \"secondary\": 50, \"tertiary\": 60}\n",
    "G = ox.add_edge_speeds(G, hwy_speeds=hwy_speeds)\n",
    "G = ox.add_edge_travel_times(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculate two routes by minimizing travel distance vs travel time\n",
    "orig = list(G)[1]\n",
    "dest = list(G)[120]\n",
    "route1 = ox.shortest_path(G, orig, dest, weight=\"length\")\n",
    "route2 = ox.shortest_path(G, orig, dest, weight=\"travel_time\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# plot the routes\n",
    "fig, ax = ox.plot_graph_routes(\n",
    "    G, routes=[route1, route2], route_colors=[\"r\", \"y\"], route_linewidth=6, node_size=0\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# compare the two routes\n",
    "route1_length = int(sum(ox.routing.route_to_gdf(G, route1, weight=\"length\")[\"length\"]))\n",
    "route2_length = int(sum(ox.routing.route_to_gdf(G, route2, weight=\"travel_time\")[\"length\"]))\n",
    "route1_time = int(sum(ox.routing.route_to_gdf(G, route1, weight=\"length\")[\"travel_time\"]))\n",
    "route2_time = int(sum(ox.routing.route_to_gdf(G, route2, weight=\"travel_time\")[\"travel_time\"]))\n",
    "print(\"Route 1 is\", route1_length, \"meters and takes\", route1_time, \"seconds.\")\n",
    "print(\"Route 2 is\", route2_length, \"meters and takes\", route2_time, \"seconds.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The yellow route minimizes travel time, and is thus longer but faster than the red route.\n",
    "\n",
    "For more examples of travel time, see the [isochrones example](13-isolines-isochrones.ipynb).\n",
    "\n",
    "For more examples of routing, including using elevation as an impedance, see the [elevations example](12-node-elevations-edge-grades.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Multiprocessing\n",
    "\n",
    "Calculating lots of shortest paths can be slow, but OSMnx has built-in shortest path solver parallelization and multiprocessing. With the `shortest_path` function, you can pass in a single origin-destination pair to solve the one shortest path, or you can pass in lists of origins and destinations to solve each shortest path between the pairs. If you're solving shortest paths for multiple origins/destinations, the `cpus` argument determines how many CPU cores to utilize for parallelized solving. Multiprocessing adds some overhead, so it's only faster if you're solving a lot of paths. It also has substantial RAM requirements (as it must copy the graph into each sub-process), so be careful with your RAM when setting the `cpus` argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculate 100,000 shortest-path routes using random origin-destination pairs\n",
    "n = 100000\n",
    "origs = np.random.choice(G.nodes, size=n, replace=True)\n",
    "dests = np.random.choice(G.nodes, size=n, replace=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# how many CPUs do you have\n",
    "mp.cpu_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %%time\n",
    "# it takes 2.3 seconds to solve all the routes using all the cores on my computer\n",
    "# I have a 24-thread AMD 5900x: performance will depend on your specific CPU\n",
    "# routes = ox.shortest_path(G, origs, dests, weight=\"travel_time\", cpus=None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "# it takes 29 seconds to solve all the routes using just 1 core on my computer\n",
    "routes = ox.shortest_path(G, origs, dests, weight=\"travel_time\", cpus=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# how many total results did we get\n",
    "print(len(routes))\n",
    "\n",
    "# and how many were solvable paths\n",
    "# some will be unsolvable due to directed graph perimeter effects\n",
    "routes_valid = [r for r in routes if r is not None]\n",
    "print(len(routes_valid))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Miscellaneous routing notes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The routing correctly handles one-way streets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G2 = ox.graph_from_address(\n",
    "    \"N. Sicily Pl., Chandler, Arizona\",\n",
    "    dist=800,\n",
    "    network_type=\"drive\",\n",
    "    truncate_by_edge=True,\n",
    ")\n",
    "origin = (33.307792, -111.894940)\n",
    "destination = (33.312994, -111.894998)\n",
    "origin_node = ox.distance.nearest_nodes(G2, origin[1], origin[0])\n",
    "destination_node = ox.distance.nearest_nodes(G2, destination[1], destination[0])\n",
    "route = ox.shortest_path(G2, origin_node, destination_node)\n",
    "fig, ax = ox.plot_graph_route(G2, route, route_color=\"c\", node_size=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also, when there are parallel edges between nodes in the route, OSMnx picks the shortest edge to plot:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "location_point = (33.299896, -111.831638)\n",
    "G2 = ox.graph_from_point(location_point, dist=400, truncate_by_edge=True)\n",
    "origin = (33.301821, -111.829871)\n",
    "destination = (33.301402, -111.833108)\n",
    "origin_node = ox.distance.nearest_nodes(G2, origin[1], origin[0])\n",
    "destination_node = ox.distance.nearest_nodes(G2, destination[1], destination[0])\n",
    "route = ox.shortest_path(G2, origin_node, destination_node)\n",
    "fig, ax = ox.plot_graph_route(G2, route, route_color=\"c\", node_size=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python (ox)",
   "language": "python",
   "name": "ox"
  },
  "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.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}