?

Log in

No account? Create an account

[icon] А рюкзак вам не уложить? - Lorem Ipsum igitur, juvenes dum sumus
View:Свежие записи.
View:Архив.
View:Друзья.
View:Личная информация.
View:Website (Мой сайт).

Tags:, ,
Security:
Subject:А рюкзак вам не уложить?
Time:11:22 pm
Занимался сегодня (и последние две недели) по работе оптимизацией размещения грузов в трейлерах. Есть у нас один клиент - перевозит трансформаторы в больших количествах. Каждая модель трансформатора грузится на отдельный поддон - паллету, эти паллеты по определенным правилам размещаются в кузове грузовика - в зависимости от размера (20+ вариантов размеров) их помещается N штук в ряд, и таких рядов, опять же, в зависимости от размера поддона может быть M штук. Плюс все возможные комбинации. Небольшие проблемы начинаются, когда типоразмеров становится много, и накладываются дополнительные ограничения типа "все экземпляры одной модели трансформатора должны ехать вместе", и "на один ряд можно ставить поддоны с разными моделями трансформаторов только при условии, что они направляются к одному и тому же клиенту". Становится немного сложнее, но в целом - банальная дискретная оптимизация, и всё решается.

Вот только... Сначала я решаю задачу оценки суммарного объема, чтобы понять, сколько грузовиков нужно. Для этого размещаю грузы в "бесконечном грузовике", применяя к размещению все те же правила, которые будут применены к плотной упаковке в реальные грузовики. Цель - получить оценку количества требуемых грузовиков снизу. На тестовом массиве данных получаю результат 14877 кубических футов. Лимит на один грузовик - 4000 куб. футов, поэтому распихиваю по четырем грузовикам. По результатам этого размещения суммарный объем получается 14675 кубических футов. То есть МЕНЬШЕ, чем в оптимальном размещении в бесконечном кузове. Подозреваю, что дело в разрывности функции зависимости количества паллет от размеров, но, блин, поймать глюк пока не получается...

А какие у вас есть интересные проблемы на работе?
comments: Оставить комментарий Previous Entry Поделиться Next Entry


spamsink
Link:(Link)
Time:2013-02-07 05:34 am
Погоди-ка. Ты не объем convex hull считаешь, часом? Если его, то ничего удивительного, что один большой больше, чем два маленьких.
(Ответить) (Thread)


torrio
Link:(Link)
Time:2013-02-07 05:47 am
Нет, я скорее играю в тетрис, и весь набор фигур у меня изначально под рукой. Вроде как очевидно, что в одном большом стакане их можно разместить более оптимально, чем в четырех маленьких. Или неочевидно?:) (сам задумался)
(Ответить) (Parent) (Thread)


mehas
Link:(Link)
Time:2013-02-07 06:57 am
ыыы, моя бакалаврская работа, оказывает это кому-то все-таки нужно
(Ответить) (Thread)


torrio
Link:(Link)
Time:2013-02-07 08:31 pm
Конечно нужно! Это ж не какие-то абстрактные алгоритмы на графах, которые никогда в жизни не пригодятся:)
(Ответить) (Parent) (Thread)


vasbur
Link:(Link)
Time:2013-02-07 07:23 am
А еще один маленький трансформаторик можно разместить в кабине водителя :)
Это тоже нужно учитывать иногда.

Edited at 2013-02-07 07:23 (UTC)
(Ответить) (Thread)


torrio
Link:(Link)
Time:2013-02-07 08:32 pm
Да, всё жду когда клиенты с таким пожеланием обратятся. Уже думаю, куда бы их послать:)
(Ответить) (Parent) (Thread)


vasbur
Link:(Link)
Time:2013-02-08 02:41 am
Когда я занимался транспортной оптимизацией - все жесткие ограничения постепенно становились нежесткими.
Так что готовься вводить штрафные функции и т.п.
(Ответить) (Parent) (Thread)


khazzar
Link:(Link)
Time:2013-02-07 07:28 am
дано: расписание доступности чего-то. ресурса какого-то. задается администратором в виде набора правил. в данный момент правила есть 4-х типов:
weekly - ресурс доступен в день недели X в промежуток времени от t1 до t2
monthly - ресурс доступен в день месяца Y в промежуток времени от t1 до t2
eventually - в конкретную дату Z в промежуток времени от t1 до t2
periodically - начиная с даты U... например, 3 дня через 4, в промежуток времени от t1 до t2
правило может быть разрешающее (доступен) или запрещающее (не доступен)
правила приоретизируются

задача: все было хорошо, пока расписание отвечало на вопрос "доступен ли ресурс в момент времени T". а теперь потребовалось просто понять, когда будет доступен ресурс, то есть составить простое линейной расписание доступности (сюрприз!).
(Ответить) (Thread)


torrio
Link:(Link)
Time:2013-02-07 08:33 pm
Нннууу... Пока что задача не выглядит сложной:) ;-)
(Ответить) (Parent) (Thread)


khazzar
Link:(Link)
Time:2013-02-08 11:57 am
ну ок, у тебя длиннее
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2013-02-08 02:38 pm
Да нет, у меня-то еще проще:) Тьфу, короче.
(Ответить) (Parent) (Thread)


khazzar
Link:(Link)
Time:2013-02-08 11:58 am
я как-то не подумал, что мы мереемся длиной. ну ок.
(Ответить) (Parent) (Thread)


amironenko
Link:(Link)
Time:2013-02-07 01:22 pm
А почему ответ в этой задаче в кубических футах, а не в погонных метрах длины кузова?
(Ответить) (Thread)


torrio
Link:(Link)
Time:2013-02-07 08:35 pm
Потому что данных о реальной длине кузова и её связи с вместительностью нет:) Знаю только, что объем кузова трейлера типа FLAT 48' составляет 4000 кубических футов, а, скажем, у VAN 53' доступный объем всего 3800 к.ф. И из этих исходных данных всё расчитываю:)

Ну и, какие могут метры?! Это ж США:)
(Ответить) (Parent) (Thread)


amironenko
Link:(Link)
Time:2013-02-08 10:55 am
смущает не футы/метры, а несовпадение размерностей (объемное/линейное)
(Ответить) (Parent) (Thread)


anatolle
Link:(Link)
Time:2013-02-07 02:49 pm
Подушек не хватает ;)
(Ответить) (Thread)


torrio
Link:(Link)
Time:2013-02-07 08:36 pm
И как думаешь решать?
(Ответить) (Parent) (Thread)


anatolle
Link:(Link)
Time:2013-02-08 01:47 am
Работать интенсивнее :)
(Ответить) (Parent) (Thread)


anatolle
Link:(Link)
Time:2013-02-08 01:47 am
Брать сон на дом :)
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2013-02-08 01:56 am
Спи быстрее! Твоя подушка нужна другому!
(Ответить) (Parent) (Thread)

[icon] А рюкзак вам не уложить? - Lorem Ipsum igitur, juvenes dum sumus
View:Свежие записи.
View:Архив.
View:Друзья.
View:Личная информация.
View:Website (Мой сайт).