Approach to a Bin Packing sql problem

Question

I have a problem in sql where I need to generate a packing list from a list of transactions.

Data Model

The transactions are stored in a table that contains:

• transaction id
• item id
• item quantity

Each transaction can have multiple items (and coincidentally multiple rows with the same transaction id). Each item then has a quantity from 1 to N.

Business Problem

The business requires that we create a packing list, where each line item in the packing list contains the count of each item in the box.

Each box can only contain 160 items (they all happen to be the same size/weight). Based on the total count of the order we need to split items into different boxes (sometimes splitting even the individual item's collection into two boxes)

So the challenge is to take that data schema and come up with the result set that includes how many of each item belong in each box.

I am currently brute forcing this in some not so pretty ways and wondering if anyone has an elegant/simple solution that I've overlooked.

Example In/Out

We really need to isolate how many of each item end up in each box...for example:

Order 1:

• 100 of item A
• 100 of item B
• 140 of item C

This should result in three rows in the result set:

• Box 1: A (100), B (60)
• Box 2: B(40), C (120)
• Box 3: C(20)

Ideally the query would be smart enough to put all of C together, but at this point - we're not too concerned with that.

Answer 1

How about something like

SELECT SUM([Item quantity]) as totalItems
     , SUM([Item quantity]) / 160 as totalBoxes
     , MOD(SUM([Item Quantity), 160) amountInLastBox
FROM [Transactions]
GROUP BY [Transaction Id]

Let me know what fields in the resultset you're looking for and I could come up with a better one

Answer 2

Have you read the bin packing bible?

http://sqlblog.com/blogs/hugo%5Fkornelis/archive/tags/Bin+Packing/default.aspx

Answer 3

Have you found a solution to this?

I was looking for something similar and all I could achieve was expanding the rows to the number of item counts in a transaction, and grouping them into bins. Not very elegant though.. Moreover, because string aggregation is still very cumbersome in SQL Server (Oracle, i miss you!), I have to leave the last part out. I mean putting the counts in one single row.. My solution is as follows:

Example transactions table:

INSERT INTO transactions
(trans_id, item, cnt) VALUES
('1','A','50'), 
('2','A','140'), 
('3','B','100'), 
('4','C','80');
GO

Create a dummy sequence table, which contains numbers from 1 to 1000 (I assume that maximum number allowed for an item in a single transaction is 1000):

CREATE TABLE numseq (n INT NOT NULL IDENTITY) ;
GO
INSERT numseq DEFAULT VALUES ;
WHILE SCOPE_IDENTITY() < 1000 INSERT numseq DEFAULT VALUES ;
GO

Now we can generate a temporary table from transactions table, in which each transaction and item exist "cnt" times in a subquery, and then give numbers to the bins using division, and group by bin number:

SELECT bin_nr, item, count(*) count_in_bin
INTO result
FROM (
  SELECT t.item, ((row_number() over (order by t.item, s.n) - 1) / 160) + 1 as bin_nr
  FROM transactions t 
  INNER JOIN numseq s
  ON t.cnt >= s.n -- join conditionally to repeat transaction rows "cnt" times
) a
GROUP BY bin_id, item
ORDER BY bin_id, item
GO

Result is:

bin_id item count_in_bin
1 A 160
2 A 30
2 B 100
2 C 30
3 C 50

In Oracle, the last step would be as simple as that:

SELECT bin_id, WM_CONCAT(CONCAT(item,'(',count_in_bin,')')) contents
FROM result
GROUP BY bin_id

Please share if you find an elegant solution..

Answer 4

This isn't the prettiest answer but I am using a similar method to keep track of stock items through an order process, and it is easy to understand, and may lead to you developing a better method than I have.

I would create a table called "PackedItem" or something similar. The columns would be:

packed_item_id (int) - Primary Key, Identity column
trans_id (int)
item_id (int)
box_number (int)

Each record in this table represents 1 physical unit you will ship.

Lets say someone adds a line to transaction 4 with 20 of item 12, I would add 20 records to the PackedItem table, all with the transaction ID, the Item ID, and a NULL box number. If a line is updated, you need to add or remove records from the PackedItem table so that there is always a 1:1 correlation.

When the time comes to ship, you can simply

SELECT TOP 160 FROM PackedItem WHERE trans_id = 4 AND box_number IS NULL

and set the box_number on those records to the next available box number, until no records remain where the box_number is NULL. This is possible using one fairly complicated UPDATE statement inside a WHILE loop - which I don't have the time to construct fully.

You can now easily get your desired packing list by querying this table as follows:

SELECT box_number, item_id, COUNT(*) AS Qty
FROM PackedItem
WHERE trans_id = 4
GROUP BY box_number, item_id

Advantages - easy to understand, fairly easy to implement. Pitfalls - if the table gets out of sync with the lines on the Transaction, the final result can be wrong; This table will get many records in it and will be extra work for the server. Will need each ID field to be indexed to keep performance good.

Answer 5

try to pick some ideas from http://www.postgresonline.com/journal/index.php?/archives/138-Allocating-People-into-Groups-with-SQL-the-Sequel.html

it uses CTE

Answer 6

Why can you not load all the data into RAM and process it with C# (or Java etc)? Sometimes SQL is not the best solution to a problem.