Changes

From Wazeopedia

Routing server

239 bytes added, 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* Whether to avoid highways* {{Passageway}} has a type-specific [[Routing penalty|penalty]].* Whether to prefer cookie munching* [[Partial 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 ==
Cookie munching refers to [[glossary|pacman]] or unconfirmed roads=== Pruning ===It is known that the Waze 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 middle of longer routes. When this option This effect is enabled, commonly called '''route pruning''' and can potentially result in the route will take changing dramatically when lengthened slightly. At distances farther than a certain threshold value from the origin or destination of a less direct route , roads lower than a certain type tend not to travel over unconfirmed roadsbe considered. Pruning thresholds with confidential, variable, increasing values exist for {{Street}}, {{Primary Street}} and {{Minor Highway}}, earning you pointsrespectively. This typically adds 10 minutes to your driving timeThere is evidence that {{Major Highway}} is never pruned. So a 3 hour drive becomes 3 hours {{Freeway}} and 10 minutes{{Ramp}} are never pruned. But 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 20 minute drive becomes 30 minute driveMinor Highway.
==Missing roads and incorrect junction connections= XL routes ===Generation of routes longer than 1000 miles in Waze tries used to be impossible, but in 2018 a new mechanism for extra-long (XL) routes was put into place. This pieces together multiple long routes to find generate one extra-long route. To save time and avoid routing timeouts, instructions and geometry details are omitted in the middle of the fastest route between you during initial calculation, but they are produced and your destinationlisted 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 [[Live Map]]middle of extra-long routes.
==Fastest RoutingReal-time current road speeds ==The routing server uses real-time road speeds (from recent Waze knows app users if available) and combines the average , historical speed of every confirmed road between you and your destinationthe segment broken down into 10-15 minute chunks. The Waze server can calculate which list time to pass through a segment is tracked separately for each route out of roads a segment. For example if a segment ends with only a left and right turn, then the routing engine isolates the time through the segment to take turn left and the time through the segment to minimize turn right. This detailed speed information is proprietary and is not displayed in the total travel timeWaze Map Editor.
While every request It is processed in known that Waze prefers to use real-time, by observation it appears that reports of current road speeds over historical average road speeds. Waze [[glossary|caches]] some requested routes or major pointsalso uses traffic congestion reports to reroute around slow traffic. This means if it already knows <!-- Early versions of the best route from B client would also report when traffic speeds were good - this was removed due to C, and you ask for 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 from A given to C, it may just calculate subsequent Wazers traveling on the best 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 of updating process|Live map update]] some routes may be less than optimal for up to a day as routes are cached and recalculatedsame road.
While As the number and density of Wazers grows, this real-time data takes on a greater importance. This emphasis is partly a complex calculation, calculating the reflection of Waze's original goal to create optimal route is possiblecommutes. The complexity arises As Waze has grown to be used as a more general-purpose GPS navigation device over roads less traveled, the "historical average speed" of the roadsroad speeds becomes more important.
==Changes Since Waze uses the future expected time of arrival onto a road segment in route due to different [[glossary|origin]]==Consider calculating a route from A to Z. The suggested route may be A order to B to C to D to Z. Then calculate the route from B to Zexpected speed on that segment, it cannot use real-time data too far in the future. You may get a suggested route So longer trips (on the order of B to C to E to Z30 minutes or more) will include future time slots where current traffic data is not available when initially calculated. At first glanceAs the trip progresses, this suggests one any real-time traffic data that is available causes the client to recalculate the route is not optimaland the ETA.
We can guess at what might be happening. There may be a problem associated with == Average road speeds ==If the possible caching of routes. Or there may be a "timing window" effect. The different arrival time at C may change average or historical road speed is not correct, then the best route to Z. Or there may not be a fine tuning effect in the routeoptimal. However, perhaps deletion of segments to avoid too many turnsreset average road speed is not recommended. So by dropping Waze uses the segment A data from Wazers traveling through the segments to Bupdate the average speed, and oftentimes an anomalous historical road speed is automatically corrected with further data collection. If Waze appears to disfavor the use of certain segments C to E to Z no longer exceed some thresholdalong a route, a number of other reasons can cause such a situation.
This effect can be observing while driving=== Time-of-day variations ===Consider a road that most Wazers drive at 5 PM when the average speed is 12 MPH. At 10 AM when the road is clear and the average speed is 60 MPH, it is the best road to take. If you recalculate a route 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 destination while driving along an already calculated given route to that same destinationis requested, Waze will get a better guess for the route may changeaverage speed at that time.
This === Shrinking window ===If there are old reports where wazers 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. So a two-way road might have not offered a route up to bypass heavy traffic but do receive 96 average road speeds in a new route when manually asking for itday. It may can be they would have been offered assumed that alternative route 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 at that point anywaydifferent times, whether or not there was bad traffic aheadthe time slot shrinks. It does raise question as to when and how Waze considers rerouting but these may have been addressed in Additional information is used based on the day of the current versionweek. Certainly There is no evidence that Waze does offer new routes sometimesrecords speeds for larger date ranges such as months or seasons; however, it will update its average speeds relatively quickly when seasonal traffic patterns change.
==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 Waze uses the average road segment speed can be for the wrong value to use.===Time of day variations===Consider a road time slot that most wazers drive applies at 5pm the time when the average speed a user is 12 mph. You choose your route expected to arrive at 10am when the that road is clear and the average speed is 60mphsegment. It is the best road to takeBecause of this time window, but Waze chooses a suggests different routes at different times of day. This is dependent on how many times are recorded on the roads along the route because it has no information . If they're all recorded at about the speed same time of day, then the time window does not help. If 1,000 times are recorded at 10am about 5 PM and assumes 2 times are recorded at 10 AM, then the speeds 10 AM average speed still is 12mph all daybased mostly on times from around 5 PM.
You === 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 course, drive the road yourself, and Waze will eventually learn. We do not know how many times Waze uses in its calculationsegment. However if Waze does discard old Traffic going straight through a traffic light might go very fast while traffic turning left might wait a very long 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 abnormalA freeway exit lane might go fast while traffic continuing hits congestion.
More [[Image:SegmentTraffic1.png|right|350px]]Waze users would help fix this. ===Turn delays===Consider a road of length 1 mile where you drive straight ahead and go through has the intersection all at 100mph taking 36 seconds. Or at ability to separately track the end average speed of the road you can sit and wait 5 minutes traffic that passes through a segment, but exits to make a turndifferent segments. The routing engine takes this into account. In the first case your average speed is 100mphdiagram, multiple times are tracked for traffic flowing through Seg4 based on the segments to which it exits. In the second case your There are then two average speed is just under 11mph.drive times for:
Now if 9/10 wazers go straight through, the average road speed is 91 mph. Waze will recommend this route, even if if involves a turn on your route, and the route is not optimal.* Seg4 to Jnct2 to Seg5
Contrariwise, if 9/10 wazers make that 5 minute turn, the average road speed is 20mph, and even though your optimal route would take you straight through at 100mph, Waze will not suggest it because it sees the average speed as 20 mph. * Seg4 to Jnct2 to Seg6
We can assume Waze is aware 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 Traffic building up on Seg4 that by collecting your route information Waze is collecting enough information turns right to give correct routing advice when it implements it. It knows Seg6 does not affect the average speed of people going straight through and it knows the average speed of people making the turn. And it can apply the correct average speed when calculating your best route. It make timing for the calculation more complextraffic also using Seg4, but instead turning left to Seg5.For this reason it can be doneis 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 the moment 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 not being donea 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.
===[[Cartouche]] editingOutdated and abnormal road speeds ===The average speed of Average speeds can change over time, and recorded times can be abnormal or wrong—and can stay wrong for a road can very long time. This may be dramatically altered due to users recording inaccurate speed data by editing doing things like walking, biking or sitting in Cartouchetheir driveways with Waze open. Consider a 50m length of road driven in 36 seconds. An editor extends this Also, if [[Segment length of road the full 10km |segments are less than {{:Segment length. Cartouche now records this road as 10km long but also driven in 36 seconds for an average road speed of 1000km/hour. This has been a particular problem as people adjust the length of ramps.==Traffic lights and stop signs==Waze does Minimum}}]] they may not be long enough to record the location of traffic lightsaccurate transition times. While There is some GPS navigation offers guidance like "turn right at the next traffic light" the information is frequently incompleteevidence that abnormal road speeds and old road speeds are discarded, incorrect or outdated. The consensus view is that Waze should at least not record used in calculating the location average speeds of traffic lightsroads.
== Recalculation ==When Waze does take into account receives notification of traffic lightsconditions, stop signs through it uses the effect they have actual speed of roads on traffic speed. Consider a traffic light with long waiting times. The road segment leading to that traffic light will have a low your route, rather than the average speed. If the average speed (This is based on the average waiting [[Real time closures|real-time) becomes long enoughclosures]] and automatic traffic condition reports - light, a longer route that avoids the light will become the preferred routemoderate, heavy traffic or complete standstill. This has been observed in practice and is an example Manual reports of ''emergent behaviour''. Waze isn't programmed to avoid traffic lights but it will avoid slow roads jams and accidents are for display only and if the traffic lights make the road slow then Waze will avoid themdo not change routing.
Some drivers will regularly take longer routes ETA is updated in response to a user's progress on the route and in response to avoid any strops or these real-time traffic conditions. If real-time traffic lightsconditions make the given route significantly worse than alternatives, winding through side streetsWaze may provide an automatic recalculation. Waze has been known to suggest The benefits of this, and also known to revert back to waiting at lights when better average speed information is collected from are balanced against the side streetsperceived hassle of changing one's route.
But note that this can be less than optimal due to the turn delays discussed above. ==Outdated Traffic lights and abnormal road speedsstop signs ==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 crawl along the roads at 2am transporting your pet goldfish. Or your GPS throws a glitch and has you travelling a 1000 mph. In short average speeds can change over time, and recorded times are abnormal or just 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 does not used in calculating record the average speeds location of roadstraffic lights==Average road speed While some GPS navigation offers guidance like "shrinking window"==If there is enough recorded speeds on a road, then Waze uses a shrinking window of speeds to better estimate the average speed turn right at the time you are travelling on it. Waze uses next traffic light" the speed of each road segment in intervals as small as 30 minutes, for each direction. So a two-way road may have up to 48 average road speeds. We can assume that when there is insufficient records for an individual time slot, a wider time range is taken, up to the 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 by the day of week. There is some observational evidence that a road that is busy on weekdays and not used for routingfrequently incomplete, 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 time you are expected to arrive at a road segment. Because of this "time window", Waze will suggest different routes at different times of day. But it is dependent on how many times are recorded on the roads along the route. And if they're all recorded at about the same time of day, then the time window will not help. If 1000 times are recorded at about 5pm and 2 times are recorded at 10am, then your 10am average speed will still mostly be based on times from around 5pm. ==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 incorrect or shortest routeoutdated.  ===Junction penalties===Currently Waze applies a 5 second time penalty for passing through each 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. This may add a 5 minute penalty 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 The consensus view is needed as the manual work that is required is enormous. The routing problem can be fixed in a variety of ways. One could Waze should not apply the penalty when there are no other existing roads meeting. Not apply the penalty when you are travelling on to a road with the same name. Not apply the penalty when the road you are travelling on is a higher class (eg highway versus street, primary street versus street) where we can assume the higher class road has record the right location of way. Or just not apply the penalty 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 it 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 routetraffic lights.
SecondlyWaze 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, if you think there is a better longer route, check in Cartouche that avoids the light becomes the preferred route. This has been observed in practice and is an example of ''emergent behavior''. Waze isn't programmed to avoid traffic lights but it does avoid slow roads are all connected along ; if the traffic lights make the routeroad slow then Waze avoids them.
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