Hacker News Reader

Comment by michaelt | Hacker News Reader

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

View on HN

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

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!

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

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

We take into account long-term trends in weather and traffic conditions like road works, school holidays, and recurring traffic patterns.

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.

What was the most fundamental problem they/you solved and why was it difficult?

what is the stack you use ? especially for the algorithm hotpath ? I'm not sure if you are using libraries like Gurobi or CPLEX.

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.

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.

Thank you for the answer. I was not aware that these kind of considerations impact the cpu vs gpu debate. I was under the impression that most cpu heavy computations can be ported to the gpu.

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.

wow I'm intrigued and haven't even heard of tabu search before you mentioned it, thank you very much! You surely are my hero today loserboss =)

What's the benefit of Gurobi or CPLEX over a CSP-Solver (mini-sat)?

With ASP (answer-set-programming) you can also avoid the specificity of modeling-language DSLs and instead focus on formalization.

Reply on news.ycombinator.com