Changes

From Wazeopedia

Routing server

2,179 bytes removed, 3 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.
==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 Routing you Navigation one can choose:* Fastest Whether to allow or shortest routeavoid [[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 proper pass)* Whether to avoid {{Ferry|Ferries}}* Whether to avoid {{Freeway|Freeways}}* Whether to allow dirt roads, never allow dirt roads , or to avoid long dirt unpaved roads* Whether to minimize avoid [[Difficult turn|difficult intersections]] (turnsmarked "difficult" through nodes or junction boxes).* Vehicle type** {{Passageway}} has a type-specific [[Routing penalty|penalty]].* Whether to * [[avoid highwaysPartial restrictions|Segment restrictions]]allow or prevent travel by certain vehicle types.
The shortest == Different route refers to physical distance. It is always better to choose the Fastest route option. 100km of freeway is better than 90km of country roads.lengths ==
==Missing roads and incorrect junction connections= Pruning ===It is known that the Waze tries to find routing engine can't calculate every possible route for long-distance routes, so it takes shortcuts by removing lower road types from consideration in the fastest middle of longer routes. This effect is commonly called '''route between you pruning''' and your can potentially result in the route changing dramatically when lengthened slightly. At distances farther than a certain threshold value from the origin or destination. Obviously it can only of a route based on , roads lower 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 it knows about{{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 your route will not be optimal if a better route does not have all the roads Primary Street with correct connections in routing road type +1 would be pruned at the Live Mapsame threshold as a Minor Highway.
==Real-time current road speeds= XL routes ===We can Generation of routes longer than 1000 miles in Waze used to be confident that Waze uses realimpossible, 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. We know that Waze 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. We can assume It is 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 optimise 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 travelledleft and right turn, then the routing engine isolates the time through the segment to turn left and the time through the segment to turn right. This detailed speed information is proprietary and is not displayed in the historical average road speeds becomes more importantWaze Map Editor.
Since It is known that Waze uses the time you expect prefers to be at a road segment to calculate the expected speed on that segment, it cannot use real -time data when you trip time moves into a future time slot. So trips reports of more than 30 minutes (and on current road speeds over historical average more than 15 minutes) will include future time slots where current road speeds. Waze also uses traffic congestion reports to reroute around slow traffic data is not available. When you enter a new time slot, real<!--time Early versions of the client would also report when traffic data may be available which may cause your client speeds were good - this was removed due to recalculate your ETA and reroute youmap clutter.==Fastest routing==But Waze knows the average speed of every confirmed road between you and your destinationwill still be receiving this information. -->The Waze server can calculate which list speeds of roads recent Wazers traveling on a road will be factored into the route given to take 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 may 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 may 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 [[glossary|origin]]Average road speeds ==Consider calculating a route from A to Z. The suggested If the average or historical road speed is not correct, then the route may not be A optimal. 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 may 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 optimalother 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 may be a problem associated with At 10 AM when the road is clear and the possible caching of routes. Or there may be a "timing window" effect. The different arrival time at C may change average speed is 60 MPH, it is the best route road to Ztake. Or there may 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 may it will update its average speeds relatively quickly when seasonal traffic patterns change.
This are old reports where wazers have not offered Waze uses the average road segment speed for the time slot that applies at the time when a route user is expected to bypass heavy trafficarrive at that road segment. Because of this time window, but do receive a new Waze suggests different routes at different times of day. This is dependent on how many times are recorded on the roads along the route when manually asking for it. It may be If they would have been offered that alternative route 're all recorded at that point anywayabout the same time of day, whether or then the time window does not there was bad traffic aheadhelp. It does raise the question as to when If 1,000 times are recorded at about 5 PM and how Waze considers rerouting2 times are recorded at 10 AM, but these may have been addressed in then the current version. Certainly Waze does offer new routes sometimes10 AM average speed still is based mostly on times from around 5 PM.
==Changes in routes due to different route lengths= Turn delays ===On a segment of a road, a user's average speed can be very different depending on what 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.
In addition, it is known that the [[Image:SegmentTraffic1.png|right|350px]]Waze routing engine can't calculate every possible route for long distance routes, so takes shortcuts for longer routes, potentially resulting in has the route changing dramatically when lengthened slightly. According ability to Waze support (as of July 2011), separately track the section average speed of traffic that passes through 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 segment, but exits to speed up the calculationdifferent segments. 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 - routing engine takes this small distance was the difference between being less than or over 10KMinto account. Now In the penalty of going diagram, multiple times are tracked for traffic flowing through a street in this case is high - so Seg4 based on the server prefers the highway." In this particular case, the observed behavior was that extending the route by a short distance caused Waze segments to suggest a very different (and much longer, both in distance and estimated time) routewhich it exits.There are then two average drive times for:
==Problems with average road speeds==If the average road speed is not correct, then the route will not be optimal. The following are reasons why using the average road speed can be the wrong value * Seg4 to use.===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 Jnct2 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.Seg5
You can, of course, drive the road yourself, and Waze will eventually learn. We do not know how many times Waze uses in its calculation. 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.* Seg4 to Jnct2 to Seg6
More Waze users would help fix this. ===Turn delays===Consider a road of length 1 mile where you drive straight ahead and go through the intersection all at 100mph taking 36 seconds. Or at Traffic building up on Seg4 that turns right to Seg6 does not affect the end of route timing for the road you can sit and wait 5 minutes traffic also using Seg4, but instead turning left to make a turnSeg5. In the first case your average speed For this reason it is 100mph. In important to keep long segment lengths before junctions as traffic congestion at the second case your average speed is just under 11mphjunction might affect exits differently.
Now To understand this problem better, consider if 9/10 wazers go straight throughwe 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 road speed &mdash; it can no longer distinguish traffic by where it is 91 mphgoing ''after'' Seg8. Now the through traffic going to Seg9 appears to Waze will recommend 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, even if if involves there is a chance that traffic can go in different directions at a turn on your routejunction and that junction can experience different amounts of congestion, and the route is not optimalsegment before the junction should be kept long, or a [[junction box]] may be used.
Contrariwise=== 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 9[[Segment length|segments are less than {{:Segment length/10 wazers make Minimum}}]] they may not be long enough to record accurate transition times. There is some evidence that 5 minute turn, the average abnormal road speeds and old road speed is 20mphspeeds are discarded, and even though your optimal route would take you straight through or at 100mph, Waze will least not suggest it because it sees used in calculating the average speed as 20 mphspeeds of roads.
We can assume == Recalculation ==When Waze is aware receives notification of this issue. You can choose the Minimize Turns option in your Routing settings. Or you can use your own discretion. The good news is that by collecting your route information Waze is collecting enough information to give correct routing advice when traffic conditions, it implements it. It knows uses the average actual speed of people going straight through and it knows roads on your route, rather than the average speed of people making the turn. And it can apply the correct average speed when calculating your best routeThis is based on [[Real time closures|real-time closures]] and automatic traffic condition reports - light, moderate, heavy traffic or complete standstill. It make the calculation more complex, but it can be doneManual reports of traffic jams and accidents are for display only and do not change routing.
At ETA is updated in response to 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 may provide an automatic recalculation. The benefits of this are balanced against the moment it is not being doneperceived hassle of changing one's route.
===Waze Map Editor changes===The average speed of a road can be dramatically altered by editing in Waze Map Editor (WME). Consider a 50m length of road driven in 36 seconds. An editor extends this length of road the full 10km length. WME now records this road as 10km long, but also driven in 36 seconds for an average road speed of 1000km/hour. Therefore be cautious of significantly changing the length of roads. Instead consider drawing new roads and linking them. ==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 may have up to 48 average road speeds. We can assume that when there are insufficient records for an individual time slot, a wider time range is taken—up to a full day. As the road is driven more, the time slot would shrink 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 will be chosen as the optimal route on weekends. At some point, Waze would also need 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 will suggest 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===Currently Waze applies a five-second time penalty when calculating a route that passes through a junction. While not an unreasonable approach to dealing with intersections, it has generated some flawed routing and is being reviewed.  One major issue arises in long highways which may be made up of hundreds of segments connected together, as this may add a penalty of as much as five minutes to a trip, even though the intersections are not real. This supports the arguments of those who aim to have a clean edit of maps where junctions are only used when necessary. In practice, we need to deal with the map as it stands. An automated tool to remove the junctions is needed as the manual work that is required is enormous. The routing problem can be fixed in a variety of ways. One could:* Not apply the penalty when there are no other existing roads meeting at the junction;* Not apply the penalty when you cross a junction onto a road with the same name;* Not apply the penalty when the road you are travelling on is a higher class (e.g. highway versus street, primary street versus street), where we can assume the higher class road has the right of way; or* Not apply the penalty at all when travelling on freeways, motorways and highways. Even if a road is correctly connected with no unnecessary segments, the junction penalty can still give incorrect results. For example a busy highway may be correctly connected to the ramps along its length. A quiet country road running in parallel may not have all the minor connecting roads recorded; it looks like a straight section of road with no junctions. Waze may choose the country road as the preferred route because of the lack of junctions. ==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 Cartouche 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 Cartouche 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