User:CBenson/Routing penalties View history

(Prior Routing penalties page)
 
m (Removed global references)
 
(17 intermediate revisions by 3 users not shown)
Line 1: Line 1:
<!--if the section parameter is defined, do not place the visible banner, only as the code block for the top of a section-->{{GlobalMark/visible}}
<!--
#####-----#####-----#####-----#####-----#####-----#####-----#####-----#####-----
####    This page has been curated  ####
####    to be included in the new    ####
####    Wazeopedia - GLOBAL Wiki.  ####
####    Please do not make any      ####
####    edits on this page without  ####
####    PRIOR CONSENSUS in the Wiki  ####
####    Updates and Discussions      ####
####    forum thread for this page.  ####
####    If a specific forum thread  ####
####    for this page doesn't exist  ####
####    please start one.            ####
####        www.waze.com/forum/      ####
####        viewforum.php?f=276      ####
#####-----#####-----#####-----#####-----#####-----#####-----#####-----#####-->
{{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 25: Line 7:
| talk        = no
| talk        = no
}}
}}
The Waze routing servers use a system that associates restricted turns and directions as a penalty amount. When it then compares the different routes, it looks at the cumulative penalty points and the lowest amount of penalty points is the better route.
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 ==
== Background ==
Waze routing is intended to work in two very different environments at the same time. One uses map information that has been carefully corrected by a group of dedicated editors. The other uses map information that was imported from an external database with no editor corrections. To support both systems the Waze development team decided to use a penalty-based routing system. That means the various segment and junction node properties that restrict certain directions between segments are applied as a routing penalty. For example, a [[Map_Editing_Quick-start_Guide#Turn_restrictions_.28allowed_turns.29|turn restriction]] indicated by the red turn restriction arrow does not prohibit the turn, rather the turn restriction applies a high penalty to any route through the turn. This penalty-based routing system permits routing to a point on street where all turns onto the street are incorrectly set as restricted. This provides for some routing in areas that have not been edited carefully or correctly.
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 [[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.
 
==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 ==
== 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 [[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.


The following segment properties cause routing penalties:
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.   


*[[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 Direction===
*[[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.
* '''One Way''' - Waze should not route the wrong way on a one way segment.
*[[Road types/USA#Non-drivable|Non-drivable road types]] including Walking Trail, Pedestrian Boardwalk, Stairway, Railroad and Runway/Taxiway.
* '''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.
*[[Best map editing practice#Toll roads|Toll roads]] for clients with avoid toll roads selected in the app.
 
*[[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.
===Road Closures===
*[[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]].
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 07:08, 4 May 2017

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.

  • Multiple Segment U-turns -
    Segment too short to allow two left turns
    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 52.49 ft (16 m) in right-hand traffic jurisdictions or with two right turns in less than 52.49 ft (16 m) in left-hand traffic jurisdictions. The specific details on configuration, and criteria for this penalty are documented in the Intersections page of the Junction Style Guide.
  • 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.