¿Cómo calcular la mejor colocación de cajas?

[nesetru]

Hola amigos.

Un amigo mio me ha pedido si es posible realizar un programa que haga lo siguiente:

Tenemos una superficie, (cuadrada o rectangular) cuyo valor introduciremos como dato, donde queremos colocar de la manera más eficiente un cierto número de cajas con diferentes medidas, entendemos como diferentes medidas la altura, el ancho y su profundidad. Las cajas las podemos poner sobre la superficie original en diferentes alturas.

Su aplicación sería el siguiente, tenemos un palet o un camión donde queremos poner un cierto número de cajas, todas ellas con sus medidas, el programa debería de decirnos la colocación de cada una de las cajas de manera que minimicemos el uso de palets o camiones.

Sé que lo dificil es el algoritmo o manera de combinar todas las cajas y en sus diferentes posiciones para sacar la mejor colocación sobre el palet, pero a ver si alguno de vosotros conoce algo que me permita hacerlo.

Un saludo y gracias. :p

[sanxpue]

De estos son los proyectos que me gustan... de a como va a ser jejejeje
La idea principal

Vt = Volumen total (osease el del transporte)
Vf = Volumen de las Cajas

Pueden haber muchos resultados osease

V1 = Vt-Vf1
V2 = Vt-Vf2
.
.
.
Vn = Vt-Vfn

donde cada Vfx trae como acomodarse y su volumen, Vx es el menor volumen sobrante

que sigue??? :D
Listo...

[roman]

Estimado sanxpue, ¿podrías ser un poco más explícito? Al menos yo no entendí nada de la solución que propones.

// Gracias

[nesetru]

Bufffff, no me ha quedado muy clara la solución que planteas. ¿Podrías explicarte un poco más?

Gracias.

[roman]

Bueno, sanxpue aún no nos satisface la duda pero yo creo que la cuestión es bastante más complicada. Lo que nesetru pregunta tiene que ver, hasta donde entiendo, con lo que se conoce como "packing". Una búsqueda en Google de "packing problems" da varios resultados interesantes que podrían estudiarse. Este (http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE192.HTM) es un ejemplo.

Claro que puedo estar equivocado y todo ser mucho más fácil.

// Saludos

[jachguate]

Pero en el caso de nesetru, tengo entendido que todos los paquetes son del mismo tamaño...

Creo que esto simplifica bastante el problema... sin dejar de tener sus detalles, claro.

[roman]

Pero en el caso de nesetru, tengo entendido que todos los paquetes son del mismo tamaño...

Ah! Yo me quedé con la idea de que "diferentes medidas" se refería a que se trataba de diferentes tamaños de cjas, pero releyendo ahora veo que es posible que sea como dices lo cual ciertamente facilitaría el problema. Esperemos a que nesetru nos aclare.

[maruenda]

vamos a ver.

primero: todos los pales son del mismo tamaño.
en este vamos a poner las cajas de manera que no sobresalga de los limites del pale. si ajustamos las cajas de esta manera, lo que buscamos es que la altura de las cajas apiladas sea la minima posible.

segundo: no puedes ocupar toda la superficie del almacen con los pales, porque necesitas sitio para moverte. tienes que tener en cuenta el espacio necesario para desplazar las cajas,( con algun tipo de maquinaria ) y piensa que esa maquinaria tiene que girar, ir para atras, etc.

entonces tendrias dos problemas, la superficie dedicada realmente al almacenaje, y a partir de ahi, saber que tamaño de pale puedes usar. una vez lo tengas, intentar ajustar la colocacion de las cajas, de manera que se ajusten a la superficie del pale, sin sobresalir.

como te he comentado , esto es de examen. ufffff. :)

[nesetru]

Gracias por vuestra ayuda amigos. Pero el problema original trata sobre cajas de diferentes medidas. Tampoco debemos tener en cuenta el espacio entre palets para movernos.

La aplicación real sería economizar a la hora de comprar palets o alquilar camiones para almacenar y transportar un número finito de cajas.



Saludos.