Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The software routing 260,000 grocery deliveries a week

ocadotechnology.com

Post reply on HN
Print view View original

1–10 of 41 posts

Re: The software routing 260,000 grocery deliveries a week

#3

Post by coldcode »

This is a similar problem to figuring out search results when you try to find an airline reservation. It's a problem people have been working on for almost 50 years and it still works, although there are a lot of likely shortcuts. I also remember we had some kind of system that tried to optimize pricing and schedules for airlines which which ran for days sometimes (this was in 2000 or so). I think modern hardware is much better and allow algorithms that are much more capable. I wonder how you test something this complex that is never actually done; how do you know its working optimally (or at least acceptably)?

Re: The software routing 260,000 grocery deliveries a week

#4

Post by sbrother »

Zizizizz wrote: post #2

For someone quite interested in these kind of problems, what's the current best practice for solving these kind of problems? Not on this scale but still large enough that Google's built-in api for solving it (only 25 points allowed) can't do it.

I did something similar for a client about 4 years ago and used simulated annealing to reasonable success. I would be interested to know if there are better options now!

Re: The software routing 260,000 grocery deliveries a week

#5

Post by paulsutter »

Zizizizz wrote: post #2

For someone quite interested in these kind of problems, what's the current best practice for solving these kind of problems? Not on this scale but still large enough that Google's built-in api for solving it (only 25 points allowed) can't do it.

99% of their code will be ordinary CRUD plumbing, dealing with orders and integrating with other systems. The algorithmic code is the fun part, and they've had years to tune it.

This is just self-congratulatory PR, trying to persuade potential investors that's they're a hard tech company.

Re: The software routing 260,000 grocery deliveries a week

#6

Post by owaislone »

Zizizizz wrote: post #2

For someone quite interested in these kind of problems, what's the current best practice for solving these kind of problems? Not on this scale but still large enough that Google's built-in api for solving it (only 25 points allowed) can't do it.

We have an in house system built from ground up in Python and use ortools (https://github.com/google/or-tools) to power the core of the algorithms.

Re: The software routing 260,000 grocery deliveries a week

#7

Post by strongai »

Zizizizz wrote: post #2

For someone quite interested in these kind of problems, what's the current best practice for solving these kind of problems? Not on this scale but still large enough that Google's built-in api for solving it (only 25 points allowed) can't do it.

I think it depends if you're interested in knowing how to solve these problems, or simply in solving them. If the latter, there's a bunch of commercial solvers out there. I won't name any for fear of an adverse reaction :0) but a trawl through the first page of Google results for 'optimization solvers' would probably work.

Re: The software routing 260,000 grocery deliveries a week

#8

Post by alfla »

Zizizizz wrote: post #2

For someone quite interested in these kind of problems, what's the current best practice for solving these kind of problems? Not on this scale but still large enough that Google's built-in api for solving it (only 25 points allowed) can't do it.

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).

Post reply on HN