The Knapsack Problem

The Knapsack Problem and Warehouse Optimization

Packing for a long trip can be a pain. There’s nothing worse than arriving at the airport only to discover that your checked bag is a few pounds over the weight limit, and now you’re facing an exorbitant fee. You can try and transfer a few items to your carry-on bag, which is already bursting at the seams, but which items? An inexpensive sweatshirt takes up a lot of room but doesn’t weigh very much. A pair of expensive shoes and a digital camera weigh more, but take up less space. How do you quickly decide what to move from bag to bag, and maybe even what to leave behind?

That’s the Knapsack Problem.

The Knapsack Problem is an optimization problem that is centered around finding the most desirable combination of items—each with its own weight and dollar value—that will fit inside a container and not exceed a weight limit. The goal is to load the most value into the knapsack.

 

The Knapsack Problem (Source: Wikimedia Commons)

Image source: Wikimedia Commons (problem solution below*)

Picking and Packing

The Knapsack Problem belongs to a class of problems known to mathematicians as NP-Complete, meaning that no efficient algorithmic solution has been identified. The best we can hope for is an approximate solution that will be reasonably close. Another example is The Traveling Salesman Problem.

The Knapsack Problem has been studied since the end of the 19th Century and has since been applied to fields as diverse as investing, cryptography and fantasy sports. And it’s particularly relevant to the world of e-commerce when it comes to warehousing and shipping. That’s why developers of mobile robotics systems, including inVia Robotics, study the problem in order to optimize the order fulfillment process. 

The most obvious application of The Knapsack Problem is in selecting what items go into a shipping box. Determining what are the most valuable items that will fit without exceeding the predetermined weight limit on an order-by-order basis not only reduces shipping costs, it reduces the amount of packing material used and potentially the overall number of boxes.

Cutting costs and reducing packaging waste is a priority for most online retailers, including Amazon, which just announced new guidelines to reduce packaging that include fining third-party sellers who ship products in oversized packaging.

At the warehouse level, The Knapsack Problem can be applied to optimizing space utilization by “defragging” wasted shelf space, which allows managers to bring in more valuable SKUs and increase revenue. Bins and totes can also be rearranged dynamically so that the fastest-moving SKUs are always closest to the packing stations. Other areas of optimization include inventory management, replenishment, and the handling of returns.

Why Does it Matter?

Our ongoing work attempting to solve The Knapsack Problem is concentrated on perfecting our warehouse automation solutions so that you can achieve the highest level of productivity possible with no big upfront costs, no disruption to your fulfillment process and no new infrastructure requirements.

Ready to start transforming your warehouse? Please give us a call – we’d love to hear from you.

(*Problem solution: if any number of each box pictured is available, pack three yellow boxes and three grey boxes for a total of 15 kg valued at $36; if only the pictured boxes are available, then pack all but the green box for a total of 8 kg valued at $15.)