17
$\begingroup$

After a bit of reading I think I've been able to conclude that state-of-the-art VRP can get solutions for 100~500 stops.

My question is around how this actually affects logistics (like Amazon for instance).

Do they actually practically use these algorithms to drive efficiencies? How? Is the current state-of-the art good enough, as in it's not a big deal for logistics companies? Or is it something they are actively looking to improve?

$\endgroup$
9
$\begingroup$

The answer to this question is quite complicated. There are two main types of vehicle routing problems, the offline and the online problem.

Solving the offline problem takes longer and is used to make planning-level decisions. The online problem is solved as real-time information comes in, and tells us what to do at the low level (as in which vehicle should go where right now).

What we need to establish is that these problems must always give us some answer, especially the online problem, because having idle vehicles means losing money.

Companies like Uber or Amazon have very sophisticated ways of achieving this, which involves a convoluted combination of methods. Amazon would solve both the online and offline problems, for thousands of destinations. The offline solutions help reduce the solution space for the online problem. Uber is more dependent on the online problem, but these problems are much easier because there are only so many cars within a 5-10 min drive at any given time.

What makes this problem complicated is that the way this problem is solved, even by the same company, changes depending on the city, time of day, and time of year. The differentiator is usually the quality/reliability of traffic data. In Europe or North America (but usually only in large urban areas) we have pretty good data to help us run data-driven optimisation with pretty good predictive power. In Africa or Asia, traffic tends to be more unpredictable and the data available is usually not as good, which means we need to depend much more on heuristic methods, machine learning, offline optimisation, and to be upfront with customers about possible delays in delivery.

Companies are indeed looking for ways to improve this, however the quality of data tends to be much more of a bottleneck than actual optimisation is. When we do have good data, more powerful optimisation software/methods do make a huge difference and tech companies are aware of this.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Great. Will wait a little more before marking as answered. Do you think that in warehouse logistics (I'm talking bots zooming around to move stuff around in a warehouse) optimisation is the bottleneck instead of data quality? In either case, the reason I asked this question is because I was trying to assess if quantum computation may add value to the industry in the next 10 years. For that, I need to understand how much demand there is for an improvement in optimisation algorithms, whether classical computing can keep up with that demand, and if not, what the bottlenecks are there. $\endgroup$ – Alexander Soare Dec 14 '19 at 20:59
  • 3
    $\begingroup$ In my opinion, definitely. The thing with new capabilities in computing is that the more our computing capacity increases, the more complexity we introduce into our calculations. Assuming quantum computing reaches the point where such algorithms can be coded, I would expect companies to start modelling much more complicated systems. My experience has been that it takes a lot of work to get people to adopt new technology, but once they do they never go back. $\endgroup$ – Nikos Kazazakis Dec 14 '19 at 21:04
  • 1
    $\begingroup$ Could you please explain where you based your answer on? Experience in the logistics industry, academic sources etc. I especially doubt the claim that heuristics, machine learning and offline optimisation are more often used in Africa and Asia compared to Europe and North America.. $\endgroup$ – Rolf van Lieshout Dec 15 '19 at 9:53
  • 1
    $\begingroup$ @RolfvanLieshout while I agree explanations are always handy, I'm also wondering about the explanation behind your reasoning. You're very welcome to leave an answer in the main thread as well! $\endgroup$ – Alexander Soare Dec 15 '19 at 12:28
  • $\begingroup$ My answer is based on experience - I know people who work on this in some of the large companies and we've done some consulting work on this. Asia specifically has numerous densely populated metropolitan centres with some of the largest traffic problems in the world, which makes the predictive power of conventional modelling quite limited. $\endgroup$ – Nikos Kazazakis Dec 16 '19 at 11:36
4
$\begingroup$

Talking about real use in logistics, I suggest reading about the UPS ORION project. Not many details, but it provides an example of a real system dealing with this kind of problem.

| improve this answer | |
$\endgroup$
4
$\begingroup$

I am a researcher in vehicle routing, and my answer is based on my experience as a researcher, conversations with practitioners and consultants, and seminars and conference talks I have attended.

You make a very interesting observation: solving VRP's to optimality is currently only possible for hundreds of customers, while problems in practice are significantly bigger. However, there are several ways how exact methods (methods that guarantee optimality) have an impact on the industry.

Splitting the problem

If a problem is too difficult to solve at once, it may be split into more manageable parts. One way to do this is by solving parts of the problem sequentially, at the cost of losing guaranteed optimality. Each sequential problem might be small enough to be solved exactly, or is at least easier to solve with heuristics. This approach was used for optimizing the timetable of the Dutch Railways, for example. To quote from The New Dutch Timetable: The O.R. Revolution:

To construct a new timetable and its related resource schedules, we modeled and solved a sequence of planning problems. As input, we had to define a linesystem. Then, we calculated the timetable, including the detailed routings through the stations. Finally, we needed to construct rolling-stock and crew schedules. Note that we solved these different planning problems sequentially.

Another way to split problems is by splitting them geographically. This is an approach that is used by some grocery deliverers for example. After dividing the service area into regions, each region is optimized independently. If the regions are sufficiently small, exact methods may be used.

Heuristics

Even if exact methods are computationally infeasible, they often serve as a starting point for developing heuristics. It is very common (especially in the scientific literature) to first present the problem as a mixed integer program, even if it will not be solved as such.

Exact methods provide a way to evaluate the performance of heuristics for small problems that can be solved to optimality. This provides some confidence that a heuristic provides good solutions.

In industry, heuristics are a lot more common than exact methods. It should be noted however, that there is also a lot of research into heuristic methods. In my experience, local search methods, e.g., variable neighborhood search, are common for vehicle routing problems. Some consultants and companies are actively involved in research, typically with a focus on heuristics. For example, I attended a talk by Mauricio Resende, Principal Research Scientist at Amazon, who talked about routing problems at Amazon at a scientific conference.

Some heuristics are based on exact methods. Such heuristics are often referred to as matheuristics. For example, one may remove all arcs that are unlikely to appear in an optimal solution, and solve the remaining problem exactly. Another example is heuristics based on column generation, where only a subset of the columns is generated. Such heuristics are used for bus scheduling, for example.

Conclusion

In industry, you are unlikely to find complex problems that are solved to optimality. However, exact methods are still useful in practice. They can be used to solve subproblems, and they inspire matheuristics. Some companies are heavily involved in research, but their interest is typically more in heuristic methods, which is a research area in itself.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.