Weekday automation or “I need a program for 3D packaging”

Automation of domestic enterprises, which you have to deal with, is a necessary and highly paid, but rather nervous job. Rescues humor. For example, when communicating with a demanding client, remember the anecdote: “Holding a hand over the wall, a man is barely standing on his feet. A child sticks to him: “Well, papa, please make me a boat!”, Papa replies: “Aha! “Now I’ll give up everything and go make you a ship!“. I want to tell you about one such ship made for a client. I hope that joint immersion in a warm tube (that is, customer-oriented) programming will bring you positive emotions, and the task has been interesting. Swam?



It all began with the client's letter, which stated that a large network retailer X (everyone knows him) demanded that shipments to his address be carried out not on pallets, but in boxes of a given size. Therefore, the manager in charge of this client needs a “program”, which, according to the composition of different-sized packages in the order, determines the required number of boxes and prints the packing lists. The letter was accompanied by a request not to delay the resolution of the issue, since the moment of transition to the new system of shipments is about to come, and penalties may cost more than the new general car. The cost of the car was known, as Ferrari was listed in the list of fixed assets. Therefore, the task reluctantly (only one workplace of almost a couple of hundred) was taken to work and put under control. Although the most massive tasks at the time were the sea: the newly developed software for data collection terminals in the raw material warehouse was just launched, an application for transferring sales representatives from PDAs to tablets was developed in the scalded cat mode, the system for registering and controlling movements of the pallet with finished products was debugged etc.

A quick analysis showed that the “container loading” task is NP-complete. To explain this to the client, who regularly with a capricious voice called with the question "when will my programm", we could not and did not try. And you try to tell a pretty girl-manager on work with clients, that her task is somehow complete there. What will she think about first? And what are your chances after this? In general, the naive belief of our customers in the endless possibilities of computers and the omnipotence of programmers played another joke that time. But it was necessary to get out and we did it.
')
To explain the following solution, one more circumstance must be kept in mind. The framework we work with is based on a scripting language. Although the language is quite flexible and hung on the principle of the Christmas tree with all sorts of crackers and rattles, including even the methods of mathematical statistics, it is not very well suited for problems with volumetric calculations. The normal cycle we have performed much longer than in the compiled language. Therefore, simple, but massive computing is more convenient to do on the server side directly at the DBMS level. To work with the database, we use a language very similar to T-SQL. Therefore, I have no doubt that the code below will be understood by everyone.

The idea of ​​the solution is to flatten the bottom of the box into small cells, get in the table all possible arrangements for each package in the grid nodes, taking into account possible rotations of this package, fix the choice of the best specific location for one package, and then adjust the decision table by lifting the “Possible locations of other remaining packages to the height of the fixed package, if their locations intersect.

In general, you realized that we used the “greedy” algorithm. By the way, apparently, after seeing this carelessly written word on the time sheet, the chief accountant then grumbled for a long time and did not want to sign the bill for the processed hours.

The size of the grid cells, generally speaking, should be equal to the greatest common divisor of all sides of the packages, but in our particular case the size range of the sides of the packages was known: the side of the cell was taken equal to one centimeter.

So, first we get a table of numbers from 0 to 255 by cascading to the power of a table of 0 and 1.

SELECT 0 AS x INTO R1 UNION SELECT 1; SELECT Lx + 2 * Hx AS x INTO R2 FROM R1 AS L, R1 AS H; SELECT Lx + 2 * Hx AS x INTO R4 FROM R2 AS L, R2 AS H; SELECT Lx + 2 * Hx AS x INTO R8 FROM R4 AS L, R4 AS H; 

Then we get a table of all possible rotations of the packages. By the way, an interesting task is to test your knowledge of TSQL. Perhaps this is a new SQL puzzle for Joe Celko

 SELECT id, CASE x WHEN 0 THEN d0 WHEN 1 THEN d1 WHEN 2 THEN d2 END AS dx, x INTO Scan FROM Items, R2 WHERE x < 3; SELECT DISTINCT B0.id, B0.dx AS d0, B1.dx AS d1, B2.dx AS d2 INTO Spin FROM Scan AS B0 JOIN Scan AS B1 ON B0.id = B1.id JOIN Scan AS B2 ON B0.id = B2.id WHERE NOT(B0.x = B1.x OR B0.x = B2.x OR B1.x = B2.x); 

