Использование кубических объемов и упаковка ячеек

Стacking: 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 остановок: 181440 маршрутов: еще можно обрабатывать компьютером

- 15 остановок: 43,6 миллиарда маршрутов: занимает часы

- 20 остановок: 60,8 квадриллионов маршрутов: занимает века

- 50 остановок: больше маршрутов, чем атомов в наблюдаемом мире

TSP NP-трудна: нет известного алгоритма, который мог бы решить ее за полиномиальное время. Чем больше N, тем точные решения становятся невозможными, и мы должны использовать гипотезы: алгоритмы, которые быстро находят хорошие (но не гарантированно оптимальные) решения.

Общие гипотезы:

- Ближайший сосед: с текущей точки всегда идете в самую ближайшую не посещенную остановку. Быстро, но часто приводит к маршрутам с некрасивыми пересечениями.

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

- 2-opt улучшение: взять завершенный маршрут и попробовать менять пары рёбер. Если удаление двух рёбер и их последующее соединение делает маршрут короче, сохраните обмен. Повторяйте, пока не будет найдено улучшение.

Гипотезы против точных решений

Компания по доставке имеет 12 остановок сегодня. Ее водитель использует гейки ближайшего соседа: в каждой точке ехать к ближайшей не посещенной остановке.

Зоны, плотность и проблема маршрутизации транспортных средств

Последняя миля доставки: где геометрия встречается с экономикой

Последняя миля - от распределительного центра до двери клиента - составляет 40-50% от общих затрат на перевозку. Это наиболее геометрически ограниченная часть цепочки поставок.

Радiales маршруты от базы: Камiones de reparto salen en radiantes desde un centro de distribución. Cada camión debe recorrer una zona geográfica compacta: no deben cruzarse las rutas de dos camiones.

Плотность доставки определяет все. En una zona urbana, un camión podría hacer 150 entregas en un turno de 8 horas. En zonas rurales, el mismo camión podría manejar 20-30. La razón geométrica: las paradas urbanas están cerca una de otra (poco tiempo de conducción entre paradas) mientras que las rurales están más lejanas.

Маршрутизация по зонам делит зону обслуживания на географические кластеры. Каждая зона назначается одному транспортному средству. Хорошие зоны должны быть компактными (круглыми или квадратными) и смежными (без пробелов или изолированных участков). Цель: минимизировать общую дистанцию, сохраняя каждую маршрут под пределом времени/емкости.

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

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

Зонирование

Компания по доставке работает из базы в центре города. У них есть 4 водителя и 200 доставок, расположенных на обслуживаемой территории с радиусом около 10 миль в виде круга.