Реферат за темою випускної роботи

Зміст

Вступ

У сучасному світі багато виробничих процесів оптимізуються за рахунок застосування інтелектуальних методів для вирішення різних завдань. Одним з таких завдань є завантаження товарів в транспортний засіб (ТЗ), при якому з'являється проблема розмістити вантаж таким чином, щоб він займав якомога менше місця, або, іншими словами, ми зіштовхуємося із задачею про оптимальну упаковку, так званою 3-х мірної задачею рюкзака. Таким чином, для задачі розміщення блоків в транспортному засобі знижується витрата на транспортування вантажів через більш компактного розподілу.

1. Актуальність теми

Упаковка коробок в контейнер, кузов транспортного засобу або на паллету є однією з найскладніших проблем упаковки з-за обмежень, які виникають в реальному світі. [10] Було встановлено, що ця задача є NP-повною. Всі точні алгоритми, які вирішують задачу про упаковку, використовують повний перебір всіх можливих рішень. В наслідок чого, навіть при невеликій кількості вантажів, програма буде працювати неприйнятно велику кількість часу. Так само проблемою є набір додаткових обмежень, які повинні бути виконані при розстановці вантажу в заданому об'ємі. Таким чином, створення наближених алгоритмів, які за прийнятний час знаходять рішення, близьке до оптимального, з урахуванням додаткових обмежень є актуальною задачею.

2. Мета і завдання дослідження, плановані результати

Мета роботи: підвищення ефективності доставки вантажу споживачам за рахунок його раціонального розміщення всередині транспортних засобів.

Планується вирішити наступні задачі:

1. Провести аналіз технологій і методів, використовуваних для вирішення транспортної задачі, сформулювати постановку задачі розміщення вантажу всередині ТЗ.

2. Розробити математичну модель розміщення вантажу з умовою обмежень.

3. Розробити модифікований генетичний алгоритм оптимізації розміщення вантажу всередині ТЗ.

4. Експериментально перевірити ефективність роботи алгоритму.

Об'єктом дослідження є процес завантаження товарів в транспортний засіб.

Предметом дослідження є визначення оптимального розміщення вантажів всередині заданого обсягу транспортного засобу.

3. Огляд досліджень і розробок

В ході аналізу робіт, присвячених створенню моделей і алгоритмів тривимірної упаковки визначено, що для вирішення подібних задач використовують, в основному, евристичні підходи. У літературі найбільш часто згадуються такі евристичні алгоритми: ітераційний локальний пошук (Iterative Local Search, ILS); спрямований локальний пошук (Guided Local Search, GLS); пошук зі змінною околицею (Variable Neighborhood Search, VNS); імовірнісний жадібний алгоритм (GRASP); еволюційний алгоритм (Evolutionary Algorithm, EA); генетичний алгоритм (Genetic Algorithms, GA); алгоритм оптимізації мурашиної колонії (Ant Colony Optimization, ACO); імітація відпалу (Simulated Annealing, SA); пошук із заборонами (Tabu Search, TS). [9] У порівнянні з числом всіляких евристик, кількість точних алгоритмів розв'язання тривимірної задачі упаковки в контейнер обмежена. Одна з причин цього полягає в складності подання ймовірної упаковки і введення обмежень з реальних задач. Навіть якщо такий метод вирішення знайдений, залишається складність у формулюванні рішення, найчастіше що є великим через кількість коробок і контейнерів. [10]

Більшість з них базується на декомпозиції вихідної задачі і зведенням її до задач меншої розмірності шляхом розбиття на шари і заповненням кожного шару будь-якої евристикою. Деякі алгоритми використовують двофазні процедури. На першій фазі відбувається упаковка коробок в шари, на другий - процес обміну коробок всередині шару для поліпшення локального рішення. [1]

3.1 Огляд міжнародних джерел

У роботах закордонних авторів вирішення проблеми розміщення вантажів всередині транспортного засобу зустрічається спільно з вирішенням проблеми побудови маршрутів, так звана задача комівояжера. При вирішенні транспортної задачі виділяється 2L-CVRP і 3L-CVRP. Завдання класу 2LCVRP розглядають двовимірне розміщення об'єктів, 3L-CVRP (Three-Dimensional Loading Capacitated Vehicle Routing Problem) відповідно тривимірне.

Наприклад, у роботах [4] та [5] використовується гібридний алгоритм вирішення 3L-CVRP, що складається з алгоритму пошуку з заборонами для складання маршрутів транспортних засобів та алгоритму підпорядкованого дерева пошуку для завантаження ящиків всіх клієнтів в вантажний простір автомобіля.

3.2 Огляд національних джерел

У роботі В.В. Псіоли пропонується алгоритм наближеного рішення, заснованого на комбінації підходів побудови по шарам і блокам. Що полягає в наступному:

pic1

Рисунок 1 – Схема алгоритму, запропонованого В.В. Псиолой [2]

1. Дані для укладання (список ящиків) передаються алгоритму комбінування ящиків в блоки.

