Методи упаковки 3D об’єктів у контейнери

dc.contributor.advisorБоярінова, Юлія Євгенівна
dc.contributor.authorБаглай, Іванна Юріївна
dc.date.accessioned2022-06-30T08:39:46Z
dc.date.available2022-06-30T08:39:46Z
dc.date.issued2022-06
dc.description.abstractenTheme urgency. Container packaging has been identified in several different forms, such as stock distribution, vehicle loading, air cargo loading, container loading, backpack problem resolution, etc., depending on the application. Pisinger's research focused on the problem of packaging. The various terms and standards used in this research will be explained in this section. Container packaging is a finite set of items with different characteristics that need to be packed in one or more containers [1]. Each container can contain any subset of the object collection, not exceeding its capacity. Container packing is also called loading containers, packing in boxes, loading cargo, backpack, etc. This means not only packing boxes into a container, but also arranging goods and items in bags, baskets, pallets. A common problem faced by a container packer is to pack the boxes into a container in such a way as to use the maximum capacity of the container and meet the constraints. This problem can be considered as a decision-making problem or an optimization problem. In the decision-making task, do you need to determine whether all the objects fit in the container? In other words, the problem is whether or not there is enough free space to hold objects and return a Boolean response. Alternatively, the optimization problem tries to minimize the number of containers or minimize the amount of lost space inside the container. This way of formulating the problem tries to optimize the use of containers and have the number "n" of numerical answers, so mathematicians and computer scientists consider the problem of container packaging as a problem of optimization. Object of research is the problem of packaging and its solution by various methods. Subject of research is the efficiency of placing boxes in containers, which is expressed as a percentage of lost space, as well as the time efficiency of algorithms. Research objective: To develop modified genetic algorithms to solve the problem of three-dimensional packaging to improve the efficiency of packaging, expressed as a percentage of unused space. Research methods. Methods of mathematical modelling, optimization and system analysis as well as numerical methods are used in the research. Scientific novelty consists in the following: 1. A genetic algorithm with the use of partially appropriate crossbreeding and tournament selection is proposed. 2. Heuristic methods of packing adapted to their use by genetic algorithm are offered. Practical value of the results obtained in the work is that the problem of optimal filling of the container, in terms of the percentage of unfilled space left after packaging, is important for companies involved in transportation. Their task is to place 3D blocks in containers optimally to deliver more goods, while using a minimum number of containers, which reduces transportation costs. Approbation. The main provisions and results of the work were published in the collection of the International Scientific Internet Conference "Information Society: Technological, Economic and Technical Aspects of Formation" and were presented and discussed at the XIV Scientific and Practical Conference of Undergraduates and Postgraduates PMK-2021. Structure and content of the thesis. Structure and scope of work. The master's dissertation consists of an introduction, four chapters, conclusions and appendices. The introduction provides a general description of the work, performed an assessment of the current state of the problem, substantiated the relevance of the direction research, formulated the purpose and objectives of research, shows the scientific novelty of the results and the practical value of the work, provides information on the testing of results and their implementation. The first section analyzed the general packaging problem and the limitations that either need to be considered when solving the problem or may be optional packaging parameters. The second section analyzes the existing packaging methods, as well as the concept of evolutionary algorithm. The third section formulates the main theoretical parts of the development, their interaction. It is explained why such methods were chosen from all possible to create the main part of the genetic algorithm. It also described its own heuristic algorithms, which will perform the packaging process and return the value of the suitability of the individual. The fourth section describes the development environment and components, and the process of the developed program, as well as describes the interaction between the parts of the class. The results of the work are analyzed in the conclusions. The appendices contain the algorithm of multilevel analysis of large data sets, the structure of the field data base, the time characteristics of the software module for analyzing the parameters of the mathematical model of the ecosystem and comparative efficiency diagrams of the results. The work is performed on 94 sheets, contains 7 appendices and links to the list of used literature sources from 30 titles. The paper presents 35 figures and 3 tables. Key words: heuristic method, genetic algorithm, suitability, individual, mutation, crossbreeding, selection.uk
dc.description.abstractukАктуальність теми. Упаковка в контейнери була визначена в кількох різних формах, таких як розподіл запасів, завантаження транспортних засобів, завантаження повітряним вантажем, завантаження контейнерів, розв’язок проблеми з ранцем тощо, залежно від застосування. Упаковка для контейнерів – це кінцева сукупність предметів із різними характеристиками, які потрібно запакувати в один або кілька контейнерів. Кожен контейнер може містити будь-яку підмножину колекції об’єктів, не перевищуючи його місткість. Упаковка контейнерів також називається завантаженням контейнерів, упаковкою в ящики, завантаженням вантажу, ранцем і т. д. Це означає не тільки пакування ящиків у контейнер, а й упорядкування товарів і предметів у мішки, кошики, піддони. Загальні проблеми, з якими стикається упаковка контейнерів, полягає у тому, щоб упакувати ящики в контейнер таким чином, щоб використовувати максимальний обсяг контейнера та задовольнити обмеження. Цю проблему можна розглядати як проблему прийняття рішень або проблему оптимізації. У задачі прийняття рішень необхідно визначити, чи всі об’єкти поміщаються в контейнер? Іншими словами, проблема стверджує, чи існує достатньо вільного простору, щоб утримувати об’єкти чи ні, і повертати булеву відповідь. Альтернативно, проблема оптимізації намагається мінімізувати кількість контейнерів або мінімізувати кількість втраченого простору всередині контейнера. Такий спосіб формулювання проблеми намагається оптимізувати використання контейнерів і мати число «n» числових відповідей, тому математики та комп’ютерні вчені розглядають проблему упаковки контейнерів як проблему оптимізації. Об’єктом дослідження є проблема упаковки та її вирішення різноманітними методами. Предметом дослідження є способи розміщення коробок у контейнери. Мета роботи. Покращення ефективності упаковки, що виражається у відсотку втраченого простору, за допомогою запропонованих методів, які базуються на модифікації генетичних алгоритмів для розв’язання задачі тривимірної упаковки. Методи дослідження. В роботі використовуються методи математичного моделювання, методи оптимізації, методи системного аналізу, чисельні методи. Наукова новизна роботи полягає в наступному: 1. Запропоновано метод, який базується на генетичному алгоритмі з використанням частково відповідним схрещуванням та турнірною селекцією. 2. Запропоновано евристичні методи упаковки, що пристосовані до використання їх генетичним алгоритмом. Практична цінність отриманих в роботі результатів полягає в тому, що проблема оптимального заповнення контейнера, з точки зору відсотку не заповненого простору, що залишиться після упаковки, є важливою. При використанні запропонованих методів отримані результати, що на 50 % менше мають втраченого простору у контейнерах. Апробація роботи. Основні положення і результати роботи були опубліковано у збірнику Міжнародної наукової інтернет-конференції «Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення» та представлялись і обговорювались на XIV науково-практичній конференції магістрантів та аспірантів ПМК-2021. Структура та обсяг роботи. Магістерська дисертація складається з вступу, чотирьох розділів, висновків та додатків. У вступі надано загальну характеристику роботи, виконано оцінку сучасного стану проблеми, обґрунтовано актуальність напрямку досліджень, сформульовано мету і задачі досліджень, показано наукову новизну отриманих результатів і практичну цінність роботи, наведено відомості про апробацію результатів і їх впровадження. У першому розділі було проаналізовано загальну проблему упаковки та обмеження, які або необхідно враховувати при рішенні задачі або можуть бути необов’язковими параметрами упаковки. У другому розділі проаналізовано існуючі методи упаковки, а також поняття еволюційного алгоритму. У третьому розділі сформульовано основні теоретичні частини розробки, їх взаємодію. Пояснено, чому було вибрано саме такі методи з усіх можливих для створення головної частини генетичного алгоритму. Також було описано власні евристичні алгоритми, що і будуть виконувати процес упаковки і повертати значення придатності індивіда. У четвертому розділі описано середовище та компоненти розробки, процес роботи розробленої програми, а також описано взаємодію між частинами-класами. У висновках проаналізовано отримані результати роботи. У додатках наведено алгоритм багаторівневого аналізу великих масивів даних, структуру бази натурних даних, часові характеристики роботи програмного модуля аналізу параметрів математичної моделі еко-системи та порівняльні діаграми ефективності отриманих результатів. Робота виконана на 88 аркушах, містить 4 додатки та посилання на список використаних літературних джерел з 31 найменувань. У роботі наведено 37 рисунків та 3 таблиць. Ключові слова: евристичний метод, генетичний алгоритм, придатність, індивід, мутація, схрещення, селекція.uk
dc.format.page90 с.uk
dc.identifier.citationБаглай, І. Ю. Методи упаковки 3D об’єктів у контейнери : магістерська дис. : 123 Комп'ютерна інженерія / Баглай Іванна Юріївна. – Київ, 2022. – 90 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/48292
dc.language.isoukuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.subjectевристичний методuk
dc.subjectгенетичний алгоритмuk
dc.subjectпридатністьuk
dc.subjectіндивідuk
dc.subjectмутаціяuk
dc.subjectсхрещенняuk
dc.subjectселекціяuk
dc.subjectheuristic methoduk
dc.subjectgenetic algorithmuk
dc.subjectsuitabilityuk
dc.subjectindividualuk
dc.subjectmutationuk
dc.subjectcrossbreedinguk
dc.subjectselectionuk
dc.subject.udc004.023uk
dc.titleМетоди упаковки 3D об’єктів у контейнериuk
dc.typeMaster Thesisuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Вантажиться...
Ескіз
Назва:
Bahlai_magistr.pdf
Розмір:
1.34 MB
Формат:
Adobe Portable Document Format
Опис:
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
1.71 KB
Формат:
Item-specific license agreed upon to submission
Опис: