У меня есть интересное задание, для которого я пытаюсь найти алгоритм или даже несколько указателей. В худшем случае мне, возможно, придется написать и реализовать его самому, а в лучшем случае мне нужно получить адекватную информацию о том, как это работает, чтобы я мог разумно протестировать и проверить готовое решение от поставщика.
Я много искал, но пока ничего не нашел. Вполне возможно, что я просто не могу подобрать правильные ключевые слова для поиска.
ДЕЙСТВИТЕЛЬНО короткая версия: из несимметричной прямоугольной сетки прямоугольных объектов того же размера найдите лучшую группу, которая вписывается в ограничивающую рамку, удалите эту группу из набора, затем повторяйте, пока не останется никаких объектов.
Подробная версия: существует множество промышленных приложений для оптимизации слоев поддонов (StackBuilder - один из примеров с открытым исходным кодом). Я смотрю на конкретное приложение на другом конце проблемы - мне нужно посмотреть на паллету, которая была оптимизирована чем-то вроде StackBuilder, и найти самый быстрый способ удалить ящиков с поддона с помощью большого инструмента, чтобы поднять несколько ящиков одновременно, в фиксированных смежных группах. Поднимать по одной коробке за раз и / или пытаться переставить их, не разрешается.
Итак, заранее зная размер ящиков и их шаблон поддонов, мне нужно найти наибольшую непрерывную группу в этом шаблоне, которая вписывается в конкретную ограничивающую рамку, а также местоположение и ориентацию этой группы. Затем «удалите» эту группу из рассмотрения и найдите следующую лучшую группу и т. Д., Пока слой поддонов не станет пустым.
Осложняющие факторы:
1. Мне нужно решение для общего случая, потому что оно должно работать с несколькими тысячами ящиками разного размера / формы, каждый со своим оптимизированным рисунком поддонов
2. Для любой группы выбора, найденной алгоритмом, подгонка внутри ограничительной рамки - это только первый критерий выбора. Мне также нужно убедиться, что ограничивающий прямоугольник не перекрывается на соседние прямоугольники, и мне нужно контролировать направление поиска - алгоритм должен выбирать из внешних краев внутрь, выбор групп в центре не требуется
3. Учитывая, насколько сложны некоторые шаблоны поддонов, так как группы поддонов удаляются с поддона, неизбежно останется несколько остатков, которые имеют , чтобы выбрать «соло», так как они плохо вписываются в один. оптимизированных по размеру групп выбора. Таким образом, алгоритм должен быть в состоянии найти «лучшую группу из того, что осталось», а не только фиксированный размер группы.
4. Группа выбора должна быть расположена в «2.5D», то есть X, Y и RZ. Итак, 2D местоположение, плюс вращение вокруг оси 3-го измерения.
Упрощающие факторы:
1. Учитывая то, как обычно работают шаблоны паллет, «ориентация» любой группы должна быть только 0 или 90 градусов (технически 180 и 270 также, но в моем случае это просто), поэтому любые решения с нечетными углами могут быть отвергнутым
2. Любой входящий поддон будет иметь только коробки одного размера, чтобы иметь дело с
3. Размеры входящей паллеты и ее образцы будут известны заранее.
4. Алгоритм должен быть только 2D, чтобы обрабатывать один слой поддона - его можно повторять для каждого слоя по мере необходимости
5. «Ограничивающий прямоугольник» для поиска групп выбора представляет собой простой прямоугольник
6. Все прямоугольники на паллете представляют собой простые прямоугольники (если смотреть с точки зрения оси Z) и могут рассматриваться как таковые. Никаких странных форм. Размеры оси Z будут обрабатываться внешним образом по этому алгоритму