2. Набір ящиків комбінуються у всілякі прямокутні блоки, блоком називається набір ящиків, підстелений поруч, так що вони утворюють паралелепіпед без щілин і пустот і представляє собою аналог ящика з іншими розмірами.

3. Сформований набір блоків передається в алгоритм 3-х мірної укладання, який складається з 3 частин:

а) перша частина вибирає площину для укладання ящиків, вибір площині для укладання є зведенням задачі 3-х мірної укладання до задачі 2-х мірної укладання;

б) друга частина вибирає набір блоків, допустимих для укладання в поточну площину, при цьому всі ці блоки повинні бути однієї висоти для відомості 3-х мірної задачі для укладання до 2-х мірної задачі;

в) третя частина є застосуванням алгоритму 2-х мірної укладання до обраної площині і допустимому набору блоків для укладання в цю площину;

4. Алгоритм 3-х мірної укладання виконується до тих пір, поки не укладені всі ящики замовлення і в ТЗ залишається вільний об'єм для укладання ящиків.

5. Після того як всі ящики укладені або об'єм повністю заповнений, розрахунок оптимальної укладки ящиків в ТЗ вважається завершеним. [2]

Однак час вирішення завдань 3-х мірної упаковки, за рахунок поліпшення локального рішення всередині кожного виділеного шару послідовними методами призводить до великих часових витрат.

Абсолютно інший підхід до цієї задачі пропонується в роботі «Застосування генетичного алгоритму розв'язання задачі тривимірної упаковки» авторами якої є В.В. Курейчик, Д.В. Заруба, Д.Ю. Запорожець. Запропонований алгоритм упаковує вантаж не пошарово. Це запропоноване рішення дозволяє розміщувати всі вантажі всередині контейнера разом. Досягається це шляхом того, що використовується модифікований генетичний алгоритм, який дозволяє працювати з закодованим рішенням (хромосомою), яка відповідає розміщенню ящиків всередині контейнерів. Тобто кожна хромосома зберігає інформацію по розташуванням і розмірам всіх блоків, що дозволяє в ході роботи алгоритму шукати оптимальне розташування вантажів всередині ТЗ. [3] Таким чином довжина хромосоми дорівнює кількості вантажів.

Даний алгоритм не враховує додаткових обмежень, наприклад, так як вага вантажу.

pic1

Рисунок 2 – Розміщення блоків у 3-х мірному просторі [3]

Так само для вирішення задач такого плану відомий метод площин, представлений у роботі О.В. Корчевської.

Особливостями цього методу є:

- безпосереднє вирішення задач, а не зведення їх до задач меншої розмірності;

- використання як шарової, так і безшарової стратегій;

- заповнення по, так званим, пріоритетним осях;

- аналіз пустот і розгляд способів їх об'єднання;

- допускається використання не одного, а декількох паралелепіпедів.

pic1

Рисунок 3 – Розбиття на області, які визначаються першої коробкою [1]

Основною відмінністю цього методу від першого наведеного є те, що тут ящики не групуються у блоки для створення шарів, а перша коробка визначає шар. Тому, алгоритм оцінює всі види коробок і їх орієнтації, щоб відкрити новий шар. Як тільки перша коробка поміщена у паралелепіпед, вона автоматично формує шар, який буде заповнюватися по висоті. Залежно від розмірів коробки і паралелепіпеда весь простір розбивається на паралелепіпедні області. [1]

3.3 Огляд локальних джерел

У Донецькому національному технічному університеті питаннями оптимізації завантаження товарів займався Трубачов Д.С. Він займався задачею розподілу вантажів усередині повітряного транспортного засобу. У його роботі розглядалася проблема навантаження з обмеженнями вантажопідйомності літака. Були запропоновані 4 методи для вирішення даної задачі: повний перебір, метод гілок і меж, метод динамічного програмування, генетичний алгоритм. [8]

4. Аналіз аналогічних систем

Був проведений аналіз існуючих комп'ютеризованих систем. Одним з найбільш популярних рішень оптимального завантаження вантажів є онлайн сервіс «packer3d». В основу використовуваних алгоритмів у програмі з розрахунку оптимального плану завантаження різнотипних вантажів покладені теоретичні та прикладні дослідження Псіола В.В. [2] Сервіс дозволяє розрахувати оптимальний план завантаження різнотипних ящиків, циліндрів і палет у контейнери, фури, вагони. Сервіс працює з безліччю обмежень на навантаження, будує 3д модель рішення і дає можливість експорту рішення у різний формати.

Так само схожим функціоналом володіє сервіс розрахунку завантаження на сайті www.searates.com. Це портал, присвячений морським вантажоперевезенням. На ньому є калькулятор завантаження, який дозволяє отримати наближено оптимальне розташування вантажів всередині контейнера.

5. Математична постановка задачі тривимірної упаковки

