Уважаемые коллеги!
А есть ли желающие поломать голову над алгоритмами?
Собссно задача. Есть n заказов и m машин. У каждого заказа есть вес и объем, у каждой машины соответсвенно вместимость и грузоподъемность. В силу специфики перевозок (легкие и объемные грузы) грузоподъемностью можно пренебречь, единственным параметром является объем. Требуется разложить заказы по машинам, так чтобы суммарное "недозаполнение" машин было минимальным...

Задача, очень практическая и очень нужная.  Как я подозреваю, это некий аналог "задачи о рюкзаке", но напрямую алгоритмы решения "задачи о рюкзаке" не идут. Если кто-нить что-нить подскажет, буду очень благодарен.

Да , надеюсь, понятно, что в каждую машину можно помещать только заказы целиком...

рекурсия?

(1) а логистика пофигу?

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

ну что рекурсия, я как-то подозреваю... вроде почти все алгоритмы на оптимизацию так или иначе рекурсивны А подробнее?

(3) +1

(3)В данном случае критично поместить заказы в машины а не оптимизировать маршруты...

(3) Когда воруют - главное, вывезти уворованное, и побольше... Куда вывозить - вторично...

(0), (3), (8) -- на Баш :)

(7) это ты так думаешь... к тому же еще и форму заказов надо учитывать, а не тупо объем... +стеллажность или как там, ограничение в установке товара друг на друга... ;)

уф-ффф... до чего же я нашу Мисту люблю... А задача как раз совершенно реальная из реальной жизни реальной московской торговой кампании...

(10) ну да я так думаю... потому что я в этой конторе уже пятый месяц сижу... и с логистами, и с кладовщиками и даже с грузчиками уже море водки выпил...

нет ограничений в установке товара, нет стеллажности, даже паллетирования нет...

(13) ну хз... может вы рулоны продаете, а их особым образом в прямоугольную машину запихивать надо...

есть тупое забивание объема машины коробками примерно одинаковых габаритов... единственная проблема - раскидать заказы по машинам...
заказов - 1000, машин - 75-80

все машины имеют одинаковую "объемоподъемность"?

суммарный объем машин превышает суммарный объем заказов мпримерно на 10%, тем не менее примерно 15% заказов не развозится... из-за того. что машины недозагружены
и так каждый день...

(16)нет, машины примерно 30 типов, у каждого типа свой объем

млин, так у тебя одни переменные и ни одной константы чтоль? даже не за что зацепится?

если коробки одинакового размера, то все просто. измеряем вместимость каждой машины в мифических коробках, сортируем заказы по объему в коробках, а машины - по свободному месту в тех же коробках. самый большой заказ кладем в машину с наибольшим свободным местом. повторяем.

(20) это, конечно, если на маршрут нас.рать ;)

(0) В управлении доставкой есть решение твоей проблемы, правда с картами стоит как УПП (цены примерно год назад смотрел)

ну вот такая математическая задачка- есть 1000 действительных чисел - это объем заказа и 80 натуральных чисел - это объемы машин . надо разбить тысячу чисел на 80 групп, так чтобы сумма каждой группы минимальа отличалась от соответствующего натурального числа

(20) этот алгоритм я щас реализовал... по сравнению с ручной раскидкой "дядей Васей" выигрыша практически не дал...

(24) есть еще тупой перебор с построением гигантского дерева, тока очень затратный...

http://ru.wikipedia.org/wiki/Задача_о_ранце#.D0.A0.D0.B5.D1.88.D0.B5.D0.BD.D0.B8.D0.B5

(21) на маршрут на...ть, важно - уменьшить не дозагрузку машины... требуется недозагрузка - не более 10%, сейчас - около 20%
(26) чуствую, что где-то рядом, но не то...

(25) тупой перебор по дереву не укладывается в сроки...

(24) ты учитываешь только объем коробки? а габариты?

в геометрии вроде была задача как при опредиленом периметре получить минимальную площадь за счет уменшение.увеличения старон 4 угольника

Теория говорит, что алгоритм очень простой:

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

ребят, ну чего усложнять... ну давайте решим хотя бы просто разбиение на объемы... потом будем думать о габаритах... при 20% недогрузе проблема не в габаритах...
вот на примере
5 заказов - 1,8; 1,9; 2,7, 0,8, 3,1 - это объемы заказов
три машины - 5, 7, 2 - это  объемы машин...
как раскидать объемы по машинам? нужен алгоритм...

(31) вот так я щас  и сделал... при этом алгоритме недозагруз упал с 20 до 15-17... не катит...

(31) это не оптимальный алгоритм... увы...

(32) зависит от величины заказов. Если например 100 заказов имеет размер каждый больше половины машины, то задача вообще не имеет решения.

