Every time it is necessary to place goods in a warehouse or load them into a vehicle, we encounter the problem of placing the cargo in such a way as to minimize the amount of space it occupies, or, in other words, with the task of packing it optimally. Scientists call this the «Backpack task» [1].
A one-dimensional version of the packing task is most often encountered in mathematical literature. It was determined that the task is NP-complete [2]. If the task is placed in a 3-dimensional space, it will become significantly more difficult than the one-dimensional, but still solvable in polynomial time on nondeterministic computing devices. Consequently, a 3-dimensional packing task is NP-complete.
Unfortunately, all of the known algorithms which are able to solve some kind of NP-complete task, and, particularly the task of packing, have exponential time complexity, which is equivalent to a full enumeration of all possible options. This means that even if the amount of goods is small (only 50) the operational time of the software which can implement these algorithms would be measured in years even using modern supercomputers. It is without coincidence that in the year 2000, the Klea Mathematical Institute, a subsidiary of Cambridge University, included the task of finding a quick (polynomial) algorithm for solving exhaustive problems in their list of 7 problems, the solution to any one which would receive a million dollars!
The solution to this situation is the creation of heuristic algorithms that can approximate an optimal solution in a reasonable amount of time.
The core of the algorithms used for the calculation of optimal loading plans for mixed cargo in the packer3d software [3] and in the online services [4], consists of theoretical and applied research, begun under the MATIS [5] department of mechanics and mathematics at M.V. Lomonosov’s Moscow State University [6] University in the year 2000 under the leadership of Dr. A.S. Strogalov [7] and Dr. A.A. Irmatov [8]. This research resulted in unique heuristic algorithms with elements of neural and genetic calculations, created at the intersection of discrete mathematics, mathematical logic, and mathematical statistics. We continue to cooperate with the department of MATIS at MGU, in the area of developing existing algorithms and creating new algorithms in logistics and other areas.
The fill density resulting from the work of this algorithm makes up an average of 80%-95% of the cargo compartment’s volume, while the operation time for a hundred boxes is only a few minutes. The calculation can account for various additional constraints, such as load capacity, maximum pressure on boxes, balancing pressure on axels, stacking, palletizing, and many others. In addition, three loading options are available: through the back door like a container, through the side door like a wagon car, or top to bottom like a platform.
