Waze, Google Maps, and other GPS navigators presents themselves as solving an optimization problem that has been studied for decades: the shortest-path problem of navigating from a given starting location to a given ending location, while staying on legal roads on a given map, with the goal of reaching the destination in the shortest possible time.

The simplest version of this problem admits a static solution, that is to say, it gives the same route regardless of time of day. In this setting, traffic conditions are ignored, and speed of driving is assumed the same for all drivers and at all times. In practice, this static solution sets a benchmark, and a lower bound for the shortest possible time.

A more sophisticated solution removes those restrictions, which is possible only if some kind of sensor data is available, via sensors buried in the ground, embedded in mobile phones, or roadside cameras. With the ingestion of "real-time" data, the solution involves a new element - forecasting.

That's because knowing the traffic where the driver is currently is useless; it's dead on arrival, so to speak. What the navigator needs ideally is the perfect crystal ball - the future traffic conditions between the current location and the destination.

***

If you're a regular Waze user, you may have noticed Waze doesn't quite have the crystal ball. I have suspected this for a while, and a recent trip by a friend from Brooklyn to Manhattan on a Sunday morning motivated me to blog about this.

When he started the journey at 11:02 a.m., Waze estimated an arrival time of 11:32 a.m., so a travel time of 30 minutes. My friend sent me a link that allowed me to track his progress, with a note: "Waze shows only 30 minutes, doubt it... Let's see."

Needless to say, the 30-minute projection was wrong. Not slightly off, but way off.

At 11:17 a.m., about half way through the original schedule, the arrival time has shifted back 4 minutes to 11:36 a.m. Not bad -- except that it kept sliding. Ten minutes later, at 11:27 a.m., Waze now showed an estimated arrival time of 11:50 a.m. Wait, the new estimated travel time was almost 20 minutes more than the original estimate of 30 minutes. My friend texted over a photo of the traffic on the road.

Twelve minutes later, at 11:39 a.m., the estimated arrival time shifted further back to 11:54. So the passage of 12 minutes added another 4 minutes of delay. At 11:46 a.m., seven minutes later, the new arrival time was 11:56; thus, another 2 minutes of delay upon passage of 7 minutes. Another three minutes later, the estimated arrival time moved again, this time, it moved earlier by 1 minute. Oops, two minutes after saying he'd get there one minute faster, the app recomputed the arrival time again, adding two minutes, more than reversing the previous update.

In the end, he got there in 60 minutes, which is double the estimated travel time of 30 minutes at the start of the journey. At 11:50 a.m., 10 minutes before actual arrival, Waze gave an estimate of 5 minutes left so the actual remaining travel time was still double the estimated time towards the end of the trip. Pretty embarrassing stuff.

Note that this was a Sunday morning trip, not a particularly busy or unpredictable time. And the delay wasn't due to traffic accidents. My friend knew it was wrong at first sight.

***

My suspicion is that these navigators are not solving any kind of mathematical problem. It is not making any forecasts. It is purely reactive, responding to what's directly ahead of them.

Ever followed the progress bar on a file download of a large file? You'd probably notice that the estimated completion time fluctuates wildly, both up and down. This fluctuating phenomenon is most apparent at the start of many downloads, when there is a burst of speed. The progress bar will give an estimate, e.g. 5 minutes left. This number soon shots up to 8, 10, 15, 20 minutes... as the download speed slows down.

I have long suspected that the remaining time as displayed is estimated by a simple calculation: remaining amount of data to download divided by the current speed of download. Thus, if the download speed increases, the remaining completion time is shortened, and if the download speed slows, the remaining time is increased.

In this setting, there is no "forecasting" per se. The computation assumes that what's happening now is what will happen in the future. The current download speed will continue into the future until the file is completely downloaded.

Constant speed is a very poor assumption because the variability of the displayed remaining time is a direct result of variable speeds. If the download speed were constant, as assumed, then the remaining time would peel off at a linear rate consistent with real time. In other words, the estimated completion time would not change. In other words, the projection based on constant speed played out as expected.

***

The feeling I got from observing my friend's Waze on his recent trip reminds me of watching large files download onto my laptop. Could it be that Waze implements a similar, simple computation? The estimated arrival time is based on the remaining distance to the destination (assuming the driver follows the prescribed route) divided by the current speed of the driver?

It must be a little better than that. If it really used the instantaneous driving speed, then every time the car stopped, the estimated arrival time would jump to infiinty. Instead of the current speed, perhaps Waze takes the average speed of some duration, say 5 minutes.

Regardless, it appears that Waze's assumed driving speed does not match reality well at all.

Read that sentence again. Then, ask yourself: did Waze give you the shortest route to your destination at the start of the trip? Could it do so without accurate projections of your driving speed on that route?

## Recent Comments