Code Monkey home page Code Monkey logo

gbp's Introduction

gbp: A bin packing problem solver

Overview

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.

Vignettes

A vignettes that demonstrates the infrastructure and algorithms available from this r-package.

A shiny application that demonstrates how to use gbp function bpp_solver in fulfilling the order packing process in business operations.

OpenCPU API

An example call to gbp::bpp_solver when an OpenCPU server is running with package gbp installed.

curl http://localhost:8004/ocpu/library/gbp/R/bpp_solver/json -H "Content-Type: application/json" -d '{"it":[{"oid":1000001,"sku":"A0A0A0","l":2.14,"d":3.58,"h":4.76,"w":243},{"oid":1000001,"sku":"A0A0A1","l":7.24,"d":7.24,"h":2.58,"w":110},{"oid":1000001,"sku":"A0A0A1","l":7.24,"d":7.24,"h":2.58,"w":110},{"oid":1000002,"sku":"A0A0A0","l":2.14,"d":3.58,"h":4.76,"w":243},{"oid":1000002,"sku":"A0A0A1","l":7.24,"d":7.24,"h":2.58,"w":110},{"oid":1000002,"sku":"A0A0A1","l":7.24,"d":7.24,"h":2.58,"w":110},{"oid":1000002,"sku":"A0A0A2","l":6,"d":6,"h":6,"w":235},{"oid":1000002,"sku":"A0A0A3","l":4,"d":4,"h":4,"w":258}], "bn":[{"id":"K0001","l":10,"d":10,"h":10},{"id":"K0010","l":20,"d":20,"h":20}], "wlmt":800, "wprecision":1}'

gbp's People

Contributors

gyang274 avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar

gbp's Issues

Package should declare version requirement for RcppArmadillo

I recently tried to install this package on my Linux machine and came across the following error:

g++ -std=gnu++11 -I/usr/share/R/include -DNDEBUG  -I"/home/sebastian/R/x86_64-pc-linux-gnu-library/3.4/Rcpp/include" -I"/home/sebastian/R/x86_64-pc-linux-gnu-library/3.4/RcppArmadillo/include"   -I../inst/include -fpic  -g -O2 -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -g -c RcppExports.cpp -o RcppExports.o
g++ -std=gnu++11 -I/usr/share/R/include -DNDEBUG  -I"/home/sebastian/R/x86_64-pc-linux-gnu-library/3.4/Rcpp/include" -I"/home/sebastian/R/x86_64-pc-linux-gnu-library/3.4/RcppArmadillo/include"   -I../inst/include -fpic  -g -O2 -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -g -c bpp.cpp -o bpp.o
In file included from bpp.cpp:1:0:
gbp_u.h: In function ‘bool approx_equal_cpp(const T&, const T&, double)’:
gbp_u.h:26:10: error: ‘approx_equal’ is not a member of ‘arma’
   return arma::approx_equal(lhs, rhs, "absdiff", tol);
          ^
/usr/lib/R/etc/Makeconf:168: recipe for target 'bpp.o' failed
make: *** [bpp.o] Error 1

I managed to fix it by updating my version of RcppArmadillo. Apparently the approx_equal function was only introduced in 0.6.700.3.0 which was released 2016-04-05.

The package should declare this requirement somewhere. Perhaps in the DESCRIPTION?

Sort Error

I am using the gbp::bpp_solver. I am getting the following error :
'''error: sort_index(): detected NaN
Error in gbp::bpp_solver_dpp_wrapper(lkit, lkbn) :
sort_index(): detected NaN'''
To calrify, I have sorted oid and bins are also in format as required. Here is the order which is giving me the error.
error_order.xlsx

Platform : Microsoft Windows 10 Enterprise OS: 10.0.16299 (Build 1709)

Stuck when item too large

If I run the bin-packing algorithm gbp::bpp:solver with an item that does not completely fit within the dimensions of the largest bin, the program freezes and the R session is stuck/unresponsive

quantity of the order and containers

Hi gyang274:

I'm on a project to solve a bin packing problem. and I tried you Rscript GBP. I feels the packing works great. Thanks for that.

however I encountered several problems, plz advice, thanks ahead

  1. is there a way that I can defined the quantity of the orders and containers? Because in my projects I need to pack multiple produces with the same size. and multiple same sized containers
  2. can i define, dont let the products rotate, cause some products had to be face up.
  3. can i define packing priority, cause some sku need to go first

I know i have many questions, thanks ahead, again, this is a great package, deeply appreciated

best

Ning

Packing is not optimised

There are 28 items and the container "K0004" is able to fit all of them. However, gbp couldn't fit the last item (1000, 1000, 1000, 100), it can only fit 27/28.

The "breaking point" of the last item is (877, 1000, 1000, 100) which if the value of 1000 is changed to 877, it packs all items correctly.

bn <- data.table::data.table(
 id = c("K0001", "K0002", "K0003", "K0004", "K0005"),
 l  = c(06.0000, 10.0000, 09.0000, 1500.0000, 22.0000),
 d  = c(06.0000, 08.0000, 08.0000, 1000.0000, 14.0000),
 h  = c(06.0000, 06.0000, 07.0000, 3200.0000, 09.0000),
 w  = c(600.000, 600.000, 800.000, 12000.000, 800.000)
)

it <- data.table::data.table(
 l   = c(  75, 600, 720, 611, 611,  656,  656, 100, 700,  80,  80,  40,  40,  40,   16,   16,   18, 2500, 700,   75, 100, 720,  55, 750, 535, 100, 700, 1000),
 d   = c( 650, 150, 620,  31,  31,   18,   18, 850, 400, 770, 770, 100, 100, 100, 2500, 2500, 2720,  650, 400,  650, 650, 620, 500,  17, 110, 550, 500, 1000),
 h   = c(1600,  18,  78, 791, 799, 2033, 2033, 750,  50, 850, 850, 165, 165, 165,   11,   11,  160,   30,  50, 1600, 750,  78, 745,  30, 500, 750,  50, 1000),
 w   = c(3500,  14, 130,  99,  99,  143,  143, 250,  60, 150, 150,   1,   1,   1,    4,    4,   48,  210,  60,  350, 220, 130,  90,  26,  35, 200,  75,  100)
)

ldhw <- t(as.matrix(it))

m <- t(as.matrix(bn[ , .(l, d, h, w)])) # multple bin
p <- gbp4d_solver_dpp_prep_create_p(ldhw, m[, 4L]) # single bin
sn4d <- gbp4d_solver_dpp(p, ldhw, m[, 4L])
gbp4d_viewer(sn4d)

Package dependencies

Thanks for the package!

Would you consider isolating the very packing algorithm in a separate package from the rgl-based viewer? Or at least make rgl as Suggested not Imported?

rgl introduces rather heavy set of dependencies. If just want to use (a package that uses) your implementation internally, and, say, on a headless server, I need to install rgl which requires a lot of system libraries including X11....

failing to find optimal solution

bn l=1870 d=1200 h=1000 w=1000000
12 times it: l=426 d=795 h=390 w=1.12

those 12 items trivially fit into the bn, but the solution can only pack 8 in one bn and adds a second bin. why?

no rotation

Hi. Can I somehow turn off rotation and get a solution without rotation of objects? thanks. Ivo

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.