4 ms·

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 e

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.

sbrother 9y ago
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!
paulsutter 9y ago
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.
- joshvm 9y ago
  Ocado is an interesting case. Their public line is that they're a technology company that happened to end up delivering groceries. They invest a lot in automation and robotics - definitely a hard tech company: http://www.gizmodo.co.uk/2017/02/inside-ocado-discover-the-hidden-robotic-intelligence-behind-your-online-shopping/ http://www.gizmodo.co.uk/2017/02/inside-ocado-discover-the-h... This is not a vapourware start-up, they've been leading the grocery delivery business in the UK for years. That said, they have the same problem as Amazon in that they invest so much into RnD that they're not terribly profitable (about £10M on a $1Bn turnover). That said, in this particular example I don't know how much their solution differs from Royal Mail (which uses fixed routes) or people like DHL, Fedex, et al. Routing isn't exactly a new problem and courier companies presumably have always had a lot of people working in operations research.
  - alexvoica 9y ago
    This gives a comparison between various developers of routing software, including Ocado https://www.technologyreview.com/s/608640/inside-the-increasingly-complex-algorithms-that-get-packages-to-your-door/ https://www.technologyreview.com/s/608640/inside-the-increas...
  - noir_lord 9y ago
    The missus uses Ocado, they really have their shit together in the UK on the logistics side (a field I work in but not groceries), the deliveries are on time, the process is slick and professional and the drivers are polite and helpful. She swears by them, I mostly swear at the bill.
- caoilte 9y ago
  Or to try and persuade techies to come and work for them on more CRUD plumbing.
owaislone 9y ago
We have an in house system built from ground up in Python and use ortools (https://github.com/google/or-tools https://github.com/google/or-tools) to power the core of the algorithms.
- Zizizizz 9y ago
  Is there any chance I could send you an email or chat with you further about this? I've been using the ortools python package and while it works, I've found support hard to find and would just like to chat with someone about it. I'm an academic and would love to talk if you have the time.
strongai 9y ago
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.
- Zizizizz 9y ago
  more about the how is what interests me. I just find it fascinating. I've tried nearest neighbour, ant colony and simmulated annealing thus far (Or read about them and tweaked some code)
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 ago
  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.
michaelt 9y ago
There are a few commercial options available, with different levels of complexity, performance and price. Depends on whether you need to support multiple vehicles with several deliveries on each, specific delivery time windows, and things like that. For example, Oracle sell a product called 'Real Time Scheduler' [1]. Google finds me a bunch of other products too, but I haven't looked at them in depth. The off-the-shelf software can deal with tens to low hundreds of orders per solution, - which can scale reasonably well if you're willing to divide your service area with boundaries you can't optimise across. Ocado built a custom system which can support more orders with fewer boundaries; this offers better routing efficiency, which is important as delivery efficiency is a key cost driver. If your business does something like, say, washing machine repair your time-per-customer might be dominated by repair time rather than travel time; in that case you might be able to operate a nationwide business on off-the-shelf software. The underlying algorithm in Ocado's system is based on simulated annealing [2] - although those precise words don't seem to have made it into the article! [1] http://www.oracle.com/us/solutions/scm/service-optimization-suite-294193.html http://www.oracle.com/us/solutions/scm/service-optimization-... [2] https://en.wikipedia.org/wiki/Simulated_annealing https://en.wikipedia.org/wiki/Simulated_annealing

sbrother 9y ago

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!

paulsutter 9y ago

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.

joshvm 9y ago
Ocado is an interesting case. Their public line is that they're a technology company that happened to end up delivering groceries. They invest a lot in automation and robotics - definitely a hard tech company: http://www.gizmodo.co.uk/2017/02/inside-ocado-discover-the-hidden-robotic-intelligence-behind-your-online-shopping/ http://www.gizmodo.co.uk/2017/02/inside-ocado-discover-the-h... This is not a vapourware start-up, they've been leading the grocery delivery business in the UK for years. That said, they have the same problem as Amazon in that they invest so much into RnD that they're not terribly profitable (about £10M on a $1Bn turnover). That said, in this particular example I don't know how much their solution differs from Royal Mail (which uses fixed routes) or people like DHL, Fedex, et al. Routing isn't exactly a new problem and courier companies presumably have always had a lot of people working in operations research.
- alexvoica 9y ago
  This gives a comparison between various developers of routing software, including Ocado https://www.technologyreview.com/s/608640/inside-the-increasingly-complex-algorithms-that-get-packages-to-your-door/ https://www.technologyreview.com/s/608640/inside-the-increas...
- noir_lord 9y ago
  The missus uses Ocado, they really have their shit together in the UK on the logistics side (a field I work in but not groceries), the deliveries are on time, the process is slick and professional and the drivers are polite and helpful. She swears by them, I mostly swear at the bill.
caoilte 9y ago
Or to try and persuade techies to come and work for them on more CRUD plumbing.

owaislone 9y ago

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

Zizizizz 9y ago
Is there any chance I could send you an email or chat with you further about this? I've been using the ortools python package and while it works, I've found support hard to find and would just like to chat with someone about it. I'm an academic and would love to talk if you have the time.

strongai 9y ago

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.

Zizizizz 9y ago
more about the how is what interests me. I just find it fascinating. I've tried nearest neighbour, ant colony and simmulated annealing thus far (Or read about them and tweaked some code)

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

michaelt 9y ago

There are a few commercial options available, with different levels of complexity, performance and price. Depends on whether you need to support multiple vehicles with several deliveries on each, specific delivery time windows, and things like that. For example, Oracle sell a product called 'Real Time Scheduler' [1]. Google finds me a bunch of other products too, but I haven't looked at them in depth. The off-the-shelf software can deal with tens to low hundreds of orders per solution, - which can scale reasonably well if you're willing to divide your service area with boundaries you can't optimise across. Ocado built a custom system which can support more orders with fewer boundaries; this offers better routing efficiency, which is important as delivery efficiency is a key cost driver. If your business does something like, say, washing machine repair your time-per-customer might be dominated by repair time rather than travel time; in that case you might be able to operate a nationwide business on off-the-shelf software. The underlying algorithm in Ocado's system is based on simulated annealing [2] - although those precise words don't seem to have made it into the article! [1] http://www.oracle.com/us/solutions/scm/service-optimization-suite-294193.html http://www.oracle.com/us/solutions/scm/service-optimization-... [2] https://en.wikipedia.org/wiki/Simulated_annealing https://en.wikipedia.org/wiki/Simulated_annealing