Routing server: Difference between revisions Discussion View history

No edit summary
No edit summary
Line 29: Line 29:
While a complex calculation, calculating the optimal route is possible. The complexity arises over the "average speed" of the roads.
While a complex calculation, calculating the optimal route is possible. The complexity arises over the "average speed" of the roads.


==Average Road Speeds==
==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===
===Turn delays===
===[[Cartouche]] editing===
 
==Traffic lights and stop signs==
 
==Outdated road speeds and outliers==
 
==Average road speed "shrinking window"==
 
==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===

Revision as of 03:37, 15 September 2010

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 operating 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 out 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 [[glossary|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 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

Turn delays

Cartouche editing

Traffic lights and stop signs

Outdated road speeds and outliers

Average road speed "shrinking window"

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