I just returned from a trip to Washington, DC. My wife was down there for a meeting with some government officials, so I decided to tag along with our daughter and do some sightseeing. Her job is fairly stressful, and what with me chasing down fun start-ups instead of good pay, I do what I can to make it easier.
We have a TomTom One, a great device, although its route optimization algorithms, and the algorithms used by every other route planning application out there, have always left me disappointed. The New Jersey to DC corridor always makes the deficiencies particularly keen, since tolls almost equal the fuel bill. Here’s the problem in a nut-shell. On the way down, time was more important than total cost, and the tolls were being expensed. On the way back, no expense account, since my wife was staying and taking the train back. I had a lot of time and preferred to avoid the toll roads. The New Jersey Turnpike, you see, has a toll-free highway right next to it, or since we live towards the West end of the state, taking I-95 through Philadelphia is slightly shorter but also slightly slower, and free. The TomTom gives us an option for avoiding toll roads entirely. That’s no good, since the toll roads through Maryland and Delaware can only be avoided with substantial delays, unlike the Delware Memorial Bridge and the NJ Turnpike. You can ding sections of the Turnpike, but its a slow process.
It would be nice if I could enter a cost function whose input is distance, time, and fees (tolls): c(d,t,f). Tolls, which on the surface seem trivial ($=$), are not because in some cases they are being expensed, as with the way down to DC. Finding the best route involves minimizing the function. TomTom has a simpler approach. Each road segment has a constant cost, either the time it takes to travel it, or the distance, corresponding to the two options for the fastest route, or the shortest route. If you say “no tolls”, it removes those from the set. A more flexible cost function would slow things down a bit, but in this case I think not noticably since the form of the function could be constrained to a very simple linear form with three coefficients.
Humans are such rotten optimizers, and the number of optimization problems we deal with is immense. Its sad that in an area where computers can help, they do only a mediocre job. There were other optimization problems to tackle that they wouldn’t be so helpful for: do we take my wife’s Lexus, with great safety features, high reliability, and a crappy 29 miles per gallon, or my aging Jetta, with mediocre reliabilty, no working radio, and 50 miles per gallon, given also that diesel is slightly more expensive right now at most stations, but my wife’s car has timing issues when it doesn’t get 93 octane, and I have that slow leak in my right rear tire from a nail that was too deep for me to dig out easily with some pliers and patch, and I’ve delayed purchasing new tires since they already have 60k miles on them and aren’t worth patching, so I just pump them up occasionally with a bike pump that I keep in my trunk. Speaking of tires, wow, that’s a tough one: low rolling resistance, performance in wet or snow, how long they will last, cost, so many factors and tradeoffs. I’m amazed at the compounds they use however, good performance in any temperature I’ve encountered, good stiction, low resistance. Anyhow you get the picture.
Maybe someone at Google Maps will do a good job with route optimization. They have plenty of smart people who ought to understand there’s a better way. Most people won’t want to enter a cost function, but I do. UPS is already there, they even factor in left versus right turns.
RSS 
March 17, 2009 at 1:50 am
Certainly the biggest hurdle here would be in interface design for how to input the cost function without either flabbergasting your less math/cs included users or be forced to reveal too much of the inner workings of the routing algorithm. I suppose the former is of much more concern than the latter since quality maps are probably the bigger difference between brands than the (most likely) stock algorithms.
Secondly, do you really want to input a cost function for every trip? Your example points out the fact that there are external factors that can change even if your start and end points do not. Today I would like to take the cheap scenic route. Tomorrow, i’m in a rush to get to the airport, etc. You could save past cost functions but I’m nor sure they’d be as reusable as you might think.
Finally, I’m going to call you on the premise that you really could enter a good cost function. People are notoriously bad at providing cost functions and utility metrics. Very few people could come up with a mathematical formula describing which combination of factors (tolls, time, distance, etc) actually work out to be more/less/equally important to them. I’m not doubting you personally could do this in general but I do think that you or anyone else with a similar background would have a harder time than you think. And once you throw this at the masses, even a 1% utilization would be a pipe dream.
March 17, 2009 at 7:28 am
That’s a great reality check, thanks. Here’s a simple option though: input a cost per mile. You can use the government rate, or estimate it yourself if you have a more or less efficient or cheap vehicle. Then you can search for the fastest, or the cheapest reasonable route with some built-in cost factor for time. Otherwise you’ll usually just get the shortest and be braking for neighborhood street hockey. The TomTom has always asked me if I want the fastest or the shortest, and the shortest route I have never found to be useful. Maybe its designed for pedestrians who happen to have a cigarette lighter somewhere on their person. It also might have some social advantage in showing the real cost of the trip. If I had been alone, it would have been clear that the train was cheaper. Google Maps by the way has an extremely useful feature for trip planning: it allows you to drag segments around when you want to avoid a particular segment is bad.
March 18, 2009 at 2:50 am
First, I absolutely love Google Maps path dragging (and requisite anchoring). It’s amazingly simple to use, despite an underlying implementation which is clearly impressive (recalculating route portions on the fly VERY quickly while also generating images of the route on the server side for huge numbers of users). I’m not sure personal GPS units (TomTom and the like) could easily do this given their much more limited interface and input mechanisms. But it might be possible in the near future with iphone-like multitouch interfaces. Moore’s Law eventually wins all these discussions.
Cost per mile would probably work well in the business case where someone else has already indicated a certain cost they are willing to reimburse you for. For average users, perhaps a simple database of typical city/highway MPG averages for your car (inputs if your car is newer) combined with an input for current gas prices could aim for an estimate that minimized gasoline costs.
After thinking longer about my earlier comments, perhaps a set of common, pre-defined cost functions could be employed. The user could select those either by some descriptive name or even by answering a few discriminating questions like those 20 questions electronic games you see now (Are you in a hurry?, Do you want to avoid tolls? Which is more important to you, cost or speed?, etc). Those questions could be designed to quickly choose a “better” cost function for a particular trip. The questions could be optional, with the function being decided by the normal fastest/shortest question.
I still think that the number of people who could consistently and competently describe their current preferred cost function is so small that the major manufacturers would lose money even trying to implement such a feature unless it somehow proved useful for their own debugging/development process.
Also, I think most of the GPS units I have used/played with only have street data and probably speed limits, but not things like stoplight locations, toll prices (as you mentioned, more important that toll existence), typical traffic density, etc. All of that extra data could provide even better weighting (as well as more dynamic weighting based on time of day and user preferences). Higher end units already come with access to real time traffic data and the like, so perhaps its also just a mater of time before all units do.
Also, the types of data we’re talking about (such as toll prices) probably just aren’t being compiled/tracked with as much accuracy as roads have been, making what is available mostly unusable. Google Maps for instance makes use of things like real time traffic and public transit schedules but only in a very limited set of major cities where such data is available. That works for a free service, but customers paying for a TomTom or Garmin are likely to just be annoyed if they get told it comes with some cool feature only to discover that it only works in San Francisco.
April 4, 2009 at 6:38 am
Just one idea to throw into the mix which I don’t think would be too complex to implement and would be fairly straightforward for users to understand: How about allowing the user to set a maximum amount that can be spent on tolls. I find the “avoid all toll roads” doesn’t offer sufficient granularity – maybe I’d be willing to go two junctions on a toll road (or pay to cross a river at a certain toll bridge) and pay 5 euros if it meant I saved 200km compared to the most optimised alternative route.
Extending the idea a little we could set a maximum cost for a trip, factoring in fuel mileage, notional wear and tear costs and toll costs. Or simply have a setting on the device to minimise that total cost, when necessary.
June 30, 2009 at 8:37 am
Garmin Nuvi 265WT
Garmin’s nüvi 265WT improves upon its 200-series predecessors by adding free real-time traffic updates from Navteq (for the life of the device) as well as Bluetooth connectivity to your cell phone. Other significant improvements in the 2×5 series include a predictive technology that provides faster satellite lock, a redesigned screen with more information, terrain maps, and an exciting new photo navigation feature. The 265WT provides complete maps for North America and the handy Text-to-Speech feature, so you get turn-by-turn spoken directions with the real names of streets (e.g. “turn left in 50 feet at Nebraska Way”, rather than merely “turn left in 50 feet”).