Routing Alternatives With Custom Spatial Data

Routing is the process of finding the optimal path between two or more locations in a network. In the context of computer science and geography, it typically involves finding the best route on a map, considering factors such as distance, time, or other constraints. It has become a crucial component of various applications, including navigation systems, logistics, delivery services, and mapping software.

Routing Algorithms:

Over the years, various routing algorithms have been developed to solve different types of routing problems. Some of the most commonly used ones include:

1. Dijkstra’s Algorithm: Finds the shortest path between two nodes in a graph.
2. A* Algorithm: A heuristic search algorithm that combines the benefits of Dijkstra’s algorithm and greedy best-first search.
3. Bellman-Ford Algorithm: Computes the shortest paths in a weighted graph, even with negative weights.
4. Floyd-Warshall Algorithm: Finds the shortest paths between all pairs of nodes in a weighted graph.

Recent advances in routing technology include the use of machine learning and artificial intelligence to predict traffic patterns and suggest more accurate and real-time routes. Additionally, graph databases and data structures optimize the storage and retrieval of spatial information.

Advanced Features:

• Road type selection: Prioritize specific road types (e.g., highways, toll roads, pedestrian paths).
• Isochrone maps: Visualize areas reachable within a certain time or distance.

The original 1922 map of travel times on rail and tram in Melbourne, Australia. klumpentown.com

• Polygon exclusion: Avoid routing through certain areas (e.g., construction zones, restricted areas).
• Real-time traffic: Adjust routes based on current traffic conditions.

• Multi-modal routing: Combine different modes of transport (e.g., driving, walking, public transit).
• Dynamic routing: Recalculate routes in response to events or changes in the network.

Routing technology has evolved significantly over the years, from basic algorithms to sophisticated solutions that consider real-time traffic, user preferences, and complex spatial constraints. As technology continues to advance, we can expect further improvements in accuracy, speed, and customization options for routing solutions.

What we need?

Road Network Data:

• Nodes and Edges: The road network is typically represented as a graph with nodes (intersections) and edges (road segments between intersections).

• Geometric Information: Each edge has geometric information, such as coordinates or geometry, defining its shape.
• Connectivity: Nodes are connected by edges, forming a network that represents the physical road layout.

Attributes for Routing:

• Speed Limits: Each road segment should have information about the speed limit, which is crucial for calculating travel times.
• Road Type: Differentiate between types of roads (e.g., highways, local roads) to consider road characteristics in routing decisions.
• Directional data: Specify if roads are one-way or two-way to model traffic flow accurately.
• Usage: Vehicle road, pedestrian way or bicycle only ways.

Cost Calculation:

• Travel Cost: A cost function considers factors like travel time, distance, or a combination of both.
• Speed-Based Cost: Incorporates speed limits to calculate time-based costs.
• Road Type Cost: Assigns costs based on road types (e.g., prefer highways over local roads).

Ready Solutions for Suitable Path Finding

OSRM (Open Source Routing Machine)

• OSRM is an open-source routing engine designed for map data. It efficiently calculates routes for various transportation modes, including car, bicycle, and pedestrian.
• Supports multiple profiles (car, bike, foot).
• Utilizes contraction hierarchies for fast preprocessing.
• Designed for high-performance routing.
• OSRM is widely used in applications requiring routing capabilities, and it’s used on the OpenStreetMap (OSM) website for routing functionality.

pgRouting

• pgRouting is an extension for the PostgreSQL database that provides geospatial routing capabilities. It integrates with PostGIS and allows routing queries directly within the database.
• Supports various routing algorithms (Dijkstra, A*, etc.).
• Integration with SQL queries for seamless database interactions.
• Extensible and customizable for different use cases.
• pgRouting is commonly used in applications that require routing capabilities in combination with PostgreSQL databases.

GraphHopper

• GraphHopper is a fast and customizable open-source routing engine. It can be used both as a standalone application and as a library for integration into other projects.
• Supports car, bike, foot, and custom profiles.
• Uses OpenStreetMap data and supports custom data imports.
• Flexible and extensible through plugins like isochrone generation.
• GraphHopper is utilized in various applications, including fleet management, logistics, and route planning. It is also used on the OSM website.

Valhalla

• Valhalla is an open-source routing engine. It focuses on providing flexible and customizable routing solutions for different transportation modes.
• Supports car, bike, pedestrian, and multimodal routing.
• Provides dynamic costing for real-time traffic conditions.
• Offers advanced features like isochrone generation.
• Valhalla is used in map-related applications and services, offering dynamic and customizable routing solutions. It is also used on the OSM website.

OpenStreetMap (OSM) Integration:

• All these routing engines — OSRM, pgRouting, GraphHopper, and Valhalla — are used by the OpenStreetMap project. OSM leverages different routing engines to provide routing services on the OSM website, catering to various user preferences and requirements. The choice of which engine to use may depend on factors such as performance, features, and ease of integration.

