Оптимальное выполнение заказа

Question

У меня следующая проблема. У пользователя есть корзина с N предметы в нем. Есть количество Q каждого предмета. Далее есть P склады, и у каждого из них есть определенный уровень запасов для каждого товара (который может быть 0). Расстояния между каждым складом и клиентом также известны. Мне нужно найти набор складов, которые могут вместить заказы и удовлетворять следующим ограничениям (упорядоченные по убыванию приоритета):

1. Он должен содержать минимальное количество складов
2. Все склады должны быть как можно ближе к клиенту.

Любые идеи высоко ценятся. Спасибо!

UPD:

Если один склад не может полностью выполнить какую-либо позицию, то он может быть доставлен несколькими разными складами. Например, нам нужно 10 яблок, и у нас есть 2 склада с запасами 7 и 3. Затем яблоки будут предоставлены этими двумя складами (всего 10).

UPD 2 Количество доступных складов составляет около 15. Так что грубая сила здесь не поможет.

Answer 1

Я бы порекомендовал пойти с решением Дэвида Эйзенстата. Если вы хотите больше узнать о теме или вам необходимо самостоятельно реализовать алгоритм для решения целочисленных программ, я могу порекомендовать следующую ссылку:

Глава 9 из лекции MIT по прикладному математическому программированию дает хорошее введение в целочисленное программирование. На третьей странице вы найдете проблему местоположения склада в качестве примера проблемы, решаемой с помощью целочисленного программирования. Обратите внимание, что описанная здесь проблема несколько более общая, чем проблема, которую вы описали в своем вопросе: для вашего случая можно предположить, что склады всегда открыты (y_i = 1), а фиксированные эксплуатационные расходы f_i склада всегда f_i = 0 в вашем случае.

Остальная часть этой главы посвящена деталям целочисленного программирования, а также освещает различные подходы к решению целочисленных программ.

Answer 2

Это разрешимо целочисленным программированием.

Пусть элементы будут проиндексированы i и склады индексируются j, Позволять Qi быть количество товара i в корзине и Sij быть количество товара i на складе j а также Dj быть расстояние от клиента до склада j,

Сначала найдите минимальное количество склада k, Пусть бинарная переменная xj быть 1 если и только если склад j участвует в заказе. k это значение этой программы.

minimize sum over j of xj
subject to
for all i, (sum over j of min(Sij, Qi) * xj) >= Qi
for all j, xj in {0, 1}

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

minimize sum over j of Dj * xj
subject to
for all i, (sum over j of min(Sij, Qi) * xj) >= Qi
(sum over j of xj) <= k
for all j, xj in {0, 1}

Есть много разных библиотек для решения целочисленных программ, некоторые бесплатные / с открытым исходным кодом. Как правило, они принимают программы в формате, похожем, но более ограниченном, чем тот, который я представил здесь. Вы должны будете написать некоторый код самостоятельно, чтобы расширить суммы и универсальные квантификаторы ("для всех").

Answer 3

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

Если у вас есть 10 пунктов на заказ.

У вас есть 9 в наличии

У вас есть 5 в одном месте и 4 в другом.

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

9 оставшихся (выполнимых продуктов) на складе будут опрошены по вашему складскому виртуальному инвентарю для получения наилучших комбинаций.

В нашем случае мы делаем три вещи:

Может ли обслуживающий персонал на складе X легко перенести товар с другого склада? Да нет

Если так, то какие продукты могут быть переданы.

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

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

Затем разделите порядок на два со ссылками на основной порядок следов бумаги.

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

Так что в основном вот то, что вы должны кодировать.

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

Соображения: убедитесь, что основной порядок ссылается на обратный порядок действий и разделяется. Убедитесь, что заказы на разделение и частичное выполнение ссылаются на любые дополнительные заказы на возврат и разделения. Заполните то, что вы можете пометить отправленным. Соберите $$$ на поставленных товарах.

Надеюсь, что это помогает и удачи!!!