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

5.5.2 Résolution par programmation dynamique

L'algorithme 6 construit un chemin qui part de la source et construit itérativement des chemins vers la destination. La construction se fait par extension de chemins partiels (appelés aussi labels ou étiquettes). Un chemin partiel est un chemin qui a pour origine la source et pour extrémité terminale un sommet du graphe. L'extension d'un chemin partiel L se fait au travers du calcul de nouveaux chemins partiels, correspondant à L augmenté d'un arc sortant par l'extrémité terminale de L. Dans le cas où l'extension d'un chemin partiel vers un nouveau sommet viole une contrainte, le chemin partiel correspondant est supprimé. On vérifie aussi la faisabilité de chaque extension. Chaque chemin partiel ainsi construit est comparé avec les autres chemins partiels possédant la même extrémité terminale. On dit qu'un chemin partiel L¹ domine un chemin partiel L², ce qui est noté L¹ < L², lorsque les deux chemins partiels ont la même extrémité terminale et que l'on peut être sûr que n'importe quelle extension de L¹ sera de coût moindre que l'extension identique pour le chemin partiel L². Les chemins partiels dominés sont éliminés de la liste des chemins partiels associés au sommet. La consommation d'un chemin partiel L sur une ressource w est notée cL(w).

On peut voir que la complexité de cet algorithme dépend donc des ressources considérées.

La figure 5.4 illustre le déroulement de l'algorithme sur un graphe à quatre sommets et deux ressources dont le coût. Un chemin partiel est identifié par son nom et son niveau de consommation des ressources entre accolades, sur le modèle

Li {coût, autre ressource} .

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

Algorithme 6 : Algorithme de programmation dynamique

Données : G : un graphe sur W ressources; L : une liste de chemins partiels non traités; Li : la liste des chemins partiels d'extrémité terminale i Résultat : LV

1 Initialisation: L ? chemin partiel réduit à {0} ;

2 3 4	tant que L =6 0 faire prendre L E L; etL := extrémité de L;
5	domine := faux;
6	pour chaque chemin partiel L' E LetL faire
7		si cL(w) = cL'(w), ?w = 0, ... ,W alors
8		LetL := LetL \ {L'};
9		sinon
10			si cL'(w) = cL(w), ?w = 0, . . . ,W alors
11				domine := vrai;
12				stop;
13			fin
14		fin
15	fin
16	si domine = faux alors
17		LetL := LetL U {L};
18		pour chaque arc (etL, i) faire
19			L' := l'extension de L par (vetL, vi);
20			si L' est valide alors
21			L := L U {L'};
22			fin
23		fin
24	fin

25 fin

L'objectif est de minimiser le coût des chemins partant de v0 en respectant les contraintes de consommation de ressource en chaque sommet, indiquées entre crochets sur la figure 5.4. À chaque itération, on étend le chemin partiel marqué par une étoile dans L. Le chemin partiel L³ issu de L¹ est supprimé car il consomme 2 unités sur la ressource qui est limitée à 1 au sommet v2. Le chemin partiel L⁵ est quant à lui supprimé car il est dominé par L⁴.

Les sections 5.6, 5.7 et 5.8 présentent de manière détaillée les méthodes que nous proposons pour la résolution du problème du 2|RO|L-VRP.

L : L^0	v [1] 1				L : L^0, L1, L2 *	L^1{1,1} v [1] 1
1,1			2,1		1,1			2,1
L^0{0,0}					L^0{0,0}
[0] v 0	1,1		v3	2	[0] v 0	1,1			v3 [2]
3,1			1,1		3,1			1,1
	v2 [1]					v2 [1]
initialisation					itération 1	L^2{3,1}
L : L^1, L^2, L3, L^4 *					L : L^2, L4, L5 *
	L^1{1,1}					L^1{1,1}
	v [1] 1					v 1 1
1,1			2,1		1,1			2,1
L^0{0,0}			L^4{3,2}		L^0{0,0}				L^4{3,2}
[0] v 0	1,1		v3	[2]	[0] v 0	1,1			v3 [2]
									L^5{4,2}
3,1			1,1		3,1			1,1	dominé
	v2 [1]					v2 [1]
itération 2	L^2{3,1} L^3{2,2}		violation de contrainte		itération 3	L^2{3,1}

FIGURE 5.4 - Trace de l'algorithme de programmation dynamique