Algoritmi per il confezionamento di contenitori tridimensionali

Question

Sono di fronte a un problema di imballaggio del bidone tridimensionale e sto attualmente conducendo alcune ricerche preliminari su quali algoritmi/euristiche stanno attualmente ottenendo i migliori risultati. Poiché il problema è NP difficile, non mi aspetto di trovare la soluzione ottimale in ogni caso, ma mi chiedevo:

1) quali sono i migliori risolutori esatti? Branch e Bound? Quali sono le dimensioni delle istanze del problema che posso aspettarmi di risolvere con risorse di calcolo ragionevoli?
2) quali sono i migliori risolutori euristici?
3) Quali soluzioni pronte all'uso esistono per condurre alcuni esperimenti?

Answer 1

Da wikipedia:

Sebbene these simple strategies sono spesso abbastanza buona, sono stati dimostrati algoritmi di approssimazione efficienti in grado di risolvere il problema bin packing all'interno di qualsiasi percentuale fissa la soluzione ottimale per sufficientemente grandi ingressi

Ecco le due fonti che danno per questo:

• Approximation Algorithms
• Bin packing can be solved within 1 + ε in linear time

Answer 2

Per quanto riguarda le soluzioni disponibili, controllare fuori MAXLOADPRO per caricare i camion. Potrebbe essere in grado di essere configurato per caricare qualsiasi volume rettangolare, ma non l'ho ancora provato. In generale, i problemi del bin-packing 3d hanno l'ulteriore complicazione che gli oggetti possono essere ruotati in posizioni diverse, quindi per qualsiasi oggetto con una determinata lunghezza, larghezza e altezza, devi effettivamente creare tre variabili che rappresentano ciascuna posizione, ma ne usi solo una in la soluzione.

In generale, le formulazioni MIP standalone (o branch e bound) non funzionano bene per il problema 2d o 3d ma la programmazione dei vincoli ha riscosso un certo successo producendo soluzioni esatte per il problema 2d. Dai un'occhiata a questo abstract. Senza guardare il documento, mi piace l'approccio di scomposizione per il problema in cui si sta cercando di ridurre al minimo il numero di bin di dimensioni uguali. Non ho visto tanti risultati per il problema 3d, ma facci sapere se trovi quelli che sono implementabili.

Buona fortuna!

Answer 3

È questione è simile a: 3d bin packing algorithm

Anche se, perché si dis-consentire la rotazione, si possono ottenere buoni risultati. Suggerisco di guardare più verso una soluzione FIRST-FIT-DECREASING.

Answer 4

Miglior risolutore esatto: utilizzare dynamic programming.

variabili

Stato:

1. elementi che si hanno confezionato e scartati.
2. Spazio riempito nel contenitore.

Se il contenitore è una griglia parallelepipeda e gli elementi si "adattano" in celle esatte della griglia, è possibile utilizzare una matrice tridimensionale per rappresentare la variabile di stato 2.Altrimenti, dovrai usare strutture dati più complesse.

migliori solutori euristici

io non lo so. Forse Variable Neighborhood Search. Ci sono alcune somiglianze tra il tuo problema e il problema di costruzione dell'orario (su cui sto lavorando), quindi la stessa euristica potrebbe essere buona per entrambi.

off-the-shelf soluzioni per condurre esperimenti

Mi dispiace, io non hanno nemmeno un indizio.

Answer 5

Ho scritto un program che verifica tre diversi algoritmi. Anche questa è una buona fonte di informazioni: A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing. È per bidone bidimensionale rettangolo, ma è sempre possibile trasformarlo in 3D.

Answer 6

3dbinpacking è una soluzione commerciale (non un algoritmo) che espone un'API da consumare con una bella visualizzazione. Offre:

• bin singolo imballaggio
• Multi bin imballaggio
• Trova terza dimensione
• trovare un bidone dimensioni