(32) один объем тебе ничего не даст...
грубо: у тебя ширина кузова 150см и 4 коробки по 40см = 160см, по объему ты легко сможешь попасть в "рамки", а вот реально по габаритам груза - нет

(34) хорошо, а можно как-нить оценить эту зависимость? ну чтобы я мог сказать, что вот то, что я сделал при данной средней величине заказа (такая статистика есть) и есть оптимальная загрузка
(35) у меня ма-а-а-а-ленькие коробки... маленькие! их можно как угодно ставить... и уменя машины НЕДОЗАГРУЖЕНЫ... туда еще можно было бы положить ... есть изменить разбивку на заказы...

(32) А ты хоть понимаешь, что даже при наилучшем решении у тебя будет недогруз?
И не факт, что он будет значительно меньше.

Автор, объясни смысл этой задачи?
Это не из разряда "подметания плаца ломиком"?

(32) решил?)))
1 машина: 1,9 и 3,1
2 машина: 1,8 и 2,7 и 0,8
3 машина: отдыхает

(34) Какая задача не имеет решения? Сделать так, чтобы недогруза не было? Она никогда не имеет решения.
Минимизировать недогруз? Имеет решение всегда.

(36).1 Сравнивать с наилучшем решением, полученным полным перебором ;-)

(40) если 100 заказов занимает больше половины машины каждый, то нужно как минимум 100 машин, а у нас 80. Естественно имеется в виду самая большая машина.

Берешь машину 1, среди груза ищещь объем равный или меньше, если меньше - ищешь груз равный или меньше остатку объема и так далее. Каждый раз сортировать.

объясняю - задача совершенно реальная - есть торговая кампания, которая торгует продуктами с доставкой... у кампании есть свой парк машин... ежедневно выписывается 1000(в среднем) счетов ночью они загружаюися по машинам и днем развозятся... штрафы не недоразвоз такие, что выигрывать на бензине (износе машин и т.д.) бессмысленно... расстояния тоже не велики - москва и москолвская область. критично только одно- уложить все заказы в машины...  вот и все...
естьвариант конечно - увеличить парк  машин... для этого ядолжен объеснить генеральному что не дозагруз примерно в 20% (после моей работы в 15-17) - это и есть самый оптимальный вариант и ничего лучшен программными или какими-то еще способами сделать нельзя...

(44) Критерий оптимальности очень слаб.

(44) некуй развозить... пусть сами в магазин ходят))

(39)(46)8 заказов - 1,8; 1,9; 2,7, 0,8, 3,1 2,3  - это объемы заказов а если так
три машины - 5, 7, 2 - это  объемы машин...
как раскидать объемы по машинам? нужен алгоритм...

(46) ну вот единственным критерием является процент недозанруза машин по объему...
(39)(47) увеличьте количество заказов до 1000, а мошин до 80... сколько врмеени это будет решаться простым перебором?

(48) Смотря как написать этот "простой перебор"

(48) >> сколько врмеени это будет решаться простым перебором?

Ну, если сделать на базе офисной сети выч. кластер и каждую ночь его заставлять это считать ... наверное справится ;-)

(48) может, с другой стороны подойти, берем самый большой заказ и грузим в самую маленькую машину и так далее по этому же принципу.

метка

ну, на самом деле, если оптимизировать на предмет одинаковости размеров машин и заказов - вполне может быть и не очень много

(53) к (48)

(51) Осподи еще один. Этот способ не дает самого оптимального варианта.

(49), (50) ... ну дык вот алгоритмик бы мне... Перебор + "метод ветвей и границ" (он же эвристика Брудно)? Пока ничего лучше не могу придумать...

(55) нам не нужен самый оптимальный. Нам нужно чтобы в 10% уложились. Читай условия задачи.

Стоп, погодите, а там разве не всего n*m вариантов? Это же совсем быстро посчитаться должно.

(57) Читай сам внимательно всю ветку.

http://www.packer3d.ru/node/231

задачка комбинаторики с ограничением - разбить n предметов на m групп... если не путаю, там что-то порядка n в степени m

(60) это программка решает задачку оптимальной укладки ОДНОГО заказа в одну или несколько машин... у меня задачка другая...

(48) Многое зависит от дисперсии объемов груза. Если все заказы составляют 51% от максимального объема машин, то можно поиметь 49% недогруза. И никакой алгоритм не поможет. Если мало заказов с небольшим объемом, трудно будет плотно упаковать машины. Хотя... При средних 12,5 заказа/машину, наверное, можно упаковать и лучше 80%...

Автор! скинь мне эксельный файл в три столбца вида
номер заказа, объем заказа, вес заказа
- натравлю на свой алгоритм, скину тебе посмотреть (самому мне интересно)

ок, скину. тока... часа через два устроит? а то домой надо ехать, с работы уже гонют... почта в личке?

а идеей алгориттма поделешься? не кодом, просто идеей...

