Techniques hybrides de recherche exacte et approchée: application à des problèmes de transport

5.9.3 Analyses des résultats

Les algorithmes présentés ont été codés en C++ et exécutés sur un processeur AMD X2 3800+ cadencé à 2 Ghz avec 1 Go de mémoire vive. Les 17 premières séries d'instances contiennent jusqu'à 40 clients et 127 objets. Chaque série contient 5 instances. Ces instances ont été résolues de manière exacte par une méthode de séparation et génération de coupe (Iori et al., 2007). Par rapport aux instances originales du CVRP, les arcs sont arrondis à la prochaine valeur entière. Dans la plupart des cas, les solutions optimales sont connues.

Le tableau 5.4 présente les résultats agrégés par série d'instances obtenus sur les 85 instances de taille moyenne. Nos résultats (HBP) sont comparés avec la méthode Branch & Cut proposée par Iori et al. (2007), la recherche Tabou proposée par Gendreau et al. (2008) et l'algorithme d'optimisation par Colonie de Fourmis de Fuellerer et al. (2008).

Inst	client	Class 2 obj. vh r%			Class 3 obj. vh r%			Class 4 obj. vh		r%	Class 5 obj. vh r%
1	15	24	3	78	31	3	82	37	4	70	45	4	61
2	15	25	5	52	31	5	59	40	5	53	48	5	39
3	20	29	5	68	46	5	77	44	5	62	49	5	54
4	20	32	6	58	43	6	58	50	6	63	62	6	47
5	21	31	4	72	37	4	75	41	4	76	57	5	53
6	21	33	6	54	40	6	63	57	6	72	56	6	46
7	22	32	5	71	41	5	66	51	5	67	55	6	49
8	22	29	5	63	42	5	71	48	5	68	52	6	38
9	25	40	8	57	61	8	61	63	8	60	91	8	53
10	29	43	6	74	49	6	66	72	7	73	86	7	63
11	29	43	6	77	62	7	74	74	7	83	91	7	63
12	30	50	9	62	56	9	52	82	9	66	101	9	58
13	32	44	7	69	56	7	68	78	7	77	102	8	59
14	32	47	7	65	57	7	65	65	7	61	87	8	49
15	32	48	6	76	59	6	84	84	8	72	114	8	72
16	35	56	11	55	74	11	57	93	11	64	114	11	49
17	40	60	14	46	73	14	42	96	14	51	127	14	40
18	44	66	9	72	87	10	75	112	10	77	122	10	58
19	50	82	11	77	103	11	83	134	12	79	157	12	61
20	71	104	14	84	151	15	83	178	16	81	226	16	69
21	75	114	14	84	164	17	82	168	17	70	202	17	61
22	75	112	15	82	154	16	81	198	17	82	236	17	66
23	75	112	14	86	155	16	83	179	16	83	225	16	72
24	75	124	17	81	152	17	77	195	17	82	215	17	66
25	100	157	21	83	212	21	85	254	22	83	311	22	65
26	100	147	19	84	198	20	82	247	20	87	310	20	75
27	100	152	19	84	211	22	82	245	22	78	320	22	71
28	120	183	23	83	242	25	83	299	25	84	384	25	72
29	134	197	24	85	262	26	83	342	28	85	422	28	74
30	150	225	29	83	298	30	87	366	30	86	433	30	70
31	199	307	38	84	402	40	85	513	42	86	602	42	70
32	199	299	38	84	404	39	85	497	39	86	589	39	73
33	199	301	37	85	407	41	84	499	41	87	577	41	71
34	240	370	46	85	490	49	86	604	50	86	720	50	72
35	252	367	45	85	507	50	85	634	50	90	762	50	74
36	255	387	47	86	511	51	86	606	51	83	786	51	74

TABLE 5.3 - Caractéristiques des classes d'instances

Les en-têtes sont les suivants :

- I : numéro de l'instance,

- n : nombre de clients,

- Branch & Cut : valeur des solutions (z) et temps d'exécution en secondes (CPU),

Chapitre 5. Application au problème de Tournées de Véhicules avec Contraintes de Chargement

- Tabu Search : valeur des solutions (z), temps d'exécution en secondes (CPU) et différence avec les solutions proposées par Iori et al. (2007),

- ACO : valeur moyenne des solutions (z) sur 5 essais, temps d'exécution en se-

condes (CPU) et différence avec les solutions proposées par Iori et al. (2007),

- HBP : valeur des solutions (z), temps d'exécution en secondes (CPU) et différence

avec les solutions proposées par Iori et al. (2007).

