Optimisation dans les réseaux Recherche Opérationnelle GC-SIE

Optimisation dans les réseaux

Recherche OpérationnelleGC-SIE

Le problème du plus court chemin

Plus courts chemins

Michel Bierlaire 3

Introduction

Plusieurs versions :– d’un nœud vers un nœud – de tous les nœuds vers un nœud – d’un nœud vers tous les nœuds– de tous les nœuds vers tous les nœuds

Nous allons étudier le problème du plus court chemin d’un nœud vers tous les autres.

Souvent, on supposera que =1.

Plus courts chemins

Michel Bierlaire 4

Introduction

Idée générale : Parcourir le réseau à partir de

l’origine Appliquer et mettre à jour des

étiquettes (d1,…,dN) à chaque nœud. Chaque étiquette est soit un

scalaire soit +.

Plus courts chemins

Michel Bierlaire 5

Conditions d’optimalité

Soient d1,d2,…,dN des scalaires tels que

dj di + aij (i,j) A Soit P un chemin entre un nœud et un

nœud . Si

dj di + aij (i,j) P Alors P est un plus court chemin entre

et .

Plus courts chemins

Michel Bierlaire 6

Conditions d’optimalité

Preuve : P est composé des arcs

(,i1),(i1,i2),…,(iP,) Longueur de P =

a,i1+ai1,i2

+…+aiP,

Comme aij = dj di (i,j) P, on a Longueur de P =

(d – diP) + (diP

– diP-1)+…+(di2

-di1)+(di1

-d)=

d-d

Plus courts chemins

Michel Bierlaire 7

Conditions d’optimalité

Soit Q un chemin quelconque entre et . Q est composé des arcs

(,j1),(j1,j2),…,(jQ,) Longueur de Q =

a,j1+aj1,j2

+…+ajQ,

Comme aij dj di (i,j) Q, on a Longueur de Q

(d – djQ) + (djQ

– djQ-1)+…+(dj2

-dj1)+(dj1

-d)=

d–d= Longueur de P.CQFD

Plus courts chemins

Michel Bierlaire 8

Algorithme générique

Idée : On démarre avec un vecteur d’étiquettes

(d1,…,dN) On sélectionne un arc (i,j) qui viole les

conditions d’optimalité, c-à-d tel que dj di + aij

On met à jour l’étiquette de jdj di + aij

Et ainsi de suite jusqu’à ce que tous les arcs vérifient la condition.

Plus courts chemins

Michel Bierlaire 9

Algorithme générique

A tout moment, l’étiquette d’un nœud i peut être interprétée comme la longueur d’un chemin reliant à i.

Si dj di + aij, cela signifie que le chemin arrivant en j à partir de i est plus court que le chemin actuel reliant à j.

Il est plus facile d’effectuer le traitement nœud par nœud.

Pour chaque nœud considéré, on traitera tous ses arcs sortant.

V= liste des nœuds à traiter

Plus courts chemins

Michel Bierlaire 10

Algorithme générique

Algorithme : Initialisation :

– V={}– d = 0, di = i

Itérations. Tant que V – Sélectionner un nœud i dans V et l’en retirer– Pour chaque arc (i,j) sortant de i,

Si dj di + aij, alors – dj di + aij

– Ajouter j à V

3

2

1 4

3

d2=+

1 1

1 3

2

d3=+

d4=+d1=0 1

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

3

2

1 4

3

d2=3

1 1

1 3

2

d3=+

d4=+d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

3

2

1 4

3

d2=3

1 1

1 3

2

d3=1

d4=+d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2

3

2

1 4

3

d2=3

1 1

1 3

2

d3=1

d4=+d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2

3

2

1 4

3

d2=3

1 1

1 3

2

d3=1

d4=+d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2

3

2

1 4

3

d2=3

1 1

1 3

2

d3=1

d4=5d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 3

3

2

1 4

3

d2=3

1 1

1 3

2

d3=1

d4=5d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 3

3

2

1 4

3

d2=3

1 1

1 3

2

d3=1

d4=4d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 3

3

2

1 4

3

d2=2

1 1

1 3

2

d3=1

d4=4d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 3

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 4

3

2

1 4

3

d2=2

1 1

1 3

2

d3=1

d4=4d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 3

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 4

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2

3

2

1 4

3

d2=2

1 1

1 3

2

d3=1

d4=4d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 4

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2

3

2

1 4

3

d2=2

1 1

1 3

2

d3=1

d4=4d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 4

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2

3

2

1 4

3

d2=2

1 1

1 3

2

d3=1

d4=4d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2

{} 0 2 1 4

3

2

1 4

3

d2=2

1 1

1 3

2

d3=1

d4=4d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2

{} 0 2 1 4

Plus courts chemins

Michel Bierlaire 25

Algorithme générique

Propriétés à la fin de chaque itération

Si dj < , alors dj est la longueur d’un chemin reliant à j.

Si i V, alors soit di = + , soit

dj di + aij j tel que (i,j) A

Plus courts chemins

Michel Bierlaire 26

Algorithme générique

Propriétés si l’algorithme se termine j t.q. dj < ,

