Difference between revisions of "Traffic in Navit"

From Navit's Wiki
Jump to: navigation, search
(Updated images to show live use case)
(Matching Traffic Reports to Map Items: Non-TMC sources)
 
(One intermediate revision by the same user not shown)
Line 7: Line 7:
 
== Using Traffic Information in Navit ==
 
== Using Traffic Information in Navit ==
  
Traffic support is currently an experimental feature. If you want to try it, you need the following:
+
Traffic support is currently an experimental feature. If you want to try it, you need Android (support for other platforms will follow) and an app which supplies TraFF messages. If you have all of these, edit your navit.xml by adding the following line before the <code><vehicle/></code> element:
  
* Android (support for other platforms will follow)
+
<code>
* [https://f-droid.org/packages/com.vonglasow.michael.qz/ Qz] version 2.0.0 or later
+
<traffic type="traff_android"/>
 +
</code>
 +
 
 +
And you should be ready to go! Fire up ypur app and pick up some messages—they should also appear in Navit, and if they affect your route, Navit will try to find a way around them if there is one. (In rare cases, though, Navit may still send you into a congestion because going around it takes longer than waiting.)
 +
 
 +
=== Qz ===
 +
 
 +
You need [https://f-droid.org/packages/com.vonglasow.michael.qz/ Qz] version 2.0.0 or later, as well as:
 
* A receiver supported by Qz:
 
* 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
 
** 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
Line 17: Line 24:
 
* 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)
 
* 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 <code><vehicle/></code> element:
+
Once you have all of these, fire up Qz, connect your receiver and see if you get any messages. 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.
  
<code>
+
=== RoadEagle ===
<traffic type="traff_android"/>
 
</code>
 
  
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 way around them if there is one. (In rare cases, though, Navit may still send you into a congestion because going around it takes longer than waiting.)
+
Another TraFF app is [https://gitlab.com/traffxml/roadeagle RoadEagle], currently under development and still in experimental status. It is not on F-Droid yet—for the moment you will have to build it from source. RoadEagle does not require any special hardware but you do need a data connection. It currently has support for Poland and Lithuania; support for other countries is being added.
  
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.
+
Fire up RoadEagle and choose your information sources in Settings. After that, RoadEagle should load traffic messages from the sources you have chosen. These should also appear in Navit.
  
 
== Traffic Data in Navit ==
 
== Traffic Data in Navit ==
Line 173: Line 178:
 
== Matching Traffic Reports to Map Items ==
 
== Matching Traffic Reports to Map Items ==
  
The first iteration of the traffic module has close links with the [http://traffxml.org 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.
+
The first iteration of the traffic module has close links with the [http://traffxml.org TraFF format], developed by the author of the traffic module. In the first use case, 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.
 
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.
+
Other sources (with TraFF converters) also exist by now; many of them offer better accuracy for their reference points.
 +
 
 +
The traffic module deals with inaccuracies in location references 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.
 
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.
+
Since the start and end points may be 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.
 
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.
Line 191: Line 198:
 
Limitations of this method:
 
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.
+
* 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. That will require an extension of the TraFF format, discussed [https://gitlab.com/traffxml/traff/issues/10 here].
* 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.
+
* 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. Most other formats seem to have similar restrictions.
 
* 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).
 
* 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).
* When a road is closed due to roadworks for a longer period of time, it is commonly tagged <code>highway=construction</code> in OSM, which causes it to disappear from the Navit map. When a closure report arrives for the same road, Navit may end up marking the detour as closed.
+
* When a road is closed due to roadworks for a longer period of time, it is commonly tagged <code>highway=construction</code> in OSM, which causes it to disappear from the Navit map. When a closure report arrives for the same road, Navit may end up marking the detour as closed. See [https://github.com/navit-gps/navit/issues/644 #644] for details.
* 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.
+
* Traffic distortions cannot apply to parts of a segment—where defined, they are valid for the entire length of the segment. This is not a major issue with TMC or other sources which always supply junctions as end points, as every junction in the road network also terminates a segment. Other sources, however, allow start or end points anywhere on the road (such as Polish road information on RoadEagle)—here Navit may end up showing an affected section longer or shorter than what the source reports.
  
  
 
[[Category:Traffic]]
 
[[Category:Traffic]]

Latest revision as of 19:46, 11 August 2019

Navit on Android routing off the motorway…
…around a traffic distortion…
…seen here
Route avoiding a traffic distortion (route in blue, traffic distortion in orange)

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.

Using Traffic Information in Navit[edit]

Traffic support is currently an experimental feature. If you want to try it, you need Android (support for other platforms will follow) and an app which supplies TraFF messages. If you have all of these, edit your navit.xml by adding the following line before the <vehicle/> element:

<traffic type="traff_android"/>

And you should be ready to go! Fire up ypur app and pick up some messages—they should also appear in Navit, and if they affect your route, Navit will try to find a way around them if there is one. (In rare cases, though, Navit may still send you into a congestion because going around it takes longer than waiting.)

Qz[edit]

You need Qz version 2.0.0 or later, as well as:

  • 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)

Once you have all of these, fire up Qz, connect your receiver and see if you get any messages. 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.

RoadEagle[edit]

Another TraFF app is RoadEagle, currently under development and still in experimental status. It is not on F-Droid yet—for the moment you will have to build it from source. RoadEagle does not require any special hardware but you do need a data connection. It currently has support for Poland and Lithuania; support for other countries is being added.

Fire up RoadEagle and choose your information sources in Settings. After that, RoadEagle should load traffic messages from the sources you have chosen. These should also appear in Navit.

Traffic Data in Navit[edit]

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 maxspeed to the expected speed.
  • Delays: there are waiting times or other time penalties on the affected segment. This is represented by setting delay to the expected delay.
  • Closures: the segment is closed to all traffic. This is represented by setting maxspeed to zero.

Both maxspeed and 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, maxspeed and 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.

Previous Usage[edit]

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.

GUI[edit]

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[edit]

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.

API[edit]

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.
Parameters
this The route graph
seg The segment to which the traffic distortion applies
delay Delay in tenths of a second, or 0 to clear an existing traffic distortion

Limitations:

  • 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[edit]

To get dynamic traffic reports into Navit (and remove them again when they are no longer valid), we have the following options:

Option Pros Cons
Maintain a textfile map and include a reference in the default mapset
  • Distortions are persistent across relaunches (may not be needed if the reports from which they originate are kept persistent)
  • Can be extended to future traffic event types (such as hazard warnings)
  • Good efficiency as distortions can be reused between routes
  • Configuration (including legacy navit.xml) can easily break this feature without any hint at the reason it doesn’t work
  • Some coding effort (existing code only supports addition; updates and removals still need to be implemented)
Add distortions via route_graph_set_traffic_distortion() or similar
  • Little coding effort (call an existing function, or a similar one still to be implemented)
  • Not vulnerable to misconfiguration/failure to update legacy configurations
  • Insertions and removals well tested (updates should be easy too)
  • Not easily extensible to traffic events other than distortions
  • No persistence (unless traffic reports leading to distortions are kept persistent)
  • Efficiency is presumably not optimal as distortions need to be re-generated for each new route
Separate (in-memory) map driver, similar to route map
  • Cleanest solution, consistent with the rest of Navit
  • Can be extended to future traffic event types (such as hazard warnings)
  • Not vulnerable to misconfiguration/failure to update legacy configurations
  • Good efficiency as distortions can be reused between routes
  • More coding effort (but similar constructs already exist)
  • No persistence (unless traffic reports leading to distortions are kept persistent)

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[edit]

The first iteration of the traffic module has close links with the TraFF format, developed by the author of the traffic module. In the first use case, 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.

Other sources (with TraFF converters) also exist by now; many of them offer better accuracy for their reference points.

The traffic module deals with inaccuracies in location references 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 may be 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. That will require an extension of the TraFF format, discussed here.
  • 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. Most other formats seem to have similar restrictions.
  • 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).
  • When a road is closed due to roadworks for a longer period of time, it is commonly tagged highway=construction in OSM, which causes it to disappear from the Navit map. When a closure report arrives for the same road, Navit may end up marking the detour as closed. See #644 for details.
  • Traffic distortions cannot apply to parts of a segment—where defined, they are valid for the entire length of the segment. This is not a major issue with TMC or other sources which always supply junctions as end points, as every junction in the road network also terminates a segment. Other sources, however, allow start or end points anywhere on the road (such as Polish road information on RoadEagle)—here Navit may end up showing an affected section longer or shorter than what the source reports.