pgrServer

Dijkstra Shortest Path Search

Driving Distance Isochrone

Traveling Salesperson Problem

All Directed Path

Vehicle Routing Problem (VRP)

Introduction

pgrServer is a routing service that is able to use pgRouting topologies to load data into a JGraphT graph for very fast searches even with dense networks such as the OpenStreetMap (OSM) data set.

The graph is created at startup when the topology is read from a PostgreSQL database. This graph though can be re-created at regular intervals by making a service request, for networks that have dynamic costs.

And similar to pgRouting, this application is not road navigation centric. This application can be used for a wide variety of networks: i.e. utilities (fiber optic lines), water systems, etc.

As of this version, the following search algorithms are included as a service:

• Dijkstra ( for dense networks )
• A-Star ( for dense networks )
• ContractionHierarchyBidirectionalDijkstra ( for dense networks * )
• K-Shortest Paths ( returns up to K alternative paths via edge penalization )
• ClosestFirstIterator ( for Driving Distance Isochrone creation )
• NearestNeighborHeuristicTSP ( for Traveling Salesperson Problem )
• All Directed Paths ( for sparse networks or short distance search)
• Bellman-Ford ( for sparse networks )
• BFS ( for sparse networks )
• Johnson ( for sparse networks )
• Floyd-Warshall ( for sparse networks )

(*Note: Initial call to a ContractionHierarchyBidirectionalDijkstra request will take time since a contraction graph will be created first. Subsequent calls will result in a much faster response.)

pgrServer is also able to solve Vehicle Routing Problems (VRP) using the JSprit VRP engine in order to find the optimal set of routes for a fleet of vehicles to traverse orders from a set of customers.

When to use pgrServer

• When a web service is required to serve route data. pgrServer can be used to easily serve data to a variety of web or mobile application clients.

• When the network is very dense and pgRouting struggles with long distance searches. pgrServer stores the entire graph into memory at start and can do route searches within the entire graph.

• When performance is paramount. pgrServer can return routes within ~50 kilometer searches in milliseconds even in very dense networks.

• When the cost (weight) of the graph is dynamic. PgrServer can be used to load and link updated costs residing in a table or view into an existing graph without having to reload the graph. Also, the data in the table or view does not have to include all the costs of the graph, only the changed costs, since pgrServer will use the existing cost if no link can be established.

Requirements

• PostgreSQL > 9.4
• PostGIS
• PgRouting or Osm2Po (for topology creation)
• Maven
• Tomcat Application Server for deployment

Docker

For convenience, a Docker image can be built for this project. There are a few environment variables that can be optionally set in order for the Docker image to work properly:

• POSTGRES_HOST: the host IP/fully qualified domain. Default localhost.
• POSTGRES_PORT: the port designated for the Postgres instance. Default 5432.
• POSTGRES_DB : the database you. Default pgr.
• POSTGRES_USER: the Postgres user name. Default postgres.
• POSTGRES_PASS: the Postgres password. Default postgres.
• PGRSERVER_VIEW_NAME: the name of the PostgreSQL view or table that pgrServer reads the topology from. Default pgrserver.

Note, it is still necessary to prepare the topology with pgRouting or osm2po. Also, the docker usage is advisable for testing or development purposes only. It is highly advisable not to run a production server with the Docker image.

# build the image and spin up the container(s)
docker build -t mbasa/pgrserver:latest .
docker-compose up -d

From here, the application can now be tested by displaying the List of APIs.

Preparing the Topology

• Create a topology table. Refer to pgRouting's Documentations on the pgr_createTopology function.

• It is also possible to use OSM2PO to create a topology table using OSM pbf data files. Refer to this pgrServer WIKI for more information on how to use OSM2PO to create topologies for pgrServer.

• Ensure that there is an index on an unique id field, an index on the source field, an index on the target field, and a spatial index on the geometry field of the topology table.

• Create a View or Table based on the topology table that will contain the following fields: id, source, target, cost, reverse_cost, length, geom.

CREATE VIEW pgrserver AS SELECT id,node_from AS source,node_to AS target,cost, reverse_cost, length, wkb_geometry AS geom FROM kanto ;

