solver

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

sn$bn

##        id     l     d     h     w
##    <char> <num> <num> <num> <num>
## 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   800

The 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).

viewer

#- 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.

gbp4d

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 potential 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 recursive 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.

#- 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.00

sn4d$k  # indicator of which items are fitted into bin

##      [,1]
## [1,]    0
## [2,]    1
## [3,]    1
## [4,]    1
## [5,]    1

sn4d$bn # matrix of bins l, d, h, w (weight limit)

##      [,1]
## [1,]   10
## [2,]   10
## [3,]   10
## [4,]  800

sn4d$o  # volume of items fitted into bin

## [1] 550.4748

sn4d$ok # indicator of whether all items are fitted into bin

## [1] FALSE

gbp4d_checkr(sn4d) #- check: no overlap in 3d volume and no over weight limit

## [1] TRUE

# gbp4d_viewer(sn4d)

#- 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.00

sn4q$k  # indicator of which items are fitted into bin

##      [,1]
## [1,]    0
## [2,]    1
## [3,]    1
## [4,]    1
## [5,]    1

sn4q$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  800

sn4q$f  # indicator of which bin is selected

##      [,1]
## [1,]    0
## [2,]    0
## [3,]    0
## [4,]    1
## [5,]    0

sn4q$o  # volume of items fitted into bin

## [1] 550.4748

sn4q$ok # indicator of whether all items are fitted into bin

## [1] FALSE

gbp4q_checkr(sn4q) #- check: no overlap in 3d volume and no over weight limit

## [1] TRUE

# gbp4q_viewer(sn4q)

single bin

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.00

sn3d$k  # indicator of which items are fitted into bin

##      [,1]
## [1,]    1
## [2,]    1
## [3,]    1
## [4,]    1
## [5,]    1

sn3d$bn # matrix of bins l, d, h

##      [,1]
## [1,]   10
## [2,]   10
## [3,]   10
## [4,]  800

sn3d$o  # volume of items fitted into bin

## [1] 586.9421

sn3d$ok # indicator of whether all items are fitted into bin

## [1] TRUE

checkr

gbp3d_checkr(sn3d) #- check: no overlap in 3d volume

## [1] TRUE

viewer

# gbp3d_viewer(sn3d)

multiple bins

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.00

sn3q$k  # indicator of which items are fitted into bin

##      [,1]
## [1,]    1
## [2,]    1
## [3,]    1
## [4,]    1
## [5,]    1

sn3q$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  800

sn3q$f  # indicator of which bin is selected

##      [,1]
## [1,]    0
## [2,]    0
## [3,]    0
## [4,]    1
## [5,]    0

sn3q$o  # volume of items fitted into bin

## [1] 586.9421

sn3q$ok # indicator of whether all items are fitted into bin

## [1] TRUE

gbp3q_checkr(sn3q) #- check: no overlap in 3d volume

## [1] TRUE

# gbp3q_viewer(sn3q)

gbp2d

The 2d scenairo contains two classes gbp2d and gbp2q, and two solvers gbp2d_solver_dpp and gbp2d_solver_dpp_filt.

#- 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    4

sn2d$k  # indicator of which items are fitted into bin

##      [,1]
## [1,]    1
## [2,]    0
## [3,]    1
## [4,]    0
## [5,]    0

sn2d$bn # matrix of bins l, d

##      [,1]
## [1,]   10
## [2,]   10
## [3,]   10
## [4,]  800

sn2d$o  # volume of items fitted into bin

## [1] 60.0788

sn2d$ok # indicator of whether all items are fitted into bin

## [1] FALSE

gbp2d_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 perception

#- 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.00

sn2q$k  # indicator of which items are fitted into bin

##      [,1]
## [1,]    1
## [2,]    1
## [3,]    1
## [4,]    1
## [5,]    1

sn2q$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  800

sn2q$f  # indicator of which bin is selected

##      [,1]
## [1,]    0
## [2,]    0
## [3,]    0
## [4,]    0
## [5,]    1

sn2q$o  # volume of items fitted into bin

## [1] 164.4964

sn2q$ok # indicator of whether all items are fitted into bin

## [1] TRUE

gbp2q_checkr(sn2q) #- check: no overlap in 2d area

## [1] TRUE

# gbp2q_viewer(sn2q)

gbp1d

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.00000

sn1d$w # vector of items weight

##      [,1]
## [1,]  243
## [2,]  110
## [3,]  110
## [4,]  235
## [5,]  258

sn1d$c # weight limit constraint

## [1] 714

sn1d$k  # indicator of which items are selected

##      [,1]
## [1,]    0
## [2,]    1
## [3,]    1
## [4,]    1
## [5,]    1

sn1d$o  # weight of items selected

## [1] 550.4748

sn1d$ok # indicator of whether all items are selected

## [1] FALSE