31–40 of 41 posts
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 :)
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 :)
https://en.wikipedia.org/wiki/Vehicle_routing_problem#VRP_va...
Earlier quoted context omitted.
did you not try to do this on the GPU by any chance ? Especially using CUDA libraries. I'm wondering what is the state of art in this field.
Our current design isn't well suited to adaption to a GPU, because it branches a lot and the memory accesses aren't strided evenly. So we couldn't just plug our current code into a java-to-cuda compiler; we'd need to change the design. So no, we haven't yet tested using GPUs.
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 sc…
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 :)
Do you route based on anything except distance? Obviously you can't deliver to people at 2AM, and drivers want to get home by a reasonable hour, but what about other stuff like weather and road traffic conditions, priority or late parcels, etc? If so, how do you weight these competing and probabilistic concerns? https://en.wikipedia.org/wiki/Vehicle_routing_problem#VRP_va...
The drivers' sat navs also (IIRC) have live traffic, which can send them down different _roads_ in response to things like accidents causing traffic jams.
Of course, there are limits to our ability to respond quickly to changes in traffic conditions for simple logistical reasons - many drivers' vans are loaded once at the start of an 8-hour shift, and we can't predict traffic accidents 8 hours before they happen!
Certain other competing concerns are balanced with a 'cost function' which has been tuned empirically.
Earlier quoted context omitted.
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 o…
did you not try to do this on the GPU by any chance ? Especially using CUDA libraries. I'm wondering what is the state of art in this field.
edit: Can you provide insight?
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 :)
what is the stack you use ? especially for the algorithm hotpath ? I'm not sure if you are using libraries like Gurobi or CPLEX.
With ASP (answer-set-programming) you can also avoid the specificity of modeling-language DSLs and instead focus on formalization.
Interesting talk on the subject from a data scientist at Instacart: https://blog.dominodatalab.com/data-science-instacart/
We've also looked at data science to solve the problem but found that a traditional approach still offers the best performance.
Earlier quoted context omitted.
did you not try to do this on the GPU by any chance ? Especially using CUDA libraries. I'm wondering what is the state of art in this field.
I take that it's a 'kind' of decision tree or random forest with gradient boosting, so usually it 'can' run faster on a CPU if optimized than on a GPU (if I'm not mistaken). That's at least what I get from BigML's offering. edit: Can you provide insight?
It is a local search algorithm that probably has simulated annealing or tabu search as a metaheuristic.
Although, they probably segment the deliveries to some common starting points and the problem size is reduced significantly - maybe to around thousand orders per starting point.
Research can easily optimize thousands of deliveries very effectively.
Earlier quoted context omitted.
I take that it's a 'kind' of decision tree or random forest with gradient boosting, so usually it 'can' run faster on a CPU if optimized than on a GPU (if I'm not mistaken). That's at least what I get from BigML's offering. edit: Can you provide insight?
It is not decision tree or any machine learning algorithm. It is a local search algorithm that probably has simulated annealing or tabu search as a metaheuristic. Although, they probably segment the deliveries to some common starting points and the problem size is reduced significantly - maybe to around thousand orders per starting point. Research can easily optimize thousands of deliveries very effectively.