Custom Data Issues

Solutions can theoretically work with any network data, but in practice, they commonly rely on OpenStreetMap (OSM) data, often provided in ‘xml’ or compressed ‘pbf’ formats. pgRouting can work with any kind of data.

At this stage, the most efficient approach is to convert the existing road data, which might be in various formats such as shapefile, MapInfo, or stored in a spatial database, into the OSM format — an XML file structure.

Before this conversion, the road data needs to undergo a transformation into network data. By network data, I refer to the process of topologically separating roads at each intersection, turning them into road junctions where directional decisions, such as turning right or left, can be made.

Utilizing existing road data, all established solutions create a graph. This structure essentially places a point at the beginning and end of each road, augments the road data with point information, and generates cache files to ensure effective operation. When a lengthy road isn’t segmented at each intersection, it might result in generating a route that spans the entire road.

If your data isn’t in the required format, you can employ the ‘QGIS split line by line’ feature to carry out this segmentation process.

OSM Data

As mentioned earlier, it’s important to note that existing routing solutions operate with OpenStreetMap (OSM) data. Consequently, a crucial step is to convert your available data into the OSM format. If you don’t have custom data, you can easily download country, continent, or global data from OpenStreetMap (I often use Geofabrik for this purpose).

While I won’t delve into exhaustive details about data editing here, it’s essential to ensure that your road data aligns with the standard OSM format. This involves understanding which columns your road data should have and making sure it contains the requisite information for OSM. For more specific guidance on the necessary modifications, you can refer to the details provided here.

After completing the OSM data conversion process, I utilized two distinct solutions to convert the data into shapefile format: ogr2osm and a custom application that I developed. In my custom application, I implemented a functionality that seamlessly transforms all shapefiles within a specified folder into a consolidated OSM file.

Ready with data? Let’s try them all!

pgRouting

Need PostGIS and pgRouting extensions on your database. I use ogr2ogr in Gdal Library to convert and data to PostGIS. When you have data on database, need to run these;

--source and target columns
ALTER TABLE routing_table ADD COLUMN "source" integer;
ALTER TABLE routing_table ADD COLUMN "target" integer;

--create topology for custom data
select pgr_createTopology('routing_table', 0.00001, 'geom', 'id', 'source', 'target')

--create cost and reverse-cost columns and calculate your own value 
alter table routing_table add column cost double precision;
alter table routing_table add column rcost double precision;

update routing_table set cost = st_length(geom) * road_type_if_integer, rcost = st_length(geom) * road_type_if_integer;
--one way restriction
update routing_table set rcost = cost + 1000000 where oneway = 1;

If ready, now just run to get a route result;

select id, geom from
pgr_dijkstra('SELECT id,source, target, st_length(geom) as cost FROM routing_table' ,
start_node_id, end_node_id, directed => false ) AS a JOIN routing_table AS b ON (a.edge = b.id)

If you have two points and need a result in GeoJSON, find the nearest nodes to those points, find the route, trim start and end edge with the points provided. Or not perfect but a usable solution as pl/pgsql function for that is here.

Then you can create a backend service to get routing results from Postgresql. And I have good news you can also create a frontend service to show results on a map.

OSRM (Open Source Routing Machine)

I always used docker images for backend and frontend, you can find all details from here.

You may modify your data and create Osm data or customize a lua file and use it while pre-processing road data. You may see car.lua on backend docker examples.

Valhalla

Valhalla also has a docker image, both frontend and backend runs on. I could run Valhalla only with pbf file so converted Osm data to pbf with Osmconvert. And also tried with pbf data downloaded from Geofabrik.

Graphhopper

GraphHopper is a fast and memory-efficient routing engine released under Apache License 2.0. It can be used as a Java library or standalone web server to calculate the distance, time, turn-by-turn instructions and many road attributes for a route between two or more points. Beyond this “A-to-B” routing it supports “snap to road”, Isochrone calculation, mobile navigation and more.

Actually as a Java developer, since it has been developed with Java, I have already used it in desktop applications, on the Spring Boot web platform, and as a Docker container. This has allowed me to use it on several platforms, making it one of the best solutions. Several examles here.

Adding that it need a small disk space for the graphed cache files.

Let’s sum up!

In conclusion, exploring the diverse range of routing solutions such as PgRouting, Valhalla, OSRM, and GraphHopper has been an enlightening journey. Each tool brings its unique strengths to the table, catering to various needs and preferences. After careful consideration and hands-on experience, I (or we as a team) ultimately chose GraphHopper for its seamless integration across different platforms.

While each solution has its merits, GraphHopper emerged as the optimal choice for my specific requirements.

In the dynamic landscape of routing solutions, the key is to weigh the pros and cons based on your project’s demands. I hope this exploration of various routing tools has provided valuable insights for your decision-making process. Happy routing!