A courier guy stuck with NP Problem

http://functionspace.org/articles/25/A-courier-guy-stuck-with-NP-Problem-

by aditgupta • 13 years ago

1 1 13 years ago

dalke• 13 years ago

I was hoping that by using "courier" instead of "traveling salesman" that this would be a real-world case of needing a Hamiltonian cycle. However, it identical to the TSP in having the non-realistic prohibition on visiting an intermediate city twice.

Specifically, this recasting of the TSP says "revisiting any city is just wasted effort."

In real life, a courier may visit the same city twice. As a trivial example, a courier starting in San Francisco with deliveries to San Rafael, Novato, Petaluma, Rohnert Park, and Santa Rosa (all north of San Francisco on US 101) will visit all of the intermediate cities on the way back to San Francisco. Other routes, while possible, take more time and fuel and are wasted effort.

And oddly, the term "Travelling salesman problem" doesn't even exist on the page.

A courier guy stuck with NP Problem

Related Stories