Re:How UPS trucks saved millions of dollars by eliminating l...
by lorenzhs on Friday February 10, 2017 @11:50AM
(#13616774)
It's not TSP. In TSP, you have a graph and want to visit every node exactly once. Here you have a (road) graph and want to visit some set of nodes (the delivery addresses) at least once (it's okay to drive past a house where you dropped off a parcel earlier if that somehow makes the journey shorter).
Also, consumer satnav systems don't support this kind of query. You can't plug in a list of dozens of destinations and ask for the shortest path to get you to all of them, in any order.
Re:How UPS trucks saved millions of dollars by eliminating l...
by DerekL on Friday February 10, 2017 @05:17PM
(#13619400)
It reduces to a special case called the metric TSP. If going through node C is shorter than going from A to B directly, then just replace the A-to-B distance with the length of A-to-C-to-B. It's just as hard to solve as regular TSP, but easier to approximate.
Re:How UPS trucks saved millions of dollars by eliminating l...
by lorenzhs on Saturday February 11, 2017 @07:04AM
(#13622252)
Well yeah it's clearly still NP-complete. But the TSP (or variant thereof) isn't related to the routing engine at all, as the routing engine only defines the edge weights. They're fairly orthogonal problems. Logistics software needs to solve both, but consumer satnav doesn't.
It would be an interesting experiment to see how different consumer grade satnav systems compare on this pure travelling salesman problem.