БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ ПЛОТНОЙ УПАКОВКИ ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ РАСКРОЯ ПОЛУОГРАНИЧЕННОЙ ПОЛОСЫ
Аннотация
Предлагается архитектура и методология раскроя-упаковки полуограниченной полосы на
основе методов биоинспирированного поиска. В основе подхода к декомпозиции обшей задачи упа-
ковки и методологии формированию карт раскроя лежат эвристики уровневого подхода к упаков-
ке полосы. Архитектура сформирована на основе декомпозиции общей задачи и включает 5 основ-
ных секций: управление процессом поиска; формирования блоков; формирование контейнеров;
компакция контейнеров; заполнения полосы контейнерами. Упаковка ориентирована на двухуров-
невый раскрой полосы. На первом уровне путем гильотинного разреза выполняется раскрой на
контейнеры. На втором уровне два варианта раскроя: путем гильотинного или путем не гильо-
тинного разреза выполняется раскрой контейнеров на детали (элементы прямоугольной формы).
Упаковка выполняется путем последовательного заполнения уровней полосы контейнерами.
В основу методологии раскроя-упаковки полуограниченной полосы положен иерархический подход
снизу вверх. Задача, решаемая на первом уровне иерархии, заключается в формировании множе-
ства блоков B одинаковой ширины на базе исходного набора A прямоугольников, включаемых в
блоки. Для решения поставленной задачи авторами разработан биоинспирированный алгоритм
одномерной упаковки элементов в одинаковые блоки. На втором уровне иерархии решается задача
распределения блоков по контейнерам. Все контейнеры и блоки имеют одинаковую ширину D,
равную ширине полосы. В каждом контейнере помещаются два блока. Задача распределения бло-
ков по контейнерам сведена к задаче нахождения максимального паросочетания минимальной
стоимости. В отличие от канонической метаэвристики муравьиного алгоритма в работе аген-
том на графе поиска решений строится максимальная клика, которая является интерпретацией
решения. На третьем уровне иерархии решается задача компакции контейнеров. Процесс распре-
деления блоков по контейнерам сопровождается процедурой сжатия каждой пары блоков, назна-
чаемых в один контейнер. Целью компакции является минимизация общей площади контейнера
путем плотного размещении блоков. Компакцию последовательно проводят во всех контейнерах.
На четвертом уровне иерархии решается задача заполнения полосы контейнерами. В качестве
модели для представления решения на графе поиска решений служит клика. Разработана база
данных коллективной эволюционной памяти. Разработана методика формирования феромоновых
точек и структур данных коллективной эволюционной памяти. Для проведения объективных экс-
периментов были использованы известные тестовые задачи, представленные в литературе и
сети Интернет. По сравнению с существующими алгоритмами достигнуто улучшение результа-
тов на 3-5%. Временная сложность алгоритма, полученная экспериментальным путем, практи-
чески совпадает с теоретическими исследованиями и для рассмотренных тестовых задач со-
ставляет (ВСА ≈ О(n2)).
Литература
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.
