4 ms·
The article is quite vague on the problem formulation, other than being somewhat equivalent to the TSP, so I'm just going to speculate a bit onto how they solve
by alfla 9y ago
The article is quite vague on the problem formulation, other than being somewhat equivalent to the TSP, so I'm just going to speculate a bit onto how they solve it. The TSP can be formulated as an Integer Linear Program (http://examples.gurobi.com/traveling-salesman-problem/ http://examples.gurobi.com/traveling-salesman-problem/). This type of problem is very well studied, and several free and commercial problem formulation tools and solvers are available, some that scale to thousands of variables.
They also probably decouple their problem into disjoint regions before solving it, to reduce the dimensionality of the problem(s).
- n4r9 9y agoThe article says that their solution is in house, and they don't seem to be using integer linear programming. My guess is that they start with a random feasible solution using a fast greedy heuristic, then iteratively improve it using a simulated annealing process.