7 ms·

The optimal road trip across the U.S. according to machine learning

30 points by ashish01 12y ago

WalterGR 12y ago
If you're wondering why the route has some 'strange' segments (why get off I-10 to head down Orlando way if you're going to drive to Jacksonville later?): The link goes to the "Major U.S. landmarks" road trip. Other trips (including across Canada, South America, and Europe) are listed here: http://rhiever.github.io/optimal-roadtrip-usa/ http://rhiever.github.io/optimal-roadtrip-usa/
- dalke 12y ago
  When it came out a few weeks back, I noticed that it went to the South Rim of the Grand Canyon, which is the popular one. Going to the North Rim would save over 100 miles of driving. To be sure, the South Rim has the better view. It also can't be done in winter, as its route through Yellowstone isn't open then.
panic 12y ago
What does "machine learning" mean here? How does the algorithm guarantee the trip is optimal?
- kahoon 12y ago
  And optimal according to what criteria? Length, safety, sightseeing?
- JASchilz 12y ago
  In general, "machine learning" means that an algorithm did it, and that the algorithm engages in some analysis of the problem space or the solution space. Usually that analysis involves an iterative or repetitive element: making several tries and modeling what makes a try good or bad, making a try and then changing the solution tiny bits to find a try that's slightly better, etc. And "good" or "bad" is determined according to a human-provided rubric (eg: +1000 points for every sight seen, -1 point for every mile driven, -10 points for every day taken, etc.) Unless the problem is very constrained, there usually is no guarantee of optimality; here there is probably no guarantee of optimality. It might be "locally" optimal, in that there might be no better trip that differs from this one by only a tiny bit. And, no, "machine learning" here doesn't mean the enterprise and establishment of "Machine Learning", just some algorithm that the author used.
- j2kun 12y ago
  I'm almost certain it was used incorrectly in this case. The correct term is "combinatorial optimization."
idlewords 12y ago
This is clearly not the optimal road trip, since it passes through Nebraska.
- wglb 11y ago
  But it does go on US2 in Montana, which is one of my criteria for an "optimal" trip through US. But insofar as Nebraska is concerned, I have relatives there, and during one family reunion, we all went to the 4th of July parade in Hoskins. The large painted sign said "Parade at 8 am, pancake breakfast at 8:30". Not a large town. But then I grew up 6 miles outside of a town of 3000, so I am not all that in favor of large towns.
- vgabios 12y ago
  Also Indiana, for its eateries may now legally refuse to serve customers that use machine learning for religous reasons.
  - jpatokal 12y ago
    This is presumably not the intended parsing of that sentence, but "machine learning for religious reasons" sounds like a great premise for a sci-fi novel.
    - vgabios 12y ago
      Expect 2015-2017 to have a number of AI/ML-themed movies as screenplays are likely now making the rounds.
  - coldtea 12y ago
    Or any state which still has the death penalty, that actually KILLS people, even teenagers in some cases, including gays. But I guess that's not as glamorous as the latest popular cause...
- jessaustin 12y ago
  Nebraska is a great place for driving really fast. One time while passing through on my way to Montana I hit 130 mph in my Integra. I don't really have anything else to say for Nebraska.
Sanddancer 12y ago
Very curious about the decision metric for "major landmark" here. The San Benito County mark, for example, leads you to a dirt road in the middle of nowhere, and the major point for Delaware is just Delaware. Neither of those seem to fit a reasonable metric for a major landmark.
- feedjoelpie 12y ago
  So, I get what you're saying, but the particular locations are completely irrelevant to the math/CS.
- coddingtonbear 12y ago
  Seconded; I mean: I can understand why somebody who was into nuclear tourism might want to swing past the Hanford Site in Washington, but I'd bet that the majority of Americans might rather steer clear.
  - cdcarter 12y ago
    Hanford Site beating out the Space Needle for tourism is very interesting.
- smcg 12y ago
  I think it's trying to pass through all 48 states, with some random landmarks and cities thrown into the mix.
