Palletizer

Introduction

This is a simple yet effective, and interesting program to solve pallatizing problem. Specifically, the Manufactuere Pallet Loading (MPL) problem (place same size boxes into a fixed size pallet), which is beleived to be a NP-complete problem. There are many papers and mathematical models to describe and solve it. In this program, I use the chess method (traditional approach like Deep Blue, NOT the one in AlphaGo Zero).

Chess

The idea of chess programming is very simple, but of course there are many genius skills. Here is a simplified logic:

Either you are a Master or Novice depends on how "fast" and how "deep" you can look ahead, and the strategies chosen. A Master can foresee more than 10 rounds (we call it level here) in less than a few minutes. Of course he/she does not move by random or bruteforce all the possible moves, and here comes the concept of evaluation functions and decision tree.

The goal is capture the King as soon as possible, which is find the shortest path to get the maximum score.

Pallet

The MPL problem and the Distributor Pallet Loading (DPL) problem (place different size boxes into a fixed size pallet) are much like chess playing, except that there is no King to be captured. The DPL problem is believed to be NP-hard, that is you cannot tell "win or lose", but you can say "good or bad" by experience (after trial and error for a few or more than billion time). The MPL problem is easier, there should be an optimial solution in given conditions (non-guillotine pattern), normally it is place as many boxes as possible in a stable manner. Human is clever and lazy, we can transform the DPL problem into MPL problem by using standard size boxes. And use many heuristic patterns to find the optimial solution.

But I am stupid but lazy too, so I bruteforce all the "possible" moves and let the computer do the hardwork. The following assumption should be clear:

• A new box will be placed to the corner of an existing boxes (align the corner to corner. In some cases may need to align edge to middle,edge to 1/3 of width or even 1/10. But you will not place in a random position along the edge normally.)
• The pallet size and boxes' size should be "reasonable",for example the number of boxes should be less than 20 in a layer (<20 levels in the decision tree which should equal to the Master of Masters). If need more, you can add some boxes manaully (like the open book in Chess).

Evaluation functions

Touched perimeter (Assume width=2,height=1)

1. touched=2+2, total=6+6, score=(2+2)/(6+6)

2. touched=1+1, total=6+6, score=(1+1)/(6+6)

Connected boxes

1. score=connected=1+2+1

2. score=connected=2+2+2

Bounding area

1. score=8/9. This is interlock pattern which is preferred in many cases. Multiply this if necessary. Reduce the total score if the hole's size is more than the minimum side of the box,since it will make the boxes unstable.

2. score=8/8

Final shape

1. Preferred since we will wrap the pallet in real world

2. Not preferred

How to use and examples

Description file

Create a text file and organize the parameters in json format. The unit is arbitrary.

maxWidth,maxHeight=pallet size, no box should outside this

boxLongEdge,boxShortEdge=box size

targetLevel=sometime we may need to find the best pattern with a few boxes only. Set to 9999 if not use.

Interface

Press "Create new" and select a description file, press "GetScore" to evaluate the current pattern described by the file.

Press "GetAll" to find the possible combinations. Press "Stop" at any time.

After the result is ready (maybe a few seconds or a few days!) ,press "Display result".

Examples

4 boxes interlock pattern, add 4 more boxes to find the best pattern

{"maxWidth":200,"maxHeight":200, "boxLongEdge":40,"boxShortEdge":20, "targetLevel":8,"boxes":[ {"box":[60,60,40,20]}, {"box":[100,60,20,40]}, {"box":[60,80,20,40]}, {"box":[80,100,40,20]}, ]}

The score is negative since the hole is bigger than the shorter side of the box.

A real example (used in 250mL drinks)

{"maxWidth":120,"maxHeight":100,"boxLongEdge":36,"boxShortEdge":20,"targetLevel":99999,"boxes":[ {"box":[0,0,36,20]}, {"box":[0,20,36,20]}, {"box":[0,40,36,20]}, {"box":[0,60,20,36]}, {"box":[20,60,20,36]}, {"box":[36,0,36,20]}, {"box":[72,0,36,20]}, ]}

Works to do

• Apply to 3D
• Apply to DPL
• Execution speed optimization, such as use C++ and apply more Chess programming skills.
• Use "smarter" strategies such as pre-built patterns.
• Enhance the evaluation functions, and add more to deal with different conditions.
• bug fix