User:CBenson/Routing penalties View history

(Up to questions about dirt road segments.)
No edit summary
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 basically calculates the least cost routes 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 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 44: Line 44:
==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 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 can 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:
===Turn Restrictions===
:* 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.
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 waze routing from the segment to the next segment indicated by the arrow is allowed.  If the Junction Arrow is red 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 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]].
:* 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  
 
and [[Scheduled restrictions#Turns|scheduled turn restrictions]] during the designated time for the designated vehicle type.
 
===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 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 private road segments and to transition from private 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 or 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 to a route that transitions from a parking lot road to a road of a different type.  This penalty is not applied to first transition from a parking lot road if the route starts on a parking lot road.  The route is considered to start on the road type of the first segment after the route passes a junction node.
* Private Road - Waze is designed to avoid routing through private roads. A significant penalty is applied to a route that transitions from a private road to a road of a different type in the same manner as with Parking Lot Roads. This penalty is not applied to first transition from a parking lot road if the route starts on a parking lot road.  The route is considered to start on the road type of the first segment after the route passes a junction node.  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 distance for many users is processor resource intensive.  To reduce the processor 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 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 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.
 
 
 
 
 




Line 64: Line 87:
*[[Best map editing practice#Toll roads|Toll roads]] for clients with avoid toll roads selected in the app.
*[[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 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 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]].
*[[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.  


== Road configurations ==
== Road configurations ==

Revision as of 20:23, 17 March 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 basically calculates the least cost routes 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 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.

Speed 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.

  • 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 used. This 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

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 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 can effect routing:

Turn Restrictions

Turn restrictions are indicated by the Junction Arrows at the ends of a road segment. If the Junction Arrow is green waze routing from the segment to the next segment indicated by the arrow is allowed. If the Junction Arrow is red 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 the turn restrictions are soft and routes through from the segment to the next segment are penalized as described regarding Soft and Hard Turns.

and scheduled turn restrictions during the designated time for the designated vehicle type.

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 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 private road segments and to transition from private 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 or 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 to a route that transitions from a parking lot road to a road of a different type. This penalty is not applied to first transition from a parking lot road if the route starts on a parking lot road. The route is considered to start on the road type of the first segment after the route passes a junction node.
  • Private Road - Waze is designed to avoid routing through private roads. A significant penalty is applied to a route that transitions from a private road to a road of a different type in the same manner as with Parking Lot Roads. This penalty is not applied to first transition from a parking lot road if the route starts on a parking lot road. The route is considered to start on the road type of the first segment after the route passes a junction node. 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 distance for many users is processor resource intensive. To reduce the processor 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 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 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.





The following segment properties cause routing penalties:

Road configurations

Other routing penalties are based on road configurations.

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

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.