As hard as it might be, it's a solved problem. FedEx is doing it. Uber is doing it. And I'm sure there are plenty of others out there, I just don't know about other industries.
"It's a solved problem"? I'm not sure what that even means. There are algorithms for finding solutions, and if you have enough time and storage space, you can solve it.
If I'm understanding the relevant WP articles correctly, the travelling salesman problem is not solved, since a solution for it would also imply a solution for all NP-complete problems. What these companies have therefore cannot be an absolute solution, but rather an optimal approximation which may or may not (but probably isn't, and probably can't be proved to be in polynomial time) equal to the absolute solution.
Of course, I don't have much firsthand knowledge of computational complexity myself, so someone else who know better should call me on any nonsense above. =D
Since you decided to nitpick: travelling salesman problem (i.e. finding an minimal route) is a solved problem as in "for decades we have known algorithms to find a minimal path and we teach them to CS grads".
What you refer to is the fact that the computational complexity (i.e. time to finish it) of known algorithms rises exponentially with the size of the problem and exponentially is a code word for "really, really quickly". It just takes too much time to find the minimal path if your graph is big.
What I meant, however, is that the problem has been solved in practice. When you ask Google how to drive from SF to NY, it'll give pretty good answer in milliseconds. Is it an optimal answer? It might be, it might be not, but it's a very good answer. Getting slightly better answer is not worth the computational time because it won't make a difference in practice in your trip.
Similarly, a car rental company doesn't have to schedule things optimally, they just have to schedule things really good, and that's possible with much less computationally expensive algorithms. The big win is when you go from "no optimization" to "good optimization", not from "good optimization" to "perfect optimization".
> What I meant, however, is that the problem has been solved in practice. When you ask Google how to drive from SF to NY, it'll give pretty good answer in milliseconds. Is it an optimal answer? It might be, it might be not, but it's a very good answer. Getting slightly better answer is not worth the computational time because it won't make a difference in practice in your trip.
That's not the traveling salesman problem, it's the shortest path problem, for which polynomial-time algorithms are well-known and taught to first-year computer-science students. (To be fair, driving directions do require coming up with good edge weights on the graph composed of the American highway system, but once you've got weights, you can run Dijkstra's algorithm and you're done. That's probably not how GMaps driving directions work, but the point is that driving directions are not TSP.)
To be sure, I wasn't suggesting the problem hadn't been practically solved, and I understand quite well that beyond a certain point, there's very little incentive in improving the solution any further.
In retrospect, I probably should have kept my thoughts to myself, and I probably deserve the downvote or two that I got for not doing so. =)
