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

Question

проблема распределения запасов.

У меня проблема с тем, что каждый из известных наборов продуктов с различными скоростями продажи должен быть распределен в одно или несколько фиксированных номеров. Каждый продукт должен быть хотя бы в одном ведре, и ведра не могут делиться продуктом. Все ведра должны быть заполнены, и продукты обычно будут в более чем одном ведре Моя задача состоит в том, чтобы оптимизировать распределение продуктов во всех сегментах, чтобы они максимально увеличивали время до того, как какой-либо продукт будет продан.

Чтобы усложнить ситуацию, каждый тип ведра может содержать различное количество каждого типа продукта. Это не обязательно связано с размером продукта (который не известен), но может быть произвольным. Например,

• Ведро A содержит 10 товаров 1, Ведро B содержит 20 товаров 2, однако
• Ведро A вмещает 5 Продуктов 2, Ведро B вмещает 8 Продуктов 1.

Итак, в качестве исходных данных у нас есть набор продуктов и скорость их продаж, например,

• Товар 1 продается 6 в день
• Товар 2 продается 5 в день
• Товар 3 продается 4 в день
• Товар 4 продается 7 в день

Набор ковшей

• Ведро A
• Ведро B
• Ведро C
• Ведро D
• Ведро E
• Ведро F
• Ведро G

И справочная таблица Product-Bucket для определения емкости каждого контейнера для каждого продукта, например,

• Prod 1 Bucket A = 40;
• Ведро 1 производства B = 45:
• Prod 1 Bucket C = 40;
• ...
• Prod 2 Bucket A = 35;
• ...
• Prod 2 Bucket E = 20;
• ...
• и т.д.

Подходы, которые я пробовал до сих пор, включают

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

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

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

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

Любой c # или псевдокод приветствуются

Answer 1

Я думаю, что эта проблема может быть завершена NP, и вам, возможно, придется прибегнуть к обычным методам поиска GA / SA / Breadth / Depth и / или согласиться на неоптимальные решения в зависимости от того, сколько ведер / продуктов у вас есть.

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

(исключительно псевдокод Python. Это не работает без изменений !!)

index = {} # a hash table containing hash tables of buckets 

for bucket in buckets:
    for product in products:
        capacity = find_capacity(bucket,product)
        sell_rate = 1/sales_velocity[product] #assuming sales_velocity are not fractions

        longevity = capacity * sell_rate

        index[bucket][product] = longevity

for bucket in buckets:
    product = find_maximum_longevity(index, bucket)
    print bucket, product

Answer 2

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

Вы также можете указать задачу в виде последовательности уравнений и вызвать пакет целочисленного программирования (IP), например, http://www.coin -or.org / , чтобы найти оптимальное или почти оптимальное решение.

Answer 3

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

каждый шаг алгоритма SA заменяет текущее решение случайным «соседнее» решение, выбранное с вероятность того, что зависит от разница между соответствующими Значения функций и на глобальном параметр Т (называемый температурой), который постепенно уменьшается в течение процесс