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

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

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

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

UPD:

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

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

Ответ 1

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

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

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

Ответ 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}

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

Ответ 3

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

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

У вас есть 9 на складе

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

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

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

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

Легко ли может выполнить сотрудник по комплектованию на складе X в магазине с другого склада? Да/Нет

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

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

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

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

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

Итак, в основном, вот что вам нужно для кода.

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

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

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