ГЕНЕТИЧНИЙ АЛГОРИТМ ЗАДАЧІ ТРИВИМІРНОГО МУЛЬТИПАКУВАННЯ ПРЯМОКУТНИХ ОБ’ЄКТІВ РІЗНИХ РОЗМІРІВ - Scientific conference
Main page
UA RU EN

Congratulation from Internet Conference!

Hello

Рік заснування видання - 2011

ГЕНЕТИЧНИЙ АЛГОРИТМ ЗАДАЧІ ТРИВИМІРНОГО МУЛЬТИПАКУВАННЯ ПРЯМОКУТНИХ ОБ’ЄКТІВ РІЗНИХ РОЗМІРІВ

11.05.2022 13:02

[1. Information systems and technologies]

Author: Баглай Іванна Юріївна, студентка, комп’ютерна інженерія, Київський політехнічний інститут ім. Ігоря Сікорського

Abstract

Проблема пакування у 3D-просторі полягає у виборі одного чи більше коробок з множини доступних коробок і розміщення його у 3-вимірному прямокутному контейнері. Коробка розміщується так, щоб використати простір контейнера ефективно. 3D-BPP (3d pin packing problem) широко використовується у фармацевтичній індустрії, транспортній і пакувальних системах. Зазвичай, у 3D-BPP коробки, які необхідно розмістити, однакового розміру, але на практиці розмір варірується. У статті описано генетичний алгоритм з використанням евристичного алгоритму для процесу упаковки. Процес упаковки конвертує послідовності коробок і контейнерів, що закодовані у хромосомі, у компактне рішення. Генетичний алгоритм використовується для ініціалізації таких послідовностей.
Ключові слова 
Пакування, генетичний алгоритм, евристичний алгоритм, контейнер,максимальний вільний простір, 3d-простір, 3D-BPP.
Вступ
Проблема тривимірного пакування (3D-BPP) - це відома задача оптимізації, яка має багато промислових застосувань, наприклад, завантаження контейнерів і піддонів, управління вантажем і складом, планування телевізійних програм. 3D-BPP передбачає упакування m прямокутних коробок в необмежену/обмежену кількість однакових прямокутних контейнерів, щоб мінімізувати кількість використаних контейнерів, тобто збільшити коефіцієнт використання контейнерів. Контейнери і коробки можуть бути взаємозамінними. У судноплавстві та транспортній індустрії використовується кілька типів стандартних контейнерів. Для наземного або повітряного транспортування - коробки різноманітних розмірів. 
Оскільки проблема, яка розглядається, є узагальненням оригінального 3D-BPP, вона зазнає обчислювальних труднощів. Крім того, задачу ускладнює і те, що обирається, яка саме коробка з послідовності буде упакована. 3D-BPP, який фокусується на упаковці прямокутних предметів ортогонально в мінімальну кількість прямокутних контейнерів ідентичного розміру, вже є NP-складною. Але у відомих алгоритмах не відбувається упаковки однієї коробки у іншу. У цій роботі розглянуто більш загальний варіант 3D-BPP, в якому контейнери і коробки можуть бути неоднорідними, тобто мати різний розмір і розглядається шестистороння орієнтація ящиків. 
Протягом останніх десятиліть були розроблені як точні, так і евристичні алгоритми для вирішення цієї проблеми. Martello та ін.[1] презентує точні та апроксимаційні алгоритми упаковки. Fekete та ін.[2] продемонстрували, що проблема упаковки у великих вимірах може бути розв’язана оптимально за допустимий час, використовуючи дворівневий алгоритм пошуку дерева. Хоча точний алгоритм може знайти оптимальне рішення, зазвичай він потребує величезної кількості часу, щоб опрацювати прості і невеликі послідовності коробок і контейнерів. Евристичний алгоритм не може гарантувати оптимальність, але здатні давати хороші результати з набагато меншими обчислювальними зусиллями.

 Faroe та інші[3] пропонують евристику, засновану на керованому локальному пошуку пакувальних елементів з фіксованою орієнтацією в мінімальну кількість однакових контейнерів. 
