One-Way Salesman Finds Fast Path Home | Hacker News Reader

One-Way Salesman Finds Fast Path Home

quantamagazine.org

82 pointsjonbaer23 comments

There's an old, nice, simple, somewhat similar piece of work by Karp: For the cities, use one of the two usual, simple, fast algorithms to find a minimum spanning tree, and then do a depth first traversal of the tree just declining to revisit a city already visited. Turns out that in Euclidean spaces (right, the symmetric problem) this simple device has some astoundingly good convergence properties as the number of cities grows. Having lots of cities is where the usual combinatorial optimization techniques, worst case, go exponential, and the work by Karp works great in just those cases.

In effect, roughly, due to the subtrees nearest the leaves, Karp's technique also works with clusters of cities maybe something like in the OP.

This [1] seems to be the paper they are referring to on arxiv.

[1] https://arxiv.org/abs/1708.04215

> The computation of the single best answer for what is known as the traveling salesman problem is famously infeasible.

I think this statement is not true. TSP can be solved to optimality when the number of cities is small^. GuRoBi and CPLEX's mixed integer solvers can solve TSPs when the number of cities is small. In fact [1] gives the largest TSPs solved. Now solving them fast is a totally different question and I feel like this distinction needs to be made

^ in a reasonable amount of time.

[1] http://www.math.uwaterloo.ca/tsp/pla85900/index.html

85,900 is a small number of cities? The US has 19,354 "incorporated places", which balloons to around 35,000 if you include unincorporated towns.

I am sorry. By small I meant more like 20 cities. You can formulate a simple optimization problem and solve it with lot of commercially available solvers if you have few cities. The point i was trying to make is that TSPs are not infeasible. They can be solved to optimality given enough time.

If I am not wrong, Concorde TSP solver which is a specialized solver, solves TSPs which have large number of cities.

An efficient solution to TSP would require an efficient solution to all instances of the problem, not an efficient solution for some instances. Most problems are easy in the small cases. And if you are solving special cases, you are solving a decidedly different problem.

>They can be solved to optimality given enough time.

I'm not sure what you mean by this. TSP is infeasible in the sense that it cannot be solved in an efficient amount of time. Naturally, it is solvable if you're given "enough time". It's not an impossible problem.

I should have worded my response better. What I meant was TSPs are intractable. But the author used the word infeasible. In optimization, infeasible and intractable convey different meanings.

You know tsp doesn't just mean cities or actual sales people right?

It can apply to lots of things like 3d printer head or other toolpath optimization and hundreds of other problems maybe millions

Obviously -- but that's not what the article is arguing is impossible.

Infeasible, not impossible.

Also, there are lots of specific configurations of cities for which an optimial solution can be found in a tractable amount of time -- it's only the general case that is the problem, and there's some debate about how "degenerate" real world examples are. In "well-behaved" cases, a good approximate answer will be the answer; in almost all cases, the differences between a good estmate and the correct solution is small relative to the total path (and so the difference is of limited importance).

I often find that optimization problems suffer from trying to optimize the general problem rather than using the constraints present in the real world.

TSP is similar to Turing machines and the halting problem -- in practice, it really doesn't matter.

Why can't the asymmetric version of TSP be re-coded into TSP but with twice the number of nodes, each of which have a "distance" of zero to their counterparts?

Ahhh, I think I've just noticed the fatal flaw here - it makes the graph directed. Perhaps fiddling with the notion of +0 and -0 might fix it ... 8)

It can, see eg Bill Cook's "in pursuit of the traveling salesman." I've also wondered how this approximation algorithm relates to the standard asymmetric to symmetric transformation. I should read the paper I guess.

It appears to me that what they've accomplished is to devise an algorithm that can, in polynomial time, find a solution to the ATSP with cost no worse than a constant multiple of the optimal solution.

Can any domain experts confirm or deny my interpretation?

This is correct.

Worth noting here is that the approximation factor here is 5500. (I.e., the algorithm is only guaranteed to return a route whose length is no more than 5500 times that of the optimal route.) Much bigger than 3/2! But apparently it's the first polynomial-time constant-factor approximation algorithm at all for it, so...

Any applications for this algorithm, besides the one mentioned in the article?

Likely to be applications in ML applied to optimized planning. For example, rapidly changing environments in littoral areas require reasonably efficient route planning of asymmetric routes.

The situation I've had to apply the travelling salesman problem to, and probably the one its most applicable in, was delivery logistics. Given a list of deliveries that need to be made, and the time windows in which they'd been booked, what is the optimal order in which to make those deliveries?

This problem gets particularly interesting when being applied to deliveries between 4pm and 10pm in London, because you have to start taking into account things like rush hour traffic, road closures, and football matches. You also occasionally have to make tradeoffs like deciding whether it's better to deliver 4 small orders a little late, or one large order really late - for those situations we could reschedule those orders and allow the routing system to generate a new route.

I know this is grossly simplifying but it seems the algorithm works exactly how a sane delivery company would work.

Imagine a company in Paris that has multiple UK deliveries coming up. First let's lump together all the deliveries in London. Then let's lump together all the deliveries in South London, then let's lump together everything in neighborhood Foo in South London. Then the routes you worry about are your longest ones, like getting to London or into London in the first place. This makes the assumption that it's quicker to get from a spot in South London to neighborhood Foo than it is from South London to say Leeds.

It didn't appear to me from this article that any consideration was given to large late orders or what you mentioned, but that would up the complexity.

I've been looking at TSP recently to solve a problem I have. I have a pen plotter (AxiDraw) that moves a pen based on a drawing, but I'd like to optimize the drawing order to reduce the time it spends moving the arms with the pen up between strokes.

Yes, that's a typical application for TSP. But the article is about an "asymmetrical TSP".

This reminds me of Google's public transport routing algorithm.

https://research.googleblog.com/2016/03/an-update-on-fast-tr...

Reply on news.ycombinator.com