– dj est la longueur du plus court chemin entre et j. – dj = min(i,j) A di+aij si j [Eq. de Bellman]– d = 0

dj = + ssi il n’y a pas de chemin reliant et j.

L’algorithme se termine ssi il n’y a aucun chemin commençant en et contenant un cycle à coût négatif

Plus courts chemins

Michel Bierlaire 27

Algorithme générique

Les équations de Bellman permettent de reconstituer les plus courts chemins à partir des étiquettes.

Le prédécesseur du nœud j dans le plus court chemin est celui qui réalise le minimum de l’équation de Bellman.

3

2

1 4

3

d2=2

1 1

1 3

2

d3=1

d4=4d1=0

3

2

1 4

3

d2=2

1 1

1 3

2

d3=1

d4=4d1=0

Plus courts chemins

Michel Bierlaire 29

Algorithme de Dijkstra

L’algorithme générique ne spécifie pas comment choisir dans V le nœud à traiter.

L’algorithme de Dijkstra impose que le nœud i à traiter soit tel que

di = minjV dj

Plus courts chemins

Michel Bierlaire 30

Algorithme de Dijkstra

Algorithme : Initialisation :

– V={}– d = 0, di = i

Itérations. Tant que V – Sélectionner un nœud i dans V tel que

di = minjV dj

– Retirer i de V– Pour chaque arc (i,j) sortant de i,

Si dj di + aij, alors – dj di + aij

– Ajouter j à V

3

2

1 4

2

d2=

1 1

1 3

1

d3=

d4=

d1=0 5

0

0

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 1

d5=

3

2

1 4

2

d2=

1 1

1 3

1

d3=

d4=

d1=0 5

0

0

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 1

d5=

3

2

1 4

2

d2=2

1 1

1 3

1

d3=

d4=

d1=0 5

0

0

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 1

d5=

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4=

d1=0 5

0

0

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 1

d5=

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 3

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4=

d1=0 5

0

0d5=

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 3

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4=

d1=0 5

0

0d5=

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 3

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4= 4

d1=0 5

0

0d5=

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 3

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 2

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4= 4

d1=0 5

0

0d5=

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 2

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4= 4

d1=0 5

0

0d5=

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 2

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4= 3

d1=0 5

0

0d5=

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 2

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4= 3

d1=0 5

0

0d5= 2

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 2

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 5

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4= 3

d1=0 5

0

0d5= 2

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 5

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 55 {4} 0 2 1 3 2 4

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4= 3

d1=0 5

0

0d5= 2

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 55 {4} 0 2 1 3 2 4

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4= 3

d1=0 5

0

0d5= 2

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 55 {4} 0 2 1 3 2 4

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 55 {4} 0 2 1 3 2 4

{} 0 2 1 3 2

3

2

1 4

2

d2=2

1 1

1 3

1

d3= 1

d4= 3

d1=0 5

0

0d5= 2

Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 55 {4} 0 2 1 3 2 4

{} 0 2 1 3 2

Plus courts chemins

Michel Bierlaire 46

Algorithme de Dijkstra

Propriété des étiquettes permanentes Si les coûts sur tous les arcs sont non

négatifs Considérons W={i¦di < et iV} Alors, pour chaque itération,

– aucun nœud appartenant à W au début de l’itération n’entrera dans V pendant l’itération

– à la fin de l’itération, didj si iW et jW.

Plus courts chemins

Michel Bierlaire 47

Notes

Si l’on désire calculer le plus court chemin de à , on peut arrêter l’algorithme de Dijkstra dès que le nœud est dans W.

Si au moins un arc a un coût négatif, rien ne garantit le caractère permanent des étiquettes

3

2

1 4

2

d2=

-2

1 1

1

d3=

d4=

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

3

2

1 4

2

d2=

-2

1 1

1

d3=

d4=

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

3

2

1 4

2

d2=

-2

1 1

1

d3=

d4=

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

3

2

1 4

2

d2= 2

-2

1 1

1

d3=

d4=

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

3

2

1 4

2

d2= 2

-2

1 1

1

d3= 1

d4=

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 1

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 3

3

2

1 4

2

d2= 2

-2

1 1

1

d3= 1

d4=

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 3

3

2

1 4

2

d2= 2

-2

1 1

1

d3= 1

d4= 2

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 3

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 2

3

2

1 4

2

d2= 2

-2

1 1

1

d3= 1

d4= 2

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 2

3

2

1 4

2

d2= 2

-2

1 1

1

d3= 1

d4= 2

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 2

3

2

1 4

2

d2= 2

-2

1 1

1

d3= 0

d4= 2

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 2

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 24 {3,4} 0 2 0 2 3

Nœud 3 rentre à nouveau dans V

3

2

1 4

2

d2= 2

-2

1 1

1

d3= 0

d4= 2

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 24 {3,4} 0 2 0 2 3

3

2

1 4

2

d2= 2

-2

1 1

1

d3= 0

d4= 1

d1=0

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 24 {3,4} 0 2 0 2 3

Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 24 {3,4} 0 2 0 2 35 {4} 0 2 0 1 4