5.9 Résultats expérimentaux
Nous présentons dans cette section les instances que
nous avons utilisées pour me-surer les performances et nous comparons
nos résultats avec plusieurs algorithmes de la littérature.
5.9.1 Paramètres retenus
Dans les méthodes de résolution, nous avons
fixé une limite de temps à 3600 secondes. Lorsque cette limite de
temps est atteinte, la résolution est arrêtée et la
meilleure solution entière est renvoyée. La taille de la liste
des chemins partiels (définie dans la section 5.8.1 a été
limitée à 500. Le nombre de bons voisins pour chaque sommet dans
la résolution du problème esclave (définie dans la section
5.8.1 est fixé à n/2 où n est le nombre
de clients. Lorsque 95% du temps alloué a été
utilisé par la résolution, l'aspect « Pricing» est
supprimé. Aucune nouvelle colonne n'est alors
générée.
L'heuristique retenue pour la génération de
routes réalisables (présentée à la section 5.7.2)
est l'heuristique Improved Bottom Left avec un tri des objets par
ordre décroissant de largeur pour les objets appartenant à un
même client. Cette heuristique est celle qui a donné les meilleurs
résultats parmi les heuristiques présentées. Cependant,
l'analyse des résultats expérimentaux montrent que l'heuristique
choisie n'est pas de qualité suffisante pour obtenir de bons
résultats.
Tous les paramètres ont été
sélectionnés par des expériences préliminaires.
5.9.2 Classes d'instances
Afin de tester les performances de notre algorithme, nous
avons utilisé un ensemble de 180 instances du problème
2|RO|L-VRP, introduites par Iori et al. (2007) et Gendreau et al.
(2008). Ces instances proviennent de 36 instances du problème de
Capacited Vehicle Routing Problem, décrites par Toth et Vigo (2002), en
caractérisant la demande des clients comme un ensemble d'objets de forme
rectangulaire à deux dimensions auxquels est associé un poids.
À partir des instances du CVRP, 5 classes d'instances ont
été introduites par Iori et al. (2007).
Chapitre 5. Application au problème de Tournées de
Véhicules avec Contraintes de Chargement
Classe 1 On associe à chaque client un
seul objet de taille nulle. Ainsi, les problèmes de la classe 1 sont des
problèmes classiques de CVRP, puisqu'il n'y a pas de contraintes de
chargement (à part les contraintes de capacité). Ces instances
permettent de mesurer l'efficacité des algorithmes en ce qui concerne
les aspects de tournées.
Classe 2 - 5 On associe à chaque
client i un ensemble de mi objets. mi est
distribué uniformément dans un intervalle donné. Chaque
objet est classé parmi une des trois catégories de formes
(verticale, homogène, ou horizontale) de manière
aléatoire, avec la même probabilité pour chaque
catégorie de forme. Les dimensions de chaque objet sont
uniformément distribuées dans un intervalle,
déterminé par la catégorie de la forme de l'objet. Le
nombre d'objets mi et les intervalles des dimensions sont fournis dans
le tableau 5.2. La hauteur et la largeur de la surface de chargement sont
égales respectivement à 40 et 20. Les coûts des arcs sont
égaux aux distances euclidiennes entre les paires de noeuds. Le tableau
5.3 résume les caractéristiques des 36 instances pour les classes
2 à 5. Pour chacune des 36 instances du CVRP, 5 instances sont
créées selon les 5 classes présentées ci-desssus.
On obtient alors un total de 180 instances. Afin d'assurer la
réalisabilité des instances, la taille de la flotte de
véhicules vh est déterminée par une heuristique
de rangement.
|
Classe mi
|
Verticale
Hauteur Largeur
|
Homogène
Hauteur Largeur
|
Horizontale Hauteur Largeur
|
|
2
|
[1,
|
2]
|
[0.4H,
|
0.9H][0.1W,
|
0.2W]
|
[0.2H,
|
0.5H][0.2W,
|
0.5W]
|
[0.1H,
|
0.2H][0.4W,
|
0.9W]
|
|
3
|
[1,
|
3]
|
[0.3H,
|
0.8H][0.1W,
|
0.2W]
|
[0.2H,
|
0.4H][0.2W,
|
0.4W]
|
[0.1H,
|
0.2H][0.3W,
|
0.8W]
|
|
4
|
[1,
|
4]
|
[0.2H,
|
0.7H][0.1W,
|
0.2W]
|
[0.1H,
|
0.4H][0.1W,
|
0.4W]
|
[0.1H,
|
0.2H][0.2W,
|
0.7W]
|
|
5
|
[1,
|
5]
|
[0.1H,
|
0.6H][0.1W,
|
0.2W]
|
[0.1H,
|
0.3H][0.1W,
|
0.3W]
|
[0.1H,
|
0.2H][0.1W,
|
0.6W]
|
TABLE 5.2 - Caractéristiques
des classes d'instances
| 