Таким чином, проблема завантаження одного контейнера (SCLP - single container loading problem) пов’язана з упаковкою вибраної підмножини предметів у один контейнер з високим коефіцієнтом використання простору. Martello та ін.[1] представляють дворівневий алгоритм Branch and Bound, який дає оптимальне рішення для пакування предметів у один контейнер. 
Kang та ін.[4] представляють гібридний генетичний алгоритм (ГА) для задачі тривимірної упаковки ящиків, в якому коробки розміщуються у один контейнер, і  критерієм ефективності якого є кількість розміщених коробок. 
Інший варіант проблеми називають проблемою відкритого простору (ODP - open dimension problem), де в контейнері є один параметр розміру, що змінюється. Bortfeldt і Mack[5] представляють евристичний метод побудови шарів для задачі пакування тривимірної стрічки (3D-SPP - three-dimensional strip packing problem), метою якого є упаковка коробок у один контейнер для мінімізації змінювальної довжини контейнера. В [5] вперше запропоновано точну математичну модель на основі праці Chen[6], а потім розробили гібридизацію ГА. Ця проблема додатково досліджується і  іншими. Bortfeldt і Mack розробили вдосконалений генетичний алгоритм зі змінною орієнтацією коробок. На відміну від 3D-BPP з одиничними або ідентичними бункерами, досі у літературі не приділялося уваги проблемі з кількома різними за розмірами контейнерами, яку також називають проблемою з кількома неоднорідними контейнерами. Chen є одним з перших, хто надає модель змішаного цілочисельного лінійного програмування (MILP - mixed integer linear programming)[6] для рішення 3D-BPP зі змінною орієнтацією та різними розмірами контейнерів. Модель використовує змінені значення x, y, z розмірів для визначені взаємного розташування предметів та змінних орієнтації, щоб імітувати різну орієнтацію упаковки. Подібну проблему досліджували Takahara і Miuamoto[7]. Запропоновано ГА, де в якості генотипу використовується пара послідовностей (одна для коробок і одна для контейнерів), а для визначення плану завантаженості з урахуванням послідовності ящиків і контейнерів використовується евристичний метод. Вони використовували евристичний метод під назвою “Branch Heuristics”, що використовує структуру хромосоми та видає готове рішення задачі. Очевидним недоліком цієї евристичної процедури є те, що вона не повністю використовує доступний простір. Eley[8] пропонує новий підхід, заснований на формуванні набору множин і використанні евристики на основі пошуку дерева для попереднього генерування шаблонів упаковки одного контейнера. Ця модель розширена Che і ін.[9] та Zhu і ін.[10], які пропонують нову евристику та апроксимаційний алгоритм для генерування стовпців. У цій роботі досліджено 3D-BPP зі змінною орієнтацією та різними розмірами контейнерів, що є NP-складною задачею. Запропоновано алгоритм рішення, який гібридизує  ГА з новою евристичною процедурою пакування. Евристична процедура пакування використовує концепцію порожніх максимальних просторів для керування вільним простором в контейнерах та вибору місця розміщення за критеріями відповідності. Ці послідовності перетворюються на рішення пакування за допомогою нової евристичної стратегії пакування, заснованої на основі концепції максимальних вільних просторів, що розвиваються у ГА та у результаті дають гарний результат.
Генетичний алгоритм
Запропонований алгоритм базується на генетичному алгоритмі  з евристичним алгоритмом упаковки. Евристична стратегія пакування генерує рішення пакування на основі заданої послідовності пакування коробок (BPS - bpx packing solution) і послідовності контейнерів (CLS - container loading sequence). ГА використовується для розвитку цих двох послідовностей. Основними елементами ГА є схема кодування хромосом, схрещування, мутація та селекція. Рисунок 1 ілюструє структуру алгоритму.



Рисунок 1. Генетичний алгоритм. Схема
Схема кодування хромосом

Одна хромосома складається з двох частин, які складаються з послідовності коробок для пакування (BPS) S1  і послідовності контейнерів, у які завантажуємо коробки (CLS) S2 . Ми використовуємо схему кодування на основі порядку для представлення послідовностей, тому S1  і  S2 є {1, ..., m} і {1, ..., N} відповідно, де m - кількість коробок, а N - кількість контейнерів.

