6 ms·

The software routing 260,000 grocery deliveries a week

63 points by alexvoica 9y ago

Zizizizz 9y ago
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
coldcode 9y ago
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)?
ensiferum 9y ago
Pure advert. No actual tech content
agravier 9y ago
My buddy and I gave a talk about how we solve the same problem at RedMart. We're not as large as Ocado (yet?), but this video has more technical content: https://www.youtube.com/watch?v=6fmFb3r7Tmg https://www.youtube.com/watch?v=6fmFb3r7Tmg
deleted 9y ago
[deleted]
shock 9y ago
I don't understand why this is on the front page. It has almost no technical details, just a bragging piece.
michaelt 9y ago
I work for Ocado, and I've spent some time working on the routing system (although I don't work on it any longer). Feel free to ask any questions and I'll try to answer them as best I can, without revealing anything I'm not supposed to reveal :)
- djhworld 9y ago
  Slightly unrelated, but it would be great if the main shop could have an API. Tesco has this, with support through IFTTT https://ifttt.com/search/query/tesco https://ifttt.com/search/query/tesco My use case is most often in the kitchen, hands covered in flour and realise I'm running out of product X. At the moment I bark at my Echo to add something to its internal "shopping list" feature, but I'd rather those commands hooked directly up to Ocado!
  - michaelt 9y ago
    There have been internal discussions of providing an Alexa skill (or something broader to support other home automation/digital assistant products). I believe it was a 20% time project, so I don't know how far it's got. I'll ask the person who was working on it. We have an API for our mobile apps, but due to the constraints of backwards compatibility it's not especially elegant, which is why it's not publicly documented. I'll ask internally about making it more available, but as I'm sure you appreciate, it's difficult to show there's customer demand for that kind of thing :)
- sandGorgon 9y ago
  what is the stack you use ? especially for the algorithm hotpath ? I'm not sure if you are using libraries like Gurobi or CPLEX.
  - michaelt 9y ago
    The optimiser is actually written in pure Java. The JIT compiler works pretty well, and with tools like JITWatch, Honest Profiler and the -XX:+LogCompilation -XX:+PrintAssembly options you can understand how the hot paths are running in a lot of detail. For our current operation, the optimisers' servers run Ubuntu on bare metal in our own data centres. Of course, like in any large organisation we make plenty of use of virtualization and EC2 - just not for our optimisers at this point in time.
FRIEDCHICKEN 9y ago
You had me until: >While the mathematics shall remain a mystery (have a look at our data science job openings if you’d like to learn more)... thptt.
heinrichf 9y ago
Interesting talk on the subject from a data scientist at Instacart: https://blog.dominodatalab.com/data-science-instacart/ https://blog.dominodatalab.com/data-science-instacart/
- alexvoica 9y ago
  We've also looked at data science to solve the problem but found that a traditional approach still offers the best performance.
  - FractalNerve 9y ago
    Can you define "traditional approach" please? :) What do you mean specifically?
throws3bit 9y ago
Good brag, but fix your https.
mgleason_3 9y ago
Took a couple classes in graph theory in college which was interesting because of the complexity involved in solving for optimal routes. We started with brute-force search and moved on to other shortest path problem algorithms like the ones mentioned here: https://en.m.wikipedia.org/wiki/Shortest_path_problem https://en.m.wikipedia.org/wiki/Shortest_path_problem This article doesn't seem to add anything to the field.

63 points by alexvoica 9y ago

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

coldcode 9y ago

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

ensiferum 9y ago

Pure advert. No actual tech content

agravier 9y ago

My buddy and I gave a talk about how we solve the same problem at RedMart. We're not as large as Ocado (yet?), but this video has more technical content: https://www.youtube.com/watch?v=6fmFb3r7Tmg https://www.youtube.com/watch?v=6fmFb3r7Tmg

deleted 9y ago

[deleted]

shock 9y ago

I don't understand why this is on the front page. It has almost no technical details, just a bragging piece.

michaelt 9y ago

I work for Ocado, and I've spent some time working on the routing system (although I don't work on it any longer). Feel free to ask any questions and I'll try to answer them as best I can, without revealing anything I'm not supposed to reveal :)

djhworld 9y ago
Slightly unrelated, but it would be great if the main shop could have an API. Tesco has this, with support through IFTTT https://ifttt.com/search/query/tesco https://ifttt.com/search/query/tesco My use case is most often in the kitchen, hands covered in flour and realise I'm running out of product X. At the moment I bark at my Echo to add something to its internal "shopping list" feature, but I'd rather those commands hooked directly up to Ocado!
- michaelt 9y ago
  There have been internal discussions of providing an Alexa skill (or something broader to support other home automation/digital assistant products). I believe it was a 20% time project, so I don't know how far it's got. I'll ask the person who was working on it. We have an API for our mobile apps, but due to the constraints of backwards compatibility it's not especially elegant, which is why it's not publicly documented. I'll ask internally about making it more available, but as I'm sure you appreciate, it's difficult to show there's customer demand for that kind of thing :)
sandGorgon 9y ago
what is the stack you use ? especially for the algorithm hotpath ? I'm not sure if you are using libraries like Gurobi or CPLEX.
- michaelt 9y ago
  The optimiser is actually written in pure Java. The JIT compiler works pretty well, and with tools like JITWatch, Honest Profiler and the -XX:+LogCompilation -XX:+PrintAssembly options you can understand how the hot paths are running in a lot of detail. For our current operation, the optimisers' servers run Ubuntu on bare metal in our own data centres. Of course, like in any large organisation we make plenty of use of virtualization and EC2 - just not for our optimisers at this point in time.

FRIEDCHICKEN 9y ago

You had me until: >While the mathematics shall remain a mystery (have a look at our data science job openings if you’d like to learn more)... thptt.

heinrichf 9y ago

Interesting talk on the subject from a data scientist at Instacart: https://blog.dominodatalab.com/data-science-instacart/ https://blog.dominodatalab.com/data-science-instacart/

alexvoica 9y ago
We've also looked at data science to solve the problem but found that a traditional approach still offers the best performance.
- FractalNerve 9y ago
  Can you define "traditional approach" please? :) What do you mean specifically?

throws3bit 9y ago

Good brag, but fix your https.

mgleason_3 9y ago

Took a couple classes in graph theory in college which was interesting because of the complexity involved in solving for optimal routes. We started with brute-force search and moved on to other shortest path problem algorithms like the ones mentioned here: https://en.m.wikipedia.org/wiki/Shortest_path_problem https://en.m.wikipedia.org/wiki/Shortest_path_problem This article doesn't seem to add anything to the field.