Buscando un modelo para representar a este problema, que sospecho que puede ser NP-completo

Question

(he cambiado los detalles de esta cuestión para evitar problemas de NDA. Soy consciente de que si se toma literalmente, hay mejores maneras de ejecutar esta empresa teórica.)

Hay un grupo de almacenes, cada uno de los cuales son capaces de almacenar y distribuir 200 productos diferentes, de un máximo de 1000 productos totales que la empresa A fabrica. Cada almacén es abastecido con productos 200, y asigna las órdenes que son luego al relleno de su acción en la mano.

El reto es que cada almacén debe ser autosuficiente. Habrá un pedido de un número arbitrario de productos (5-10 por lo general), que se asigna a un almacén. El almacén continuación, los paquetes de los productos requeridos para la orden, y los envía juntos. Para cualquier artículo que no está disponible en el almacén, el artículo debe ser entregado de forma individual para el almacén antes de la orden se puede enviar.

Por lo tanto, el problema radica en la determinación de las mejores configuraciones de almacén / producto para que el mayor número posible de órdenes puede ser embalado sin tener que esperar el orden y para los artículos individuales.

Por ejemplo (uso de productos de cada uno representado por una letra, y almacenes capaces de almacenar líneas 5 de productos):

Warehouse 1: [A, B, C, D, E]
Warehouse 2: [A, D, F, G, H]

Order: [A, C, D] -> Warehouse 1
Order: [A, D, H] -> Warehouse 2
Order: [A, B, E, F] -> Warehouse 1 (+1 separately ordered)
Order: [A, D, E, F] -> Warehouse 2 (+1 separately ordered)

El objetivo es utilizar los datos históricos para reducir al mínimo el número de productos pedidos de forma individual en el futuro. Una vez que los almacenes se han creado cierta manera, el software acaba de determinar qué almacén podría manejar un pedido con un mínimo de gastos.

Esto me parece de inmediato como un problema de estilo de aprendizaje de máquina. También parece que una combinación de ciertos problemas NP-completos conocidos, aunque ninguno de ellos parece encajar correctamente.

¿Hay un modelo que representa este tipo de problema?

Answer 1

Si he entendido bien, usted tiene que problemas separados:

• Predecir lo que debe cada almacén antes de la compra
• Obtener el mejor deposito para una orden

Para el primer problema, se lo apunte al Netflix premio : esto era casi el mismo problema, y se han propuesto grandes soluciones. (Mi manual de extracción de datos está en casa y no puedo recordar por palabra clave precisa para Google, sorry.Try "minería de datos de series de tiempo")

En la segunda, esto es un problema para Prolog.

• Establecer un costo de ordenar por separado un elemento
• Establecer un costo, para, idk, proximidad al cliente
• Establecer el coste de ya poseer el producto a 0
• Hacer la regla para obtener un producto: comprarlo si no lo tiene, lo consigue si lo hace
• Hacer la regla para obtener todos los productos: producto foreach, regla anterior
• obtener el costo de esta regla
• preguntar suavemente Prolog para obtener una solución. Si no es lo suficientemente bueno, pida más.

Si no desea utilizar Prolog, hay varias bibliotecas limitaciones que hay. Sólo Google "restricción biblioteca <insert your programming language here>"

Answer 2

La primera parte del problema (que los artículos son frecuentemente ordenados juntos) es a veces conocido como el problema de co-ocurrencia, y es una gran parte de la literatura de minería de datos. (Lo que recuerdo es que el problema está en NP, pero existen muy buenos algoritmos aproximados).

Una vez que tenga los datos de co-ocurrencia que es feliz con, usted sigue siendo la izquierda con la asignación de artículos a los almacenes. Es un poco como el problema de puesta a cubrir, pero no exactamente lo mismo. Este problema es NP-duro.