BIO-INSPIRED DENSE PACKING ALGORITHM TO INCREASE THE EFFICIENCY OF SEMI-LIMITED STRIP CUTTING
Abstract
A methodology has been developed for finding solutions to the semi-infinite strip packing problem
based on models of adaptive behavior of biological systems. To reduce the overall labor intensity of the
search procedure, an approach based on decomposition of the problem being solved is proposed.
The packaging is designed for cutting by guillotine cutting of the tape into containers and non-guillotine
cutting of containers into elements. Packaging is carried out by sequentially filling the strip with containers.
The problem of packing rectangles into strips is solved in three stages. At the first stage, the agent
solves the problem of distributing a set A of rectangular-shaped elements in a set of blocks B. The problem
of forming a set of blocks B, including sets of rectangular-shaped elements A, is solved by an algorithm for
one-dimensional packing of elements into identical blocks. At the second stage, the problem of distributing
blocks among containers is solved. All containers have the same width D, equal to the width of the strip.
Each container holds two blocks. The process of distributing blocks into containers is accompanied by a
compaction procedure for each pair of blocks assigned to one container. The purpose of compaction is to
minimize the total area of the container by densely placing the blocks. Compaction is carried out sequentially
in all containers. The problem of distributing blocks into containers is reduced to the problem of
finding the maximum matching of the minimum cost. In contrast to the canonical paradigm of the ant algorithm,
when working as an agent, a clique is built on the solution search graph, on the edges of which a
pheromone is deposited. A technique has been developed for the formation of pheromone points and data
structures of collective evolutionary memory. To conduct objective experiments, well-known test problems
presented in the literature and on the Internet were used. Compared to existing algorithms, a 3-5% improvement
in results was achieved. The time complexity of the algorithm, obtained experimentally, practically
coincides with theoretical studies and for the considered test problems is ≈ О(n2).
References
Application, 2011, pp. 13032-13042.
2. Timofeeva O.P., Sokolova E.S., Milov K.V. Geneticheskiy algoritm v optimizatsii upakovki
konteynerov [Genetic algorithm in optimization of container packaging], Trudy NGTU. Informatika i
sistemy upravleniya [Proceedings of NSTU. Informatics and control systems], 2013, No. 4 (101),
pp. 167-172.
3. Valeeva A.F. Primenenie konstruktivnykh evristik v zadachakh raskroya-upakovki [Application of
constructive heuristics in cutting-packing problems], Prilozhenie k zhurnalu «Informatsionnye
tekhnologii» [Supplement to the journal «Information Technologies»], 2006, No. 11, pp. 1-24.
4. Lebedev B.K., Lebedev O.B., Lebedeva E.M. Modernizirovannyy murav'inyy algoritm sinteza
identifitsirovannogo dereva gil'otinnogo razreza pri planirovanii SBIS [Modernized ant algorithm for
synthesizing an identified guillotine cut tree when planning VLSI], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2017, No. 7, pp. 15-28.
5. Lebedev O.B., Zorin V.Yu. Upakovka na osnove metoda murav'inoy kolonii [Packaging based on the
ant colony method], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2010, No. 12, pp. 25-30.
6. Defu Zhang, Yuxin C., Furong Y., Yain-Whar S., Stephen C. A hybrid algorithm based on variable neighbourhood
for the strip packing problem, Journal of Combinatorial Optimization, 2016, pp. 513-530.
7. Akhtyamov A.A., Kartak V.M. Upakovka i otsenka plotnosti upakovki ortogonal'nykh mnogougol'nikov
v polubeskonechnuyu polosu [A hybrid algorithm based on variable neighbourhood for the
strip packing problem], Informatsionnye tekhnologii intellektual'noy podderzhki prinyatiya resheniy
[Information technologies for intelligent decision support], 2014, pp. 117-121.
8. Jaya T., Narendra S. Hybrid approach for 2d strip packing problem using genetic algorithm, Proceedings
of the 12th international conference on Artificial Neural Networks: advances in computational intelligence,
2013.
9. Mesyagutov M.A., Mukhacheva E.A., Belov G.N., Shaytkhauer G. Upakovka odnomernykh
konteynerov s prodolzhennym vyborom identichnykh predmetov: tochnyy metod poiska optimal'nogo
resheniya [Packing one-dimensional containers with continued selection of identical items: an exact
method for finding the optimal solution], Avtomatika i telemekhanika [Automation and Remote Control],
2011, No. 1, pp. 154-173.
10. Lei W., Aihua Y. A quasi-human algorithm for the two dimensional rectangular strip packing problem:
in memory, Journal of Combinatorial Optimization, 2016, pp. 416-444.
11. Potarusov R.V., Kureychik V.M. Problema odnomernoy upakovki elementov [The problem of onedimensional
packing of elements], Izvestiya TRTU [Izvestiya TSURE], 2006, No. 8, pp. 88-93.
12. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy:
ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired by nature: a tutorial].
Moscow: Izd-vo MGTU im. N.E. Baumana, 2021, 448 p.
13. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy kolonii v zadachakh proektirovaniya [Models
of adaptive behavior of an ant colony in design problems]. Taganrog: Izd-vo YuFU. 2013, 199 p.
14. Lebedev B.K., Lebedev O.B. Murav'inye algoritmy razbieniya, ispol'zuyushchie predstavleniya
zadachi, otlichnye ot kanonicheskogo [Ant partitioning algorithms using problem representations different
from the canonical one], Vestnik Rostovskogo gosudarstvennogo universiteta putey
soobshcheniya [Bulletin of the Rostov State University of Transport and Communications], 2016,
No. 3 (63), pp. 42-47.
15. Blum C., Roli A. Metaheuristics in combinatorial optimization: overview and conceptual comparison,
ACM computing surveys, 2003, pp. 268-308.
16. Lebedev B.K., Lebedev O.B. Raspredelenie resursov na osnove gibridnykh modeley roevogo intellekta
[Resource distribution based on hybrid models of swarm intelligence], Nauchno-tekhnicheskiy vestnik
informatsionnykh tekhnologiy, mekhaniki i optiki [Scientific and Technical Bulletin of Information
Technologies, Mechanics and Optics], 2017, No. 6, pp. 1063-1073.
17. Zhitnikov V.P. Zadacha pryamougol'noy upakovki v polubeskonechnuyu polosu: poisk resheniya v
okrestnosti lokal'noy nizhney granitsy [The problem of rectangular packing in a semi-infinite strip:
searching for a solution in the neighborhood of the local lower boundary], Informatsionnye tekhnologii
[Information Technologies], 2007, No. 6, pp. 55-61.
18. Raidl G.R. A Unified View on Hybrid Metaheuristics, Lecture Notes In CS, 2006, pp. 1-12.
19. Lebedev B.K., Lebedev O.B. Roevoy algoritm planirovaniya raboty mnogoprotsessornykh
vychislitel'nykh sistem [Swarm algorithm for scheduling the operation of multiprocessor computing
systems], Inzhenernyy vestnik Dona [Engineering Bulletin of the Don], 2017, No. 3.
20. Lebedev B.K., Lebedev O.B., Ganzhur M.A. Upakovka v polubeskonechnuyu polosu na osnove dekompozitsii
i gibridizatsii bioinspirirovannykh metodov [Packaging in a semi-infinite strip based on
decomposition and hybridization of bioinspired methods], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2023, No. 4, pp. 109-125.
21. Cong J., Romesis M., Xie M. Optimality, Scalability and Stability Study of Partitioning and Placement
Algorithms, Proc. of the International Symposium on Physical Design, 2003, pp. 88-94.
22. Hifi M., M'Hallah R. A hybrid algorithm for the two-dimensional layout problem: The cases of regular
and irregular shapes, International Transactions in Operational Research, 2003, pp. 195-216.
23. Zhang DeFu, Han ShuiHua, Ye WeiGuo. A Bricklaying Heuristic Algorithm for the Orthogonal Rectangular
Packing Problem, Chinese Journal of Computers, 2008, pp. 509-515.
