User:CBenson/Routing penalties View history

(Up to questions about dirt road segments.)
m (→‎Road Type: wordsmithing)
 
(14 intermediate revisions by 3 users not shown)
Line 18: Line 18:


{{construction
{{construction
| contact    = https://www.waze.com/forum/viewtopic.php?f=276&t=174367
| contact    = http://www.waze.com/forum/viewtopic.php?f=276&t=174367
| contacttype = forum
| contacttype = forum
| draft      = yes
| draft      = yes
Line 28: Line 28:


== Background ==
== Background ==
Waze routing basically calculates the cost of different routes between the origin and the destination and selects the route with the least cost.  When the navigation type is set to fastest the cost is primarily based on the time the route is calculated to take.  When the navigation type is set to shortest the cost is primarily based on the distance of the route.  The cost is based on the properties of the road segments that make up the route and the speed data collected for each road segment.  There are other considerations that may cause the cost to deviate from simply the fastest or shortest route.  These considerations are typically applied to the routes in the form of penalties that increase the cost of route.  For example, if avoid toll road is set in the client, then the cost of road segments marked as toll is greatly increased.  Thus a segment in a route that that is penalized causes the cost of the route to be higher.
Waze routing essentially calculates the least cost route between the origin and the destination.  When the navigation type is set to fastest the cost is primarily based on the time the route is calculated to take.  When the navigation type is set to shortest the cost is primarily based on the distance of the route.  The cost is based on the properties of the road segments that make up the route and the speed data collected for each road segment.  There are other considerations that may cause the cost to deviate from simply the fastest or shortest route.  These considerations are typically applied to the routes in the form of penalties that increase the cost of route.  For example, if avoid toll road is set in the client, then the cost of road segments marked as toll is greatly increased.  Thus a segment in a route that is penalized causes the cost of the route to be higher.  In this manner Waze avoids penalized routes.


== Speed and Distance Data ==
== Speed and Distance Data ==
Line 34: Line 34:
Distance data is calculated based on the geometry of a segment. Thus the placement of the  junction nodes at segment ends and the placement of geometry nodes within a segment change the length of a segment.
Distance data is calculated based on the geometry of a segment. Thus the placement of the  junction nodes at segment ends and the placement of geometry nodes within a segment change the length of a segment.


===Speed Data===
===Traffic Data===
Speed data for a segment in a route is dependent on the next segment in the route.  In this way the speed data accounts for difference in the time to make different turns (such as a right turn, continuing straight, or turning left) at an intersection.  The speed data for each segment can be considered to be two components. One component is based on the time to traverse the majority of the length of the segment.  The other component is based on the time waiting at the end of the segment to travel to the next segment.
Waze retains speed data for each road segment as discussed regarding [[User:Voludu2/Traffic_data|traffic data]]Map editors do not control the speed data. With the exception of the default speed, the speed data is based on actual drives of Wazers.  It is important for segments to be properly placed on the map in relation to the drives (as shown in the GPS layer) so that waze assigns the wazers drive speeds to the proper segment.
* Default Speed Data - when a road segment is added to the map it is assigned speed data based on the road type of the segment.
* Historic Speed Data - when a Wazer drives a road segment, Waze retains the speed data from the drive.  Waze retains speed data for each segment for different times of the day and for different days of the week.  As speed data is collected the collected data is favored over the default speed data for the segment.
* Realtime Speed Data - where there is speed data from Wazers that have recently driven a segment that a route will use in the near future, that speed data is usedThis realtime traffic data allows waze to route around traffic jams to find the fastest route.
 
The editor does not control the speed data. With the exception of the default speed, the speed data is based on actual drives of Wazers.  It is important for segments to be properly placed on the map in relation to the drives (as shown in the GPS layer) so that waze assigns the wazers drive speeds to the proper segment.
    
    
==Client Navigation Settings==
==Client Navigation Settings==
There are several options in the client application that effect how the cost of the route is calculated.
There are several options in the client application that effect how the cost of the route is calculated.
* Navigation type - Fastest causes the route cost to be based on speed data.  Shortest causes the route cost to based on distance.
* '''Navigation type''' - Fastest causes the route cost to be based on speed data.  Shortest causes the route cost to based on distance.  Fastest is the default setting.
* Avoid toll road - Causes segments marked as toll to be penalized.
* '''Avoid toll road''' - Causes segments marked as toll to be highly penalized.  This setting is off by default.
* Avoid freeways - Causes freeway segments to be penalized.
* '''Avoid freeways''' - Causes freeway segments to be penalized.  This setting is off by default.
* Dirt roads - Causes dirt road segments to be penalized.
* '''Dirt roads''' - Causes dirt road segments to be penalized.  This setting can be set to Allow, Don't Allow or Avoid long ones.  Don't Allow is the default setting.
* Vehicle type - Causes segments with appropriate vehicle restrictions to be penalized.
* '''Vehicle type''' - Causes segments with appropriate vehicle restrictions to be penalized.  This setting can be set to Private or Taxi.  Private is the default setting.


== Segment properties ==
== Segment properties ==
The properties of a road segment can effect routing:
The properties of a road segment effect routing:
* Road Type - as mentioned above the default speed data is based on the road type. The road type also effect the routing as follows:
:* Freeway - Avoided when "Avoid freeways" is selected in the client application.  When "Avoid freeways" is selected in the client application, a high penalty is applied for each freeway segment included in the route.
:* Dirt Road - Avoided based on the "Dirt roads" setting in the client. No penalty is applied when the setting is set to "Allow."  A penalty is applied


===Road Type===
As mentioned above the default speed data is based on the road type. The road type also affects routing as follows:
* '''Freeway''' - Avoided when "Avoid freeways" is selected in the client application.  When "Avoid freeways" is selected in the client application, a very high penalty is applied for each freeway segment included in the route.
* '''Dirt road / 4X4 Trail''' - Avoided based on the "Dirt roads" setting in the client application.  When the client application is set to "Allow," no penalty is applied. When the client application is set to "Don't Allow," a significant penalty is applied to transition from another road type to dirt road segments and to transition from dirt road segments to another road type.  When the client application is set to "Avoid long ones" the transition penalties are only applied to a series a segments over a set length on the order of 300m.
* '''Parking Lot Road''' - Waze is designed to avoid routing through a parking lot to reach another destination.  A significant penalty is applied each time the route transitions from a segment of parking lot road type to a segment of a different type.  This penalty is not applied to the first transition from a parking lot road if the route starts on a parking lot road.
* '''Private Road''' - Waze is designed to avoid routing through private roads.  A significant penalty is applied each time the route transitions from a segment of private road type to a segment of a different type in the same manner as with Parking Lot Roads. This penalty is not applied to the first transition from a private road if the route starts on a private road. These penalties apply to transitions from Parking Lot Roads to Private Roads and to transitions from Private Roads to Parking Lot Roads.  Detailed examples of using this penalty  is discussed in detail in [[Private Installations]].
* '''Non-Drivable Road Types''' - Waze should not route on the non-drivable road types of Walking Trail, Pedestrian Boardwalk, Stairway, Railroad and Runway/Taxiway.
====Pruning====
To find optimal routes over long distances for many users is processor resource intensive.  To reduce the processor time required so as to find a route in a reasonable amount of time the Waze routing algorithm may sacrifice finding the absolute optimal route in favor a finding a route that is likely to be optimal, or at least likely to be close to an optimal route in a much faster time using much fewer processor resources.  One method of doing this is to essentially penalize routes that include lower road types in the middle of long routes.  This essentially assumes that major highways and freeways will be mostly used for long routes and that highways will be mostly used routes of moderate length.  Street segments are penalized when more than about 10-15 km from the ends of the route.  Primary street and Dirt Road / 4X4 segments are penalized when more than about 15-30 km from the ends of the route.  Minor highway segments are penalized when more than about 100-160 km from the ends of the route. Major highway segments are penalized when more than about 200-320 km from the ends of the route.  Ramps and Freeways are not penalized. 


The following segment properties cause routing penalties:
The effect of pruning is that for longer routes Waze will favor higher road types for the middle portion longer routes.  Roads that are intended to provide routes between distant points should have a road type higher than residential roads that merely provide access to local destinations.


*[[Map Editing Quick-start Guide#Turn restrictions .28allowed turns.29|Turn restrictions]] and [[Scheduled restrictions#Turns|scheduled turn restrictions]] during the designated time for the designated vehicle type.
===Road Attributes===
*[[Creating and Editing street segments#Set Road Type.2C Direction.2C and Elevation|One-way roads]] against the designated direction of travel and [[Scheduled restrictions#Segments|scheduled segment restrictions]] for the designated time for the designated vehicle type.
* '''Toll Road''' - Routes over toll roads are penalized based on the navigation setting set in the client app. This allows the user to avoid roads marked with the toll road attribute. When "Avoid toll roads" is on, waze applies a significant penalty for each toll segment on the route.  When "Avoid toll roads" is off, waze applies a very low penalty for each toll segment on the route, to choose the non-toll route when other cost factors are essentially equal.
*[[Road types/USA#Non-drivable|Non-drivable road types]] including Walking Trail, Pedestrian Boardwalk, Stairway, Railroad and Runway/Taxiway.
 
*[[Best map editing practice#Toll roads|Toll roads]] for clients with avoid toll roads selected in the app.
===Restrictions===
*[[Road types/USA#Dirt|Dirt road/4X4 Trail]] for clients with "don't allow" selected in the app, or when segment length exceeds 300m with "avoid long ones" selected.
====Turn Restrictions====
*[[Road types/USA#Parking Lot Road|Parking lot roads]] and [[Road types/USA#Private Road|private roads]] when transitioning '''from''' one of these two road types '''to a different road type'''. Not when entering these two road types. This is discussed in detail in [[Private Installations]].
Turn restrictions are indicated by the [[Map_Editing_Quick-start_Guide#Junction_arrows|Junction Arrows]] at the ends of a road segment. If the Junction Arrow is green then waze routing from the segment to the next segment indicated by the arrow is allowed. If the Junction Arrow is red then waze should not route from the segment to the next segment indicated by the arrow. If there is a purple question mark at the end of the segment then the turn restrictions are soft and routes through from the segment to the next segment are penalized as described regarding [[Soft_and_hard_turns|Soft and Hard Turns]].
 
Waze should not route through a partial restrictions, indicated by a yellow Junction Arrow, during the time that the restriction is in effect.  Partial restrictions are discussed further below.
 
====Partial Restrictions====
[[Scheduled_restrictions|Partial Restrictions]] can be applied to turn restrictions and to segments. Restrictions can be set for specified days of the week, for specified times of the day, for specified date ranges and for specified vehicle types. Multiple restrictions may be set for each turn or segment.  Waze should not route though a partial turn restriction during the designated time for the designated vehicle type.  Waze should not use a partially restricted segment for routing during the designated time for the designated vehicle type.
 
From the routing point of view, the relevant time is the time that routing algorithm calculates that the turn will be made or the segment will be entered.  Waze will route through a turn or segment with a partial restriction that expires while in route if Waze calculates that the route will reach the restriction after the restriction expires. Waze routing will not route through a turn or segment with a partial restriction that is not in effect when the route begins but the partial restriction begins before Waze calculates the route will reach the partially restricted turn or segment.
 
From the routing point of view, the relevant vehicle is the vehicle that is set in the client application.  Thus, restrictions for "private vehicles" will be effective for the standard Waze user as "private" is the default vehicle type in the client.    
 
===Road Direction===
* '''One Way''' - Waze should not route the wrong way on a one way segment.
* '''Unknown''' - Waze favors roads that have been reviewed and corrected by editors. This is done by applying a penalty for each unknown direction segment on a route.
 
===Road Closures===
Waze provides for various methods for entering [[Real_time_closures|real time road closures]].  Road segments can be closed by direction.  For routine routes, Waze should not use a segment for routing in the direction of the closure.  For long routes, Waze may not account for closures that are far away.


== Road configurations ==
== Road configurations ==
Other routing penalties are based on road configurations.
Waze realizes that some routes are undesirable even if faster or slower.  To avoid such routes waze penalizes several road configurations.


*[[File:MinSegLengthUturn2.png|border|390px|right|Segment too short to allow two left turns]] Waze will penalize a route (which forms a U-turn) with two left turns in less than {{:Routing penalties/U-turn minimum}} in [[right-hand traffic]] jurisdictions or with two right turns in less than {{:Routing penalties/U-turn minimum}} in [[left-hand traffic]] jurisdictions. ''The specific details on configuration, and criteria for this penalty are documented in the [[Junction_Style_Guide/Intersections#Avoiding_U_turns|Intersections page of the Junction Style Guide]].''
* '''Multiple Segment U-turns''' - [[File:MinSegLengthUturn2.png|border|390px|right|Segment too short to allow two left turns]] Waze will penalize a route (which forms a U-turn) with two left turns in less than {{:Routing penalties/U-turn minimum}} in [[right-hand traffic]] jurisdictions or with two right turns in less than {{:Routing penalties/U-turn minimum}} in [[left-hand traffic]] jurisdictions. ''The specific details on configuration, and criteria for this penalty are documented in the [[Junction_Style_Guide/Intersections#Avoiding_U_turns|Intersections page of the Junction Style Guide]].''
{{clear}}
{{clear}}


*[[File:OffOnFreeway.png|border|390px|right|Ramps should prevent detour]] Waze penalizes some routes that leave a highway or freeway only to immediately return to the same freeway or highway. This is covered in more detail in [[Detour Prevention Mechanisms]].
* '''Highway Off/On Routing''' - [[File:OffOnFreeway.png|border|390px|right|Ramps should prevent detour]] Waze penalizes some routes that leave a highway or freeway only to immediately return to the same freeway or highway. This is covered in more detail in [[Detour Prevention Mechanisms]].
{{clear}}
{{clear}}


* When a new node is created along a current or new segment, the node will default to a 5 second penalty through that node until someone drives across it and the [[map tiles]] are rebuilt with the new data. After that point the 5 second penalty is removed and the measured transit time through that node is used.
* '''Small Detours''' - Waze avoids routes that make a right turn and a U-turn or continue straight, make a U-turn and turn right to avoid a left turn. Waze applies a small penalty to routes that pass through the same intersection more than once as is also mentioned in [[Detour Prevention Mechanisms]].
 
== Preventing routes with certainty ==
If a segment should never be used for routing, it should not be connected to the road network. For example, Waze may route over walking trail or stairway segments connected to the road network if conditions are such that the penalized route is still found to be the best route. This is common where there are no alternate routes, such as when Waze finds that the origin or destination is on the penalized segment.


[[Category:Waze operations]]
[[Category:Waze operations]]

Latest revision as of 00:07, 19 April 2016

This new page is currently undergoing modifications. The information presented should be considered a draft, not yet ready for use. This content is open to changes from anyone during construction. If you would like to make changes or have questions, please post a message in this forum.

The primary purpose of the Waze map is to provide a framework to present a Wazer an optimum route from one place to another place. Various street segment properties and configurations are weighted differently by the routing server. When troubleshooting routing problems it is important to understand how various segment properties configurable by a map editor effect routes provided to Wazers.

Background

Waze routing essentially calculates the least cost route between the origin and the destination. When the navigation type is set to fastest the cost is primarily based on the time the route is calculated to take. When the navigation type is set to shortest the cost is primarily based on the distance of the route. The cost is based on the properties of the road segments that make up the route and the speed data collected for each road segment. There are other considerations that may cause the cost to deviate from simply the fastest or shortest route. These considerations are typically applied to the routes in the form of penalties that increase the cost of route. For example, if avoid toll road is set in the client, then the cost of road segments marked as toll is greatly increased. Thus a segment in a route that is penalized causes the cost of the route to be higher. In this manner Waze avoids penalized routes.

Speed and Distance Data

Distance Data

Distance data is calculated based on the geometry of a segment. Thus the placement of the junction nodes at segment ends and the placement of geometry nodes within a segment change the length of a segment.

Traffic Data

Waze retains speed data for each road segment as discussed regarding traffic data. Map editors do not control the speed data. With the exception of the default speed, the speed data is based on actual drives of Wazers. It is important for segments to be properly placed on the map in relation to the drives (as shown in the GPS layer) so that waze assigns the wazers drive speeds to the proper segment.

Client Navigation Settings

There are several options in the client application that effect how the cost of the route is calculated.

  • Navigation type - Fastest causes the route cost to be based on speed data. Shortest causes the route cost to based on distance. Fastest is the default setting.
  • Avoid toll road - Causes segments marked as toll to be highly penalized. This setting is off by default.
  • Avoid freeways - Causes freeway segments to be penalized. This setting is off by default.
  • Dirt roads - Causes dirt road segments to be penalized. This setting can be set to Allow, Don't Allow or Avoid long ones. Don't Allow is the default setting.
  • Vehicle type - Causes segments with appropriate vehicle restrictions to be penalized. This setting can be set to Private or Taxi. Private is the default setting.

Segment properties

The properties of a road segment effect routing:

Road Type

As mentioned above the default speed data is based on the road type. The road type also affects routing as follows:

  • Freeway - Avoided when "Avoid freeways" is selected in the client application. When "Avoid freeways" is selected in the client application, a very high penalty is applied for each freeway segment included in the route.
  • Dirt road / 4X4 Trail - Avoided based on the "Dirt roads" setting in the client application. When the client application is set to "Allow," no penalty is applied. When the client application is set to "Don't Allow," a significant penalty is applied to transition from another road type to dirt road segments and to transition from dirt road segments to another road type. When the client application is set to "Avoid long ones" the transition penalties are only applied to a series a segments over a set length on the order of 300m.
  • Parking Lot Road - Waze is designed to avoid routing through a parking lot to reach another destination. A significant penalty is applied each time the route transitions from a segment of parking lot road type to a segment of a different type. This penalty is not applied to the first transition from a parking lot road if the route starts on a parking lot road.
  • Private Road - Waze is designed to avoid routing through private roads. A significant penalty is applied each time the route transitions from a segment of private road type to a segment of a different type in the same manner as with Parking Lot Roads. This penalty is not applied to the first transition from a private road if the route starts on a private road. These penalties apply to transitions from Parking Lot Roads to Private Roads and to transitions from Private Roads to Parking Lot Roads. Detailed examples of using this penalty is discussed in detail in Private Installations.
  • Non-Drivable Road Types - Waze should not route on the non-drivable road types of Walking Trail, Pedestrian Boardwalk, Stairway, Railroad and Runway/Taxiway.

Pruning

To find optimal routes over long distances for many users is processor resource intensive. To reduce the processor time required so as to find a route in a reasonable amount of time the Waze routing algorithm may sacrifice finding the absolute optimal route in favor a finding a route that is likely to be optimal, or at least likely to be close to an optimal route in a much faster time using much fewer processor resources. One method of doing this is to essentially penalize routes that include lower road types in the middle of long routes. This essentially assumes that major highways and freeways will be mostly used for long routes and that highways will be mostly used routes of moderate length. Street segments are penalized when more than about 10-15 km from the ends of the route. Primary street and Dirt Road / 4X4 segments are penalized when more than about 15-30 km from the ends of the route. Minor highway segments are penalized when more than about 100-160 km from the ends of the route. Major highway segments are penalized when more than about 200-320 km from the ends of the route. Ramps and Freeways are not penalized.

The effect of pruning is that for longer routes Waze will favor higher road types for the middle portion longer routes. Roads that are intended to provide routes between distant points should have a road type higher than residential roads that merely provide access to local destinations.

Road Attributes

  • Toll Road - Routes over toll roads are penalized based on the navigation setting set in the client app. This allows the user to avoid roads marked with the toll road attribute. When "Avoid toll roads" is on, waze applies a significant penalty for each toll segment on the route. When "Avoid toll roads" is off, waze applies a very low penalty for each toll segment on the route, to choose the non-toll route when other cost factors are essentially equal.

Restrictions

Turn Restrictions

Turn restrictions are indicated by the Junction Arrows at the ends of a road segment. If the Junction Arrow is green then waze routing from the segment to the next segment indicated by the arrow is allowed. If the Junction Arrow is red then waze should not route from the segment to the next segment indicated by the arrow. If there is a purple question mark at the end of the segment then the turn restrictions are soft and routes through from the segment to the next segment are penalized as described regarding Soft and Hard Turns.

Waze should not route through a partial restrictions, indicated by a yellow Junction Arrow, during the time that the restriction is in effect. Partial restrictions are discussed further below.

Partial Restrictions

Partial Restrictions can be applied to turn restrictions and to segments. Restrictions can be set for specified days of the week, for specified times of the day, for specified date ranges and for specified vehicle types. Multiple restrictions may be set for each turn or segment. Waze should not route though a partial turn restriction during the designated time for the designated vehicle type. Waze should not use a partially restricted segment for routing during the designated time for the designated vehicle type.

From the routing point of view, the relevant time is the time that routing algorithm calculates that the turn will be made or the segment will be entered. Waze will route through a turn or segment with a partial restriction that expires while in route if Waze calculates that the route will reach the restriction after the restriction expires. Waze routing will not route through a turn or segment with a partial restriction that is not in effect when the route begins but the partial restriction begins before Waze calculates the route will reach the partially restricted turn or segment.

From the routing point of view, the relevant vehicle is the vehicle that is set in the client application. Thus, restrictions for "private vehicles" will be effective for the standard Waze user as "private" is the default vehicle type in the client.

Road Direction

  • One Way - Waze should not route the wrong way on a one way segment.
  • Unknown - Waze favors roads that have been reviewed and corrected by editors. This is done by applying a penalty for each unknown direction segment on a route.

Road Closures

Waze provides for various methods for entering real time road closures. Road segments can be closed by direction. For routine routes, Waze should not use a segment for routing in the direction of the closure. For long routes, Waze may not account for closures that are far away.

Road configurations

Waze realizes that some routes are undesirable even if faster or slower. To avoid such routes waze penalizes several road configurations.

  • Highway Off/On Routing -
    Ramps should prevent detour
    Ramps should prevent detour
    Waze penalizes some routes that leave a highway or freeway only to immediately return to the same freeway or highway. This is covered in more detail in Detour Prevention Mechanisms.
  • Small Detours - Waze avoids routes that make a right turn and a U-turn or continue straight, make a U-turn and turn right to avoid a left turn. Waze applies a small penalty to routes that pass through the same intersection more than once as is also mentioned in Detour Prevention Mechanisms.