Дана область тривимірного простору шириною W, довжиною L і висотою H - контейнер для навантаження ззаду з частиною, що відкривається, розмірами H×W для завантаження і розвантаження товарів і вантажопідйомністю D. Також дано безліч блоків N. Уся безліч блоків розбита на безліч типів T. Кожен тип визначає геометричні параметри, вага, цінність і ряд інших параметрів блоків. Потрібно розрахувати точне положення блоків у заданому об'ємі таким чином, щоб його заповнення було допустимим і ефективним, тобто сумарний об'єм блоків, що помістилися, повинен бути максимальний. Допустимим становищем блоку вважається таке, коли всі упаковані блоки знаходяться всередині заданого обсягу, не перетинаються і спираються на дно і стінки інших блоків.

pic1

Рисунок 4 – Завантаження в 3х мірному просторі
(анімація: 7 кадрів, циклів повторення - 12, розмір 39 Кб)

Обмеженнями можуть бути:

1. Сумарний об'єм елементів не повинен перевищувати обсягу транспортного засобу.

2. Жоден елемент не може виходити за межі заданого обсягу.

3. Займана вага не може перевищувати вантажопідйомність транспортного засобу.

4. Коробки можуть розміщуватися тільки таким чином, щоб їх межі були паралельні стінам контейнера.

5. Коробки не повинні перетинатися один з одним.

Цільова функція:

F = (xmax - xmin) * (ymax - ymin) * (zmax - zmin) , F →min,

де точки (xmin, ymin, zmin) та (xmax, ymax, zmax) – точки, що визначають паралелепіпед блоків.

Розглядаючи задачу розміщення вантажів в транспортному засобі, введемо правила навантаження транспортного засобу, які необхідно враховувати при реалізації алгоритму:

1. Блоки можуть мати тільки форму паралелепіпеда

2. Заповнення обсягу ТЗ блоками походить від дальньої стінки до ближньої.

3. Упаковані можуть бути тільки ті блоки, які проходять в дверний отвір транспортного засобу шириною W1 і висотою H1.

4. Упаковані можуть бути тільки ті блоки, які повністю поміщаються в контейнері.

Так само можуть додаватися додаткові обмеження, які будуть з однієї сторони не значними, а з іншого боку можуть серйозно вплинути на план навантаження товарів в транспортний засіб:

- обмеження на крихкість предметів: не крихкі предмети не можуть бути розміщені зверху крихких;

- обмеження на орієнтацію і повороти коробок;

- кожна коробка має цілком знаходитися на плоскій поверхні, тобто повністю спиратися на контейнер або іншу коробку.

Для реалізації даного завдання в ході аналізу методів був обраний модифікований генетичний алгоритм.

Висновки

В результаті науково-дослідної роботи були зібрані і вивчені матеріали з питань, пов'язаних з темою магістерської роботи. Були досліджені застосовувані методи і алгоритми оптимізації завантаження вантажів у транспортні засоби. Були виявлені переваги і недоліки існуючих комп'ютерних систем, методів оптимізації, що відносяться до різних класів. На підставі результатів аналізу був обраний напрямок власних досліджень в області розміщення вантажу в транспортних засобах.

Зауваження

На момент написання даного реферату магістерська робота ще не завершена. Передбачувана дата завершення: травень 2017 р. Повний текст роботи, а також матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.

Список джерел

  1. Корчевська О.В. Дисертація Інформаційні моделі та методи розв'язання задач ортогонального розкрою-упаковки на основі конструктивних і нейромережевих підходів // СГТУ, 2009 р. – 147с.
  2. Псіола. В.В. Дисертація Про одне наближення щільної упаковки // МГУ имени М.В. Ломоносова, 2011 р. -143с.
  3. Курейчик В.В., Заруба Д.В., Запорожець Д.Ю. Застосування генетичного алгоритму розв'язання задачі тривимірної упаковки // Известия ПФУ. Технічні науки,2012 р. - 264с.
  4. Andreas Bortfeldt A hybrid algorithm for the capacitated vehicle routing problem with threeв dimensional loading constraints // — Режим доступу:ftp.fernuni-hagen.de/pub/fachb/wiwi/winf/forschng/publi/DBFakWiWI460.pdf
  5. Ruan Q., Ruo Q., Woghiren K., Miao K. A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints // — Режим доступу: ntl.bts.gov/lib/37000/37900/37921/A_hybrid_genetic_algorithm_for_the_vehicle_routing_problem_with_three-dimensional_loading_constraints.pdf
  6. Сайт компанії Packer3d // — Режим доступу: packer3d.ru
  7. Сайт компанії Searates // — Режим доступу: searates.com
  8. Трубачов Д. С. Система формування динамічного розкладу рейсів, з урахуванням повітряних ресурсів авіакомпанії // - Режим доступу: masters.donntu.ru/2013/fknt/trubachev/
  9. Кощєєв І.С. Оптимізація доставки вантажу споживачам з урахуванням його розміщення всередині транспортних засобів на основі евристичних методів. Дисертація // - Режим доступу:www.ugatu.ac.ru/assets/files/documents/dissov/03/2014/KoshcheevIS/diss.pdf
  10. Юдаков А.В. Задача про тривимірну упаковку і методи її вирішення. Огляд // Інженерний вісник № 06 , червень 2015 р.