[travisjungroth]

Optimal is overblown for business problems in general. Knowing there’s a mathematically optimal solution, people want it. Even if it’s practically impossible to get. It feels like if you have the optimal, you don’t have to consider trade offs (not usually true).

Having a solution within 1% of optimal with ten nines of confidence is usually indistinguishable.

Anyone ever notice how these CS problems are rarely famous business problems? It’s because the pure problems don’t usually matter and the approximate versions are usually quite easy. You almost never need the shortest route for a salesman, or need to pick a secretary with no chance of going back.

[baq]

I'm quite convinced that if you had a 1% better solution to the salesman problem than what fedex or ups currently have, they'll pay good money, though :)

[theamk]

I would not be so sure.

What's the point of the theoretically perfect solution when the travel times are so unpredictable? The truck stops are 3-5 minutes apart on average (according to random reddit comment [0]), 1% of that is 3 seconds. Meanwhile a single missed light (say because some other vehicle was driving slow or UPS driver was guided into non-familiar route) can add more than a minute.

So something like a better way to arrange packages in truck, or better traffic preidiction model, would be much more useful than any TSP improvements.

[0] https://www.reddit.com/r/UPS/comments/89zw0h/how_long_does_o...

[ilyagr]

No individual truck would notice the difference. But averaged over many trucks and many days, it should result in a measurable change in gas spending.

[adwn]

The problem is that in practice, you don't have complete information, and the information you have is slightly incorrect. You also don't have a complete model, and the model you have is slightly incorrect.

[travisjungroth]

Throw on a few more decimal places if you like. The point is that in the physical world, “best” isn’t usually categorically different from “extremely close to best with high probability”.