物流業中車輛路徑問題的現狀如何?


17

經過一番閱讀,我認為我可以得出結論,最新的VRP可以解決100到500個停靠點。

我的問題是,這實際上如何影響物流(例如亞馬遜)。

他們實際上是否實際上使用這些算法來提高效率?怎麼樣?對於物流公司來說,目前的最新技術是否足夠好,因為這並不重要?還是他們正在積極尋求改進?

9

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.


4

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.


4

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.