Ініціалізація популяції

Механізм ініціалізації відповідає механізму, описаному у роботі Wang і Chen [11] для евристичного генерування деяких спеціальних хромосом у першому поколінні. Цей механізм заснований на спостереженні, що пакунки більшого розміру повинні бути упаковані в коробку першими. Послідовність генів S1  генерується шляхом сортування за спаданням відповідно до значення обсягу, довжини, ширини та висоти кожного продукту, тоді як  S2 генерується випадковим чином.

Селекція

Для описаного ГА було вибрано турнірний метод селекції. Покоління складається з популяції хромосом. Вони відсортовані у порядку спадання параметру fitness (показник ефективності упаковки). Придатність хромосоми визначається евристичною стратегією упаковки. Перші E хромосоми обираються, як елітарність, яка безпосередньо переходить у наступне покоління. З популяції обираються E кількість батьків у пул для парування за допомогою методу відбору турніру з розміром турніру рівним 2. У кожному раунді ми випадковим чином вибираємо дві різні хромосоми з популяції. З ймовірністю pro b  , константне значення, що визначається перед роботою алгоритму, кращий (більш пристосований) додається в парний пул, інакше додається слабкий. Ми відбираємо послідовні дві хромосоми в парний пул як батьків. Для кожної пари батьків існує ймовірність того, що вони підуть напряму у наступне покоління, інакше відбувається схрещування для генерації нащадків.

Схрещення і мутації

На відміну від схеми двійкового кодування, яка полегшує прості операції схрещування, такі як одноточкове схрещення, коли генні рядки просто замінюються одиничною точкою розрізу, розробка операції перехрещення для схеми кодування на основі порядку не є такою простою. Вчені розробили кілька операторів схрещення для цього типу хромосом, наприклад, схрещення з частковою відповідністю (PMX - Partial-Maped Crossover), циклічне схрещування (CX), порядкове схрещення (OX - Order Crossover), Для послідовності генів випадковим чином вибираються дві точки зрізу, скажімо, i та j. Батьки P1  і P2  дадуть двох нащадків  O1 і O2 . Послідовність генів дитини O1 S1    генерується наступним чином, гени в позиціях від i + 1 до j копіюються з  P1. Інші позиції в  O1  заповнені відсутніми генами, починаючи з j + 1 по кругу. Відсутні гени отримують шляхом кругового підмітання P2 від j + 1 і перевірки, чи з’явиться він в O1 , якщо ні, то заповнити поточну позицію в  O1 геном з P2 . Дитину  O2 отримуємо змінивши послідовність P1  і P2 . Послідовність інших генів S2 функціонує незалежно таким же чином. Приклад продемонстровано на рисуноку 2. Мутація проводиться на кожному новоствореному потомстві з ймовірністю Pm , константне значення, що визначається програмістом перед роботою алгоритму. Для кожної послідовності генів випадковим чином вибираються дві позиції, і гени на цих позиціях міняються місцями.






Рисунок 2. Ілюстрація схрещення


Кращий евристичний алгоритм упаковки

Хромосома оцінюється за допомогою евристичної стратегії пакування, яка використовуючи хромосому формує рішення. Враховуючи послідовність упаковки ящиків (BPS) і список послідовностей завантаження (CLS), дотримання евристичної стратегії пакування перетворює ці послідовності на рішення для пакування. Традиційна евристика Deepest Bottom Left з заповненням (DBLF) та її варіації є популярними евристичними методами, які використовуються для рішення проблем пакування контейнерів. Евристика завжди шукає простір з мінімальною координатою x (найглибша) для розміщення поточного елемента. Ми помічаємо, що ця евристика має два недоліки: по-перше, лише одна координата (x) відіграє домінуючу роль у виборі кандидата простору; по-друге, спочатку визначається або елемент, або простір, а потім вибирається його відповідник на основі певних правил пріоритету. На основі цього спостереження ми пропонуємо те, що ми називаємо найкращою евристичною стратегією пакування.
Максимально порожній простір
Пропонується використовувати концепцію максимально порожніх просторів (EMS) для представлення вільних просторів у ящиках, тобто списку найбільшого порожнього кубічного простору, доступного для упаковки, який не міститься в жодному іншому просторі. Рисунок 3 ілюструє концепцію. Чорна рамка окреслює місце доступне на даний момент для упаковки, тобто представляє грані контейнера. 



