News for hackers. Stuff that matters.

A comment on The software routing 260,000 grocery deliveries a week. Parent comment

Re:The software routing 260,000 grocery deliveries a week by alfla on Tuesday August 15, 2017 @12:39PM (#15019783)
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/). 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).

[ Parent | on HN ]
Re:The software routing 260,000 grocery deliveries a week by n4r9 on Wednesday August 16, 2017 @04:25AM (#15025824)
The 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.
[ Parent | on HN ]