Option projet informatique 2006-2008 : chargement de camions (container packing)
Enonçé et consignes
(pdf)
Vous respecterez la syntaxe des fichiers de données
(exemple) :
Chaque ligne contient les dimensions d'un parallélépipède (profondeur, largeur, hauteur).
La première ligne correspond aux dimensions du contenant (camion ou container).
Les autres lignes décrivent la suite de colis disponibles, que l'on doit mettre dans le container.
Visualisation des solutions
Visualisateur par tranches visu2d-Linux
Visualisateur en trois dimensions
vise-3D
(c'est lent !).
Programme de génération problèmes (linux only) :
pack-gen
Notes.
On tente de remplir une tranche en fixant son epaisseur.
Pour affiner le calcul on essaie avec plusieurs epaisseurs differentes (k : c'est un paramètre du programme), et on gardera la "meilleure", sans doute celle qui présente le meilleur taux de remplissage.
La sélection des k epaisseurs se fait à partir des dimensions des colis libres : on peut par exemple choisir celles qui apparaissent le plus souvent tout en s'arrangeant pour qu'il y en ait qui soient plutot grandes afin de placer rapidement les colis qui vont poser des problèome (on peut aussi y mettre des petites largeurs,...).