pgrouting: Geospatial Routing

pgRouting is PostgreSQL and PostGIS extension adding geospatial routing functionality.

The core functionality of pgRouting is a set of path finding algorithms including:

• All Pairs Shortest Path, Johnson’s Algorithm
• All Pairs Shortest Path, Floyd-Warshall Algorithm
• Shortest Path A*
• Bi-directional Dijkstra Shortest Path
• Bi-directional A* Shortest Path
• Shortest Path Dijkstra
• Driving Distance
• K-Shortest Path, Multiple Alternative Paths
• K-Dijkstra, One to Many Shortest Path
• Traveling Sales Person
• Turn Restriction Shortest Path (TRSP)

Enable the extension#

Example#

As an example, we'll solve the traveling salesperson problem using the pgRouting's pgr_TSPeuclidean function from some PostGIS coordinates.

A summary of the traveling salesperson problem is, given a set of city coordinates, solve for a path that goes through each city and minimizes the total distance traveled.

First we populate a table with some X, Y coordinates

Next we use the pgr_TSPeuclidean function to find the best path.

Resources#

• Official pgRouting documentation