Loading a shipping container — Part I
Lets start with a fable about 3D bin packing. Yes, they were worried about algorithms in the panchatantra era too. Our default character set: a wise old sage, one greedy miner and one righteous miner. The sage offers the following get-rich-quick scheme to the miners. There is a heap of 100 gold bricks and 1 wooden trunk. Each brick has a uniquely different length, breadth and height. But the sage wants to play fair — the volume of the 100 gold bricks is exactly equal to the the volume of the wooden trunk. The sage announces a task — you may either choose to take one gold brick or all 100 gold bricks. The kicker — if you choose to take all the bricks then you must carry all of them in that single trunk before sunset else you get to take zero gold bricks. If you choose just one brick, well you just get to keep that single brick. The greedy miner of course chooses to take all the bricks and the other miner is happy to take the single largest gold brick. Here comes the anti-climax — like most fables the greedy one suffers — goes home empty handed and the righteous one gets to keep his single brick. Read on to understand the cliche.
Fast-forward to the current age. There is tremendous economic incentive for optimisation of 3D bin packing solutions. Fast moving consumer goods are manufactured in a central facility and dispatched in boxes to multitudes of distribution depots. Combinations of these boxes of varying dimensions are then carried by trucks to retail shops. And unlike gold, the contents of these boxes often cannot even be melted to fit into the truck. The only trick that can help one maximise the boxes carried by the truck is figuring out the perfect packing sequence. Higher the volumetric packing efficiency — lower is the cost per kg of the shipped goods. But, packing a larger 3D cuboid container with smaller cuboids of equal net volume is harder than it seems. The individual geometries of different boxes must be taken into account while making a loading plan.
Traditionally, the loading “plan” is created on-the-spot for every new shipment by cargo loaders themselves while they perform the loading! The loader crew, often with little education, executes the task by trial and error and some judgement calls. But occasionally this modus operandi results in sub-optimal container utilisation. Industry veterans know this fact and often a “rule of thumb” is applied in assigning the right truck for the given shipment. The volume of all the boxes is summed up and a “suitable” truck is chosen assuming 20–30% void space. But the truth is that, it is only until after the attempt to load the truck with the said set of boxes has been made, that one realises the actual percentage void space. There may exist a better packing sequence than the one that the loaders came up with on that Monday. But how does one find it? Ordinary mortals, except the wise old sage, are apparently forbidden from knowing the perfect packing sequence. Under-estimating the true packing capacity of the truck leads to under-utilisation. Over-estimating the true capacity leads to item drops. Both are undesirable for business.
It is computationally hard to obtain optimal solutions, in a reasonable amount of time, to problems involving 3D packing of boxes of arbitrary dimensions in a given container. It is a combinatoric problem with NP-hard complexity. For such problems it is theoretically possible to try out every possible packing sequence and choose the most optimal one. But practically it is often not possible to do so since the search space of all the possible packing sequences can be huge. However, and luckily so, given a particular packing sequence it is rather trivial, computationally, to evaluate the optimality of the specified plan. The 3D packing problem also happens to belong the NP-complete subset— an algorithm that is able to find an optimal solution in linear time is mathematically guaranteed to be able to solve all other NP-hard problems belonging to the NP-complete subset in linear time. The problems that fall in that subset are some of the hardest problems known to humanity such as — the protein folding problem, knapsack and the travelling salesman problem to name a few. This underscores the magnitude of the complexity of the 3D packing problem.
Real-life constraints and other parameters, to be optimised, make the planning of 3D packing even harder. For instance, a single truck may carry goods headed to multiple destinations. The goods intended for the first drop-off location need to be loaded last i.e. a last-in-first-out (LIFO) loading sequence needs to be adhered to. Items that are fragile need to be placed in the top-most layer of the truck. Moreover, some items may disallow rotations about all but one axis. Adherence to these constraints could lead to and may come at the expense of optimal volumetric packing. For each business the relative importance of individual optimality criterion may vary significantly and some trade-offs are necessary. The task of loading hundreds of boxes while adhering to all of these constraints becomes an impossible task for manual planning under real-life time constraints. Locus’ proprietary 3D bin packing engine automates this part of the loading process. It simulates hundreds of thousands of truck packings until it finds an optimal sequence that satisfies each of the multiple objectives. The final loading plan is presented as a step-by-step box loading sequence that can be effected by cargo loaders at the loading bay.
This is the first part in the series of write-ups on the Lattice 3D packing engine. Here is the second part of this series of write-ups with a focus on packing benchmarks obtained using this packer. Follow us on blog.locus.sh. Reach us at Locus.
