Is Waze a ruse?

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?

 

 

 

Comments

[Mickey Droy]

I'm an occasional Google Maps user here in UK.
It certainly does use actual data to enhance forecasts. Travelling from North UK to South London there are various routes to consider from using the M25 orbital to avoid London completely to going straight through London (only sensible at 3 in the morning). And a network of alternative N-S routes parallel to the most direct M1 route. Google regularly updates, suggests different routes and adjusts to real time situations. If it predicts a jam ahead there will be one.
What it doesn't do yet is predicting worsening or improving conditions. It updates current situations but then every thing is static "as is now". So an accident 15 mins ahead where there is a 5 min tailback is predicted as a 5 min delay based on how long cars took just now. Of course by the time I get there the tailback will be 3 times as long. In other cases a cleared blockage means that the predicted delay keeps falling and is zero when I reach the point.
So there is still one level of prediction that falls to the driver.

[Kaiser]

MD: Thanks for providing your experience. I should have included in the post for people who don't know that Waze was acquired by Google Maps some years ago.

I didn't intend to trivialize the difficulty of the real-time problem. I did intend to make readers think about how one should frame the real-time problem.

To take your example, I doubt that any navigator can predict an accident with any adequate level of accuracy but it may have access to real-time data feeds that inform it of an accident.

if the navigator has access to real-time data feeds, it should be able to track the slowing traffic around the accident. The more an algo hones to the real-time data, the less "prediction" it is doing, but also the software can be simpler and faster.

[CraigM]

The algorithm is doing more than directing you, it is also offering advice to many other drivers on the road. If a large enough share of drivers are using the same platform, it not only has to deal with the effects of congestion, it can CAUSE congestion by rerouting too many cars so they will be on the same segment at the same time. Since there are inherent delays in the system, unless the algorithm randomly balances choices about alternative segments, oscillatory solutions are obviously possible if not likely. Given the hyperbolic increase in queueing delays as most systems near saturation, failure to address this problem would be obvious with only a couple of services providing routing - obviously there is load-balancing in the algorithms.

I stopped using Google Maps for most trips within the highly-connected metro area I live in when I realized that in a region with a large percentage of drivers using Google Maps or equivalent, these programs are essentially leveling out urban congestion. Travel time differences are almost always within prediction error margins, and random events such as recent accidents on the route account for almost all the risk of delay. If everyone else is using Google Maps, I don't have to bother. And this ability to freeride complicates the economics of providing traffic data without the advantage of acquiring extremely valuable user data.

[Kaiser]

CM: Great points. I discussed this in Numbers Rule Your World. Transportation research confirms your experience; mitigation measures just shift traffic around; at equilibrium, pretty much every route should have the same amount of traffic/congestion.
That said, the scenario described in the post is one in which the algo failed by a massive margin to predict arrival time, in an urban city, during off-peak hours, without unpredictable accidents.