Changes

From Wazeopedia

Routing server

1,772 bytes removed, 1 month ago
m
Pruning: wordsmithery
When using the Waze application, Waze servers use routing algorithms to determine the best path for a given route at that particular time. The specific details of the routing algorithms used by the Waze server are not publicly disclosed and ; the following is based on observation, speculation, and some information revealed by Waze staff. It is assumed that the The operation of the routing server is considered to be proprietary and a competitive advantage to Waze. It is also assumed that it The information on this page is subject to change, and that any information that has been revealed might may be incomplete or out of date.
== Client -based routing ==Calculating an optimal route is a difficult task. While the client device app has a routing algorithm included, this is not used unless there is no connection to the Waze server. Client-based routing only uses cached map tiles. It does not use real-time traffic data, reports or closures, because this information is not accessible. Therefore, it does not provide an ETA.
== Routing requests ==
When you request a user requests a route calculationwith a network connection, the request is sent to the Waze server. That route is then transmitted back to your the client device and displayed.
The requests for routing vary according to the settings you have chosen for the user's account on your the client device. Under Navigation you one can choose:* Whether to allow or avoid [[toll roads]]* Which, if any, [[Carpool, HOV, Transit lanes|toll and HOV ]] passes you choose to use on this drive apply (some segments are permitted only to those who hold the proper pass)* Whether to avoid ferries{{Ferry|Ferries}}* Whether to avoid freeways{{Freeway|Freeways}}
* Whether to allow, never allow, or avoid long unpaved roads
* Whether to avoid / not avoid [[Difficult turn|difficult intersections ]] (turns marked "difficult"through nodes or junction boxes).* Vehicle type** {{Passageway}} has a type - Some segment types (passageway / narrow alley) and segment specific [[Routing penalty|penalty]].** [[Partial restrictions|Segment restrictions ]] allow or prevent travel by certain vehicle types.
== Missing roads and incorrect junction connections Different route lengths ==Waze tries to find the best route between you and your destination based on your navigation settings. Obviously it can only route based on roads that it knows about, so your route will not be optimal if a better route does not have all the roads with correct connections in the [[Waze Map Editor]]. Also if [[Segment length|segments are less than {{:Segment length/Minimum}}]] they can cause routing issues.
== Real-time current road speeds = Pruning ===The It is known that the Waze routing server uses realengine can't calculate every possible route for long-time distance routes, so it takes shortcuts by removing lower road speeds (types from recent Waze app users if available) and combines consideration in the historical speed middle of longer routes. This effect is commonly called '''route pruning''' and can potentially result in the segment broken down into 10-15 minute chunksroute changing dramatically when lengthened slightly. The time to pass through At distances farther than a certain threshold value from the origin or destination of a segment is tracked separately for each route out of , roads lower than a segmentcertain type tend not to be considered. For example if a segment ends Pruning thresholds with a left confidential, variable, increasing values exist for {{Street}}, {{Primary Street}} and right turn (no straight let's say){{Minor Highway}}, then the routing engine isolates the time through the segment to turn left and the time through the segment to turn rightrespectively. This detailed speed information There is proprietary & evidence that {{Major Highway}} is part of the data Waze sells/plans to sell never pruned. {{Freeway}} and {{Ramp}} are never pruned. The pruning mechanism uniquely accounts for [[Creating and won't editing road segments#Special properties|routing road type]], so a Primary Street with routing road type +1 would be displayed through pruned at the editorsame threshold as a Minor Highway.
It is known that === XL routes ===Generation of routes longer than 1000 miles in Waze uses realused to be impossible, but in 2018 a new mechanism for extra-time reports of current road speeds by preference over historical average road speedslong (XL) routes was put into place. Waze also uses traffic congestion reports This pieces together multiple long routes to reroute around slow trafficgenerate one extra-long route. <!-- Early versions To save time and avoid routing timeouts, instructions and geometry details are omitted in the middle of the client would also report when traffic speeds were good - this was removed due to map clutterroute during initial calculation, but they are produced and listed later as the user drives along the route. But Dependent upon multiple factors such as server load and road types, transcontinental routes can be calculated in Waze will still be receiving with this informationmechanism. -->It is assumed also evident that , since XL routes are combinations of shorter routes, the speed of any Wazer ahead of you on a stretch of aforementioned pruning behaves differently for them, so that lower road will be types may appear in the speed used when your route is calculatedmiddle of extra-long routes.
As == Real-time current road speeds ==The routing server uses real-time road speeds (from recent Waze app users if available) and combines the number and density average, historical speed of Wazers grows, this realthe segment broken down into 10-15 minute chunks. The time data takes on to pass through a greater importance. This emphasis segment is partly tracked separately for each route out of a reflection of Waze's original goal to create optimal commutessegment. As Waze has grown to be used as For example if a segment ends with only a more general purpose GPS navigation device over roads less traveledleft and right turn, then the historical average road speeds becomes more important. Since Waze uses routing engine isolates the time you expect to be at a road through the segment to calculate turn left and the time through the expected speed on that segment, it cannot use real time data when your trip time moves into a future time slotto turn right. So trips of more than 30 minutes (This detailed speed information is proprietary and on average more than 15 minutes) will include future time slots where current traffic data is not available when initially calculated. When you enter a new time slot, any real-time traffic data that is available causes your client to recalculate your ETA and reroute you at that pointdisplayed in the Waze Map Editor.
== Fastest routing ==It is known that Waze knows the prefers to use real-time reports of current road speeds over historical average speed of every confirmed road between you and your destinationspeeds. The Waze server can calculate which list also uses traffic congestion reports to reroute around slow traffic. <!-- Early versions of roads the client would also report when traffic speeds were good - this was removed due to take map clutter. But Waze will still be receiving this information. -->The speeds of recent Wazers traveling on a road will be factored into the route given to minimize subsequent Wazers traveling on the total travel timesame road.
While every request is processed in As the number and density of Wazers grows, this real-time, by observation it appears that Waze [[glossary|caches]] some requested routes or major points. This means if it already knows the best route from B to C, and you ask for data takes on a route from A to C, it might just calculate the best route from A to B, once it checks that there isn't a better route bypassing B altogethergreater importance. This does mean that when there emphasis is partly a [[Timeline reflection of updating process|Live map update]] some routes might be less than Waze's original goal to create optimal for up commutes. As Waze has grown to be used as a day as routes are cached and recalculatedmore general-purpose GPS navigation device over roads less traveled, the historical average road speeds becomes more important.
While Since Waze uses the future expected time of arrival onto a complex calculationroad segment in order to calculate the expected speed on that segment, calculating it cannot use real-time data too far in the future. So longer trips (on the optimal route order of 30 minutes or more) will include future time slots where current traffic data is possiblenot available when initially calculated. The complexity arises over As the "average speed" of trip progresses, any real-time traffic data that is available causes the client to recalculate the route and the roadsETA.
== Changes in route due to different origin Average road speeds ==Consider calculating a If the average or historical road speed is not correct, then the route from A to Zmay not be optimal. The suggested route might be A However, deletion of segments to B to C to D to Zreset average road speed is not recommended. Then calculate Waze uses the route data from B Wazers traveling through the segments to Zupdate the average speed, and oftentimes an anomalous historical road speed is automatically corrected with further data collection. You might get If Waze appears to disfavor the use of certain segments along a suggested route , a number of B to C to E to Z. At first glance, this suggests one route is not optimal because the [[Glossary|origin]] changedother reasons can cause such a situation.
We can guess === Time-of-day variations ===Consider a road that most Wazers drive at what might be happening5 PM when the average speed is 12 MPH. There might be a problem associated with At 10 AM when the road is clear and the possible caching of routes. Or there might be a "timing window" effect. The different arrival time at C might change average speed is 60 MPH, it is the best route road to Ztake. Or there might be a fine tuning effect in If Waze only has historical speed data from 5 PM, it will assume that the speed of the routeroad is 12 MPH all day, perhaps and it may not recommend this road. As more people drive this road closer to avoid too many turns. So by dropping the segment A to Btime of day when a given route is requested, Waze will get a better guess for the segments C to E to Z no longer exceed some thresholdaverage speed at that time.
This effect can be observed while driving=== Shrinking window ===If there are enough recorded speeds on a road, then Waze uses a shrinking window of speeds to better estimate the average speed at the current time. Waze uses the speed of each road segment (in both directions) in intervals as small as 30 minutes. If you recalculate So a route two-way road might have up to 96 average road speeds in a destination while driving along day. It can be assumed that when there are insufficient records for an already calculated route individual time slot, a wider time range is used (up to a full day). As the road is driven more at different times, the time slot shrinks. Additional information is used based on the day of the week. There is no evidence that same destinationWaze records speeds for larger date ranges such as months or seasons; however, the route can it will update its average speeds relatively quickly when seasonal traffic patterns change.
Waze sometimes offers a new route to bypass heavy traffic which raises uses the average road segment speed for the time slot that applies at the question as to time when and how Waze considers rerouting. == Changes in routes due a user is expected to different route lengths == In addition, it is known arrive at that the Waze routing engine can't calculate every possible route for long distance routes, so it takes shortcuts for longer routes, potentially resulting in the route changing dramatically when lengthened slightlyroad segment. According to Waze support ({{as Because of|July 2011|lc=y}})this time window, the section Waze suggests different routes at different times of a route more than 10 km from each endpoint is heavily weighted towards non-streets (iday.e. "Primary Streets" or the various Highway types). It This is believed that Waze servers simply ignore streets outside of dependent on how many times are recorded on the 10 km radius from roads along the endpoints when doing its calculations to speed up the processroute== Problems with average road speeds ==If they're all recorded at about the average road speed is not correctsame time of day, then the route will time window does not be optimal. However, it is never recommended to delete segments in order to reset the average road speed for that segment. Waze uses the data from Wazers traveling through the segments to update the average speedhelp. If you suspect Waze is not using certain segments along a route1, there are a number of other reasons that can cause such a situation. Don't assume deleting the segment is the place to start. The following 000 times are reasons why the routing engine might not use the average road speed. === Time of day variations ===Consider a road that most Wazers drive recorded at 5pm when the average speed is 12 mph. You choose your route at 10am when the road is clear about 5 PM and the average speed is 60mph. It is the best road to take, but Waze chooses a different route because it has no information about the speed 2 times are recorded at 10am and assumes the speed is 12mph all day. You can10 AM, of course, drive the road yourself, and Waze eventually learns the speed for that time. We do not know how long Waze holds the older data in computing then the 10 AM average speed. However, if Waze does discard old time information, you might not accumulate new time faster than it is discarded. It still is also possible that your based mostly on times are being ignored as being abnormal. More Waze users would help fix thisfrom around 5 PM.
=== Turn delays ===
On a segment of a road, your a user's average speed can be very different depending on what you do is done at the end of the segment. Traffic going straight through a traffic light might go very fast while traffic turning left might wait a very long time. A freeway exit lane might go fast while traffic continuing hits congestion.
[[Image:SegmentTraffic1.png|right|350px]]Waze has the ability to separately track the average speed of traffic that passes through a segment, but exits to different segments. The routing engine takes this into account. In the diagram, multiple times are tracked for traffic flowing through Seg4 based on the segments to which it exits. There are then two average drive times for:
For this reason it is important to keep long segment lengths before junctions as traffic congestion at the junction might affect exits differently.
To understand this problem better, consider if we add a short Seg8 between Seg7 and Jnct4. Let's say the traffic exiting Seg10 backs up all the way to Seg7 (easy enough, since Seg8 is short). Because Seg7 only has a single exiting segment (Seg8), the routing server is only able to collect a single average speed &mdash; it can no longer distinguish traffic by where it is going ''after'' Seg8. Now the through traffic going to Seg9 appears to Waze to slow down through Seg7, even though it doesn't in reality. At a minimum this causes an incorrect ETA for routing, and it might actually cause traffic to be rerouted unnecessarily, and less optimally, through another route. Hence, if there is a chance that traffic can go in different directions at a junction and that junction can experience different amounts of congestion, you should keep the segment before that the junction should be kept long, or a [[junction box]] may be used. === Outdated and abnormal road speeds ===Average speeds can change over time, and recorded times can be abnormal or wrong—and can stay wrong for a very long time. This may be due to users recording inaccurate speed data by doing things like walking, biking or sitting in their driveways with Waze open. Also, if [[Segment length|segments are less than {{:Segment length/Minimum}}]] they may not be longenough to record accurate transition times. There is some evidence that abnormal road speeds and old road speeds are discarded, or at least not used in calculating the average speeds of roads.
Note this data == Recalculation ==When Waze receives notification of traffic conditions, it uses the actual speed of roads on your route, rather than the average speed. This is based on [[Real time closures|real-time closures]] and automatic traffic condition reports - light, moderate, heavy traffic or complete standstill. Manual reports of traffic jams and accidents are for display only and do not presented change routing. ETA is updated in response to users through a user's progress on the route and in response to these real-time traffic conditions. If real-time traffic conditions make the given route significantly worse than alternatives, Waze Map Editor, but is only visible to may provide an automatic recalculation. The benefits of this are balanced against the routing serverperceived hassle of changing one's route.
== Traffic lights and stop signs ==
Waze does not record the location of traffic lights. While some GPS navigation offers guidance like "turn right at the next traffic light" the information is frequently incomplete, incorrect or outdated. The consensus view is that Waze should not record the location of traffic lights.
Waze does take traffic lights and stop signs into account by noting the effect they have on traffic speed. Consider a traffic light with long waiting times. The road segment leading to that traffic light will have a low average speed. If the average speed (based on the average waiting time) becomes low enough, a longer route that avoids the light becomes the preferred route. This has been observed in practice and is an example of ''emergent behaviourbehavior''. Waze isn't programmed to avoid traffic lights but it does avoid slow roads; if the traffic lights make the road slow then Waze avoids them.
Some drivers regularly take longer routes — even winding through side streets — to avoid any stops or traffic lights. Waze has been known to suggest this, and also known to revert to waiting at lights when better average speed information is collected from the side streets. But note that this can be less than optimal due to the turn delays discussed above.
 
== Outdated and abnormal road speeds ==
Road conditions change, construction work comes and goes, and average road speeds can change dramatically. One day you might be stuck behind a truck, and another day you might be crawling along the roads at 2 a.m. transporting your pet goldfish. Or your GPS might have a glitch and show you travelling at 1,000 mph.
 
In short, average speeds can change over time, and recorded times can be abnormal or just plain wrong—and can stay wrong for a very long time.
 
We can assume Waze is aware of this. There is some evidence that abnormal road speeds and old road speeds are discarded, or at least not used in calculating the average speeds of roads.
 
== Average road speed "shrinking window" ==
If there are enough recorded speeds on a road, then Waze uses a shrinking window of speeds to better estimate the average speed at the time you are travelling on it. Waze uses the speed of each road segment (in both directions) in intervals as small as 30 minutes. So a two-way road might have up to 96 average road speeds. We can assume that when there are insufficient records for an individual time slot, a wider time range is used (up to a full day). As the road is driven more, the time slot shrinks down to 30 minutes.
 
We can speculate that there is additional information used that is based upon the day of the week. There is some observational evidence that a road that is busy on weekdays and not used for routing is chosen as the optimal route on weekends.
 
At some point, Waze also needs to consider the months of the year as seasonal variations can affect the speed of the roads.
 
Waze uses the average road segment speed for the time slot that applies at the time you are expected to arrive at that road segment.
 
Because of this "time window", Waze suggests different routes at different times of day. This is dependent on how many times are recorded on the roads along the route. If they're all recorded at about the same time of day, then the time window does not help. If 1,000 times are recorded at about 5 p.m. and 2 times are recorded at 10 a.m., then your 10 a.m. average speed still is based mostly on times from around 5 p.m.
 
== Routing algorithm refinements ==
=== Routing options ===
It's easy to see how routing options can be implemented. For example, to minimize turns we can add a time [[Routing_penalties|penalty]] for fastest routing or a distance penalty for shortest routing, when calculating the fastest or shortest route.
 
=== Junction penalties ===
For newly created roads, currently Waze applies a five-second time [[Routing_penalties|penalty]] for each junction through which a route passes. Once vehicles drive over that road and generate Waze traffic data, the penalty for these junctions is dropped.
== What to do if you think the generated route is wrong ==
Firstly, use # Use the option to generate alternative routes. This might give you some clues as to why Waze is offering that route. Secondly, if # If you think there is a better route, check in WME the [[Waze Map Editor]] that the all of its roads are connected, and all connected along legal turns are allowed.# Communicate the routeproblem.Possible means of communication include:#* Report a [[map issue]] in the app and respond to comments on it.Thirdly, post #* Post a message detailing the problem route - (origin, destination and a WME permalink ) to the [http://www.waze.com/forum/viewforum.php?f=6&sid=2872533f5796ac39dc6747511398e907 Navigation forum]. Other eyes will check it, and you might indeed find a flaw in the Waze routing algorithm. Fixing it might make it better for everyoneor your state's local forum== Change of routing ==When #* Join your local community's Waze receives notification of traffic conditions it uses the actual speed of roads on Discord server (accessible from your route, rather than the average speedstate wiki page). This is based only on will usually produce the automatic traffic condition reports - light, moderate, heavy traffic or complete standstill. Manual reports of traffic jams and accidents are for your information only and do not change routing. It might be that even with the traffic reports, there is no better route and Waze cannot offer you onefastest response from local editors.
== You are the driver ==
Waze can never see that the traffic light is green going straight, or know that today is a public holiday. It can offer you guidance as to what is the best route under average conditions. But you are the driver and you are in the best position to make the decision for today under today's conditions.
If everyone followed Waze directions and never drove on a new route, Waze might never learn that route is better. When Waze is recording your travels, every trip helps make Waze better for everyone. That includes when you think you know better. Sometimes you will be right. And sometimes you will be wrong. But it is better to find out you are wrong so you can choose the better route. And when you are right, all Waze users benefit by the sharing of your knowledge.
[[Category:Waze operations]]
1,270
edits