JT Smith > Box-Calc > Box::Calc

Download:
Box-Calc-1.0000.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 1.0000   Source  

NAME ^

Box::Calc - Packing Algorithm

VERSION ^

version 1.0000

SYNOPSIS ^

 use Box::Calc;
 
 my $box_calc = Box::Calc->new;
 
 # define the possible box types
 $box_calc->add_box_type( x => 12, y => 12, z => 18, weight => 16, name => 'big box' );
 $box_calc->add_box_type( x => 4, y => 6, z => 8, weight => 6, name => 'small box' );

 # define the items you want to put into boxes
 $box_calc->add_item( 3,  { x => 6, y => 3, z => 3, weight => 12, name => 'soda' });
 $box_calc->add_item( 1,  { x => 3.3, y => 3, z => 4, weight => 4.5, name => 'apple' });
 $box_calc->add_item( 2,  { x => 8, y => 2.5, z => 2.5, weight => 14, name => 'water bottle' });

 # figure out what you need to pack this stuff
 $box_calc->pack_items;
 
 # how many boxes do you need
 my $box_count = $box_calc->count_boxes; # 2
 
 # interogate the boes
 my $box = $box_calc->get_box(-1); # the last box
 my $weight = $box->calculate_weight;
 
 # get a packing list
 my $packing_list = $box_calc->packing_list;

DESCRIPTION ^

Box::Calc helps you determine what can fit into a box for shipping or storage purposes. It will try to use the smallest box possible of the box types. If every item won't fit into your largest box, then it will span the boxes letting you know how many boxes you'll need.

Once it's done packing the boxes, you can get a packing list for each box, as well as the weight of each box.

How The Algorithm Works

Box::Calc is intended to pack boxes in the simplest way possible. Here's what it does:

  1. Sort all the items by volume.
  2. Eliminate all boxes that won't fit the largest items.
  3. Choose the smallest box still available.
  4. Place the items in a row starting with the largest items.
  5. When the row runs out of space, add another.
  6. When you run out of space to add rows, add a layer.
  7. When you run out of layers either start over with a bigger box, or if there are no bigger boxes span to a second box.
  8. Repeat from step 3 until all items are packed into boxes.

Motivation