La lecture des résultats nous permet de dire que notre méthode semble intéressante. Elle est en moyenne moins efficace que la méthode ACO proposée par Fuellerer et al. (2008), mais permet d'obtenir de bons résultats en des temps d'exécutions raisonnables. En limitant le temps à une heure (limite de temps qui n'est jamais atteinte pour ces instances), elle permet d'améliorer certaines instances non résolues à l'optimum dans la limite de temps de 24 heures par la méthode de Branch & Bound de Iori et al. (2007) (ce qui explique que dans certains cas le pourcentage de différence avec les solutions optimales soit négatif). Les temps d'exécution sont similaires au temps des autres méthodes. Néanmoins, il semble que les heuristiques de chargement utilisées ne permettent pas de retrouver toutes les routes réalisables relativement aux contraintes de chargement, ce qui explique des résultats inférieurs aux méthodes les plus performantes.

I	n	Branch & Cut z CPU		Tabu search z CPU		Gap	ACO z CPU		gap	z	HBP CPU	gap
1	15	281	29.9	281.4	7.6	0.14	286.4	8.9	1.92	285	12.1	1.42
2	15	336.6	14.7	337.2	3.9	0.18	337.4	0.7	0.24	337.8	4.5	0.36
3	20	375.4	25.4	377.6	18	0.59	376.6	7	0.32	378.2	15.6	0.75
4	20	430	17	433.8	14	0.88	431	4.1	0.23	433.6	15.1	0.84
5	21	377.2	597.8	387	28.8	2.6	378	19.5	0.21	385	27.3	2.07
6	21	490.4	67.4	494.6	23.1	0.86	491.7	5.6	0.27	495.2	22.4	0.98
7	22	687.2	676.3	699.8	39.2	1.83	690	11.9	0.41	698.6	31.5	1.66
8	22	705.8	261.6	717.4	45	1.64	713.1	16.6	1.03	718.6	38.7	1.81
9	25	614.2	469.9	616.6	38.2	0.39	616	8.3	0.29	616.6	32.8	0.39
10	29	676	51791.2	684	150.8	1.18	666.9	48.6	-1.35	678	72.9	0.3
11	29	725.6	69120.4	718.4	175.7	-0.99	691.7	134	-4.67	724.2	183.5	-0.19
12	30	609.4	86400.4	612	87.3	0.43	602.3	12.9	-1.17	610.4	74.2	0.16
13	32	2713.6	58268	2588.4	296.2	-4.61	2540.7	59	-6.37	2653.6	259.4	-2.21
14	32	1233.4	74228.8	1157.8	343.3	-6.13	1146	131.9	-7.09	1181.4	354.8	-4.22
15	32	1252.6	69124.2	1191.6	308	-4.87	1182.4	235.2	-5.6	1201.6	291.8	-4.07
16	35	683.8	10098.1	686.4	161.8	0.38	684.9	11.1	0.16	687.4	212.5	0.53
17	40	854.6	86400.3	844.4	234.7	-1.19	846.2	9.4	-0.98	848.8	176.3	-0.68
Moyenne		767.46	29858.32	754.61	116.21	-0.39	745.96	42.63	-1.3	760.82	107.38	-0.01

TABLE 5.4 - Résultats expérimentaux : qualité des solutions sur instances moyennes

Le tableau 5.5 présente les résultats agrégés par série d'instances obtenus sur les 180 instances de grande taille. Dans ces instances, les distances ne sont pas arrondies à la prochaine valeur entière. Les en-têtes des colonnes sont les mêmes que les en-têtes

du tableau précédent, à la différence que la qualité des solutions est calculée relativement aux solutions fournies par la recherche Tabou de Gendreau et al. (2008). À ce jour, aucune méthode de résolution exacte n'a été proposée.

Les résultats présentés dans le tableau 5.5 sont similaires aux résultats des solutions sur les instances de taille moyenne. Notre méthode est moins performante que la méthode d'Optimisation par Colonie de Fourmis de Fuellerer et al. (2008), que ce soit en terme de qualité des solutions ou de temps d'éxécution. Cependant, les résultats obtenus par notre méthode sont comparables en terme de qualité et de temps avec la méthode de Recherche Tabou de Gendreau et al. (2008).

Enfin, le tableau 5.6 présente les résultats agrégés sur les 180 instances pour nos deux méthodes heuristiques. La différente de qualité de solution de la méthode de génération de routes réalisables est calculée relativement aux valeurs de solutions de la méthode de Branch & Price heuristique.

Très clairement, la méthode de génération de routes réalisables (HCG) est de moins bonne qualité que la méthode de Branch & Price heuristique(HBP) avec en moyenne un pourcentage de différence proche de 20%. Cela s'explique par le fait que la méthode de génération de routes réalisables ne fait appel qu'à une seule heuristique de chargement. De plus, une fois que les objets sont insérés, le chargement de ceux-ci n'est jamais remis en question. Ainsi, un nombre important de routes réalisables ne sont pas ajoutées. On peut cependant noter que cette méthode est plus rapide que la méthode de Branch & Price heuristique, ce qui s'explique encore une fois par l'utilisation limitée des heuristiques de chargement.