A multi-strategy depot-selection portfolio for the Capacitated Location Routing Problem
This paper proposes a multi-strategy depot-selection portfolio for the Capacitated Location Routing Problem that combines randomized preselection, iterative sweeping, multi-starts, and reassignment with an Adaptive Large Neighborhood Search and exact allocation models to outperform the Hexaly Optimizer baseline on 29 of 30 benchmark instances, particularly in moderate capacity regimes.
Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer
Logistics is the invisible engine that keeps modern life moving, a vast and complex puzzle of deciding where to place warehouses and how to send trucks to deliver goods. At its heart lies a difficult question: if you build a warehouse in the wrong spot, you might save on rent but spend a fortune on fuel; if you send a truck on a bad route, you waste time and money even if the warehouse is perfect. These two decisions—where to open a facility and how to drive the vehicles—are deeply connected, yet they are often solved separately. This separation creates a blind spot. A warehouse that looks cheap to build might end up being a disaster once the trucks start moving, just as a perfect driving route might be impossible if the warehouse is too small or too far away. Solving this combined problem efficiently is crucial for businesses, but it is also one of the hardest challenges in computer science because the number of possible combinations is so vast that checking them all is impossible.
A team of researchers at the Monterrey Institute of Technology and Higher Education in Mexico tackled this specific challenge using a new set of test cases designed to mimic real-world logistics in the Monterrey metropolitan area. They were not just looking for a slightly better answer; they were trying to fix a hidden flaw in how computers usually approach this problem. The standard tools used by logistics companies, and even the reference solutions provided for this specific test, rely on a rigid, step-by-step method to pick which warehouses to open. This method is deterministic, meaning it follows a strict set of rules without any flexibility. It looks at each customer, finds the single closest warehouse, and locks that choice in before it ever considers the cost of driving the truck. The researchers discovered that this rigid approach creates a structural bias. On many of the test cases, the computer would get stuck in the same suboptimal pattern over and over again, unable to see that a slightly more expensive warehouse or a different combination of locations would actually save money on the total trip.
To break this deadlock, the team built a flexible system that acts like a portfolio of different strategies rather than a single rigid algorithm. Instead of forcing the computer to make the warehouse decision once and for all at the beginning, they created four independent mechanisms to revisit that choice. One strategy randomly shuffles the initial choices, allowing the computer to occasionally pick a warehouse that is not the absolute closest but might be part of a better overall plan. Another strategy starts with a full set of warehouses and then systematically tries closing the most expensive ones to see if the routes can still work without them. A third approach does the opposite, adding back cheaper warehouses that were initially left out to see if they can shorten the driving distances enough to pay for themselves. Finally, for the smallest test cases, they used a precise mathematical model to find the perfect warehouse selection before worrying about the driving routes. These different approaches were run in parallel, and the system kept the cheapest, most efficient solution found by any of them.
The results showed that this flexible, multi-strategy approach significantly outperformed the standard commercial software used as a baseline. Across thirty different test scenarios, ranging from small towns with eighty customers to massive metropolitan areas with two thousand five hundred customers, the new method found a cheaper solution in twenty-nine of the cases. On average, the new method reduced the total cost by 3.62 percent, with some individual cases showing improvements as high as 11.62 percent. This was not just a matter of running the computer longer; the researchers found that the advantage was not uniform. The biggest gains appeared in a specific "moderate" regime where the capacity of the warehouses and the number of available trucks were neither too loose nor too tight. In these realistic middle-ground situations, the interaction between where the warehouses are and how the trucks drive is most complex, and the rigid, single-path methods of the past struggled the most. When the constraints were very loose or very tight, the advantage of the new method nearly vanished, suggesting that the old tools were actually quite good at the extremes but failed in the messy middle.
The study also revealed that the size of the problem was not the main factor determining success. The researchers found that the difficulty came from the specific structure of the constraints, not just the number of customers. For the largest instances, which used real road networks with one-way streets and traffic patterns that made distances asymmetric, the team could not run as many different variations as they did for the smaller cases. Even with these limitations, the method held its ground, proving that the ability to revisit and change the initial decision about which warehouses to open is a powerful tool. The team concluded that for complex logistics problems, relying on a single, fixed way of thinking is a mistake. By treating the problem as a portfolio of different strategies, each attacking the decision from a different angle, they were able to find savings that a single, rigid approach simply could not see. This suggests that the future of solving these problems lies not in finding one perfect algorithm, but in building systems that can adapt their strategy based on the specific shape of the challenge they face.
Drowning in papers in your field?
Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.