6 ms·
One-Way Salesman Finds Fast Path Home
- rocqua 9y agoThis [1] seems to be the paper they are referring to on arxiv. [1] https://arxiv.org/abs/1708.04215 https://arxiv.org/abs/1708.04215
- amelius 9y agoAny applications for this algorithm, besides the one mentioned in the article?
- CharlesMerriam2 9y agoLikely 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.
- jon-wood 9y agoThe 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.
- fred_is_fred 9y agoI 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.
- paulgb 9y agoI'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.
- amelius 9y agoYes, that's a typical application for TSP. But the article is about an "asymmetrical TSP".
- nagVenkat 9y ago> 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 http://www.math.uwaterloo.ca/tsp/pla85900/index.html
- deleted 9y ago[deleted]
- excalibur 9y ago85,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.
- nagVenkat 9y agoI 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.
- Retra 9y agoAn 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.
- graycat 9y agoThere'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.
- antoncohen 9y agoThis reminds me of Google's public transport routing algorithm. https://research.googleblog.com/2016/03/an-update-on-fast-transit-routing-with.html https://research.googleblog.com/2016/03/an-update-on-fast-tr...
- scott00 9y agoIt 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?
- sanxiyn 9y agoThis is correct.
- gerdesj 9y agoWhy 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)
- Tarrosion 9y agoIt 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.
- Sniffnoy 9y agoWorth 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...