It sure would be great if mapping services like Google Maps and Bing Maps would make better use of robust optimization. I know from being “on the inside” that the techniques used to find the best route from A to B are incredibly sophisticated. It’s far more complicated than simply solving a shortest path problem; they prune silly solutions using a variety of techniques. Mapping services do an outstanding job with directions most of the time, but of course that won’t stop me from complaining. It may very well be that Google/Bing/etc already do this kind of thing and my assumptions are wrong – in which case this blog post will look pretty silly. I guess that’s a risk I will have to take.
Suppose you’re planning a trip from Evanston, Illinois to my home town of Cedar Falls, Iowa. Here’s what pops up for Google (and Bing) for the first segment of the trip. Google reports the driving time as 5 hours, 1 minute.
I’m being asked to hop on 94 and hook up with 90 W. (The remaining steps are left as an exercise for the reader.) Now it turns out that if avoid 94 and take Golf Road, the estimated time is 5 hours 5 minutes (4 more minutes):
I don’t know for sure, but my guess is that there is more variance on the 94 – 90 route than the Golf Road route because of traffic considerations. Big interstates running through big cities get jammed up. Yes, you have to contend with traffic lights on the Golf Road route, but that’s probably more predictable than I-94 traffic. So while the best or average case may be slighty better for 94-90, there are probably a larger percentage of scenarios where there are significant delays. If we compared the two routes over a range of plausible traffic scenarios, I bet the expected time for the Golf road route over all routes would be shorter. (This is a key principle in stochastic programming: if uncertainty is involved taking the “average solution” is not always your best move – see for example Jeff Linderoth’s lecture notes from a few years ago.)
The moral of the story: if two routes have similar average durations, give me the one with lower variance.