Search code examples
vbasortingms-accessbin-packing

Is there a variant of the Bin packing algorithm which is applicable here?

Suppose you are stacking a crate with items, where each item in the crate is identical in dimensions, items cant be tipped so all are standing and items are in a single layer.

Now what my aim is to have a crate selector where a user enters the item and number of items in the purchase order and in return receives a report telling the user which crate to select to pack the items.

For example

Input: 
    24 x Item 199111
Output:
    Option 1: 2 x crate #1 with 12 item 199111 per crate
    Option 2: 1 x Crate #3 with 24 item 199111 per crate

I have currently created a Microsoft access database with the tables

  • tblCrateInfo (contains crate dimensions of available crates)
  • tblItemInfo (contains items dimensions and weight of items to pack which the user can select from)

I also have a form that the user can add new items as they are created. we only have 30 crate sizes and 200 items to pick from.

My question is which tools in access can I can use to achieve this or any books i can read to find out. My main struggle is with checking how many of an item will fit in each crate.

Solution

  • I'll be using queries with calculated fields based on public functions. The access query designer can use publicly available functions. So we can create functions to handle the math around how many creates we need and the total cost of those crates for each combination item quantity, packing arrangement and crate type.

    enter image description here

    calculated variable details and where the public functions are called

    CratesNeeded: CratesNeededforOrder([tblItemInfo]![ItemLength],[tblItemInfo]![ItemWidth],[tblCrateInfo]![CrateLength],[tblCrateInfo]![CrateWidth],[tblOrderInfo]![ItemQuantity])

Cost: Cost([ItemLength],[ItemWidth],[CrateLength],[CrateWidth],[ItemQuantity],[CrateCost])

    note the calculated field CratesNeeded in a row has access to that rows value of ItemLength.

    To add public functions of a database go to the design tab of the ribbon and add a code module, usually on the far right. Then add the public functions in the code module:

    'assume all items have an approximating rectangle and all items packed with the same orientation so crate length is divided by either item length or item width giving us only two packing arrangements
Public Function AtLeast1ItemFitsintoCrate(itemlength As Double, itemwidth As Double, cratelength As Double, cratewidth As Double) As Boolean
Dim temp As Double 'make sure length is equal or larger than width
If itemwidth > itemlength Then
temp = itemlength
itemlength = itemwidth
itemwidth = temp
End If
If cratewidth > cratelength Then
temp = cratelength
cratelength = cratewidth
cratewidth = temp
End If
If (itemlength <= cratelength) And (itemwidth <= cratewidth) Then
AtLeast1ItemFitsintoCrate = True
Else
AtLeast1ItemFitsintoCrate = False
End If
End Function
Public Function HowManyitemsWillFitinCrate(itemlength As Double, itemwidth As Double, cratelength As Double, cratewidth As Double) As Integer
Dim itemsinpackingarrangement1 As Integer
Dim itemsinpackingarrangement2 As Integer
itemsinpackingarrangement1 = CInt(cratelength / itemlength) * CInt(cratewidth / itemwidth)
itemsinpackingarrangement2 = CInt(cratelength / itemwidth) * CInt(cratewidth / itemlength)
If itemsinpackingarrangement1 > itemsinpackingarrangement2 Then
HowManyitemsWillFitinCrate = itemsinpackingarrangement1
Else
HowManyitemsWillFitinCrate = itemsinpackingarrangement2
End If
End Function
Public Function CratesNeededforOrder(itemlength As Double, itemwidth As Double, cratelength As Double, cratewidth As Double, itemquantity As Integer) As Integer
Dim itemspercrate As Integer
itemspercrate = HowManyitemsWillFitinCrate(itemlength, itemwidth, cratelength, cratewidth)
CratesNeededforOrder = Ceiling(itemquantity / itemspercrate)
End Function
Public Function Cost(itemlength As Double, itemwidth As Double, cratelength As Double, cratewidth As Double, itemquantity As Integer, cratecost As Currency) As Currency
'found technical annoyance that functions used in queries must avoid passing calculated fields as parameters, cratequantity must be calculated here when used for queries
Dim cratequantity As Integer
cratequantity = CratesNeededforOrder(itemlength, itemwidth, cratelength, cratewidth, itemquantity)
Cost = cratequantity * cratecost
End Function
Public Function Ceiling(number As Double) As Integer
Ceiling = -Int(-number)
End Function

    I forgot to filter the query by AtLeast1ItemFitsintoCrate so I leave it as an exercise. As you get a better model of packing you can modify the functions supporting the cost function. Minimization is handled by enumerating all possible cases and sorting by cost.