Рисунок 3. Коцепція максимально порожнього простору
Коли одна синя коробка розміщена в кутку, вона генерує три максимальні порожні місця, які представлені жовтими кубами. Ця концепція нещодавно використана в роботах Gonçalves та ін. і Parreño та ін. для вирішення проблем пакування контейнерів. Максимальні простори представлені їх вершинами з мінімальною та максимальною координатами (xi, yi, zi)  та (Xj, Yj, Zj)  відповідно. В роботі  використано процес різниці (DP - difference process) [12], для оновлення цих порожніх максимальних просторів. Для прискорення процесу дотримуємося правил елімінації, запропонованих у роботі Gonçalves [13].

Пріоритет максимально вільного простору

Пріоритет максимально порожніх просторів визначається за наступним правилом: для двох порожніх максимальних просторів з мінімальних просторів з мінімальними координатами вершин (x1, y1, z1)   і (x2, y2, z2) . Спочатку порівнюються найменші значення координат двох вершин, вершині з меншим значенням надається вищий пріоритет, якщо вони збігаються,  порівнюється друге найменше значення та приписується вищий пріоритет вершині з меншим числом. Якщо другі значення знов однакові, то беремо треті найменші числа і порівнюємо їх. Надаємо більший пріоритет вершині з меншим значенням.

Приклад:
Порівнюємо дві вершини (3,5,4) і (6,3,3)
     Беремо найменші числа з двох вершин 3 = 3
     Беремо наступні два найменших числа 4 > 3
     Відмічаємо, що вищий пріоритет має друга вершина


Причина такого визначення пріоритетів полягає у тому, що потрібно розмістити коробки спочатку в одному куті та прилеглих сторонах контейнера, а потім у його внутрішньому просторі. Сортуються порожні місця у кожному контейнері відповідно до пріоритету, визначеного вище, після кожного оновлення EMS.
Вибір місця

Вибір місця розміщення визначається шляхом застосування критеріїв відбору до можливих кандидатів. На кожні ітерації вибираються перші kb  розпакованих коробок у порядку наведеному у BPS. Потім вибираються перші ke EMS у порядку визначеному вище.. Для цих коробок ke  і  kb EMS ми знаходимо всі можливі призначення розміщення з 6-сторонньою організацією коробки. Тоді для розміщення спочатку вибирається пара (коробка, максимальний порожній простір) з найбільшим коефіцієнтом заповнення. Якщо одна коробка має кілька можливих розміщень на одному порожньому місці, вибирається поле з найменшим. Це можна зробити, обчислити таким чином: розміри простору (X1 - x1, Y1 - y1 , Z1 - z1 ), як визначено, визначаємо розмір коробок після обертання як (l', w', h')  , віднімаємо два вектори і отримаємо (X1 - x1 - l', Y1 - y1 - w', Z1 - z1 - h'), що представляє поля до трьох граней простору. Тоді пріоритет розміщення визначається таким же чином, як і при виборі максимально порожнього простору. Рисунок 4 ілюструє ідею у двовимірному випадку
/div>



Рисунок 4. Розміщення коробки


Якщо немає можливого призначення розміщення для поточного вибору ящиків і пробілів, ми спробуємо наступні ke EMS в контейнері, процес продовжується, поки не буде знайдено принаймні одне можливе розміщення. Якщо спробувати всі EMS в поточному контейнері,  рухаємося вперед, щоб спробувати EMS в наступному відкритому контейнері. Якщо спробувати всі відкриті контейнери, не знайшовши жодного можливого розташування,  відкриваємо наступний невідкритий контейнер у порядку визначеному у CLS. Якщо у списку немає контейнера, то алгоритм зупиняється, не знайшовши прийнятного рішення для упаковки. У цьому випадку  встановлюємо придатність індивіда рівним нулю.

