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?
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.
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.
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.
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.
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.
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.
In my experience when solving Vehicle Routing with time windows in the industry, with one case handling 50 000+ vehicles and 100 000+ visits per day as well as many other cases with lower numbers, all running in production, I notice that:
The problem is often (un)naturally partitioned, due to Conway's law. In the 50K+ vehicles case, each vehicle and visit is confined to a region, so each region is a partition. The size of the regions varies (sometimes it's a US state), but if I recall correctly the partitions went up to around 1k vehicles.
At some point, depending on the solver, partitioning increases solution quality given a fixed time limit. This is a sign of weakness that every solver will run into when scaling VRP. The question is not if, but when. Note you can first solve partitions and then warm start a global solver on the merging of the resulting partitioned solutions, which sometimes leads to better results.
Multi-threaded solving (our moveThreadCount) and nearby selection make a world of difference. Our OptaPlanner got scores in minutes what OR-Tools and 2 other competitors took hours to do, in the customer's extensive benchmarks consistently across multiple rounds. Your mileage may vary. Tuning matters.
Management was expecting a 1-2% improvement in driving time reduction. It was 25%, to their surprise. This resulted in huge (CEO level) savings and a reduction of 10 000 000+ kg of CO² fuel emissions per year.
Night planning (batch planning) != day planning (real-time planning as the problem changes). Both deliver huge benefits. Start with a Minimum Viable Product that only does nightly planning, that's easier to implement.
Do not use air distances. Use actual road times (= distance matrix). In my experiments, optimizations on air distances are easily 4% off compared to real road distances on my test Belgium datasets which have very dense road networks (so others countries will be much worse).
Distances matrix are tricky. A distance matrix of 10 000 visits takes 1.6 GB RAM memory in it's most efficient form (it doesn't matter if it's Java, C++, Python, etc). That's without traffic data. When the number of visits double, the RAM reqs quadruple.
Good demo's matter too. Decision makers rejected our Java Swing demo's, so we recently we build a dedicated open source webapp to demo VRP:
I make a commercial vehicle routing solver for both dynamic and static problems (see https://odllive.com), and so I can offer a bit of industry insight into this question.
Using heuristics, metaheuristics including things like clever splitting of the problem, you can get to much larger problem sizes. This doesn't mean of-course that you're getting optimal solutions for these larger problem sizes, but you are getting 'good enough' solutions to be workable in real-life. For example, we have a 'fuzzy splitting' algorithm within our ODL Live engine that lets us get reasonable solutions in a reasonable timeframe for 5000 delivery problems, as shown in the following screenshot:
Although I've no doubt there's other commercial solvers which can get to this size of problem, 5000 appears to be on the large size for most. For example, as of September 2020 a popular solver called Routific appears to have an upper limit of 2000 deliveries - see https://dev.routific.com/pricing
Interestingly enough once you get to these size of problems, creating and holding the distance and travel time matrix in-memory can also become a bottleneck. Academic works using large problems tend to just assume Euclidean (i.e. straight line) distances between points which they can just calculate on-demand, so they don't tend to hit this issue. In-reality you need to be doing calculations based on the road network, with adjustments for rush hours etc. This adds significant overhead in both matrix calculation time and memory storage space.
It's also worth mentioning that what you would assume to be the really large problems encountered in industry - i.e. parcel delivery problems - are actually commonly split up into really small problems instead, as for high density parcel delivery operations often each driver has their own fixed territory. So you may have (for example) someone like DHL or UPS delivering tens or hundreds of thousands of items within a large city, but these could all be independent single-vehicle problems with perhaps 100 stops per vehicle. This is common because fixed driver territories makes sortation at the depots more efficient, and allows drivers to build up local knowledge (i.e. best places to park) which helps them complete their route quicker. Presumably this offsets to some extent the loss of efficiency through treating as isolated subproblems.