andrenatal 12y ago
Ok. Following this "algorithm", California coast it is not interesting. I pass it.
- narrator 12y ago
  Yeah, and the Hanford Site in Washington is a tourist destination. Pass!
mceoin 12y ago
The cable car museum? Ok, that makes sense for SF. http://www.cablecarmuseum.org/info.html http://www.cablecarmuseum.org/info.html
stox 12y ago
WTF! Skips Chicago? Made a huge detour for the Wright Bros.
- acconrad 12y ago
  And LA, San Diego, Seattle, Miami...basically every major city outside of the north east (shy of Portland and San Francisco). Very strange indeed.
pyk 12y ago
Careful -- this is only locally optimal! You can do better :). [1] is the proven globally optimal solution of a very similar problem from one of the foremost experts in the TSP, Bill Cook at U of Waterloo. It is solvable in less than a second on your iPhone [2] -- yes your iPhone can solve a TSP to "true" optimality. [1] http://www.math.uwaterloo.ca/tsp/usa50/road.html http://www.math.uwaterloo.ca/tsp/usa50/road.html [2] https://twitter.com/wjcook/status/575762813345480705 https://twitter.com/wjcook/status/575762813345480705
- rtkwe 12y ago
  Also the route is just wrong at some points like the Delaware stop being 1+ hour south from where it's supposed to be due to Google Maps spitting out a weird result for New Castle Historic District.
j2kun 12y ago
I'm being pedantic, but the problem being solved here is not a learning problem, but a combinatorial optimization problem.
- bengali3 12y ago
  agreed, but you're too early. The current buzzword your looking for to put in your marketing material is 'Machine Learning'. Revisit 'Combinatorial Optimization', possibly combined with 'Cloud' again in a few years. Edit: hey great post of yours btw. http://jeremykun.com/2014/09/29/hybrid-images/ http://jeremykun.com/2014/09/29/hybrid-images/
jjp 12y ago
Not clear to me is whether the machine learning is for the destinations, the sequencing or am I routed on scenic roads?
nthcolumn 12y ago
Skips LA - clever girl.

30 points by ashish01 12y ago

If you're wondering why the route has some 'strange' segments (why get off I-10 to head down Orlando way if you're going to drive to Jacksonville later?): The link goes to the "Major U.S. landmarks" road trip. Other trips (including across Canada, South America, and Europe) are listed here: http://rhiever.github.io/optimal-roadtrip-usa/ http://rhiever.github.io/optimal-roadtrip-usa/

dalke 12y ago
When it came out a few weeks back, I noticed that it went to the South Rim of the Grand Canyon, which is the popular one. Going to the North Rim would save over 100 miles of driving. To be sure, the South Rim has the better view. It also can't be done in winter, as its route through Yellowstone isn't open then.

panic 12y ago

What does "machine learning" mean here? How does the algorithm guarantee the trip is optimal?

kahoon 12y ago
And optimal according to what criteria? Length, safety, sightseeing?
JASchilz 12y ago
In general, "machine learning" means that an algorithm did it, and that the algorithm engages in some analysis of the problem space or the solution space. Usually that analysis involves an iterative or repetitive element: making several tries and modeling what makes a try good or bad, making a try and then changing the solution tiny bits to find a try that's slightly better, etc. And "good" or "bad" is determined according to a human-provided rubric (eg: +1000 points for every sight seen, -1 point for every mile driven, -10 points for every day taken, etc.) Unless the problem is very constrained, there usually is no guarantee of optimality; here there is probably no guarantee of optimality. It might be "locally" optimal, in that there might be no better trip that differs from this one by only a tiny bit. And, no, "machine learning" here doesn't mean the enterprise and establishment of "Machine Learning", just some algorithm that the author used.
j2kun 12y ago
I'm almost certain it was used incorrectly in this case. The correct term is "combinatorial optimization."

idlewords 12y ago

This is clearly not the optimal road trip, since it passes through Nebraska.

