Container Optimization Algorithms

To select algorithms, go to the Logic Configuration page and select a Logic Configuration type of Container Optimization.

Note: The use of column generation with any 3D based algorithm (e.g. 3D load configuration, pattern based load configuration, tree search based load configuration) is not recommended.

The following diagram shows the interaction and incompatibilities of the Column Generation algorithm with other algorithms. 

Note: The following diagram is only applicable when choosing Column Generation or Multi-Container MIP. Other packing algorithms (e.g., Quick Packing, Enumeration, Single Container MIP, Multi-Container Heuristic, 3D Load Config, Pattern Based Load Config, and Tree Search Load Config) can be used independently without using Column Generation Algorithm or Multi-Container MIP.

 

The Column Generation algorithm employs other seed algorithms to generate various combinations of packing units into pieces of equipment. The other algorithms that you select, in addition to the Column Generation algorithm, are used as seed algorithms. However, there are some restrictions on choosing the seed algorithms.

• If no other algorithm is selected, then Quick Packing is used as the default seed algorithm for column generation.
• If one or more of the non-load-configuration only algorithms (i.e. Quick Packing, Enumerative, Single Container MIP, Multi-Container Heuristic) are selected along with the Column Generation algorithm, all of them will be used as seed algorithms for column generation.
• If one or more of only load-configuration algorithms (3D Load Config, Pattern Based Load Config, Tree Search Load Config, and Multi-Container Heuristic with 3D Load Config) are selected along with the Column Generation algorithm, all of them will be used as seed algorithms for column generation.
• If one or more non-load-configuration algorithms are selected along with one or more algorithms from the load-configuration set, then only the algorithms selected from the load-configuration set will be used as seed algorithms for column generation.
• If the Multi-container MIP algorithm is selected along with the Column Generation algorithm, the multi-container MIP algorithm is ignored.

Categorization of Container Optimization Algorithms

You need to select at least one algorithm for Container optimization to work. In all algorithms, the inputs are 1) Ship units (along with the counts) and 2) Equipment Groups (possibly with capacity limits) and the output is a set of containers (from the input eq groups) packed with the input ship units. There are various ways to achieve this with varying complexity, each having a different solution quality and run time consequences.

The algorithms can be categorized into two depending on whether OTM is packing all items into multiple containers at once (multi-container algorithms) OR pack one container at a time in an iterative manner until all items are packed (single container algorithms). In the latter, the idea is to pack one container of all equipment groups with the items, and greedily pick the container based on an objective such as utilization and continue again with the left over items and the left over distinct equipment groups. Once a container is picked along with the items in the algorithm, OTM does not go back and move around items to improve the utilization or change the equipment group at that time.

The algorithms can be categorized into two depending on whether the packing considers dimensions of the items and not just the weight and volume. Considering dimensions of the items and associated constraints, and showing exact placements of each ship unit piece is called Load Configuration. OTM has "Load Configuration" based algorithms and some non-load configuration  based.

Also, some of the algorithms use iterative algorithms/heuristics. Some others use Mathematical programming techniques (MIP - Mixed Integer Programming). Math programming techniques require modeling the problem at hand using variables and constraints, optimizing the objective (such as cost, utilization etc). This is another way of categorization.

 

Algorithms	Single container algorithm?	Math programming technique used?	Is it load configuration based?	Is it an exact algorithm?	Run time increases exponentially with problem size
USE 3D BASED LOAD CONFIGURATION	Y	N	Y	N	Y
USE BULK PACKING MIP	Y	Y	N	N	Y
USE COLUMN GENERATION ALGORITHM
USE ENUMERATIVE ALGORITHM	Y	N	N	N	Y
USE MULTICONTAINER HEURISTIC ALGORITHM	N	N	Y/N	N	N
USE MULTICONTAINER MIP	N	Y	N	Y	Y
USE PATTERN BASED LOAD CONFIGURATION	Y	N	Y	N	N
USE QUICK PACKING ALGORITHM	Y	N	N	N	N
USE SINGLE CONTAINER MIP	Y	Y	N	N	N
USE TREE SEARCH LOAD CONFIGURATION	Y	N	Y	N	Y

 

The default is "Use Quick Packing Algorithm". This is an algorithm where the items are sorted based on a certain metric. You can select multiple algorithms. Once you decide whether to use Load Configuration or not, you should select algorithms within that family. You should not mix Quick Packing and 3D Load Config, for example.

Quick Packing: The ship units are sorted based on a metric selected in the Container Optimization Metrics section. While packing a container, the algorithm packs the ship units from the sorted list one after the other until the container is full. This process is repeated with different equipment groups (same item list) and one equipment group is picked based on an objective selected in the Container Optimization Objectives section. After selecting the equipment, the items packed are removed from the list and the process is repeated with the updated item list and remaining equipment groups to pick the next equipment and so on.

Single Container MIP: This is a single container packing algorithm (like Quick packing) but this does not pack items from a sorted list but optimizes the items in order to pack the single container. This usually results in better packing but can take more run time. However, this is still packing one container at a time and hence the greediness of single container algorithms still exist.

Enumerative Algorithm: The algorithm and even the solution is the same as Single Container MIP. The difference is that solution is derived based on an algorithm iteratively using Dynamic Programming whereas Single Container MIP uses Math programming techniques. Both are solving the same problem called Knapsack problem, which is quite popular in the Computer algorithm/Operations Research communities.

Multicontainer MIP: This algorithm is an exact one that works well for smaller size Container Optimization problems. First, it estimates the maximum number of each equipment group that is needed to pack all the items. Then, using Math programming techniques, it assigns items to each instance of various equipment groups without violating constraints. This is an exact algorithm and can work well in cases when there are not too many equipment groups to work with. 

Note: Enable the log ID 'OptMipData' to export a CSV file of column generation information (like columns, dual, variable names and their OTM object references, load points) when it is used. This log can be used to analyse the solution obtained from the column generation.

Load configuration algorithms

3D Load Configuration: This is an algorithm where each ship unit piece is placed individually in the container, after ensuring that the constraints such as Space (cannot go out of container), Stacking constraints (stacking index, max weight, max height, stacking layer), overhang constraint, load bearing constraints, orientation constraints etc. are not violated. 3D scoring acts on top of the basic algorithm which tends to favor better utilization with higher run times. This is not an exact algorithm to minimize the loading length or minimize the equipment packed. This also packs one container at a time and is part of the single container algorithms. There is also a flavor here that uses auto-generated patterns as well as User-defined patterns.

Pattern Based Load Configuration: In this algorithm, each ship unit (all count) is packed in patterns. It has capability to pack boxes as well as cylinders. For boxes, it looks at patterns such as Lengthwise, Crosswise, Pinwheel (some lengthwise and some crosswise). For cylindrical shaped ship units, it considers Standing Straight, Standing Nested, Rolling, Cannon patterns. It can stack the same ship unit in multiple layers. If there's a remnant floor area leftover after placing a ship unit, the algorithm tries to place the next ship unit in that remnant area before trying new space away from the nose.

Tree Search Load Configuration: In this algorithm, there is logic to look ahead and consider what items are yet to be placed in order to determine what item to place now. This is a variation of 3D load configuration algorithm. This also considers all user defined constraints.

Multicontainer Heuristic: This is a heuristic that tries to pack items into multiple pieces of equipment at once rather than one piece of equipment at a time. This is still not an exact algorithm like Multicontainer MIP but it can scale well to larger problems. Also, this is a hybrid algorithm that can solve both non-3D as well as 3D. This algorithm in turn resorts to calling Quick packing/3D algorithm iteratively to solve the multi-container problem.