Translations:WME Image Overlays/1/en

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.

Speculation

The routing algorithm used by the Waze server is not publicly disclosed and the following is based on observation, speculation, and some 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 Waze. We can also assume that it is subject to change, and that any information that has been revealed may be incomplete o r out of date.

Routing requests

When you request a route calculation, the request is sent to the Waze server. That route is then transmitted back to your client device and displayed.

The requests for routing vary according to the settings you have chosen on your client device. Under Routing you can choose:

• Fastest or shortest route
• Whether to allow dirt roads, never allow dirt roads or to avoid long dirt roads
• Whether to minimize turns
• Whether to avoid highways
• Whether to prefer cookie munching

The shortest 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.

Cookie munching refers to pacman or unconfirmed roads. When this option is enabled, the route will take a less direct route to travel over unconfirmed roads, earning you points. This typically adds 10 minutes to your driving time. So a 3 hour drive becomes 3 hours and 10 minutes. But a 20 minute drive becomes 30 minute drive.

Missing roads and incorrect junction connections

Waze tries to find the fastest route between you and your destination. 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 Live Map

Fastest Routing

Waze knows the average speed of every confirmed road between you and your destination. The Waze server can calculate which list of roads to take to minimize the total travel time.

While every request is processed in real-time, by observation it appears that Waze caches some requested routes or major points. This means if it already knows the best route from B to C, and you ask for 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 altogether. This does mean that when there is a Live map update some routes may be less than optimal for up to a day as routes are cached and recalculated.

While a complex calculation, calculating the optimal route is possible. The complexity arises over the "average speed" of the roads.

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

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 the end of the road you can sit and wait 5 minutes to make a turn. In the first case your average speed is 100mph. In the second case your average speed is just under 11mph.

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.

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.

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 that by collecting your route information Waze is collecting enough information to give correct routing advice when it implements it. It knows 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 the calculation more complex, but it can be done.

At the moment it is not being done.

Cartouche editing

The average speed of a road can be dramatically altered by editing in Cartouche. Consider a 50m length of road driven in 36 seconds. An editor extends this length of road the full 10km 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 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 into account traffic lights, stop signs through 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 long enough, a longer route that avoids the light will become the preferred route. This has been observed in practice and is an example of emergent behaviour. Waze isn't programmed to avoid traffic lights but it will avoid slow roads and if the traffic lights make the road slow then Waze will avoid them.

Some drivers will regularly take longer routes to avoid any strops or traffic lights, winding through side streets. 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 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 not used in calculating the average speeds of roads.

Average road speed "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 at the time you are travelling on it. We can imagine the code may look something like this: select averagespeed on road sort by absolute(timeofdaynow-timeofdaytravelled) limit 100

So that would take the average speed of up to 100 trips closest to the time of day of your trip. If you are travelling at 3pm and there are 100 times recorded between 2.58pm and 3.02pm on that road, then you would be using average times from a 4 minute window. If there were only ever 12 times recorded for that stretch of road, you would use the average of all 12 and there would be no time window. As the road was driven more, the window would shrink automatically.

A similar approach could be used to combine average speeds based on the day of the week.

For long trips, we would like to assume that Waze uses the time you are expected to arrive at the road, rather than the time at the start of your trip.

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 or shortest route.

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 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. 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 the right of way. Or just not apply the penalty when travelling on freeways 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 route.

Secondly, if you think there is a better route, check in Cartouche that the roads are all connected along the route.

Thirdly, post a message detailing the problem route - origin, destination and a Cartouche permalink to the Navigation forum. Other eyes will check it, and you may indeed find a flaw in the Waze routing algorithm. Fixing it may make it better for everyone.

Change of Routing

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 only on the automatic traffic condition reports - light, moderate, heavy traffic or complete standstill. Manual reports of traffic jams and accidents are for you information only and do not change routing.

It may be that even with the traffic reports, there is no better route and Waze will not offer you one.

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