AI Solves Delivery Puzzle for Small Stores

In densely populated urban areas of developing countries, delivering goods to small retailers known as nanostores is a major logistical challenge. These stores stock limited items, forcing suppliers to make frequent trips with vehicles packed with diverse products like cleaning supplies, groceries, and alcohol. A new study addresses this by introducing a smarter packing method that ensures incompatible items, such as those risking contamination, are never placed together, optimizing deliveries for efficiency and safety.

The key finding is that researchers have developed a variable neighborhood search (VNS) metaheuristic algorithm to solve the Bin Packing Problem with Compatible Categories (BPCC). This approach minimizes the number of bins—or vehicle loads—needed by grouping items into categories that must be compatible, meaning no conflicting categories share a bin. For example, cleaning products and food items might be incompatible due to contamination risks, and the algorithm ensures they are packed separately while using the fewest bins possible.

Methodologically, the team modeled the problem using a linear integer programming framework with binary decision variables to track item assignments and category compatibility. The VNS algorithm starts with an initial solution from a greedy heuristic, then systematically explores different neighborhood structures by shaking and local search procedures. Shaking introduces random changes, such as removing and repacking items from selected categories, while local search improves bin density by moving or swapping items between bins only if it enhances packing efficiency without violating compatibility rules.

Results from computational experiments show that the VNS algorithm achieved optimal or near-optimal solutions quickly. Testing on up to 403 items with varying vehicle capacity factors (100% to 200%), the heuristic ran on a standard personal computer and matched results from high-performance computing systems in much shorter times. For instance, with 202 items at 150% capacity, the algorithm used an average of 5.059 bins and took about 1.774 seconds, compared to longer runtimes for exact solvers. In many cases, it found solutions where traditional methods struggled, especially at lower capacities.

This advancement matters because it offers a practical tool for logistics in emerging megacities, where nanostores are common. By reducing the number of delivery trips and ensuring product safety, it can lower costs and environmental impact for suppliers, ultimately making goods more accessible in crowded urban centers. The method's speed and simplicity make it suitable for real-world applications without needing expensive computing resources.

Limitations include that the algorithm was tested on specific instances derived from benchmark problems, and its performance on larger or more varied category matrices remains unverified. The paper notes that further research should assess efficiency in broader scenarios and develop better lower-bound techniques tailored to this problem's characteristics.