Estoy escribiendo un programa para resolver un problema de optimización combinatoria. He estado trabajando en un algoritmo que obtiene los resultados deseados, pero estoy teniendo dificultades para obtener el algoritmo para realizar el bien.
El dominio del problema es el suministro de equipos médicos de la industria, y el requisito básico es el de asignar elementos a los paquetes de modo que el precio del alquiler se reduce al mínimo. Los equipos se pueden alquilar de forma individual, pero también hay paquetes definidos que contienen una combinación de equipos, y el precio del alquiler de los paquetes es menor que el total de la carga de alquiler de los equipos individuales. Mientras que la generación de la factura, tengo que asignar los elementos de los paquetes que sea posible, de tal manera que el total de la cuota de alquiler se reduce al mínimo.
En mi modelo, los paquetes son definidos de la siguiente manera
- Cada paquete contiene 1..N los Grupos G1, G2, G3,.. GN.
- Cada Grupo debe tener un mínimo de elementos X (donde X >= 0), y en la mayoría de las Y los artículos ( Y > 0, Y >= X)
- Cada Grupo puede contener 1..n Tipos de elementos de IT1, IT2, ... Nti
- Cada Tipo de Elemento que debe incluirse al menos Una veces (A >= 0) en el grupo, y en la mayoría de los B veces (B > 0, B >= A)
Un ejemplo de paquetes podrían ser de la siguiente manera;
Bed and Wheelchair package
Group: Bed (total item min 1, max 1)
Bed 6 feet (min 0, max 1)
Bed 6.5 feet (min 0, max 1)
Group: Wheelchair (total item min 1, max 1)
Manual wheelchair (min 0, max 1)
Motorized wheelchair (min 0, max 1)
Group: Accessories (min 0, max 3)
Air Mattress (min 0, max 1)
Air blower (min 0, max 1)
Pillows (min 0, max 2)
Habría varios paquetes disponibles similar a la anterior. Un determinado Tipo de Elemento puede aparecer sólo una vez en un paquete. Sin embargo, los paquetes diferentes pueden tener el mismo Tipo de Elemento.
Supuestos O Requisitos:
- Cada paquete tiene un precio de alquiler asociados con ella, como lo hace cada Tipo de Elemento.
- A la hora de alquilar un paquete, sólo el precio del paquete es una carga, no los elementos que hay dentro del paquete. Un alquiler puede estar compuesta de paquetes y los elementos individuales.
- Cuando el alquiler de X número de elementos de diferentes tipos, los elementos deben ser asignados a los paquetes donde sea posible, de modo que el total del alquiler se reduce al mínimo.
- Puede haber varias maneras de formar los paquetes, y los que tienen el más bajo de alquiler debe ser seleccionado.
- Puede haber varias combinaciones que producen el menor alquiler de. Todos ellos son necesarios en el resultado. (Yo podría ser capaz de trabajar alrededor de este requisito si es absolutamente necesario).
- Necesito el apoyo de alquiler de hasta 25 elementos. El número de paquetes disponibles pueden variar de 10 a 20.
- Una complejidad adicional que necesito agregar más tarde es para apoyar el concepto de paquetes de contenidos en el interior de los paquetes.
- Que tengo que hacer esto por múltiples alquiler de facturas en un modo por lotes, lo que hace que la el rendimiento del algoritmo de manera crítica.
Mi enfoque hasta ahora:
- Para cada elemento, encontrar una lista de los paquetes que se puede pertenecer a basado en el tipo de elemento.
- Crear un grafo donde cada nodo es un elemento de un paquete de asignación. Organizar el gráfico de modo que los nodos en cada nivel de hoja representan los posibles paquete de asignaciones de un solo elemento.
- Hacer una profundidad de primer recorrido de la gráfica, la poda, el subárbol y retroceso, cuando es obvio que el subárbol no puede resultar en una solución óptima. Yo soy la poda de los subárbol cuando cualquiera de las siguientes es falsa:
- Cuando el resto de los elementos están incluidos, puede satisfacer las cantidades mínimas requeridas para cada paquete en la sucursal hasta el momento ?
- Es el precio total de los paquetes incluidos así que mucho menos que el total del precio individual de todos los elementos de línea ?
El enfoque es acabar con una cara de cálculo. En una prueba con 24 ítems y un pequeño número de paquetes, recorrido de 2,5 millones de nodos y tomó más de un minuto para que los resultados vienen de vuelta. Idealmente, me gustaría que los resultados se devuelven en segundos.
Yo te aprecio mucho los punteros a un algoritmo eficiente que puede ser utilizado para este problema.
EDIT: estoy agregando un ejemplo de un proyecto de ley y el paquete.
Bed and Accessories package
Group: Bed (total item min 1, max 1)
Bed (B) (min 1, max 1)
Group: Accessories (total item min 0, max 2)
Mattress (M) (min 0, max 1)
Pillows (P) (min 1, max 2)
Total cantidades en la factura: B: 2, M: 3, P: 5
Los paquetes se pueden formar de diferentes maneras:
2 packages, remaining items billed individually
(1B, 1M, 1P), (1B, 2P)
(1B, 2P), (1B, 2P)
(1B), (1B)
etc
1 package, remaining items billed individually
(1B, 1P),
(1B, 2P),
(1B, 1M, 1P),
(1B),
etc
Con IP, la función a ser minimizado puede ser definida como
aD + bB + cM + dP
where D is the quantity of discount package
B, M and P are the quantities of the items not billed as packages,
and a, b, c, d are the rental costs for each.
Algunas de las limitaciones:
B <= 2
M <= 3
P <= 5
D + B = 2
Sin embargo, para el grupo Accesorios, que va a ser complejo. Yo no tengo
D + M = 3,
como D puede ser formado sin ningún tipo de colchón, como el [(1B, 2P), (1B, 2P)] combinación. En esta combinación, D = 2 y M = 3, ya que todos los estados miembros están siendo facturados de forma individual, y hay 2 paquetes de descuento. Yo estaba pensando en introducir algunas variables adicionales para representar lo que las cantidades son recogidos para cada grupo, pero creo que va a resultar en una restricción cuadrática.