At The Game Crafter (http://www.thegamecrafter.com) we ship a lot of games and game pieces. We tried using a more complicated system for figuring out which size box to use, or how many boxes would be needed in a spanning situation. The problem was that those algorithms made the boxes pack so tightly that our staff spent a lot more time putting the boxes together. This algorithm is relatively dumb, but dumb in a good way. The boxes are easy and fast to pack. By releasing this, we hope it can help those who are either using too complicated a system, or no system at all for figuring out how many boxes they need for shipping/storing materials.

Tips

When adding items, be sure to use the outer most dimensions of oddly shaped items, otherwise they may not fit the box.

When adding box types, be sure to use the inside dimensions of the box. If you plan to line the box with padding, then subtract the padding from the dimensions, and also add the padding to the weight of the box.

What units you use (inches, centimeters, ounces, pounds, grams, kilograms, etc) don't matter as long as you use them consistently.

METHODS ^

new()

Constructor.

box_types()

Returns an array reference of the Box::Calc::BoxTypes registered.

count_box_types()

Returns the number of Box::Calc::BoxTypes registered.

get_box_type(index)

Returns a specific Box::Calc::BoxType from the list of box_types

index

An array index. For example this would return the last box type added:

 $box_calc->get_box_type(-1)

add_box_type(params)

Adds a new Box::Calc::BoxType to the list of box_types. Returns the newly created Box::Calc::BoxType instance.

params

The list of constructor parameters for Box::Calc::BoxType.

NOTE: You can optionally include an argument of "categories" and a box type will be created for each category so you don't have to do it manually.

box_type_categories()

Returns an array reference of categories associated with the box types.

sort_box_types_by_volume()

Sorts the list of box_types by volume and then returns an array reference of that list.

types

Optional. Array ref of box types. Will call box_types if not passed in.

determine_viable_box_types(category)

Given the list of items and the list of box_types this method rules out box types that cannot hold the largest item, and returns the list of box types that will work sorted by volume.

category

Optional. If this is specified, it will match this category name to the categories attached to the boxes and only provide a list of boxes that match that category.

items()

Returns an array reference of the Box::Calc::Items registered.

count_items()

Returns the number of Box::Calc::Items registered.

get_item(index)

Returns a specific Box::Calc::Item.

index

The array index of the item as it was registered.

add_item(quantity, params)

Registers a new item. Returns the new item registered.

quantity

How many copies of this item should be included in the package?

params

The constructor parameters for the Box::Calc::Item.

load(payload)

Allows the loading of an entire dataset.

payload

A hash reference containing the output of the dump method, with two exceptions:

  • You can create a categories element that is an array ref in each box type rather than creating duplicate box types for each category.
  • You can create a quantity element in each item rather than creating duplicate items to represent the quantity.

dump()

sort_items_by_volume()

Returns an array reference of the list of items registered sorted by volume.

items

Optional. An array reference of items. Will call items if not passed in.

sort_items_by_zxy()

Returns an array reference of the list of items registered sorted by z, then x, then y, ascending.

items

Optional. An array reference of items. Will call items if not passed in.

sort_items_by_zA()

Returns an array reference of the list of items registered sorted by z ASC, then area DESC

items

Optional. An array reference of items. Will call items if not passed in.

sort_items_by_Az()

items

Optional. An array reference of items. Will call items if not passed in.

Returns an array reference of the list of items registered sorted by A DESC, then z ASC

find_max_dimensions_of_items()

Given the registered items, returns the max x, y, and z of all items registered as an array reference.

boxes()

Returns an array reference of the list of Box::Calc::Boxes needed to pack up the items.

NOTE: This will be empty until you call pack_items.

count_boxes()

Returns the number of boxes needed to pack up the items.

get_box(index)

Fetches a specific box from the list of <boxes>.

index

The array index of the box you wish to fetc.

reset_boxes()

Deletes the list of boxes.

If you wish to rerun the packing you should use this to delete the list of boxes first. This is handy if you needed to add an extra item or extra box type after you already ran pack_items.

reset_items()

Deletes the list of items.

For the sake of speed you may wish to reuse a Box::Calc instance with the box types already pre-loaded. In that case you'll want to use this method to remove the items you've already registered. You'll probably also want to call reset_boxes.

find_tallest_z ( [ items ] )

Determines the median of z across all items in the list.

items

An array reference of items. Optional. Defaults to items.

stack_like_items( options )

Stacks all like-sized items into stacks of stack_height for denser packing. Could be used as an optimizer before running pack_items.

options

A hash.

items

Optional. If not specified, will be the items list.

stack_height

Optional. If not specified, will be determined by calling find_tallest_z.

pack_items(options)

Uses the list of box_types and the list of items to create the list of boxes to be packed. This method populates the boxes list.

options

A hash.

items

Optional. If omitted the items list will be populated with whatever the current best general purpose preprocessed item list is. Currently that is sort_items_by_zA.

category

Optional. If this is specified, it will match this category name to the categories attached to the boxes and only pack in boxes that match that category.

packing_list()

Returns a data structure with all the item names and quantities packed into boxes. This can be used to generate manifests.

 [
    {                                   # box one
        id              => "xxx",
        name            => "big box",
        weight          => 30.1,
        packing_list    => {
            "soda"          => 3,
            "apple"         => 1,
            "water bottle"  => 2,
        }
    }
 ]

packing_instructions()

Returns a data structure with all the item names individually packed into rows, layers, and boxes. This can be used to build documentation on how to pack a set of boxes, and to generate a complete build history.

 [
    {                                                   # box one
        id              => "xxx",
        name            => "big box",
        layers           => [    
            {                                           # layer one
                rows => [
                    {                                   # row one
                        items => [
                            {                           # item one
                                name    => "apple",
                                ...
                            },
                            ...
                        ],
                    },
                    ...
                ],
                ...
            },
        ],
    },
 ]

TODO ^

There are some additional optimizations that could be done to speed things up a bit. We might also be able to get a better fill percentage (less void space), although that's not really the intent of Box::Calc.

PREREQS ^

Moose Ouch Log::Any

SUPPORT ^

Repository

http://github.com/rizen/Box-Calc

Bug Reports

http://github.com/rizen/Box-Calc/issues

SEE ALSO ^

Although these modules don't solve the same problem as this module, they may help you build something that does if Box::Calc doesn't quite help you do what you want.

Algorithm::Knapsack
Algorithm::Bucketizer
Algorithm::Knap01DP

AUTHOR ^

JT Smith <jt_at_plainblack_dot_com>
Colin Kuskie <colink_at_plainblack_dot_com>

LEGAL ^

Box::Calc is Copyright 2012 Plain Black Corporation (http://www.plainblack.com) and is licensed under the same terms as Perl itself.

syntax highlighting: