Research client side draggable route selection with pgRouting

Created by Ko Nagase, Georepublic Japan

Agenda

  • Self-introduction
  • Background
  • Draggable routing frameworks
  • Leaflet Routing Machine (LRM) pgRouting plugin
  • Future plans

Ko Nagase (sanak)

  • Developer, Georepublic Japan
  • pgRouting contributor
    • Initial Windows binary (MinGW) creator
    • Fixed/Improved Alpha Shape function
    • Multi OS (Mac/Win/Linux) build tester
  • QGIS pgRoutingLayer plugin contributor
    • Supported pgRouting v2.0 functions
    • Supporting pgRouting v2.1 functions is coming soon!

QGIS pgRoutingLayer plugin demo

Background

  • Specific pgRouting use case
    • All possible routes
    • Round trip case
    • Parallel edges case
  • K shortest path (KSP) limitations
  • Necessity of draggable routing

All possible routes

Round trip case


  • The combinatorial explosion becomes worse...

Same source/target parallel edges case


K shortest path (KSP) limitations


  • KSP returns 1st, 2nd, ..., Kth shortest "alternative" routes
  • pgr_ksp - K-Shortest Path
  • KSP is not for "all possible" routes...
  • KSP doesn't support "round trip" case
  • To support parallel edges case, post processing becomes necessary link

Necessity of draggable routing


  • After selecting "start"/"end" points, then drag a point on intermediate edges to on another edge
  • Just do S=>1, 1=>2, 2=>E routing
  • Supporting "round trip" case is possible
  • To support parallel edges case, edge based routing is necessary, and "pgr_trsp" supports it

Draggable routing frameworks

  • Google Maps Directions API
  • Open Source Routing Machine (OSRM)
  • Leaflet Routing Machine (LRM)

Google Maps Directions API

Open Source Routing Machine (OSRM)

Leaflet Routing Machine (LRM)

Leaflet Routing Machine (LRM) pgRouting plugin

  • Quick glance at LRM plugin interface
  • Server side design
  • Client side processing
  • Demo

Quick glance at LRM plugin interface 1/2


?loc=34.944479,135.702857&loc=34.944916,135.702972&loc=34.944530,135.703476

Quick glance at LRM plugin interface 2/2

  • Get response from the server
  • Parse the results, then format and pass it to LRM IRoute interface object
  • LRM render waypoints and coordinates in a map, and show summary and instructions in a panel

Server side design 1/3

  • To make it simple, use GeoServer WFS layer (SQL View) + PL/pgSQL wrapper function
  • PL/pgSQL wrapper function parses input waypoints, then call "pgr_trsp" function for each waypoints
  • GeoServer doesn't support multiple geometry columns' layer, so, designed that PL/pgSQL returns merged TRSP result edges with "point type" attribute
Value Meaning
1 Edge start node is source(origin) point
2 Edge end node is target(destination) point
4 Edge start node is intermediate way point
8 Edge end node is intermediate way point

Server side design 2/3

- PL/pgSQL wrapper function -


CREATE OR REPLACE FUNCTION routing.viaPoints(
        IN points text, -- Format: "Lng,Lat|Lng,Lat|..."
        IN tbl varchar DEFAULT 'osm_2po_4pgr'::varchar, -- Edge table name
        : -- Other default values
        OUT seq integer,
        OUT gid integer,
        OUT name text, -- Road name
        OUT heading double precision, -- Angle from edge start to edge end (not used)
        OUT cost double precision,
        OUT geom geometry, -- Edge geometry (ordered)
        OUT distance double precision,
        OUT point_type smallint -- Point type
    )
    RETURNS SETOF record AS
    :
  • Parse passed waypoints text
  • Find each waypoint's nearest edge, position in the edge and snapped point
  • Call "pgr_trsp" function for each waypoints

Server side design 3/3

  • GeoServer SQL View settings to pass a waypoints parameter to PL/pgSQL wrapper function

Client side processing 1/5

  • Request waypoints as "viewparams" value to the GeoServer WFS layer

options: {
	serviceUrl: 'http://localhost:8080/geoserver/pgrouting/wfs',
	timeout: 30 * 1000,
	urlParameters: {
		version: '1.0.0',
		request: 'GetFeature',
		outputFormat: 'application/json'
	}
},
:
						

route: function(waypoints, callback, context, options) {
	:
	url = this.buildRouteUrl(waypoints, options);
	:
	corslite(url, L.bind(function(err, resp) {
		:

Client side processing 2/5


buildRouteUrl: function(waypoints, options) {
	var points = [],
		i,
		baseUrl;
	
	for (i = 0; i < waypoints.length; i++) {
		points.push(waypoints[i].latLng.lng + '\\,' + waypoints[i].latLng.lat);
	}

	baseUrl = this.options.serviceUrl + L.Util.getParamString(L.extend({
			typeName: this._typeName,
			viewparams: 'points:' + points.join('|')
		}, this.options.urlParameters), baseUrl);

	return baseUrl;
},

Client side processing 3/5

  • Get response GeoServer WFS layer

route: function(waypoints, callback, context, options) {
	:
	corslite(url, L.bind(function(err, resp) {
		:
		if (!timedOut) {
			if (!err) {
				data = JSON.parse(resp.responseText);
				this._routeDone(data, wps, callback, context);
				:

Client side processing 4/5


_routeDone: function(response, inputWaypoints, callback, context) {
	var alts = [],
	:
	for (i = 0; i < response.features.length; i++) {
		feature = response.features[i];
		edgeCoords = this._coordsToLatLngs(feature.geometry.coordinates);
		if ((feature.properties.pointType & 1) || (feature.properties.pointType & 4)) {
			viaCoords.push(edgeCoords[0]);
			viaIndices.push(routeCoords.length);
		}
		if (feature.properties.pointType & 2) {
			viaCoords.push(edgeCoords[edgeCoords.length - 1]);
			viaIndices.push(routeCoords.length + edgeCoords.length - 1);
		}
		instructions = instructions.concat(this._convertInstructions(feature.properties, routeCoords, edgeCoords));
		routeCoords = routeCoords.concat(edgeCoords);
		totalDistance += feature.properties.distance;
		totalTime += feature.properties.cost * 3600;
	}

	actualWaypoints = this._toWaypoints(inputWaypoints, viaCoords);

	alts.push({
		name: '',
		coordinates: routeCoords,
		instructions: instructions,
		summary: {
			totalDistance: totalDistance,
			totalTime: Math.round(totalTime)
		},
		inputWaypoints: inputWaypoints,
		waypoints: actualWaypoints,
		waypointIndices: viaIndices
	});

	callback.call(context, null, alts);
},

Client side processing 5/5

  • Result route and waypoints are rendered in a map
  • Result summary and instructions are displayed in a panel

Demo

Resources

Future plans

  • More simplification and test
  • Try to develop OL3 custom interaction
  • Try to develop QGIS Python plugin

More simplification and test

  • Current implementation depends on "osm2po" converting edge table schema, so more generalization is necessary
  • Currently, "instructions" contents is built at the client side, but moving its logic to server PL/pgSQL side may be better
  • Currently, tested it only with small data set, so testing it with larger data set become necessary

Try to develop OL3 custom interaction

  • Port LRM itself to OL3 custom interaction as "OL3 Routing Machine (ORM)"
  • Port LRM pgRouting plugin to an OL3 class

Try to develop QGIS Python plugin

  • Port LRM itself to QGIS Python plugin as "QGIS Routing Machine (QRM)"
  • Port LRM pgRouting plugin to a Python class
  • If possible, consider about direct access from "QGIS Python plugin" to "PL/pgSQL wrapper function"

Thank you!