Имеем сеть складов. Пусть каждый склад представлен в виде вектора
StockX, X1,X2,X3,... XN
где StockX — это идентификатор склада, X1 — остаток товара X1 на конец дня.
В конце дня приходит понимание сколько какого товара должно оказаться на каждом складе. Исходя из этого понимания мы знаем что:
1. Товара X1 избыток (лишних 5 единиц) в Stock1
2. Товара X1 избыток (лишних 15 единиц) в Stock2
3. На Stock3 надо отправить 3 единицы X1
4. На Stock4 надо отправить 7 единиц X1
и т.д.
В конечном итоге хотелось бы сделать пересылку товаров между складами за минимальное количество посылок.
В какую сторону копать? В идеале стоимость пересылки между разными складами различная и конечная цель минимизировать стоимость все пересылок.
V>В какую сторону копать? В идеале стоимость пересылки между разными складами различная и конечная цель минимизировать стоимость все пересылок.
Что-то не договариваешь. Определи потери на складах от недостач по позициям, отнесенные к единице товара. Пока минимум же ясно виден сразу — ничего никому не посылать -> стоимость пересылки 0.
А так по недостаткам и избыткам формируй требуемые посылки от всех ко всем. Что бы ты ни делал, сложность будет порядка O(N^2 * L). L — число позиций товаров, N — количество складов, т.е. вполне себе реализуемо должно быть. При распределении избытков по конкретным складам с недостачами учитывай стоимость пересылки и потери от недостач.
Здравствуйте, andyp, Вы писали:
A>Что-то не договариваешь. Определи потери на складах от недостач по позициям, отнесенные к единице товара.
Да, пытался формализировать. Речь идет не о потерях. Есть сеть физических магазинов обуви. И есть онлайн магазин. Клиент покупает "Красные Кеды Размер 43" и ставит галочку "заберу послезавтра в ближайшем магазине". Таким образом возникает необходимость наличия "Красные Кеды Размер 43" в ближайшем магазине.
Сам факт того, что будет инициирована посылка из магазин1 в магазин2 уже стоит денег. Таким образом иногда выгодно делать пересылку методом замещения. Например мы видим что пересылка некоторых товаров из М1 в М2 уже точно есть, её не избежать. Переслыка из М2 в М3 тоже неизбежна. Но есть некая позиция которая в избытке в М1 и в недостатке в М3. А в М2 её как раз столько сколько нужно. То вместо того чтобы формировать еще одну пересылку М1-М3 мы перешлем этот товар из М2 в М3 а образовавшийся недостаток в М2 закроем в посылке из М1 в М2. Таким образом у нас по прежнему всего то 2 послыки вместо трех.
Загвоздка заключается в нахождении всех возможных комбинаций. На больших наборах данных занимает часы.
Составить оценочную функцию для набора посылок и вычислить минимум уже дело механики.
Здравствуйте, Vladimir256, Вы писали:
V>Загвоздка заключается в нахождении всех возможных комбинаций. На больших наборах данных занимает часы.
Ну имхо тут уже факториальная сложность от числа точек, между которыми перемещаешь товары — просматриваешь все цепочки из М магазинов, ведущие к заданному — уже M! перестановок, включающих и более короткие маршруты. Можно ограничиться рассматриванием 2-3 скачков максимум для перемещения каждой позиции. Может, есть какой способ построить некий начальный вариант пересылок и улучшать его итеративно, то тут я
Здравствуйте, Vladimir256, Вы писали:
V>Имеем сеть складов. Пусть каждый склад представлен в виде вектора V>StockX, X1,X2,X3,... XN V>где StockX — это идентификатор склада, X1 — остаток товара X1 на конец дня.
V>В конце дня приходит понимание сколько какого товара должно оказаться на каждом складе. Исходя из этого понимания мы знаем что: V>1. Товара X1 избыток (лишних 5 единиц) в Stock1 V>2. Товара X1 избыток (лишних 15 единиц) в Stock2 V>3. На Stock3 надо отправить 3 единицы X1 V>4. На Stock4 надо отправить 7 единиц X1 V>и т.д.
V>В конечном итоге хотелось бы сделать пересылку товаров между складами за минимальное количество посылок. V>В какую сторону копать? В идеале стоимость пересылки между разными складами различная и конечная цель минимизировать стоимость все пересылок.
