Changes

From Wazeopedia

Routing server

2,833 bytes removed, 2 months ago
m
Pruning: wordsmithery
==Client based When using the Waze application, Waze servers use routing==Calculating an optimal 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; the following is a difficult taskbased on observation, speculation, and some information revealed by Waze staff. While The operation of the [[client device]] app has routing server is considered to be proprietary and a routing algorithm included, competitive advantage to Waze. The information on this page is not used unless there is no connection subject to the Waze serverchange, and any information that has been revealed may be incomplete or out of date.
==SpeculationClient-based routing ==The Calculating an optimal route is a difficult task. While the client device app has a routing algorithm included, this is not used by unless there is no connection to the Waze server is . Client-based routing only uses cached map tiles. It does not publicly disclosed and the following is based on observationuse real-time traffic data, speculationreports or closures, and some because this information revealed by Waze staff. We can assume that the operation of the routing server is considered to be proprietary and a competitive advantage to Wazenot accessible. We can also assume that Therefore, it is subject to change, and that any information that has been revealed may be incomplete or out of datedoes not provide an ETA.
What has been confirmed is the Waze Map Editor (WME) displays the overall average speed for == Routing requests ==When a segment for each direction of travel through the segment. Also the routing engine uses real-time speeds (from recent Waze app users in front of you when available) and combines the historical speed of the segment broken down into 10-15 minute chunks. Also the time to pass through user requests a segment is tracked separately for each route out of a segment. For example if a segment ends calculation with a left and right turn (no straight let's say)network connection, then the routing engine isolates the time through the segment request is sent to turn left and the time through the segment to turn rightWaze server. This detailed speed information That route is proprietary & is part of then transmitted back to the data Waze sells/plans to sell client device and won't be displayed through the editor.
==Routing The requests==for routing vary according to the settings chosen for the user's account on the client device. Under Navigation one can choose:When you request a route calculation* Whether to allow or avoid [[toll roads]]* Which, if any, [[Carpool, HOV, Transit lanes|toll and HOV]] passes to apply (some segments are permitted only to those who hold the request is sent proper pass)* Whether to the Waze serveravoid {{Ferry|Ferries}}* Whether to avoid {{Freeway|Freeways}}* Whether to allow, never allow, or avoid long unpaved roads* Whether to avoid [[Difficult turn|difficult intersections]] (turns marked "difficult" through nodes or junction boxes).* Vehicle type** {{Passageway}} has a type-specific [[Routing penalty|penalty]]. That route is then transmitted back to your ** [[client devicePartial restrictions|Segment restrictions]] and displayedallow or prevent travel by certain vehicle types.
The requests for routing vary according to the settings you have chosen on your [[client device]]. Under Navigation you can choose:* Fastest or shortest == Different route* Whether to allow or [[avoid toll roads]]* Whether to allow dirt roads, never allow dirt roads, or to avoid long dirt roads* Whether to [[avoid highways|avoid major highways]]lengths ==
The shortest === Pruning ===It is known that the Waze routing engine can't calculate every possible route refers to physical for long-distanceroutes, so it takes shortcuts by removing lower road types from consideration in the middle of longer routes. Most people will usually prefer This effect is commonly called '''route pruning''' and can potentially result in the Fastest route option; 100km of freeway is better changing dramatically when lengthened slightly. At distances farther than 90km a certain threshold value from the origin or destination of country a route, roadslower than a certain type tend not to be considered. Pruning thresholds with confidential, variable, increasing values exist for {{Street}}, {{Primary Street}} and {{Minor Highway}}, respectively. There is evidence that {{Major Highway}} is never pruned. {{Freeway}} and {{Ramp}} are never pruned. The pruning mechanism uniquely accounts for [[Creating and editing road segments#Special properties|routing road type]], so a Primary Street with routing road type +1 would be pruned at the same threshold as a Minor Highway.
==Missing roads and incorrect junction connections= XL routes ===Generation of routes longer than 1000 miles in Waze tries used to find be impossible, but in 2018 a new mechanism for extra-long (XL) routes was put into place. This pieces together multiple long routes to generate one extra-long route. To save time and avoid routing timeouts, instructions and geometry details are omitted in the middle of the best route between you during initial calculation, but they are produced and your destination based on your navigation settingslisted later as the user drives along the route. Obviously it Dependent upon multiple factors such as server load and road types, transcontinental routes can only route based on roads be calculated in Waze with this mechanism. It is also evident that it knows about, since XL routes are combinations of shorter routes, the aforementioned pruning behaves differently for them, so your route will not be optimal if a better route does not have all the roads with correct connections that lower road types may appear in the Waze Map Editor. Also if [[Minimum segment length|segments are too short]] they can cause routing issuesmiddle of extra-long routes.
==Real-time current road speeds==We can be confident that Waze The routing server uses real-time reports of current road speeds by preference over (from recent Waze app users if available) and combines the average, historical average road speedsspeed of the segment broken down into 10-15 minute chunks. We know that Waze uses traffic congestion reports The time to reroute around slow trafficpass through a segment is tracked separately for each route out of a segment. Early versions of For example if a segment ends with only a left and right turn, then the routing engine isolates the time through the client would also report when traffic speeds were good - this was removed due segment to map clutter. But Waze will still be receiving this information. We can assume that turn left and the speed of any wazer ahead of you on a stretch of road will be time through the segment to turn right. This detailed speed used when your route information is proprietary and is calculatednot displayed in the Waze Map Editor.
As the number and density of Wazers grows this It is known that Waze prefers to use real-time data takes on a greater importancereports of current road speeds over historical average road speeds. Waze also uses traffic congestion reports to reroute around slow traffic. This emphasis is partly a reflection <!-- Early versions of Waze's original goal the client would also report when traffic speeds were good - this was removed due to create optimal commutesmap clutter. As But Waze has grown to will still be used as receiving this information. -->The speeds of recent Wazers traveling on a more general purpose GPS navigation device over roads less travelled, road will be factored into the route given to subsequent Wazers traveling on the historical average same road speeds becomes more important.
Since Waze uses As the time you expect to be at a road segment to calculate the expected speed on that segmentnumber and density of Wazers grows, it cannot use this real -time data when you trip time moves into takes on a future time slotgreater importance. So trips This emphasis is partly a reflection of Waze's original goal to create optimal commutes. As Waze has grown to be used as a more than 30 minutes (and on general-purpose GPS navigation device over roads less traveled, the historical average road speeds becomes 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, real-time traffic data may be available which may cause your client to recalculate your ETA and reroute you at that pointimportant.
==Fastest routing==Since Waze knows uses the average speed future expected time of every confirmed arrival onto a road between you and your destinationsegment in order to calculate the expected speed on that segment, it cannot use real-time data too far in the future. The Waze server can calculate which list So longer trips (on the order of roads 30 minutes or more) will include future time slots where current traffic data is not available when initially calculated. As the trip progresses, any real-time traffic data that is available causes the client to take to minimize recalculate the route and the total travel timeETA.
While every request == Average road speeds ==If the average or historical road speed is processed in real-timenot correct, by observation it appears that then the route may not be optimal. However, deletion of segments to reset average road speed is not recommended. Waze [[glossary|caches]] some requested routes or major points. This means if it already knows uses the best route data from B Wazers traveling through the segments to Cupdate the average speed, and you ask for a route from A oftentimes an anomalous historical road speed is automatically corrected with further data collection. If Waze appears to C, it may just calculate disfavor the best use of certain segments along a route from A to B, once it checks that there isn't a better route bypassing B altogether. This does mean that when there is a [[Timeline number of updating process|Live map update]] some routes may be less than optimal for up to other reasons can cause such a day as routes are cached and recalculatedsituation.
While === Time-of-day variations ===Consider a complex calculation, calculating road that most Wazers drive at 5 PM when the optimal route average speed is possible12 MPH. The complexity arises over At 10 AM when the road is clear and the "average speed" is 60 MPH, it is the best road to take. If Waze only has historical speed data from 5 PM, it will assume that the speed of the road is 12 MPH all day, and it may not recommend this road. As more people drive this road closer to the time of day when a given route is requested, Waze will get a better guess for the roadsaverage speed at that time.
==Changes in route due to different origin= Shrinking window ===Consider calculating If there are enough recorded speeds on a road, then Waze uses a route from A shrinking window of speeds to Zbetter estimate the average speed at the current time. The suggested route may be A to B to C to D to ZWaze uses the speed of each road segment (in both directions) in intervals as small as 30 minutes. Then calculate the route from B So a two-way road might have up to Z96 average road speeds in a day. You may get It can be assumed that when there are insufficient records for an individual time slot, a suggested route of B wider time range is used (up to C to E to Za full day). At first glanceAs the road is driven more at different times, this suggests one route the time slot shrinks. Additional information is not optimal because used based on the day of the [[Glossary|origin]] changedweek. There is no evidence that Waze records speeds for larger date ranges such as months or seasons; however, it will update its average speeds relatively quickly when seasonal traffic patterns change.
We can guess Waze uses the average road segment speed for the time slot that applies at what might be happeningthe time when a user is expected to arrive at that road segment. There may be a problem associated with the possible caching Because of routes. Or there may be a "timing this time window" effect. The , Waze suggests different arrival time routes at C may change different times of day. This is dependent on how many times are recorded on the roads along the best route to Z. Or there may be a fine tuning effect in If they're all recorded at about the routesame time of day, perhaps to avoid too many turnsthen the time window does not help. So by dropping the segment A to BIf 1,000 times are recorded at about 5 PM and 2 times are recorded at 10 AM, then the segments C to E to Z no longer exceed some threshold10 AM average speed still is based mostly on times from around 5 PM.
This effect can be observed while driving. If you recalculate a route to a destination while driving along an already calculated route to that same destination, the route may change. This are old reports where wazers have not offered a route to bypass heavy traffic, but do receive a new route when manually asking for it. It may be they would have been offered that alternative route at that point anyway, whether or not there was bad traffic ahead. It does raise the question as to when and how Waze considers rerouting, but these may have been addressed in the current version. Certainly Waze does offer new routes sometimes. ==Changes in routes due to different route lengths== In addition, it is known that the Waze routing engine can't calculate every possible route for long distance routes, so takes shortcuts for longer routes, potentially resulting in the route changing dramatically when lengthened slightly. According to Waze support (as of July 2011), the section of a route more than 10 km from each endpoint is heavily weighted towards non-streets (i.e. "Primary Streets" or the various Highway types). My personal guess is that it simply ignores streets outside of the 10 km radius from the endpoints when doing its calculations to speed up the calculation. The specific quote from support was: "Above some distance (currently 10KM) from both end points (start and destination) the server prefers to go through non streets. Now as it happens here - this small distance was the difference between being less than or over 10KM. Now the penalty of going through a street in this case is high - so the server prefers the highway." In this particular case, the observed behavior was that extending the route by a short distance caused Waze to suggest a very different (and much longer, both in distance and estimated time) route. ==Problems with average road speeds==If the average road speed is not correct, then the route will 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 speed. If you suspect Waze is not using certain segments along a route, 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 are reasons why the routing engine may not use the average road speed. ===Time of day variations===Consider a road that most Wazers drive at 5pm when the average speed is 12 mph. You choose your route at 10am when the road is clear 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 at 10am and assumes the speeds is 12mph all day. You can, of course, drive the road yourself, and Waze will eventually learn the speed for that time. We do not know how long Waze holds the older data in computing the average speed. However if Waze does discard old time information, you may not accumulate new time faster than it is discarded. It is also possible that your times are being ignored as being abnormal. More Waze users would help fix this.  ===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:
* Seg4 to Jnct2 to Seg6
Traffic building up on Seg4 that turns right to Seg6 will does not affect the route timing for the traffic also using Seg4, but instead turning left to Seg5.For this reason it is important to keep long segment lengths before junctions if 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, the segment before the junction should be kept long, or a [[junction box]] may be used.
To understand this problem better=== Outdated and abnormal road speeds ===Average speeds can change over time, consider if we add and recorded times can be abnormal or wrong—and can stay wrong for a short Seg8 between Seg7 and Jnct4very long time. Let's say the traffic exiting Seg10 backs up all the way This may be due to Seg7 (easy enough, since Seg7 is short). Because Seg7 only has a single exiting segment (Seg8), the routing server is only able to collect a single average users recording inaccurate speed &mdash; it can no longer distinguish traffic data by where it is going ''after'' Seg8. Now the through traffic going to Seg9 appears to Waze to slow down through Seg7doing things like walking, even though it doesn't biking or sitting in realitytheir driveways with Waze open. At a minimum this will cause an incorrect ETA for routingAlso, and it might actually cause traffic if [[Segment length|segments are less than {{:Segment length/Minimum}}]] they may not be long enough to be rerouted unnecessarily, and less optimally, through another routerecord accurate transition times. Hence if there There is a chance some evidence that traffic that goes abnormal road speeds and old road speeds are discarded, or at least not used in different directions at a junction experiences different congestion, keep calculating the segment before that junction longaverage speeds of roads.
Note this data is not presented to users through == Recalculation ==When Waze receives notification of traffic conditions, it uses the Waze Map Editoractual speed of roads on your route, but 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 visible to the and do not change routing server.
===Waze Map Editor changes===The average speed of a road can be dramatically altered by editing ETA is updated in Waze Map Editor (WME). Consider response to a 50m length of road driven user's progress on the route and in 36 secondsresponse to these real-time traffic conditions. An editor extends this length of road If real-time traffic conditions make the full 10km length. WME now records this road as 10km longgiven route significantly worse than alternatives, but also driven in 36 seconds for Waze may provide an average road speed of 1000km/hourautomatic recalculation. Therefore be cautious The benefits of significantly changing this are balanced against the length perceived hassle of roads. Instead consider drawing new roads and linking themchanging 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 will become 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 will does avoid slow roads; if the traffic lights make the road slow then Waze will avoid avoids them. Some drivers will 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 back 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 may be stuck behind a truck, and another day you may 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 takes up a full day. As the road is driven more, the time slot shrinks down to 30 minutes. We can speculate that there may be 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 will 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 will still mostly be based 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 minimise turns we can add a time 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 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 the option to generate alternative routes. This may give you some clues as to why Waze is offering that route. Secondly, if you think there is a better route, check in WME that the roads are all connected along the route.
ThirdlySome drivers regularly take longer routes — even winding through side streets — to avoid any stops or traffic lights. Waze has been known to suggest this, post a message detailing the problem route - origin, destination and a WME permalink also known to revert to waiting at lights when better average speed information is collected from the [http://wwwside streets.waze.com/forum/viewforum.php?f=6&sid=2872533f5796ac39dc6747511398e907 Navigation forum]. Other eyes will check it, and you may indeed find a flaw in But note that this can be less than optimal due to the Waze routing algorithm. Fixing it may make it better for everyoneturn delays discussed above.
==Change of RoutingWhat to do if you think the generated route is wrong ==When # Use the option to generate alternative routes. This might give you some clues as to why Waze receives notification of traffic conditions it uses is offering that route.# If you think there is a better route, check in the actual speed [[Waze Map Editor]] that all of its roads on your routeare connected, rather than and all legal turns are allowed.# Communicate the average speedproblem. This is based only Possible means of communication include:#* Report a [[map issue]] in the app and respond to comments on it.#* Post a message detailing the automatic traffic condition reports - lightproblem route (origin, moderate, heavy traffic destination and a WME permalink) to the [http://www.waze.com/forum/viewforum.php?f=6&sid=2872533f5796ac39dc6747511398e907 Navigation forum] or complete standstillyour state's local forum. Manual reports of traffic jams and accidents are for #* Join your local community's Waze Discord server (accessible from your information only and do not change routingstate wiki page). This will usually produce the fastest response from local editors.
It may be == You are the driver ==Waze can never see that even with the traffic reports, there light is green going straight or know that today is a public holiday. It can offer you guidance as to what is no better the best route under average conditions. But you are the driver and Waze will not offer you oneare in the best position to make the decision for today under today's conditions.
==You are the driver==If everyone followed Waze directions and never drove on a new route, Waze can might never see learn that the traffic light route is better. When Waze is green going straightrecording your travels, or every trip helps make Waze better for everyone. That includes when you think you know that today is a public holidaybetter. Sometimes you will be right. It can offer And sometimes you guidance as to what is the best route under average conditionswill be wrong. But it is better to find out you are wrong so you can choose the driver and better route. And when you are in right, all Waze users benefit by the best position to make the decision for today under today's conditionssharing of your knowledge.
If everyone followed [[Category:Waze directions and never drove on a new route, Waze may 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 benefits by sharing in your knowledge.operations]]
1,270
edits