Выполнение оптимального заказа

Question

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

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

Любые идеи приветствуются. Благодаря!

UPD:

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

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

Answer 1

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

Chapter 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 оставшихся (выполненных изделий) на складе будут запрашиваться против вашего виртуального инвентаря складов для наилучших комбинаций.

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

Может ли персонал выполнения на передаче Х склада в пункте другого склада легко? Да/Нет

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

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

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

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

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

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

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

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

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