03.03.2019 23:25
KirillHome
 
Полная задача:
Завод ЖБИ (железобетонных изделий) производит разного типа плиты, кольца, бордюры - и прочие изделия из бетона.
Эти изделия надо перевезти к заказчику.
Для перевозки могут использоваться автомобили разных размеров и грузоподъёмности (в настоящее время - 5 разных типов).

Нужно наиболее оптимально (вес как можно ближе к грузоподъёмности автомобиля - но не более её) расположить все эти изделия в кузове (рейсов может быть несколько). То есть задача - уменьшить количество рейсов.

Изделие меньшей длины, чем ширина кузова - может быть расположено как вдоль, так и поперёк кузова. Ряд изделий (не все) могут быть размещены в несколько рядов по высоте (количество рядов в высоту зависит от изделия). При расположении в кузове надо соблюсти ещё одно условие - нагрузка на левую ось (вес изделий, находящихся левее центра) не должна сильно отличаться от нагрузки на правую ось (вес изделий, находящихся правее центра). Допустимое отклонение зависит от типа автомобиля.
Ну, и ещё есть технологические зазоры между изделиями (и, возможно, между изделием и бортом автомобиля).

Всё это осложняется тем, что сделать надо на 1с (да и визуализировать расстановку изделий в каждом конкретном кузове ).

В присланных мне примерах максимальное количество разных наименование в одном заказе - 50, максимальное количество единиц - 400, максимальный вес - 600 тонн.
Простой перебор - не подойдёт.

Пока думаю как-то упростить.
Первое - всё в один ряд в высоту.

Далее - сумбурные мысли, которые можно и нужно критиковать (и предлагать свои на замену):
Кузов автомобиля - матрица NxM точек (каждая точка - 5х5 см или 10х10) со значением 0.
Каждое изделие - своя матрица KxL точек (точки - такие же). Круглые изделия - для простоты считаются квадратными.
При размещении изделия в кузове - "занятые точки" кузова принимают значение 1 (или "вес точки" - для контроля веса и перекосов).

Сортируем весь список по длине, кладём сначала более длинные.
Этот вариант обозначим "вариант 1".

Те изделия, которые можно повернуть - поворачиваем. Заново сортируем весь список, кладём сначала более длинные.
Этот вариант обозначим "вариант 2".

Выбираем из них "лучший вариант"

Дальше - пока только метод Монте-Карло вижу.
Сортируем список случайным образом, раскладываем, сравниваем с "лучшим вариантом", получается лучше - запоминаем как "лучший вариант" и повторяем итерацию 100 (1000? 10'000? не знаю...) раз.

Плохие проблемы: - контроль перекоса, допустимость "многоэтажности"

В общем - буду признателен за "направления мысли".
04.03.2019 07:38
OlegON
 
Мне кажется, что задачи такого типа пока нерешаемы. Просто в силу неточности измерений, криворукости грузчиков, выступающих частей, установки круглого матрешкой и прочее. Надо бы понимать, действительно, как часто приходится дополнять до грузоподъемности машины, ставя все друг на друга или это вообще никогда не бывает (крошится, например).
Думаю (навскидку), что пошел бы все таки перебором. Для уменьшения количества вариантов отсортировал бы массив по сумме веса и размера, поделил на три группы количеством, после чего до 2/3 грузоподъемности заполнял большими, потом средними и 1/6 мелкими. Пропорции покрутил бы. Мне кажется, что такое могло бы помочь, хотя, в целом, уверен, что с бумаги эффективная укладка невозможна.

Форум на базе vBulletin®
Copyright © Jelsoft Enterprises Ltd.
В случае заимствования информации гипертекстовая индексируемая ссылка на Форум обязательна.