Wednesday, December 8, 2010

The shortest path between OR jobs

Driving from my old job in the Burlington, MA area to Elmsford, NY (near my new job location at Yorktown Heights) took less than 3 hours. It seemed like a race-course full of caffeine-high jihadi drivers after all those leisurely strolls through the somnolent country roads of Maine. I got a newer GPS product (yet another Garmin) from an e-tailer. Having worked on retail pricing during the past four years, and this being a pre-Black Friday deal, I almost reflexively asked for a price match and sure enough - there was 60$ in savings to be had after pushing against some soft constraints. Since this was Garmin's latest version in the series it wasn't discounted on BF, so it turned out to be a pretty decent deal in the end.

The GPS product, on its short maiden voyage from MA to NY decided to take me through no fewer than four interstate highways: I-95, I-90, I-91, and I-84. The route seemed simpler on paper. I quickly realized that newer does not necessarily mean better. The re-routing algorithm is still ancient even though the newer one allegedly takes traffic congestion into account. To avoid extensive re-calculation of the shortest path in real time, the product continues to merely finds the quickest way to get back to plan. This is an approach typically used in airline online crew recovery ops (even though fancier global optimization algorithms have been available on paper). In general, this is not a bad idea as long as you don't wander off deep into the reservation. Forcing a recalculation enables you to recover the faster (optimal?) route, and my ETA dropped by about 10 minutes. The newer version has an "EcoRoute" option that allows you to find minimal cost paths, in addition to the standard metrics based on distance and time. Looks like you can also plan a trip having multiple intermediate nodes. That looks like a nice TSP structure. An analysis of these new features makes for an interesting post on another day.

3 comments:

  1. Are you sure that the reroute was shortest path back to plan and not shortest path? If the unit defines "shortest" in terms of time, rerouting back to an interstate might well be the revised global optimum.

    ReplyDelete
  2. Hi Paul:
    thanks for the query. It is a very interesting question that made me think twice. My conclusion is that for a non-trivial amount of time, the GPS product indeed forced me suboptimally "back to plan"

    Here's the common instance:
    Everytime i'm on I-95 from Maine to Boston, GPS asks me to go thru I-295 (Portland, ME) for about 30-40 miles, and then back to I-95. I choose to simply stay on I-95 (delaying my GPS- predicted ETA by 5-10 mins but practically not very different) and the GPS bugs me to get back to I-295. After about 3-4 such attempts at exits, it does give up and re-routes thru I-95, and the projected ETA instantly improves by a big chunk of 5-10 mins.

    This is probably not due to the fault of the algorithms; more likely it is the rules that decide when and how frequently a particular re-routing algorithm is called en-route and with what constraints. But it was never 'wildly' suboptimal. I will have more 'field' feedback after my next trip.

    I also wonder how near pareto-optimal routes are processed?

    Yesterday, it made me take an exit ramp to a highway and then back to an entry ramp rather than just go straight on an arterial road ! Presumably the ramps are considered "65mph arcs" and thus 0.1% faster in theory, but of course, practically not the optimal choice.

    ReplyDelete
  3. You're hitting on a couple of key points here. Rather than using a single criterion (say, travel time), the objective function ought to be a weighted combination of things, including perhaps a small penalty for every transition from one artery to another. There also should be a rule that says reroute only if the improvement exceeds some strictly positive threshold.

    ReplyDelete

Note: Only a member of this blog may post a comment.