У іншому випадку  завжди знаходимо одне або кілька можливих призначень розташування та вибираємо з найбільшим коефіцієнтом заповнення. Потім  поміщаємо коробку у вибране порожнє місце, видаляємо елемент зі списку товарів і оновлюємо EMS за допомогою методу, що запропонований Lai і Chan [11]. Якщо у списку коробок немає жодного елементу, алгоритм завершує роботу зі знайденим рішенням, а придатність особи встановлюється як коефіцієнт заповнення. Алгоритм  представляє псевдокод евристичного пакування


Висновки

У цій роботі  розглянуто варіант задачі тривимірного пакування об’єктів (3D-BPP), яка полягає в упаковці без перекриття один одного набору тривимірних коробок прямокутної форми у різні за розміром контейнери з метою максимального використання простору. Запропоновано гібридизований ГА з новим евристичним алгоритмом пакування. 


Перевагою використання генетичних алгоритмів разом з евристичними методами упаковки полягає у збільшені ефективності пакування. Головним критерієм ефективності є відсоток заповненості контейнерів. Таким чиним завдяки селекції у ГА обираються найкращі варіанти. Кожне наступне покоління(ітерація) демонструє кращі результати роботи методу упаковки.  Таким чином можна досягти ефективності упаковки з 66 % до 92% за 100 поколінь.


Література


1. Martello, S., Pisinger, D., Vigo, D., 2000. The three-dimensional bin packing problem. Operations Research 48 (2), 256–267.


2. Fekete, S. P., Schepers, J., van der Veen, J. C., 2007. An exact algorithm for higher-dimensional orthogonal packing. Operations Research 55 (3), 569–587.


3. Faroe, O., Pisinger, D., Zachariasen, M., 2003. Guided local search for the three-dimensional bin-packing problem. INFORMS Journal on Computing 15 (3), 267–283.


4. Kang, K., Moon, I., Wang, H., 2012. A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem. Applied Mathematics and Computation 219 (3), 1287–1299.


5. Bortfeldt, A., Mack, D., 2007. A heuristic for the three-dimensional strip packing problem. European Journal of Operational Research 183 (3), 1267–1279.


6. Chen, C., Lee, S., Shen, Q., 1995. An analytical model for the container loading problem. European Journal of Operational Research 80 (1), 68–76.


7. Takahara, S., Miyamoto, S., 2005. An evolutionary approach for the multiple container loading problem. In: HIS 05: Proceedings of the Fifth International Conference on Hybrid Intelligent Systems. IEEE, pp. 227–232.


8. Eley, M., 2003. A bottleneck assignment approach to the multiple container loading problem. OR Spectrum 25 (1), 45–60.


9. Che, C. H., Huang, W., Lim, A., Zhu, W., 2011. The multiple container loading cost minimization problem. European Journal of Operational Research 214 (3), 501–511.


10. Zhu, W., Huang, W., Lim, A., 2012. A prototype column generation strategy for the multiple container loading problem. European Journal of Operational Research 223 (1), 27–39.


11. Wang, H., Chen, Y., 2010. A hybrid genetic algorithm for 3d bin packing problems. In: Bio-Inspired Computing: Theories and Applications (BIC-TA), 2010 IEEE Fifth International Conference on. IEEE, pp. 703–707.


12. Lai, K., Chan, J. W., 1997. Developing a simulated annealing algorithm for the cutting stock problem. Computers & industrial engineering 32 (1), 115–127



13. Gonçalves, J. F., Resende, M. G., 2013. A biased random key genetic algorithm for 2d and 3d bin packing problems. International Journal of Production Economics 145 (2), 500–510




______________




Науковий керівник: Боярінова Ю.Є., к.т.н., Київський політехнічний інститут ім. Ігоря Сікорського

Creative Commons Attribution Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Another articles in this section

Сonferences

Conference 2024

Conference 2023

Conference 2022

Conference 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення