What Is Important In Route Calculation

Routing API and its variants (Navigation, Matrix routing used in route optimization, Isochrone, Map Matching) are the most complex and challenging to develop amongst all Map APIs. The list below covers the essential characteristics of good routing services.

Time-dependent routing, speed profiles, and real-time traffic information

Speed profiles, real-time traffic information, and time-dependent routing are almost nowadays standard features.

Traditionally used average travel speeds of a particular road segment are static and don't always reflect the real-world traffic conditions. To overcome this problem, modern routing engines use dynamic travel speeds or speed profiles. Speed profiles define average travel speed during the day, usually for 15 minutes time spans, thus providing realistic ETAs (estimated time of arrival).

Compared to speed profiles and typical travel speeds, real-time traffic information (live traffic) provides current travel speeds, making it a little more valuable. However, combining speed profiles and real-time traffic provides the best routes with highly accurate travel times.

Time-dependent routing is the basis of speed profiles and real-time traffic information. The end-user typically specifies arrival or departure time, and the routing engine needs to calculate the fastest route that respects given restrictions. Restrictions can vary from daily or seasonal road closures, reversible roads, etc. The resulting route is always mathematically the fastest. Sometimes this means that the suggested route will prefer, e.g., 15 minutes waiting for the road to open instead of making a detour.

Limit on the number of waypoints

Routing API vendors typically, depending on the selected plan, limit the number of route points.

To name a few, Mapbox limits the requests to only 3 waypoints for live-traffic-based routing, 25 for non-traffic-based routing, Google to 10 waypoints (25 for Directions Advanced SKU), Graphopper 5-150 waypoints, etc.

Alternative routes

Typically, routing engines calculate the fastest route and provide alternative options, which are obviously very useful in real-world situations and appreciated by end-users.


Alternative routes need to make sense in real-world situations - they should resemble the ones a real-world user would come up with.
 This means that an alternative route bypassing a few roads doesn't count as an alternative; it needs to differ enough from the main route geometrically.
 At the same time, alternatives shouldn't be too much longer nor too much slower.


These requirements must be taken into account without endangering the performances. However, calculating alternative routes takes 3x times longer than finding just the fastest route. Some Routing APIs will try to circumvent this issue by offering only alternatives on shorter routes.


Country-specific features

The majority of routing algorithms handle left-side driving countries with ease but make sure to double-check.
 Even more important is handling country-specific options, such as handling routing through dangerous areas or congestion charging zones.

• Due to specific political situations, routing through A, B, and C West Bank Areas should be completely or partially restricted for security reasons.
• To reduce air and noise pollution, driving in cities like Central London, Stockholm, and Gothenburg is charged per entry, and routing through this area should be optional. Moreover, in Stockholm and Gothenburg, the congestion tax applies only on weekdays and during the daytime.
• Access to central Athens is allowed on alternate days only, based on the odd-even license plates system. To provide adequate routes, the routing engine should be parameterized with the license plate numbers.
• Traffic in Istanbul takes place between the European and Asian sides. A routing engine's desirable feature is always to provide alternative routes passing through all Bosphorus bridges and tunnels.

Multimodal routing

Routing engines handle different transport modes besides car and taxi, such as combining public transport and walking. Public transportation schedule data is typically provided in a GTFS format.

Performance

Road network data is huge. Just to get a glimpse, in Italy, there are 260,000 km of roads, which corresponds to roughly 300 MB of compressed data. For an entire Europe, that translates into 7 GB and billions of road segments.
To find the best path from point A to B, the routing algorithm needs to process gigabytes of data - efficiently. Efficiently means in milliseconds on commodity hardware because the goal is that a routing API serves as many as possible end-users on as less as possible hardware resources. This is the hard part.



The performance of routing API (sometimes referred to as route planner API) is crucial for route optimization purposes and Distance Matrix API. Because the Distance Matrix API provides travel distance between a matrix of start and end locations, the underlying routing algorithm must calculate the routes as fast as possible.

The majority of routing algorithms use some variation of 1960s Dijkstra's shortest path in a graph algorithm. But only the good ones know how to modify it to become really fast, efficient, and accurate. Namely, the out-of-the-box Dijkstra and bi-directional Dijkstra algorithms are too slow and too resource-intensive for real-world applications.
Calculating routes between distant locations spread over several countries can be quite resource- hungry operations.