3d ago

Storage Optimization Algorithm

I'm hoping to get pointed in the right direction on finding or creating a tool that can optimize the storage of items based on their dimensions and the dimensions of storage spaces available. Luckily there is only 1 dimension to measure (Width), so the constraints and logic are fairly simple (no 3D stacking needed).

In very rough terms, there will be 2 tables with the following fields: Table 1: Storage Space

Storage ID: Unique ID for the space
Storage Width: Numerical value in metres
Storage Capacity: Numerical how many items can be stored side by side - generally 1 or 2.

Table 2: Storage Items

Item ID: Unique ID for the item being stored
Item Width: Numerical value in Metres

The optimization exercise is to run through the list of Storage Items and assign them to a Storage Space while minimizing the unallocated storage width (i.e. pack these items as tight as it can) while respecting that a Storage Space may have a maximum capacity of 1 or 2 items.

I'm not the coding sort myself (I can work my way around programming logic but I'm not immersed in it and it will take me a good deal of time) so I'm wondering if anyone may be familiar with tools that could hand hold analyzing data sets in this way, or ready-made solutions that happen to tackle the optimization problem.

Thanks in advance!

4 comments

This is, nonobviously, the definition of the cutting stock problem. The cutting stock is your tables, from which you want to cut item-sized chunks. A table that can hold two items is just two tables that can only hold one. Mathematically, you can't do it faster than enumerating all the possibilities and checking them. But that doesn't help you much.
There are plentiful ready-made solutions online, or you can do it with an SMT solver if you prefer.
- Thank you, that was a great read and a great nudge in the right direction
https://en.wikipedia.org/wiki/Knapsack_problem ?
If I remember right, problems of that type are either NP-Complete or even NP-Hard, meaning they are incredibly hard to compute and/or don't have a known solution. They have been studied for centuries, so there should be ample scientific research (see the links the other commenters posted already), but my point is a "perfect solution" probably isn't a realistic goal. I would aim for an approximation that's "good enough" for your use case.