УПАКОВКА В ПОЛУБЕСКОНЕЧНУЮ ПОЛОСУ НА ОСНОВЕ ДЕКОМПОЗИЦИИ И ГИБРИДИЗАЦИИ БИОИСПИРИРОВАННЫХ МЕТОДОВ

  • Б. К. Лебедев Южный федеральный университет
  • О. Б. Лебедев Южный федеральный университет
  • М. А. Ганжур Донской государственный технический университет
Ключевые слова: Упаковка в полубесконечную полосу, декомпозиция, одномерная упаковка, роевой интеллект, муравьиная колония, адаптивное поведение, гибридизация, поисковая оптимизация

Аннотация

Объектом исследования является задача прямоугольной упаковки в полубесконечную
полосу. Задан набор прямоугольников. Дан один большой объект (называемый полосой), чья
ширина D задана, а HP высота – искомое значение переменной. Цель состоит в том, что-
бы минимизировать высоту HP полосы, содержащей прямоугольники, помещенные в поло-
су без их взаимного перекрытия. Для решения задачи упаковки предложен новый гибридный
подход на основе декомпозиции общей задачи упаковки и гибридизации биоиспирированных
методов, а также новый гибридный подход к декомпозиции общей задачи упаковки. Разра-
ботаны новые архитектура и методы решения задачи упаковки, построенные на основе
декомпозиции и гибридизации разработанных авторами роевых методов, использующие
различные стратегии поиска, функционирующие параллельно-последовательно и реали-
зующие более широкий обзор пространства решений, что позволяет обеспечить более
высокую вероятность локализации глобального экстремума за приемлемое время. Разра-
ботана методология нового направления поиска решений задач ортогональной упаковки на
основе моделей адаптивного поведения биологических систем. Разработан высокоэффек-
тивный гибридный биоинспирированный метод решения задач одномерной и прямоугольной
упаковки, основанный на декомпозиции задачи на множество подзадач и интеграции ме-
тодов поисковой оптимизации. Предложены новые механизмы решения задачи упаковки,
использующие математические методы, в которых заложены принципы природных меха-
низмов принятия решений. В отличие от канонической парадигмы муравьиного алгоритма
агентом на графе поиска решений в качестве решения формируется разбиение множества
прямоугольных элементов A на подмножества Ak
i, где Ak
j ‒ подмножество элементов, на-
значенных агентом в блок. Разработаны поисковые методы для решения задач гильотин-
ного и не гильотинного прямоугольного раскроя. Для проведения объективных эксперимен-
тов были использованы известные тестовые задачи, представленные в литературе и Ин-
тернет. Получены лучшие результаты по сравнению с тестируемыми методами. Пред-
ложенные в работе теоретические положения для решения задач упаковки и раскроя про-
мышленных объектов в условиях единичного производства реализованы в виде методик,
алгоритмов и прикладного программного обеспечения. По сравнению с существующими
алгоритмами достигнуто улучшение результатов на 3–5%. Временная сложность алго-
ритма, полученная экспериментальным путем, практически совпадает с теоретическими
исследованиями и для рассмотренных тестовых задач составляет О(n2).

Литература

1. Stephen C.H. Leung, Defu Zhang. A fast layer-based heuristic for non-guillotine strip packing,
Expert System with 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], Tr. NGTU.
Informatika i sistemy upravleniya [Proceedings of NSTU. Informatics and control systems],
2013, 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, 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, pp. 25-30.
6. Defu Zhang, Yuxin Che, Furong Ye, Yain-Whar Si, 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 [Packing and estimation of the packing density
of orthogonal polygons in a semi-infinite strip], Informatsionnye tekhnologii intellektual'noy
podderzhki prinyatiya resheniy [Information technologies for intelligent decision support],
2014, pp. 117-121.
8. Jaya Thomas, Chaudhari 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, pp. 213-230.
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, pp. 154-173.
10. Lei Wang, Aihua Yin. A quasi-human algorithm for the two-dimensional rectangular strip
packing problem: in memory of Prof. Wenqi Huang, Journal of Combinatorial Optimization,
2016, pp. 416-444.
11. Potarusov R.V., Kureychik V.M. Problema odnomernoy upakovki elementov [The problem of
one-dimensional packing of elements], Izvestiya TRTU [Izvestiya TSURE], 2006, 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, 2016, 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
other than the canonical one], Vestnik Rostovskogo gosudarstvennogo universiteta putey
soobshcheniya [Bulletin of the Rostov State Transport University], 2016, 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], Nauchnotekhnicheskiy
vestnik informatsionnykh tekhnologiy, mekhaniki i optiki [Scientific and technical
bulletin of information technologies, mechanics and optics], 2017, 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, In: Lecture Notes In Computer Science.
Springer, Verlag, 2006, pp. 1-12.
19. Lebedev B.K., Lebedev O.B., Lebedeva E.O. 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.
20. 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.
21. 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.
22. Zhang DeFu, Han ShuiHua, Ye WeiGuo. A Bricklaying Heuristic Algorithm for the Orthogonal
Rectangular Packing Problem, Chinese Journal of Computers, 2008, pp. 509-515.
Опубликован
2023-10-23
Выпуск
Раздел
РАЗДЕЛ I. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