pgRouting: A Technique for Generating Route Loops

pgRouting (http://www.pgrouting.org/) is a set of stored procedures and C libraries for performing routing calculations over a network of intersecting lines. In this case, it's a multilinestring shapefile full of of trail segments, loaded into PostGIS.

My first day already had me doing Dijkstra routing, that was comparatively easy thanks to the FOSS4G presentations, which now form the how-to documentation for pgRouting.

But this latest task is, as far as I can tell, something that nobody has ever done before. The client wants to generate loops, where one starts at a location, walks approximately M miles, and ends up back at their starting location. I see one patent for generating route loops, but what I eventually came up with is completely dissimilar.

Note that this is a heuristic, not an algorithm. If your network has "islands" of connectivity, then it may pick waypoints on two islands and not be able to find a route. Still, for our needs (a dense network of trails, and a desire to take the scenic route) it's working quite nicely.

So here goes. Examples below are in CodeIgniter, but should be readily adaptable to your DB library of choice.

PHASE 1: WAYPOINTS FOR THE LOOP

* Start with an approximate desired total distance for the loop, call it M for miles. Multiply by 5280 to get the distance in feet, and divide by 2 on the assumption that our return trip will be about the same distance as our trip out. (M = 5 miles = 16400 feet / 2 = 8200 feet)

    $totallength = 5280.0 * $_GET['miles'] / 2.0;

* Divide the total distance M by a fixed number of waypoints, to get the per-hop distance or P. We settled on 4 because experimentally it seemed to be the most fluid, not over-managing the route and forcing it into weird convolutions. (P = 8200 / 4 = 2050 feet)

    $howmanywaypoints = 4;
    $segmentlength = $totallength / $howmanywaypoints;

* Select your first waypoint (WP0), that being the routing node closest to your chosen Lat Lon location.

    $saved_waypoints[] = array();

    $point = sprintf("ST_Transform(ST_GeometryFromText('POINT(%f %f)',4326),3734)", $_GET['lng'], $_GET['lat'] );

    $node  = $this->db->query("SELECT *, ST_Distance(the_geom, $point) AS distance FROM $route_table ORDER BY distance LIMIT 1")->row();
    $start_gid   = $node->gid;

    $saved_waypoints[$node->gid] = $node;

 

* Select a set of random waypoints (WPs), each one a random selection from the closest to that distance from the previous waypoint. Use something like the query below, inserting the geometry of the previous waypoint and the value of P.

    for ($wp=1; $wp<=$howmanywaypoints; $wp++) {
        $point = sprintf("ST_GeometryFromText('

POINT(%f %f)',3734)", $node->x, $node->y );
        $node  = $this->db->query("SELECT * FROM (SELECT * FROM $route_table ORDER BY ABS($segmentlength - ST_DISTANCE(the_geom,$point)) limit 25) AS foo ORDER BY random() LIMIT 1")->row();
        $saved_waypoints[$node->gid] = $node;
    }

* At this point, WP is a set of waypoints. WP0 is your starting node, WPs 1 2 3 and 4 are each a random direction from each other, and a straight line between them may form a random zig-zag and may crossing itself. Point is, one WP to another at approximately P straight-line distance per leg.

* Run a TSP on the set of points. Traveling Salesperson Problem (TSP) means "the straightest path to visit all of these points and return home" In the case of pgRouting, TSP is very minimal and merely takes a list of GIDs and returns a list of GIDs. That's why we kept the list of GIDs as $saved_waypoints

$waypoints = array();

$node_gids_string = implode(",",array_keys($saved_

waypoints));
    $nodes = $this->db->query("SELECT * FROM tsp('SELECT gid AS source_id, x, y FROM $route_table WHERE gid IN ($node_gids_string)', '$node_gids_string', $start_gid)");
    foreach ($nodes->result() as $r) {
                $waypoints[] = $saved_waypoints[$r->vertex_id];
    }

 

 PHASE 2: ROUTING

Now we have a list of waypoints, sorted into what we hope is a sensical sequence. If we do Dijkstra or A* between them, we effectively have a meandering route via some random waypoints to a final location, and then routing from that final location back to our start should take us through a completely different route than we came.

    // $waypoints is a list of routing nodes

    // the A* is done as a subquery, and associates back to the route_segments table so we have info about

    // each segment: name, length in miles, etc. Swap in your own.

     $route_segments = array();

     for ($i=0; $i<sizeof($waypoints)-1; $i++) {

        $onode = $waypoints[$i];
        $dnode = $waypoints[$i+1];

 

        // run the query, to route  between this WP and the next

        $routesqlquery = "SELECT ST_AsText(route.the_geom) AS wkt, route_segments.gid, route_segments.length, route_segments.duration, route_segments.name FROM route_segments, (SELECT gid, the_geom FROM astar_sp_delta('$route_table',?,?,1000,'cost',true,true)) as route WHERE route_segments.gid=route.gid";

        $routesqlparam = array($onode->source, $dnode->target);
        $route = $this->db->query($routesqlquery,$routesqlparam);
        if ($route->num_rows() == 0) die("Cannot find a route the entire way."); 

        foreach ($route->result() as $segment) $route_segments[] = $segment;

 

From here, you now have $route_segments which has everything you need to know. From here, you iterate over the segments and calculate total distance, total time, textual directions, what have you. Point is, if you plot those lines and directions onto a map, chances are good that you have a nice route There And Back Again.