Traffic in Navit
Traffic support in Navit is currently (as of October 2018) experimental and needs to be enabled manually.
Until October 2018, Navit lacked full support for routing around traffic problems, although the routing engine has had the core functionality for many years. Full traffic support, i.e. receiving traffic reports and routing around congestions, is currently an experimental feature and still under development. Follow the latest developments on the traffic branch if you’re interested in seeing how it works, or are interested in contributing. The project board will give you an idea of what is currently being worked on, and where we are looking for contributions.
Traffic support is currently an experimental feature. If you want to try it, you need the following:
- Android (support for other platforms will follow)
- Qz version 2.0.0 or later
- A receiver supported by Qz:
- GNS FM9-BT (requires Bluetooth): this receiver comes in a permanently installed and a pluggable variant; the permanently installed one is recommended for its superior reception
- One of the various Si470x-based USB tuners (requires USB OTG)
- A decent antenna for the receiver (stub or pigtail antennas are generally insufficient)
- Being in an area with a free-to-air TMC service supported by Qz (Austria, Germany, Italy and Switzerland are known to work, Benelux, Denmark, Slovakia, Slovenia, Spain and Sweden might also work)
If you have all of these, edit your navit.xml by adding the following line before the
And you should be ready to go! Fire up Qz, connect your receiver and see if you get any messages—they should also appear in Navit, and if they affect your route, Navit will try to find a cheaper way around them.
If you don’t see any messages in Qz, most likely your antenna setup is insufficient (TMC is quite sensitive to reception quality). Check the Qz wiki for known issues. Or you might be in an area without a TMC service supported by Qz—areas in which Qz works are currently limited to parts of Western and Central Europe.
Internally, Navit uses traffic distortions to model traffic issues which may affect the choice of route. A traffic distortion can represent the following:
- Slow traffic: speed on the affected segment is below the posted limit (or whatever Navit assumes the default speed for the segment to be), e.g. because of dense traffic or because of temporary speed limits. This is represented by setting
maxspeedto the expected speed.
- Delays: there are waiting times or other time penalties on the affected segment. This is represented by setting
delayto the expected delay.
- Closures: the segment is closed to all traffic. This is represented by setting
delay can be set at the same time and their effects will add up.
Traffic distortions are just map items, denoted by the
type_traffic_distortion type, and can be stored in any map.
When evaluating traffic distortions, Navit would originally (up to October 2018) just look at the item type,
delay, ignoring other attributes. This meant that:
- Traffic distortions would always apply to both directions of the affected segment, one-way distortions being only possible for roads with segregated carriageways, which are mapped as two separate, parallel ways.
- Navit lacked support for vehicle-specific traffic distortions (e.g. size restrictions, closures for certain vehicle types, different waiting times for trucks and passenger cars).
The traffic branch changed that by introducing access flags for traffic distortions. They work similarly to access flags on ways, where they specify which modes of transportation can use the way, and in which direction. For traffic distortions, they specify the modes of transportation and the directions to which this particular traffic distortion applies.
Prior to the traffic branch, traffic distortions were already used internally in limited ways (all of which continue to work).
Traffic distortions are (ab)used to generate penalties for turning around if these are defined in the current vehicle profile. This is done in route.c, in the
route_path_new() function, which can be used as an example for inserting traffic distortions into the route graph. (See #Dynamic Traffic Reports for other options to get traffic distortions to the routing engine.)
Traffic distortions can also be entered manually through the GUI, though this is not supported by all GUIs and should probably be considered an experimental feature. See #GUI.
The GTK GUI has menu items to enter traffic distortions, but they don’t work in a straightforward manner. If you find Navit happily routing even over the segment you just marked as closed, read on.
All the menu items do is write the segment and its traffic distortion to a map in textfile format called distortion.txt, found in Navit’s data dir. However, that file doesn’t do anything unless it is added to the active mapset. Apparently this is a feature that never got fully implemented to the point of being usable out of the box.
Traffic Distortion in Maps
Traffic distortions are map items and can (presumably) be stored in any map, whether in memory or read from a file. As mentioned under #GUI, this is what happens with traffic distortions entered manually through the GTK GUI—they get written to a textfile map. Here’s an example of its contents:
type=traffic_distortion maxspeed=0 0x13a07c 0x5e9634 0x139e87 0x5e98ae type=traffic_distortion maxspeed=10 0x139f22 0x5d6a5a 0x139ec5 0x5d6a13 0x139e88 0x5d69e7 0x139e83 0x5d69e4 type=traffic_distortion delay=3600000 0x13a0f3 0x5d6a41 0x13a101 0x5d6a33 0x13a110 0x5d6a29 0x13a154 0x5d6a03
The first line for each distortion is the item data: item type (always
traffic_distortion here) and its attributes. The following lines are the coordinates for the affected segment.
In the default configuration, that file doesn’t do anything as it is just written to, but never read. You can change that by adding the following line to the active mapset in your navit.xml file:
<map type="textfile" enabled="yes" data="distortion.txt"/>
Restart Navit, and it will route around the distortions you have just entered. Note that no path is necessary for the map created by GTK GUI, as the it resides in Navit’s default data path.
Changes to this file will not be picked up immediately, because Navit lacks a notification mechanism for changes to the map.
In order to see the new distortions on the map, you will need to redraw it (which happens automatically in a moving vehicle if the map follows the vehicle).
In order to route around the new distortions, you will need to stop navigation and set the destination again (which will cause a new route graph to be built—simply recalculating the route is also not sufficient, because that still uses the same route graph). Navit has no way to tell routing about the changes, and the currently used Dijkstra algorithm does not support partial updates.
This is being changed in the traffic branch. First, when a traffic message is received, that will always trigger a map redraw, causing traffic distortions to show up in the map as soon as they are received. Also, the routing algorithm was changed to LPA*, which supports partial updates. Thus, when a traffic distortion changes, Navit will automatically recalculate the cheapest route.
This refers to Navit up to October 2018. The traffic branch introduced additional API functions.
The only function to edit traffic distortions is found in route.c:
static void route_graph_set_traffic_distortion(struct route_graph *this, struct route_graph_segment *seg, int delay);
- Sets or clears a traffic distortion for a segment.
- This sets a delay (setting speed is not supported) or clears an existing traffic distortion. Note that, although setting a speed is not supported, calling this function with a delay of 0 will also clear an existing speed constraint.
The route graph
The segment to which the traffic distortion applies
Delay in tenths of a second, or 0 to clear an existing traffic distortion
- This function prototype is not part of the header file, i.e. not part of the public API. Currently, it is only used internally.
- There is currently no way to set a maxspeed or closure. However, calling
route_graph_set_traffic_distortion()with a zero delay will unset any existing traffic distortion.
Dynamic Traffic Reports
To get dynamic traffic reports into Navit (and remove them again when they are no longer valid), we have the following options:
|Maintain a textfile map and include a reference in the default mapset||
| Add distortions via
|Separate (in-memory) map driver, similar to route map||
If we assume that traffic distortions are generated out of traffic reports (which may affect multiple segments), and that the reports are kept persistent at least throughout their validity period, then the last option (separate in-memory map driver) is a one-off coding effort but provides the biggest benefit in the long run. The textfile map option may work as a quick win in an early dev phase (e.g. to verify proper processing of traffic messages) but is not suitable for production use due to its limitations.
For this reason, the traffic branch implements an in-memory map driver.
Matching Traffic Reports to Map Items
The first iteration of the traffic module has close links with the TraFF format, developed by the author of the traffic module. Currently messages are received from an external source, which converts them from TMC. For this reason location referencing is similar to TMC: the start and end points are given, along with some attributes which help identify the road. The TraFF converter adds extra auxiliary points to locations for which TMC supplies only one point, or for locations on ring roads.
Unfortunately, the points do not always correspond precisely with the roads on the map. TMC is particularly nasty in that it reduces even motorway junctions to one single point, although the entire junction can be as much as 1,000 meters or more across. Even then, unambiguously matching the points to a road does immediately give us the segments connecting them.
The traffic module solves this by using a variation of the routing algorithm.
Cost is primarily calculated based on the length of each segment. If the location specifies attributes for the road (such as the road type, road number or road name), then these are compared to the attributes of the segment, and the segment length is multiplied with a penalty factor. If all attributes match, the length of the segment is used unchanged; for poor matches the assumed cost may be multiple times the segment length.
Since the start and end points are off-road, we assume each point in the route graph has an imaginary link to them, which is, however, more expensive than even a poorly-matched road. Initially, each point is initialized with the cost of getting to the end of the end point over that imaginary link. Then points are evaluated based on the cost of their neighbors and the segments linking them. When all is finished, the point for which the sum of its cost and the cost of reaching it from the start point is lowest is assumed to be the start point of the affected stretch of road.
If the message comes from a source with low resolution (e.g. TMC, which is limited to road junctions and a few chosen landmarks on roads), then attributes of the points are used to refine the match.
For three-point locations, this is done twice, and the two resulting stretches of road are then concatenated.
For single-point locations (with one or two auxiliary points), the resulting stretch of road is then truncated to the one segment.
Limitations of this method:
- This work only for traffic locations with two points, or three if they are spaced reasonably far apart. The data model is currently limited to three points anyway, but this limitation may become an issue (and need to be revised) if we want to support sources which rely on more detailed representations of the road geometry.
- Identifying the road by its attributes does not work well if the affected stretch of road comprises multiple roads with different attributes. This is not a problem with TMC, where messages never span multiple roads.
- If the stretch of road affected is not the shortest connection between the points (corrected for attributes), this will give incorrect results. With the TMC messages tested so far (which come with attributes to identify the road), this has seldom caused any problems (the only one being a serpentine road in the Alps).
- Traffic distortions cannot apply to parts of a segment—where defined, they are valid for the entire length of the segment. This is currently not a major issue, as every junction in the road network also terminates a segment.