The name of this view or table defaults to pgrserver and can be changed via the pgrserver.view.name property in application.properties, as a command-line argument, or as an environment variable:

Method	Example
application.properties	pgrserver.view.name=my_network
Command line	java -jar pgrServer.war --pgrserver.view.name=my_network
Environment variable	PGRSERVER_VIEW_NAME=my_network

Note:

1. the length column has to be in meters(m) units.

2. the reverse_cost value has to be greater than the cost in order for the edge to be considered as a one-way street.

Getting the Application

The latest WAR file of the application can be downloaded from each stable release of this repository, and can either be placed in a Tomcat Application Server or run stand alone via the command:

java -jar pgrServer.war

Building the Application

• Edit src/main/resources/application.properties and modify the PostgreSQL Database URL and login parameters.

• Create a WAR file that can be deployed to a Tomcat Server.

    mvn clean install -DskipTests

• Or run and test the application with the built-in Tomcat container.

    mvn spring-boot:run

Display the List of APIs

The list of APIs can be viewed by displaying the Swagger page:

http://localhost:8080/pgrServer/

Dynamic Costs

PgrServer can use dynamic costs from an existing table or view in PostgreSQL, and link it into the graph without having to do a reload to create truly dynamic routes. The table or view must contain the following fields: id, source, target, cost.

CREATE VIEW dynamic_cost AS select id,source,target,length + 1000 as cost from pgrserver ;

This table or view name can be passed as a parameter for the following APIs:

• dijkstra_dyncost
• astar_dyncost

K-Shortest Paths

pgrServer supports K-Shortest Paths, which returns up to K alternative routes between two points. The first path is the true shortest path (Dijkstra). Each subsequent path is found by penalizing the edges used in the previous path and re-running Dijkstra, encouraging genuinely different routes. The penalty multiplier is configurable via ksp.penalty.factor in application.properties (default: 10.0).

Two endpoints are available, accepting either node IDs or latitude/longitude coordinates:

Endpoint	Parameters
GET /api/node/kShortestPath	source, target, k (optional)
GET /api/latlng/kShortestPath	source_x, source_y, target_x, target_y, k (optional)

The k parameter controls how many paths are returned. It defaults to 3 and is capped at a maximum of 10. The response is a GeoJSON FeatureCollection with one Feature per path.

# Example: 3 alternative paths between two coordinates (default k)
curl "http://localhost:8080/pgrServer/api/latlng/kShortestPath?source_x=139.620139631&source_y=35.710788822&target_x=139.620928086&target_y=35.699183061"

# Example: up to 5 paths
curl "http://localhost:8080/pgrServer/api/latlng/kShortestPath?source_x=139.620139631&source_y=35.710788822&target_x=139.620928086&target_y=35.699183061&k=5"

For more details, refer to the K-Shortest Path in pgrServer wiki page.

Reload the Graph

To reload the graph if the complete cost has changed, send a POST request with the authcode parameter value. The authcode value can be set by updating the installed pgrs_auth table in the PostgreSQL database.

curl -X POST -F "authcode=abc12345" "http://localhost:8080/pgrServer/api/graphreload"

Viewing the Data

A demo application, pgrServerDemo , has been created to easily display selected features of pgrServer.

Also, pgrServer returns a GeoJSON object for the created route or driving distance polygon, hence any application that supports GeoJSON can be used to view the results.

To quickly view the results, GeoJSONLint web service can be used:

http://www.geojsonlint.com

It is also possible to use the result as a Vector Layer in QGIS by doing:

Layer -> Add Layer -> Add Vector Layer

and set the protocol to HTTP and add the URL request of pgrServer.

Tomcat Deployment

Since this is a memory intensive application, configuring Tomcat to use more memory will be necessary, especially with very large data sets ( greater than or equal to 9 million edges ) to avoid OutOfMemoryError problems. The argument settings below can be used to let Tomcat allocate up to 8GB of memory for its usage:

-Xms2048m -Xmx8192m -server

Refer to Tomcat documentation for more information on memory allocation.

When using the spring-boot application's Tomcat, the following can be performed to pass the required memory parameters:

mvn spring-boot:run -Dspring-boot.run.jvmArguments="-Xms2048m -Xmx8192m"