Використання об'єму & упаковування в контейнери

Укладання: 3D геометрія в кожному причепі

Стандартний поддон у Північній Америці - це 48 дюймів на 40 дюймів (поддон GMA). Це фундаментальна одиниця геометрії логістики.

Використання об'єму вимірює, наскільки ефективно ви заповнюєте простір: фактичний обсяг продукту розділений на доступний обсяг. Причіп, який повний за вагою, але наполовину порожній за об'ємом, має погане використання об'єму. Причіп, упакований до стелі, має відмінне використання об'єму.

Укладання колон: кожен шар ідентичний, коробки прямо одна на одній. Структурно слабке, але ефективно використовує простір.

Черезрядне (вітряне) укладання: чергуючі шари повертаються на 90 градусів. Набагато стабільніше, але створює порожнечі по краях, марнуючи 5-15% площі поддона.

Завантаження контейнерів - це реальна геометрична проблема: умістити прямокутні коробки різних розмірів у 40-футовий контейнер доставки (внутрішні розміри приблизно 39'5" x 7'8" x 7'10"). Це 3D упаковування в контейнери: одна з класичних NP-складних задач у інформатиці. Жодний алгоритм не може гарантувати оптимальне рішення за розумний час для великих екземплярів.

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

Ефективність завантаження поддонів

Вам потрібно завантажити коробки розміром 12 дюймів в довжину, 10 дюймів в ширину & 8 дюймів в висоту на стандартний поддон 48" x 40". Максимальна висота укладання - 48 дюймів.

Чому оптимізація маршруту стає складною

Задача комівояжера (TSP)

Припустимо, вам потрібно відвідати 10 клієнтів & повернутися на вашу базу. Який найкоротший маршрут? Це задача комівояжера: одна з найбільш вивчених задач у математиці & інформатиці.

Складність полягає у комбінаторному вибуху. Для N зупинок існує (N-1)!/2 унікальних маршрутів (ділення на 2, тому що за годинниковою стрілкою & проти годинникової стрілки мають однакову відстань).

- 5 зупинок: 12 маршрутів: перевірте їх усі за мілісекунди

- 10 зупинок: 181 440 маршрутів: все ще керовано для комп'ютера

- 15 зупинок: 43,6 мільярда маршрутів: займає години

- 20 зупинок: 60,8 квадрильйона маршрутів: займає століття

- 50 зупинок: більше маршрутів, ніж атомів у спостережуваному Всесвіті

TSP - це NP-важка: немає відомого алгоритму, який може вирішити це за поліноміальний час. Коли N зростає, точні рішення стають неможливими & ми повинні використовувати евристики: алгоритми, які знаходять хороші (але не гарантовано оптимальні) рішення швидко.

Загальні евристики:

- Найближчий сусід: З поточного місця, завжди йдіть до найближчої невідвіданої зупинки. Швидко, але часто створює маршрути з безглуздими перетинаннями.

- Вставлення опуклої оболонки: Почніть з найовалювіших зупинок (опукла оболонка: геометрична межа). Потім вставляйте внутрішні зупинки одна за одною там, де вони додають найменше відстані.

- 2-opt покращення: Візьміть завершений маршрут & спробуйте поміняти пари ребер. Якщо видалення двох ребер & повторне з'єднання різними означає коротший маршрут, зберігайте обмін. Повторюйте, поки не буде покращення.

Евристики проти точних рішень

Доставка компанії має 12 зупинок сьогодні. Їхній водій використовує евристику найближчого сусіда: у кожній точці їхати до найближчої невідвіданої зупинки.

Зони, щільність & задача маршрутизації транспортних засобів

Доставка на останній милі: де геометрія зустрічається з економікою

Остання миля: від розподільчого центру до дверей клієнта: становить 40-50% від загальної вартості доставки. Це найбільш геометрично обмежена частина ланцюга поставок.

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

Щільність доставки визначає всього. У щільному міському районі вантажівка може зробити 150 доставок за 8-годинну зміну. У сільській місцевості та ж вантажівка може керувати 20-30. Геометрична причина: міські зупинки близько одна до одної (короткі проїзди між зупинками), а сільські зупинки далеко одна від одної.

Маршрутизація на основі зон ділить службову область на географічні кластери. Кожній зоні призначена одна машина. Хороші зони - це компактні (приблизно круглі або квадратні) & суміжні (немає прогалин або ізольованих кишень). Мета: мінімізувати загальну відстань, не виходячи за часові/ємнісні обмеження кожного маршруту.

Задача маршрутизації транспортних засобів (VRP) узагальнює TSP на кілька машин. Дано базу, N клієнтів & K вантажівок (кожна з ємністю & часовими обмеженнями), призначте клієнтів вантажівкам & упорядкуйте маршрут кожної вантажівки, щоб мінімізувати загальну відстань. VRP також NP-важка.

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

Проектування зон

Доставна компанія працює з бази в центрі міста. У них є 4 водії & 200 доставок розповсюджені по приблизно круглій службовій області з радіусом 10 миль.