5.3.2 Algorithmes de chargement
Le problème de chargement d'objets à deux
dimensions est très proche de plusieurs
problèmes de rangement. On peut détailler deux
problèmes en particulier :
- Le problème de Bin Packing à deux
dimensions ou Two Dimensional Bin Packing Problem (2BPP) : l'objectif
est de ranger un ensemble d'objets rectangulaires dans un nombre minimal de
boites rectangulaires identiques. Les approches exactes pour le 2BPP sont
généralement basées sur des techniques de recherches
arborescentes et permettent de résoudre des instances contenant
jusqu'à une centaine d'objets. Cependant, certaines instances avec
seulement 20 objets restent non résolues. Des algorithmes exacts et des
calculs de bornes inférieures ont été proposés par
Martello et Vigo (1998), Boschetti et Mingozzi (2003a,b) et Pisinger et Sigurd
(2007).
- Le problème de Strip Packing à deux
dimensions ou Two Dimensional Strip Packing Problem (2SP) : l'objectif
est de ranger un ensemble d'objets rectangulaires dans une bande de largeur
définie et de hauteur infinie de façon à minimiser la
hauteur totale occupée par le rangement. Un algorithme exact a
été proposé par Martello et al. (2003) et peut
résoudre des instances contenant jusqu'à 200 objets.
Néanmoins, encore une fois, certaines instances de petites tailles ne
sont pas résolues optimalement.
Chapitre 5. Application au problème de Tournées de
Véhicules avec Contraintes de Chargement
Du point de vue de la complexité algorithmique, le
problème de Tournées de Véhicules avec Contraintes de
Capacités et le problème de Bin Packing à deux dimensions
sont tous les deux NP-difficiles et en pratique se montrent
séparément difficiles à résoudre. De manière
évidente, ces remarques sont également valables pour le
2|RO|LVRP. À notre connaissance, la seule méthode exacte
disponible à ce jour pour le 2|RO|LVRP est l'approche
développée par Iori et al. (2003) et (Iori et
al., 2007).
| 
