Использование объема и упаковка контейнеров

Укладка: 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 миль.