(64) А объемы машин не важны?

(65) дубль ответа отправил тебе на мыло. отвечай на него. да устроит, я тож как раз буду дома часика через два.

(61) А мне таки кажется, что n*m, или у меня уже совсем маразм.

(67) для начала считаем что все машины - одинаковые...

(63) я тоже думаю, что можно бы... но не идет...

(69) но n = 1000 факториал.

(66) рекурсивный алгоритм, обсуждался здесь (NS), делал по нему с вылавливанием парочки ошибок. кое-где подглючивает по мелочи, но мне это некритично, но хочу доточить до ума...

(71) Что не идет? Лучше 80%? Сам же сказал, что снизил недогруз до 15-17%

(72) Блин, да откуда там факториал то?

тут бяка в "суммарном недозаполнении"...
имхается мне бабахаем рекурсию, с доп услвоиями типа "отбор сначала самых крупных", "отбор сначала самых мелких" и "смешанный отбор" - получим псевдооптимальное решение... более чем уверен, что примерно при равных объемах заказов особо точно смысла считать нет - будет все примерно одинаково по критерию "суммарного незаполнения" - если одну машину набъем под 90% то какаие то другие будут поменьше заполнены... а вот если размеры заказов очень сильно варьируются - тут можно и выиграть одну машину...

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

(76) Смотри (44) Автору не нужно псевдооптимальное решение, автору нужно строго доказать, что лучше уже нельзя.

(0) Тебе какой параметр операции оптимизировать надо? В чем выигрыш получить?

(12) > потому что я в этой конторе уже пятый месяц сижу... и с логистами, и с кладовщиками и даже с грузчиками уже море водки выпил...
- ну ты еще водки попей

се проблемы нахрен отпадут.. потому что решать не сможешь... ;-)

(0) Метод Монте-Карло: раскидываем случайно груз по машинам, считаем заполненность, запоминаем. Делаем так 50 000 раз. Выбираем лучший вариант из попавшихся (очень сильно зависит от ГСЧ)

> важно - уменьшить не дозагрузку машины... требуется недозагрузка - не более 10%, сейчас - около 20%
- вряд ли сильно выиграешь. при большом обьеме и куче мелких коробок разных размеров, потеря в объеме (эмпирическая оценка, из-за неоптимальности укладки составляет от 0 до 20% объема) что твои цифры и подтверждают... пакуй/рассчитывай как работали раньше - просто увеличь поправочный коэффициент и все... выиграешь ты одну машину из 80, но потеряешь по времени погрузки, которое увеличиться из-за рекомендуемой раскладки...

(0) Еще можно "генетический алгоритм" прикрутить. Дольше, чем метод Монте-Карло, но и дает лучший результат. Тут главное целевую функцию правильно составить

(82) Нахрена? Полный перебор.

(84) Писатель не читатель? Целевая функция давно определена и проста как табуретка.

эх блин, не удастся оперативно автору помочь... у мну разбиение считается для одинаковых "машин"...

(69) Да, таки маразм. m^n таки. Полный перебор не катит. Хотя, если среди машин есть одинаковые, то вариантов будет меньше.

(85) В порядки быстрее
(86) значит, ознакомиться с высказанным в (84) -- и в добрый путь

З.Ы. это, конечно, если вообще хочется что-то сделать

Просьба автору написать о том на каком решении он все таки остановился.
В свою очередь я предлагаю вот что, нужно оптимизировать загрузку каждой машины по количеству предметов а уже потом по весу. Этот вариант должен дать лучший результат когда коробки "примерно одинаковые".То есть разброс не большой в обьемах коробок.

(90) вес можно пока вообще исключить...

1. Если пофигу на логистику, то разбивай заказы на части.
2. Если логисты и кладовщики откажутся, значит надо еще выпить и вернуться к пункту 1.
3. Если клиенты откажутся, то пусть машины ездят гуськом друг за дружкой и собирают заказ на месте, далее см. пункт 2

(0) Андрей, тема еще актуальна?
Если да, то можно ли как-то получить конкретные данные, на которых можно было бы потестировать.

Зря вы забиваете на логистику. Если будет получаться раскладка оптимальная по загрузки + оптимальная по маршруту, то и экономия по времени будет и по бензину и по машинам.

Тоже влезу
(0) Можно уже расшифровать "машины недозагружены"?
1. По расчетам дожно влезть 15 заказов, а загрузят удалось только 13
2. По расчетам дожно влезть 15 заказов, загрузили 15 заказов, а места еще дофига и больше
-----
Водители наверняка грузят по маршруту, т.е. сначала самые последние заказы, а ближе к разгрузке самые первые по маршруту

(93)+  Послал письмо на Gmail.

(0) не надо изобретать велосипед. Это обычная задача линейного программирования. Идешь в библиотеку, берешь книгу и решаешь