Basic infrastructure and several algorithms for 1d - 4d bin packing problem. This package provides a set of c-level classes and solvers for 1d - 4d bin packing problem, and an r-level solver for 4d bin packing problem, which is a wrapper over the c-level 4d bin packing problem solver.
The 4d bin packing problem solver aims to solve bin packing problem, a.k.a container loading problem, with an additional constraint on weight. Given a set of rectangular-shaped items, and a set of rectangular-shaped bins with weight limit, the solver looks for an orthogonal packing solution such that minimizes the number of bins and maximize volume utilization. Each rectangular-shaped item i = 1, .. , n is characterized by length l_i, depth d_i, height h_i, and weight w_i, and each rectangular-shaped bin j = 1, .. , m is specified similarly by length l_j, depth d_j, height h_j, and weight limit w_j. The item can be rotated into any orthogonal direction, and no further restrictions implied.
library(gbp)Imagine yourself as a store manager, and your customers are placing orders on your inventory catalog. The orders should be specified in a data.table, where each order is uniquely identified by the order id (oid), and each order includes one or more products which each uniquely identified by stock keeping unit (sku) with specific length (l), depth (d), height (h) and weight (w). The orders are expected to be packed into one or more boxes, a.k.a, bins. The available bin types are specified in a data.table, where each type of bin is uniquely indentified by a bin id (id) with specific length (l), depth (d), height (h) and weight limit (w). The objective is packing each order into the smallest number of bins, and then smallest bins to achieve highest utlization rate, subject to the three dimensional none overlap contraints and weight limit constraint.
#- bpp_solver: input: order list in data.table `it` and bin list in data.table `bn`
#- it
# it item <data.table>
# - oid order id <integer>
# - sku items id <character>
# - l it length which scale will be placed along x-coordinate <numeric>
# - d it depth which scale will be placed along y-coordinate <numeric>
# - h it height which scale will be placed along z-coordinate <numeric>
# - w it weight which scale will be placed along w-coordinate <numeric>
# l d h are subject to rotate, while w is on a separate single dimension
it <- data.table::data.table(
oid = c(1428571L, 1428571L, 1428571L, 1428572L, 1428572L, 1428572L, 1428572L, 1428572L),
sku = c("A0A0A0", "A0A0A1", "A0A0A1", "A0A0A0", "A0A0A1", "A0A0A1", "A0A0A2", "A0A0A3"),
l = c(2.140000, 7.240000, 7.240000, 2.140000, 7.240000, 7.240000, 6.000000, 4.000000),
d = c(3.580000, 7.240000, 7.240000, 3.580000, 7.240000, 7.240000, 6.000000, 4.000000),
h = c(4.760000, 2.580000, 2.580000, 4.760000, 2.580000, 2.580000, 6.000000, 4.000000),
w = c(243.0000, 110.0000, 110.0000, 243.0000, 110.0000, 110.0000, 235.0000, 258.0000)
)
knitr::kable(it)| oid | sku | l | d | h | w |
|---|---|---|---|---|---|
| 1428571 | A0A0A0 | 2.14 | 3.58 | 4.76 | 243 |
| 1428571 | A0A0A1 | 7.24 | 7.24 | 2.58 | 110 |
| 1428571 | A0A0A1 | 7.24 | 7.24 | 2.58 | 110 |
| 1428572 | A0A0A0 | 2.14 | 3.58 | 4.76 | 243 |
| 1428572 | A0A0A1 | 7.24 | 7.24 | 2.58 | 110 |
| 1428572 | A0A0A1 | 7.24 | 7.24 | 2.58 | 110 |
| 1428572 | A0A0A2 | 6.00 | 6.00 | 6.00 | 235 |
| 1428572 | A0A0A3 | 4.00 | 4.00 | 4.00 | 258 |
#- bn
# bn bins <data.table>
# - id bn id <character>
# - l: bn length limit along x-coordinate <numeric>
# - d: bn depth limit along y-coordinate <numeric>
# - h: bn height limit along z-coordinate <numeric>
# - w: bn weight limit along w - a separate single dimension <numeric>
# - l, d, h will be sorted to have l >= d >= h within solver
# bin must be ordered by preference such that the first bin is most preferred one.
bn <- data.table::data.table(
id = c("K0001", "K0002", "K0003", "K0004", "K0005"),
l = c(06.0000, 10.0000, 09.0000, 10.0000, 22.0000),
d = c(06.0000, 08.0000, 08.0000, 10.0000, 14.0000),
h = c(06.0000, 06.0000, 07.0000, 10.0000, 09.0000),
w = c(600.000, 600.000, 800.000, 800.000, 800.000)
)
knitr::kable(bn)| id | l | d | h | w |
|---|---|---|---|---|
| K0001 | 6 | 6 | 6 | 600 |
| K0002 | 10 | 8 | 6 | 600 |
| K0003 | 9 | 8 | 7 | 800 |
| K0004 | 10 | 10 | 10 | 800 |
| K0005 | 22 | 14 | 9 | 800 |
The function gbp::bpp_solver(it, bn) aims to pack each order into the smallest number of bins, and then smallest bins to achieve highest utlization rate, subject to the three dimensional none overlap contraints and weight limit constraint.
#- bpp_solver: output: packing solution
#- sn
# sn bpp_solution packing solution <list>
# - it item <data.table>
# - oid: order id <integer>
# - sku: stock keeping unit as it id <character>
# - tid: ticket id - an unique id within oid <integer>
# - otid: order id x ticket id - an unique indentifier indicate it with same tid can be packed into one bin <character>
# - bid: bn id <integer>
# - x, y, z it position in bid bin <numeric>
# - l, d, h it scale along x, y, z <numeric>
# - w it weight <numeric>
# - bn bins <data.table>
# - id bn id <character>
# - l bn length limit along x-coordinate <numeric>
# - d bn depth limit along y-coordinate <numeric>
# - h bn height limit along z-coordinate <numeric>
# - w bn weight limit along w - a separate single dimension <numeric>
sn <- gbp::bpp_solver(it = it, bn = bn)## bpp_solver_dpp: processing order id: 1428571 on index: 0 - 2 ..
## bpp_solver_dpp: processing order id: 1428572 on index: 3 - 7 ..sn$it## oid tid otid bid sku x y z l d h w
## 1: 1428571 1 1428571X1 K0002 A0A0A0 7.24 0.00 0.00 2.14 3.58 4.76 243
## 2: 1428571 1 1428571X1 K0002 A0A0A1 0.00 0.00 2.58 7.24 7.24 2.58 110
## 3: 1428571 1 1428571X1 K0002 A0A0A1 0.00 0.00 0.00 7.24 7.24 2.58 110
## 4: 1428572 2 1428572X2 K0001 A0A0A0 0.00 0.00 0.00 3.58 2.14 4.76 243
## 5: 1428572 1 1428572X1 K0004 A0A0A1 0.00 0.00 2.58 7.24 2.58 7.24 110
## 6: 1428572 1 1428572X1 K0004 A0A0A1 0.00 0.00 0.00 7.24 7.24 2.58 110
## 7: 1428572 1 1428572X1 K0004 A0A0A2 0.00 2.58 2.58 6.00 6.00 6.00 235
## 8: 1428572 1 1428572X1 K0004 A0A0A3 6.00 2.58 2.58 4.00 4.00 4.00 258sn$bn## id l d h w
## 1: K0001 6 6 6 600
## 2: K0002 10 8 6 600
## 3: K0003 9 8 7 800
## 4: K0004 10 10 10 800
## 5: K0005 22 14 9 800The packing solution is revealed in the data.table sn[[“it”]]. The packing solution table includes 12 columns: the order id (oid), the stock keeping unit (sku), the ticket id (tid) which identify items should be packed into the same bin, the order ticket id (otid) which is a unique identifier accross all orders, the bin id (bid) which identify the bin type associated with the ticket, the coordinates within the bin x, y, z, and the item’s length (l), depth (d), height (h) and weight (w). The solution can be viewed using gbp::bpp_viewer(sn).
#- bpp_viewer: a packing solution viewer
# requires rgl, run in r-console will create interactive 3d views in rgl window
# bpp_viewer(sn)The function bpp_solver is fast. I applied a simpler version of bpp_solver when designing and optimizing the set of boxes used in Jet.com’s warehouses. Back then, Jet.com receives 15,000 - 20,000 orders everyday, and 1 - 100 items in each order. The bpp_solver can pack all orders in 2 minutes - 5 minutes. The solution quality is also high. We formulated a mixed integer linear programming algorithm to find global optimial solution, using the bpp_solver solution as initial search point. We observed that bpp_solver solution is often equivalent or very close to the global optimial solution - often within 1% - 2% of utilization rate difference. One particular case to note is that the utilization rate difference could be as high as 4% - 5% when bpp_solver solution requires exact 2 bins. This is a consequence of the greedy algorithm. At last, the bpp_solver is 300x faster than the mixed integer linear programming.
The design flow of c-level classes, solvers and viewers are straightforward. The gbp1d, gbp2d, gbp3d, and gbp4d are classes defined at each dimension, an instance of such class holds a feasible bin packing solution in corresponding dimension. The gbp1d_solver_dpp, gbp2d_solver_dpp, gbp3d_solver_dpp, and gbp4d_solver_dpp are solvers designed to solve corresponding problem, and return an instance of corresponding class. The gbp2d_checkr, gbp3d_checkr, and gbp4d_checkr are checkers designed to verify a solution is feasible. And, the gbp2d_viewer, gbp3d_viewer, and gbp4d_viewer are viewers designed to visualize a solution.
The 4d scenairo contains two classes gbp4d and gbp4q, and two solvers gbp4d_solver_dpp and gbp4d_solver_dpp_filt.
The two solvers implement an extreme point based best fit first recursive algorithm. At each step an item is fit into all pontential positions with all possible orientation, and a fit schema is scored by entropy of the extreme points segmented residual space. The fit schema with lowest entropy score will be selected for recursive calls. The recursive is a limited rescursive fit on last few high profitable items, number of recursive call is gradually increasing toward the end of fit sequence. The idea is that last few items often small, moving them around can help finding feasible solutions.
The function gbp4d_solver_dpp(p, ldhw, m) aims to solve four dimensional bin packing (three dimensional none overlapping with weight limit) with repect to packing into a single bin. The inputs are the profit vector p which is a numeric vector defines the item’s packing sequence, highest profit first pack, the item’s characterization matrix (ldhw) which is a 4 x N numeric matrix with each column corresponding to an item’s length, depth, height and weight, and the bin’s characterization vector (m) which is a 4 x 1 numeric vector corresponding to bin’s length, depth, height and weight limit. The objective is fit as much item volume as possible into the bin. The solution resturned is an instance of gbp4d class.
#- gbp4d
#- ldhw: item l, d, h, w in matrix
ldhw <- t(as.matrix(it[oid == 1428572L, .(l, d, h, w)]))
ldhw## [,1] [,2] [,3] [,4] [,5]
## l 2.14 7.24 7.24 6 4
## d 3.58 7.24 7.24 6 4
## h 4.76 2.58 2.58 6 4
## w 243.00 110.00 110.00 235 258#- m: bin l, d, h in matrix
m <- t(as.matrix(bn[ , .(l, d, h, w)])) # multple bin
m## [,1] [,2] [,3] [,4] [,5]
## l 6 10 9 10 22
## d 6 8 8 10 14
## h 6 6 7 10 9
## w 600 600 800 800 800#- p: item fit sequence w.r.t bin
p <- gbp4d_solver_dpp_prep_create_p(ldhw, m[, 4L]) # single bin
p## [,1]
## [1,] 0
## [2,] 3
## [3,] 4
## [4,] 2
## [5,] 1#- sn
sn4d <- gbp4d_solver_dpp(p, ldhw, m[, 4L])
sn4d$it # matrix of items x, y, z, w (weight bn is holding when fit it into bn), l, d, h, w (weight of it itself) (x, y, z, w set into -1 when item not fit into bin)## [,1] [,2] [,3] [,4] [,5]
## [1,] -1.00 0.00 0.00 0.00 6.00
## [2,] -1.00 0.00 0.00 2.58 2.58
## [3,] -1.00 2.58 0.00 2.58 2.58
## [4,] -1.00 110.00 0.00 220.00 455.00
## [5,] 2.14 7.24 7.24 6.00 4.00
## [6,] 4.76 2.58 7.24 6.00 4.00
## [7,] 3.58 7.24 2.58 6.00 4.00
## [8,] 243.00 110.00 110.00 235.00 258.00sn4d$k # indicator of which items are fitted into bin## [,1]
## [1,] 0
## [2,] 1
## [3,] 1
## [4,] 1
## [5,] 1sn4d$bn # matrix of bins l, d, h, w (weight limit)## [,1]
## [1,] 10
## [2,] 10
## [3,] 10
## [4,] 800sn4d$o # volume of items fitted into bin## [1] 550.4748sn4d$ok # indicator of whether all items are fitted into bin## [1] FALSEgbp4d_checkr(sn4d) #- check: no overlap in 3d volume and no over weight limit## [1] TRUE# gbp4d_viewer(sn4d)The function gbp4d_solver_dpp_filt(ldhw, m) aims to solve four dimensional bin packing (three dimensional none overlapping with weight limit) with repect to packing into a multiple bins. The input bin’s characterization vector (m) is a 4 x M numeric vector with each column corresponding to one bin’s length, depth, height and weight limit. The objective is fit as much item volume as possible into the bin, and select the bin with smaller index when two bin’s can fit the same volume. The solution resturned is an instance of gbp4q class.
#- gbp4q
sn4q <- gbp4d_solver_dpp_filt(ldhw, m) # multiple bins, no fit sequence p
# p is determined w.r.t each bin using algorithm in gbp4d_solver_dpp_prep_create_p
sn4q$it # matrix of items x, y, z, w (weight bn is holding when fit it into bn), l, d, h, w (weight of it itself) (x, y, z, w set into -1 when item not fit into bin)## [,1] [,2] [,3] [,4] [,5]
## [1,] -1.00 0.00 0.00 0.00 6.00
## [2,] -1.00 0.00 0.00 2.58 2.58
## [3,] -1.00 2.58 0.00 2.58 2.58
## [4,] -1.00 110.00 0.00 220.00 455.00
## [5,] 2.14 7.24 7.24 6.00 4.00
## [6,] 4.76 2.58 7.24 6.00 4.00
## [7,] 3.58 7.24 2.58 6.00 4.00
## [8,] 243.00 110.00 110.00 235.00 258.00sn4q$k # indicator of which items are fitted into bin## [,1]
## [1,] 0
## [2,] 1
## [3,] 1
## [4,] 1
## [5,] 1sn4q$bn # matrix of bins l, d, h, w (weight limit)## [,1] [,2] [,3] [,4] [,5]
## [1,] 6 10 9 10 22
## [2,] 6 8 8 10 14
## [3,] 6 6 7 10 9
## [4,] 600 600 800 800 800sn4q$f # indicator of which bin is selected## [,1]
## [1,] 0
## [2,] 0
## [3,] 0
## [4,] 1
## [5,] 0sn4q$o # volume of items fitted into bin## [1] 550.4748sn4q$ok # indicator of whether all items are fitted into bin## [1] FALSEgbp4q_checkr(sn4q) #- check: no overlap in 3d volume and no over weight limit## [1] TRUE# gbp4q_viewer(sn4q)The 3d scenairo contains two classes gbp3d and gbp3q, and two solvers gbp3d_solver_dpp and gbp3d_solver_dpp_filt.
The function gbp3d_solver_dpp(p, ldh, m) aims to solve three dimensional bin packing with repect to packing into a single bin. The inputs are the profit vector p which is a numeric vector defines the item’s packing sequence, highest profit first pack, the item’s characterization matrix (ldh) which is a 3 x N numeric matrix with each column corresponding to an item’s length, depth, and height, and the bin’s characterization vector (m) which is a 3 x 1 numeric vector corresponding to bin’s length, depth, and height. The objective is fit as much item volume as possible into the bin, and the solution resturned is an instance of gbp3d class.
#- gbp3d
sn3d <- gbp3d_solver_dpp(p, ldhw[1L:3L, ], m[, 4L])
sn3d$it # matrix of items x, y, z, l, d, h (x, y, z set into -1 when item not fit into bin)## [,1] [,2] [,3] [,4] [,5]
## [1,] 6.00 0.00 0.00 0.00 6.00
## [2,] 6.58 0.00 0.00 2.58 2.58
## [3,] 2.58 2.58 0.00 2.58 2.58
## [4,] 3.58 7.24 7.24 6.00 4.00
## [5,] 2.14 2.58 7.24 6.00 4.00
## [6,] 4.76 7.24 2.58 6.00 4.00sn3d$k # indicator of which items are fitted into bin## [,1]
## [1,] 1
## [2,] 1
## [3,] 1
## [4,] 1
## [5,] 1sn3d$bn # matrix of bins l, d, h## [,1]
## [1,] 10
## [2,] 10
## [3,] 10
## [4,] 800sn3d$o # volume of items fitted into bin## [1] 586.9421sn3d$ok # indicator of whether all items are fitted into bin## [1] TRUEgbp3d_checkr(sn3d) #- check: no overlap in 3d volume## [1] TRUE# gbp3d_viewer(sn3d)The function gbp3d_solver_dpp_filt(ldh, m) aims to solve three dimensional bin packing with repect to packing into a multiple bins. The input bin’s characterization vector (m) is a 3 x M numeric vector with each column corresponding to one bin’s length, depth, and height. The objective is fit as much item volume as possible into the bin, and select the bin with smaller index when two bin’s can fit the same volume. The solution resturned is an instance of gbp3q class.
#- gbp3q
sn3q <- gbp3d_solver_dpp_filt(ldhw[1L:3L, ], m) # multiple bins, no fit sequence p
# p is determined w.r.t each bin using algorithm in gbp3d_solver_dpp_prep_create_p
sn3q$it # matrix of items x, y, z, l, d, h (x, y, z set into -1 when item not fit into bin)## [,1] [,2] [,3] [,4] [,5]
## [1,] 6.00 0.00 0.00 0.00 6.00
## [2,] 2.58 0.00 0.00 2.58 4.72
## [3,] 2.58 2.58 0.00 2.58 2.58
## [4,] 3.58 7.24 7.24 6.00 4.00
## [5,] 2.14 2.58 7.24 6.00 4.00
## [6,] 4.76 7.24 2.58 6.00 4.00sn3q$k # indicator of which items are fitted into bin## [,1]
## [1,] 1
## [2,] 1
## [3,] 1
## [4,] 1
## [5,] 1sn3q$bn # matrix of bins l, d, h## [,1] [,2] [,3] [,4] [,5]
## [1,] 6 10 9 10 22
## [2,] 6 8 8 10 14
## [3,] 6 6 7 10 9
## [4,] 600 600 800 800 800sn3q$f # indicator of which bin is selected## [,1]
## [1,] 0
## [2,] 0
## [3,] 0
## [4,] 1
## [5,] 0sn3q$o # volume of items fitted into bin## [1] 586.9421sn3q$ok # indicator of whether all items are fitted into bin## [1] TRUEgbp3q_checkr(sn3q) #- check: no overlap in 3d volume## [1] TRUE# gbp3q_viewer(sn3q)The 2d scenairo contains two classes gbp2d and gbp2q, and two solvers gbp2d_solver_dpp and gbp2d_solver_dpp_filt.
The function gbp2d_solver_dpp(p, ld, m) aims to solve two dimensional bin packing with repect to packing into a single bin. The inputs are the profit vector p which is a numeric vector defines the item’s packing sequence, highest profit first pack, the item’s characterization matrix (ld) which is a 2 x N numeric matrix with each column corresponding to an item’s length and depth, and the bin’s characterization vector (m) which is a 2 x 1 numeric vector corresponding to bin’s length and depth. The objective is fit as much item volume as possible into the bin, and the solution resturned is an instance of gbp2d class.
#- gbp2d
sn2d <- gbp2d_solver_dpp(p, ldhw[1L:2L, ], m[, 4L])
sn2d$it # matrix of items x, y, l, d (x, y set into -1 when item not fit into bin)## [,1] [,2] [,3] [,4] [,5]
## [1,] 7.24 -1.00 0.00 -1 -1
## [2,] 0.00 -1.00 0.00 -1 -1
## [3,] 2.14 7.24 7.24 6 4
## [4,] 3.58 7.24 7.24 6 4sn2d$k # indicator of which items are fitted into bin## [,1]
## [1,] 1
## [2,] 0
## [3,] 1
## [4,] 0
## [5,] 0sn2d$bn # matrix of bins l, d## [,1]
## [1,] 10
## [2,] 10
## [3,] 10
## [4,] 800sn2d$o # volume of items fitted into bin## [1] 60.0788sn2d$ok # indicator of whether all items are fitted into bin## [1] FALSEgbp2d_checkr(sn2d) #- check: no overlap in 2d area## [1] TRUE# gbp2d_viewer(sn2d) #- view on XZ surface and set Y into 1 to give stereo perceptionThe function gbp2d_solver_dpp_filt(ld, m) aims to solve two dimensional bin packing with repect to packing into a multiple bins. The input bin’s characterization vector (m) is a 2 x M numeric vector with each column corresponding to one bin’s length and depth. The objective is fit as much item volume as possible into the bin, and select the bin with smaller index when two bin’s can fit the same volume. The solution resturned is an instance of gbp2q class.
#- gbp2q
sn2q <- gbp2d_solver_dpp_filt(ldhw[1L:2L, ], m) # multiple bins, no fit sequence p
# p is determined w.r.t each bin using algorithm in gbp2d_solver_dpp_prep_create_p
sn2q$it # matrix of items x, y, l, d (x, y set into -1 when item not fit into bin)## [,1] [,2] [,3] [,4] [,5]
## [1,] 18.48 7.24 0.00 14.48 14.48
## [2,] 6.00 0.00 0.00 0.00 6.00
## [3,] 2.14 7.24 7.24 6.00 4.00
## [4,] 3.58 7.24 7.24 6.00 4.00sn2q$k # indicator of which items are fitted into bin## [,1]
## [1,] 1
## [2,] 1
## [3,] 1
## [4,] 1
## [5,] 1sn2q$bn # matrix of bins l, d## [,1] [,2] [,3] [,4] [,5]
## [1,] 6 10 9 10 22
## [2,] 6 8 8 10 14
## [3,] 6 6 7 10 9
## [4,] 600 600 800 800 800sn2q$f # indicator of which bin is selected## [,1]
## [1,] 0
## [2,] 0
## [3,] 0
## [4,] 0
## [5,] 1sn2q$o # volume of items fitted into bin## [1] 164.4964sn2q$ok # indicator of whether all items are fitted into bin## [1] TRUEgbp2q_checkr(sn2q) #- check: no overlap in 2d area## [1] TRUE# gbp2q_viewer(sn2q)The 1d scenairo contains a single solver gbp1d_solver_dpp, which aims to solve one dimensional bin packing problem, a.k.a Knapsack problem. In mathematical, gbp1d_solver_dpp(p, w, c) will: maximize \(\sum_{j=1}^{n} p_j x_j\), subject to \(\sum_{j=1}^{n} w_j x_j \leq c, x_j \in \{0, 1\}, j = 1, ...., n\), where p is a numeric vector of each item’s profit, w is an integer vector of each item’s weight, c is an integer scalar of the total weight limit.
The function gbp1d_solver_dpp(p, w, c) implements a dynamic programming solution, and return an instance of gbp1d class. A gbp1d class instance would have 6 member fields: the profit vector p, the weight vector w, the weight constraint c, the selection vector k which is a boolean vector indicates whether or not an item is selected in the solution, the objective value o which is the sum of the weight of the items selected, and the boolean indicator ok indicates whether or not all items are selected.
#- gbp1d
v <- apply(ldhw[1L:3L, ], 2L, prod)
sn1d <- gbp1d_solver_dpp(p = v, w = ldhw[4L, ], c = 714.28)
sn1d$p # vector of items profit## [,1]
## [1,] 36.46731
## [2,] 135.23741
## [3,] 135.23741
## [4,] 216.00000
## [5,] 64.00000sn1d$w # vector of items weight## [,1]
## [1,] 243
## [2,] 110
## [3,] 110
## [4,] 235
## [5,] 258sn1d$c # weight limit constraint## [1] 714sn1d$k # indicator of which items are selected## [,1]
## [1,] 0
## [2,] 1
## [3,] 1
## [4,] 1
## [5,] 1sn1d$o # weight of items selected## [1] 550.4748sn1d$ok # indicator of whether all items are selected## [1] FALSEA shiny application that demonstrates how to use gbp function bpp_solver in fulfilling the order packing process in business operations.