wglb 11y ago
But it does go on US2 in Montana, which is one of my criteria for an "optimal" trip through US. But insofar as Nebraska is concerned, I have relatives there, and during one family reunion, we all went to the 4th of July parade in Hoskins. The large painted sign said "Parade at 8 am, pancake breakfast at 8:30". Not a large town. But then I grew up 6 miles outside of a town of 3000, so I am not all that in favor of large towns.
vgabios 12y ago
Also Indiana, for its eateries may now legally refuse to serve customers that use machine learning for religous reasons.
- jpatokal 12y ago
  This is presumably not the intended parsing of that sentence, but "machine learning for religious reasons" sounds like a great premise for a sci-fi novel.
  - vgabios 12y ago
    Expect 2015-2017 to have a number of AI/ML-themed movies as screenplays are likely now making the rounds.
- coldtea 12y ago
  Or any state which still has the death penalty, that actually KILLS people, even teenagers in some cases, including gays. But I guess that's not as glamorous as the latest popular cause...
jessaustin 12y ago
Nebraska is a great place for driving really fast. One time while passing through on my way to Montana I hit 130 mph in my Integra. I don't really have anything else to say for Nebraska.

Sanddancer 12y ago

Very curious about the decision metric for "major landmark" here. The San Benito County mark, for example, leads you to a dirt road in the middle of nowhere, and the major point for Delaware is just Delaware. Neither of those seem to fit a reasonable metric for a major landmark.

feedjoelpie 12y ago
So, I get what you're saying, but the particular locations are completely irrelevant to the math/CS.
coddingtonbear 12y ago
Seconded; I mean: I can understand why somebody who was into nuclear tourism might want to swing past the Hanford Site in Washington, but I'd bet that the majority of Americans might rather steer clear.
- cdcarter 12y ago
  Hanford Site beating out the Space Needle for tourism is very interesting.
smcg 12y ago
I think it's trying to pass through all 48 states, with some random landmarks and cities thrown into the mix.

andrenatal 12y ago

Ok. Following this "algorithm", California coast it is not interesting. I pass it.

narrator 12y ago
Yeah, and the Hanford Site in Washington is a tourist destination. Pass!

mceoin 12y ago

The cable car museum? Ok, that makes sense for SF. http://www.cablecarmuseum.org/info.html http://www.cablecarmuseum.org/info.html

stox 12y ago

WTF! Skips Chicago? Made a huge detour for the Wright Bros.

acconrad 12y ago
And LA, San Diego, Seattle, Miami...basically every major city outside of the north east (shy of Portland and San Francisco). Very strange indeed.

pyk 12y ago

Careful -- this is only locally optimal! You can do better :). [1] is the proven globally optimal solution of a very similar problem from one of the foremost experts in the TSP, Bill Cook at U of Waterloo. It is solvable in less than a second on your iPhone [2] -- yes your iPhone can solve a TSP to "true" optimality. [1] http://www.math.uwaterloo.ca/tsp/usa50/road.html http://www.math.uwaterloo.ca/tsp/usa50/road.html [2] https://twitter.com/wjcook/status/575762813345480705 https://twitter.com/wjcook/status/575762813345480705

rtkwe 12y ago
Also the route is just wrong at some points like the Delaware stop being 1+ hour south from where it's supposed to be due to Google Maps spitting out a weird result for New Castle Historic District.

j2kun 12y ago

I'm being pedantic, but the problem being solved here is not a learning problem, but a combinatorial optimization problem.

bengali3 12y ago
agreed, but you're too early. The current buzzword your looking for to put in your marketing material is 'Machine Learning'. Revisit 'Combinatorial Optimization', possibly combined with 'Cloud' again in a few years. Edit: hey great post of yours btw. http://jeremykun.com/2014/09/29/hybrid-images/ http://jeremykun.com/2014/09/29/hybrid-images/

jjp 12y ago

Not clear to me is whether the machine learning is for the destinations, the sequencing or am I routed on scenic roads?

nthcolumn 12y ago

Skips LA - clever girl.