As someone who prefers to walk from Point A to B, I have noticed that the “estimated time  to destination” on Google Maps has been a lot less accurate ever since I moved to NYC. For example, an inquiry for directions from my apartment (37th St and 10th Ave) to my office (49th St and 7th Ave) provides 3 suggested routes:

1. Walk to 39th St, cross from 10th Ave to 7th Ave, then walk straight to 49th St.
2. Walk to 48th St, cross from 10th Ave to 7th Ave, then walk straight to 49th St.
3. Walk to 49th St, cross from 10th Ave to 7th Ave. (My preferred route)

Curiously, Google shows all 3 routes as taking 24 minutes. While Options 2 and 3 are essentially the same, Option 1  is clearly inferior due to the amount of time spent on 7th Ave and cutting through one of the busiest areas of Times Square. Therefore, whatever method Google is using to map out its walking routes, it doesn’t seem to be employing the optimal shortest-path algorithm.  One explanation is that it is simply using actual distances as edge weights, which is highly naive. Indeed, given the grid-like nature of midtown Manhattan, that would yield the same travel time for any path from Point A to B. A more effective method would be to use time values as edge weights, by approximating the time it takes to travel the length of any one block (using either actual walking data, or traffic data as a proxy for human walking activity).

In this Excel file, I create a quick “contour map” of midtown Manhattan, estimating the walking time for every block (or edge) that can exist on a given path from my apartment to my office. This involves giving much higher time values to avenues than streets, and relatively higher values to busier areas (e.g. Times Square).

In this case, my preferred route (Walk to 49th St, cross from 10th Ave to 7th Ave.) also happens to be an optimal route and takes a total of 1,140 seconds, or 19 minutes. On the other hand, crossing directly to 7th Ave from 10th Ave and then walking to 49th St takes 1,350 seconds, or 22.5 minutes. Running a random sample of 2,337 routes gave me an average travel time of 1,344 seconds (22.4 min) and a max travel time of 1,390 seconds (23.2 min). While it may not seem like much on an absolute basis, the difference of ~3.5 minutes between the optimal and average travel time equates to about an 18% increase in travel time. Do that twice a day for a year and the minutes can really add up.

The point of this (besides engaging in an extremely nerdy exercise), is to not only highlight the value of shortest-path algorithms, but also the importance of choosing the correct inputs when optimizing such algorithms. Google clearly has the resources at its disposal to bring us all a much more accurate Maps interface. As an avid user, that is something I would love to see in the future.