Finally, we initialize the decision table, multiplying the grid coordinates by the rotation table.

 SELECT FromLeft.x AS d0l, FromBack.x AS d1l, FromLeft.x + d0 AS d0h, FromBack.x + d1 AS d1h, 0 AS d2l, d2 AS d2h, 0 AS v, d0 * d1 AS s, id INTO Vista FROM R8 AS FromLeft, R8 AS FromBack, Spin WHERE FromLeft.x + d0 < = &Width AND FromBack.x + d1 < = &Depth AND d2 < = &Height; 

Now run the loop:

To select the best option, use the following query.

 SELECT TOP 1 id, d0l, d1l, d2l, d0h, d1h, d2 FROM Vista WHERE d2l + d2 < = &Height ORDER BY s * d2l - v, s * d2 DESC, d2l + d2, d0l, d1l, d0h; 

That is, at the next step, for packing in a box, according to this rule, the package is selected that minimally covers the unused volume. Under equal conditions of the closed void, the package of the maximum volume is selected, the minimum raising the upper level of the packages in the box, with the leftmost edge, with the farthest edge, and the farthest front. However, the rule is easy to change by changing the sort order.

Changing the decision table, taking into account that a certain place in the box becomes occupied, is done like this:

 SELECT Vi.d0l, Vi.d1l , ISNULL(CASE WHEN It.d2l + It.d2 > Vi.d2l THEN It.d2l + It.d2 END, Vi.d2l) AS d2l , Vi.d0h, Vi.d1h, Vi.d2 , Vi.v + ISNULL((CASE WHEN It.d1l < Vi.d1l THEN It.d1l ELSE Vi.d1l END - CASE WHEN It.d0l > Vi.d0l THEN It.d0l ELSE Vi.d0l END) * (CASE WHEN It.d1h < Vi.d1h THEN It.d1h ELSE Vi.d1h END - CASE WHEN It.d1l > Vi.d1l THEN It.d1l ELSE Vi.d1l END) * It.d2, 0) AS v , Vi.s, Vi.id FROM Vista AS Vi LEFT JOIN Items AS It ON (Vi.d1l < = It.d1l AND It.d1l < Vi.d1h OR It.d1l < = Vi.d1l AND Vi.d1l < It.d1h) AND (Vi.d0l < = It.d0l AND It.d0l < Vi.d0h OR It.d0l < = Vi.d0l AND Vi.d0l < It.d0h) WHERE Vi.id <> &id AND It.id = &id; 

Well, if there is not a single unplaced package that raises the level less than the height of the box, we assume the box is full and initialize the decision table again for the next box.

Here, in general, and all.

Thought about the decision for a long time. But not at the computer, but on trips from the client’s factory outside the city to the central office. It is quite convenient to think at the wheel - complex solutions are filtered by themselves. The programming itself took about half a day.

Below is a screenshot of the packing list used for debugging.



This packing list looks pretty boring: 2.5D graphics packers were not needed. Actually the result of the work is just another print form, connected to the order. Works on typical orders of this particular client fairly quickly.

In general, the client in the person of the girl manager was satisfied. True, not so much. But why? It is unlikely that she could be upset by the instruction to the program, which said that it only works with a fat client in ordinary forms (this was the tenth edition). We all know that the majority of our customers never open instructions. In general, the solution of the thoughts of individual users is not “container loading” to you, but a truly insoluble problem.

It is interesting that on the same project there was also an application from the deputy head of the supply department, who spent a lot of time selecting the production plan in order to make the best use of the available raw materials. But that's another story.

PS: Here everything is true and nothing is made up - colleagues will not let you lie. And for some reason, the deepest impression was left by those whom I brought up on my blue impreza. Everyone remembered the number 200, but these were by no means the achieved percentages of utilization of the box volume.
Here is a paradox of psychology!

(C) ildarovich