Методи упаковки 3D об’єктів у контейнери
Вантажиться...
Дата
2022-06
Автори
Баглай, Іванна Юріївна
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Актуальність теми. Упаковка в контейнери була визначена в кількох різних формах, таких як розподіл запасів, завантаження транспортних засобів, завантаження повітряним вантажем, завантаження контейнерів, розв’язок проблеми з ранцем тощо, залежно від застосування. Упаковка для контейнерів – це кінцева сукупність предметів із різними характеристиками, які потрібно запакувати в один або кілька контейнерів. Кожен контейнер може містити будь-яку підмножину колекції об’єктів, не перевищуючи його місткість. Упаковка контейнерів також називається завантаженням контейнерів, упаковкою в ящики, завантаженням вантажу, ранцем і т. д. Це означає не тільки пакування ящиків у контейнер, а й упорядкування товарів і предметів у мішки, кошики, піддони.
Загальні проблеми, з якими стикається упаковка контейнерів, полягає у тому, щоб упакувати ящики в контейнер таким чином, щоб використовувати максимальний обсяг контейнера та задовольнити обмеження. Цю проблему можна розглядати як проблему прийняття рішень або проблему оптимізації. У задачі прийняття рішень необхідно визначити, чи всі об’єкти поміщаються в контейнер? Іншими словами, проблема стверджує, чи існує достатньо вільного простору, щоб утримувати об’єкти чи ні, і повертати булеву відповідь. Альтернативно, проблема оптимізації намагається мінімізувати кількість контейнерів або мінімізувати кількість втраченого простору всередині контейнера. Такий спосіб формулювання проблеми намагається оптимізувати використання контейнерів і мати число «n» числових відповідей, тому математики та комп’ютерні вчені розглядають проблему упаковки контейнерів як проблему оптимізації.
Об’єктом дослідження є проблема упаковки та її вирішення різноманітними методами.
Предметом дослідження є способи розміщення коробок у контейнери.
Мета роботи. Покращення ефективності упаковки, що виражається у відсотку втраченого простору, за допомогою запропонованих методів, які базуються на модифікації генетичних алгоритмів для розв’язання задачі тривимірної упаковки.
Методи дослідження. В роботі використовуються методи математичного моделювання, методи оптимізації, методи системного аналізу, чисельні методи.
Наукова новизна роботи полягає в наступному:
1. Запропоновано метод, який базується на генетичному алгоритмі з використанням частково відповідним схрещуванням та турнірною селекцією.
2. Запропоновано евристичні методи упаковки, що пристосовані до використання їх генетичним алгоритмом.
Практична цінність отриманих в роботі результатів полягає в тому, що проблема оптимального заповнення контейнера, з точки зору відсотку не заповненого простору, що залишиться після упаковки, є важливою. При використанні запропонованих методів отримані результати, що на 50 % менше мають втраченого простору у контейнерах.
Апробація роботи. Основні положення і результати роботи були опубліковано у збірнику Міжнародної наукової інтернет-конференції «Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення» та представлялись і обговорювались на XIV науково-практичній конференції магістрантів та аспірантів ПМК-2021.
Структура та обсяг роботи. Магістерська дисертація складається з вступу, чотирьох розділів, висновків та додатків.
У вступі надано загальну характеристику роботи, виконано оцінку сучасного стану проблеми, обґрунтовано актуальність напрямку досліджень, сформульовано мету і задачі досліджень, показано наукову новизну отриманих результатів і практичну цінність роботи, наведено відомості про апробацію результатів і їх впровадження.
У першому розділі було проаналізовано загальну проблему упаковки та обмеження, які або необхідно враховувати при рішенні задачі або можуть бути необов’язковими параметрами упаковки.
У другому розділі проаналізовано існуючі методи упаковки, а також поняття еволюційного алгоритму.
У третьому розділі сформульовано основні теоретичні частини розробки, їх взаємодію. Пояснено, чому було вибрано саме такі методи з усіх можливих для створення головної частини генетичного алгоритму. Також було описано власні евристичні алгоритми, що і будуть виконувати процес упаковки і повертати значення придатності індивіда.
У четвертому розділі описано середовище та компоненти розробки, процес роботи розробленої програми, а також описано взаємодію між частинами-класами.
У висновках проаналізовано отримані результати роботи.
У додатках наведено алгоритм багаторівневого аналізу великих масивів даних, структуру бази натурних даних, часові характеристики роботи програмного модуля аналізу параметрів математичної моделі еко-системи та порівняльні діаграми ефективності отриманих результатів.
Робота виконана на 88 аркушах, містить 4 додатки та посилання на список використаних літературних джерел з 31 найменувань. У роботі наведено 37 рисунків та 3 таблиць.
Ключові слова: евристичний метод, генетичний алгоритм, придатність, індивід, мутація, схрещення, селекція.
Опис
Ключові слова
евристичний метод, генетичний алгоритм, придатність, індивід, мутація, схрещення, селекція, heuristic method, genetic algorithm, suitability, individual, mutation, crossbreeding, selection
Бібліографічний опис
Баглай, І. Ю. Методи упаковки 3D об’єктів у контейнери : магістерська дис. : 123 Комп'ютерна інженерія / Баглай Іванна Юріївна. – Київ, 2022. – 90 с.