Cours de recherche opérationnelle

Problème de recherche du plus court chemin

Problème de recherche du pus court chemin

1. Introduction

Soit G=(X,U) ; on associe à chaque arc u= (i,j)∈U un nombre réel qu’on note l(u) ou lij
appelé longueur de l’arc u. On dit alors que le graphe G est valué par les longueurs l(u).

Les longueurs des arcs peuvent correspondre à :

des distances physiques,

des coûts de transport,

des dépenses de construction,

temps nécessaire à une réalisation, …

La longueur d’un chemin µ joignant le sommet i au sommet j est donnée par : l (µ)

Le problème de plus court chemin entre deux sommets i et j consiste à déterminer un chemin
de i à j, µ (i, j), de longueur minimale.

La longueur d’un chemin comprenant un circuit de longueur strictement négative est non
bornée (il suffit d’emprunter ce circuit une infinité de fois). Ce type de circuit est appelé
circuit absorbant

L’absence d’un circuit absorbant constitue une condition nécessaire à l’existence d’un chemin
de longueur minimale

2. Exemples de modélisation par PCC

2.1 Stratégie de remplacement d’équipements :

Une mine a une durée totale d’exploitation de T années. Elle utilise un équipement qu’elle a
acquis à la date i=0 (équipement neuf).

Au début de chaque année i, deux possibilités s’offrent à la mine :

- garder l’équipement en service pendant [i, i+1]
- revendre cet équipement à un prix de récupération de v(x) avec x est son âge et acheter
un équipement neuf au prix p (i)

Le coût d’une année de fonctionnement r(x) dépend de l’âge.

L’équipement doit être vendu à la date T.

Déterminer la politique de remplacement de l’équipement à coût minimal.

1 Hanen Bouchriha
Cours de recherche opérationnelle
Problème de recherche du plus court chemin

Le problème peut être représenté par un graphe comme suit :

0 1 2 T

- Un sommet est associé à chaque date (T+1 sommets).

- Un arc qui relie deux sommets i et j représente la décision d’acheter un équipement à la date
i et le vendre à j (j>i).
- La longueur d’un arc = ∑(coût d’achat + coût de fonctionnement – prix de vente)
j −i
lij = p(i) – v(j-i)+ ∑ r ( x)
x =1
- La politique de remplacement de l’équipement à coût minimal est représenté par le plus
court chemin de 0 à T.

2.2 Optimisation des achats

Le service d’achat doit assurer l’approvisionnement pendant T périodes pour réaliser un

programme de production. Le prix d’achat p(t) dépend de la période d’approvisionnement t.

Afin de tirer profit de la variation des prix, l’entreprise peut :

- Acheter la matière en t et constituer des stocks. Le coût unitaire de stockage est h (t) en
la période t.
- Reporter sa demande moyennant une pénalité de retard. p est la pénalité de reporter
une unité de la demande pendant une période.

Déterminer le plan d’approvisionnement à coût minimal.

2 Hanen Bouchriha
Cours de recherche opérationnelle
Problème de recherche du plus court chemin

Le problème peut être représenté par un graphe comme suit :

S
p(4)
p(1)
p(2) p(3)

1 2 3 T
h(1) h(2)
))
p p p

- X = S ∪ {t, t =1,.., T} (T+1 sommets)

- Un arc (S,t) correspond à la décision d’acheter en la période t. lst = p(t)
- Tout sommet t (t =1,.., T-1) est relié à t+1. L’arc (t,t+1) correspond à la décision de
stocker pendant la période t et a une longueur de h(t)
- Tout sommet t (t =2,.., T) est relié à t-1. L’arc (t, t-1) correspond à la décision de
reporter la demande de la période t à la période t-1 et a une longueur de p.
- La Politique optimale d’approvisionnement correspond à la recherche du plus court
chemin entre S et tous les sommets du graphe

3. Algorithmes de résolution :

3.1 Principe d’optimalité de Bellman :

Théorème :
Soit µ un chemin entre i et j de longueur optimale. Toute partie µ 1 de µ reliant un sommet h à
un sommet l est alors de longueur optimale.

Ce théorème permet de conclure que le chemin optimal est composé de sous chemins
optimaux.

Démenstration :
Pour démontrer ce théorème on peut raisonner par l’absurde :
µ étant un chemin entre i et j de longueur minimale. On suppose qu’il existe une partie µ 1 de
µ joignant h à l qui n’est pas de longueur minimale. Il existe alors un chemin µ 2 de h à l tel
que l(µ 1)≥l(µ 2). Le graphe µ’ identique à µ sauf pour la partie µ 1 qui est remplacée par µ 2, est
alors de longueur inférieure à celle de µ ; ce qui contredit l’hypothèse de départ.

3 Hanen Bouchriha
Cours de recherche opérationnelle
Problème de recherche du plus court chemin

Illustration :

2 3

4 5

Soit π(5) : La longueur du plus court chemin entre 1 et 5

π(5) = min {π(2) + l25 ; π(3) + l35 ; π(4) + l45}

3.2 Classification des algorithmes de recherche de PCC

Les algorithmes de résolution du problème de recherche du plus court chemin seront

différents suivant.

les propriétés du graphe :

- graphe valué par des longueurs positives.
- graphe valué par des longueurs de signes quelconques.
- graphe sans circuit.

le problème considéré :
- recherche du plus court chemin d’un sommet à un autre.
- recherche du plus court chemin d’un sommet à tous les autres.
- recherche du plus court chemin entre tous les couples de sommets.

3.3 Cas d’un graphe valué par des longueurs positives : Algorithme de Dijkstra-
Moore (1959):

Cet algorithme permet la recherche du plus court chemin partant d’un sommet (noté 1) à tous
les autres sommets du graphe.
Les sommets sont partitionnés en deux sous-ensembles
- P : ensemble de sommets ayant une étiquette permanente
- T = X-P : ensemble de sommets ayant une étiquette temporaire
À chaque itération un sommet est transféré de T vers P. L’algorithme converge en n-1
itérations (n étant l’ordre du graphe G=(X,U))

On désigne par π(x) : la longueur du plus court chemin entre le sommet 1 et le sommet x. Le
calcul des plus courtes distances se fait de proche en proche par ajustements successifs.

4 Hanen Bouchriha
Cours de recherche opérationnelle
Problème de recherche du plus court chemin

Algorithme de Dijkstra-Moore (1959):

Etape 1 : Initialisation

π(1)=0
P={1}
T={2, …, N}
∀ i ∈ T, π(i)= l1i si (1,i) ∈U
= ∞ sinon

Etape 2 :

Sélectionner j ∈ T tel que π(j)= min π (i )

i∈T
Faire : T=T\{j}
P=P∪{j}

Si T = ∅ alors fin sinon aller à l’étape 3.

Etape 3 :

∀ i ∈ T tel que (j,i)∈U faire : π(i) ← min (π(i), π(j)+ lji) (Principe d’optimalité de Bellman)

Aller à l’étape 2.

Exemple

Une entreprise doit distribuer la marchandise à ses clients situés aux nœuds 2 à 6. La distance
à parcourir d’un point à un autre et le sens de circulation sont indiqués dans la figure ci-
contre.

4
40 50
20
2 5
70 10
1 50 30
20
10
3 6
40

Déterminer les plus courts chemins entre 1 et 2 et entre 1 et 6 ?

5 Hanen Bouchriha
Cours de recherche opérationnelle
Problème de recherche du plus court chemin

Etape 1 :
π(1)=0, π(2)=70, π(3)=10, π(4)= π(5)= π(6)= ∞
P= {1}, T= {2, 3, 4, 5, 6}
Etape 2 :
j=3
P= {1, 3}, T= {2, 4, 5, 6}
Etape 3 :
π(2)=min {70, 10+50} = 60
π(5)=min {∞, 10+20} = 30
π(6)=min {∞, 10+40} = 50
Etape 2 :
j=5
P= {1, 3,5}, T= {2, 4, 6}
Etape 3 :
π(2)=min {60, 30+20}= 50
π(4)=min {∞, 30+50} = 80
π(6)=min {50, 30+30} = 50
Etape 2 :
j=6
P= {1, 3,5,6}, T={2, 4}
Etape 2 :
j=2
P= {1, 3,5,6,2}, T={4}
Etape 3 :
π(4)=min {30+50,50+40} = 80
Etape 2 :
j=4
P= {1, 3, 5, 6, 2,4}, T=∅

Fin de l’algorithme

On peut représenter le calcul sous forme de tableau comme suit :

Itération 1 2 3 4 5 6
1 - 70 10 ∞ ∞ ∞
2 - 60/3 - ∞ 30/3 50/3
3 - 50/5 - 80/5 - 50/3
4 - 50/5 - 80/5 - -
5 - - - 80/5 - -

Le plus court chemin de 1 à 2 est 1, 3, 5, 2 de longueur 50.

Le plus court chemin de 1 à 6 est 1, 3, 6 de longueur 50.

6 Hanen Bouchriha
Cours de recherche opérationnelle
Problème de recherche du plus court chemin

3.4 Cas d’un graphe valué par des longueurs de signes quelconques

Cet algorithme s’applique pour un graphe ayant des coûts quelconques. Il permet la recherche
du plus court chemin entre un sommet et tous les autres.

Il y a convergence en absence de circuit absorbant.

Il s’agit de déterminer le plus court chemin de proche en proche en calculant à chaque

itération le plus court chemin à un sommet donné i en utilisant les plus courts chemins à tous
les prédécesseurs de i (Processus itératif)

Dans l’algorithme, m représente l’indice de l’itération et πm (i) est le plus court chemin entre
le sommet 1 et le sommet i calculé à l’itération m.

Algorithme de BELLMAN

Soit G = (X,U) un graphe d’ordre N

Etape 1 : Initialisation
- m=1
- π1(1)=0
- ∀ j # 1 π1 (j) = l1j si (1,j) ∈ U
= +∞ sinon

Etape 2 :
Tant que {m ≤ N-1} et { ∃ j / πm (j) < πm-1 (j) } Faire
Début
πm+1 (j) = min (πm (j) , min { πm (k) + lkj } )
k# j
m=m+1
Fin

Remarque : L’algorithme converge en N-1 itérations.

Si m=N et il existe j / πm (j) < πm-1 (j) ⇒ il existe un circuit de longueur négative (circuit
absorbant)

Exemple :

Un agent commercial se trouvant à la ville S décide de participer à une foire à la ville T. Pour
cela, il doit emprunter le réseau routier donné par la figure ci-contre. L’agent commercial a
estimé le coût de son transport ainsi que les bénéfices rapportées par la vente de produits aux
différentes villes intermédiaires. Sur le graphe, les dépenses ont été représentées par des
longueurs positives ; les bénéfices réalisés ont été représentés par des longueurs négatives.

7 Hanen Bouchriha
Cours de recherche opérationnelle
Problème de recherche du plus court chemin

7
A D
2 -8 4 5
-5
S B -1 T
4 1 3
7
C E
4

Trouver le chemin emprunté par l’agent permettant de minimiser ses coûts nets

Application :

Itération O A B C D E T

1 0/O 2/O -5/O 4/O +∞ +∞ +∞

2 0/O 2/O -6/A 4/O -1/B -2/B +∞

3 0/O 2/O -6/A 4/O -3/E -3/B 4/D

4 0/O 2/O -6/A 4/O -4/E -3/B 2/D

5 0/O 2/O -6/A 4/O -4/E -3/B 1/D

Le chemin le plus court est O → A → B → E → D → T de coût = 1

3.5 Cas d’un graphe sans circuit :

Dans un graphe sans circuit, il existe au moins un sommet ne possédant aucun précédent,
sinon G posséderait un circuit. Ce sommet est appelé racine du graphe. Soit 1 ce sommet

Dans un graphe sans circuit, il existe au moins un sommet ne possédant aucun successeur,
sinon G posséderait un circuit.

Dans le cas d’un graphe sans circuit, il y a un algorithme plus simple de recherche du plus
court chemin du sommet 1 à tous les autres

8 Hanen Bouchriha
Cours de recherche opérationnelle
Problème de recherche du plus court chemin

Algorithme de détermination du rang d’un sommet :

Définition :

On définit le rang d’un sommet i d’un graphe G sans circuit par :

- rg(1) = 0,
- rg (i) = le nombre d’arcs dans un chemin allant de 1 à i, de cardinalité maximum.

Algorithme de détermination des rangs dans un graphe sans circuit :

Etape 1 :
Initialisation : S=X, k=0
Etape 2 :
Sk ={ensemble des sommets sans précédent dans S}
Pour tout i ∈ Sk, rg(i) = k
Etape 3 :
S=X-Sk
Si S=∅ fin
Sinon
Début
Eliminer du graphe tous les arcs ayant pour origine un sommet de Sk
k=k+1,
Retour à l’étape 2
Fin

Algorithme de détermination du plus court chemin dans un graphe sans circuit :

Etape 1 : Initialisation

On pose π(1)=0, k=1 et S=X-{i∈X / rg(i)=0}

Etape 2 :

Sk={ i∈X / rg(i)=k}

Pour tout i ∈Sk faire π (i) = min (π ( j ) + lji )
( j ,i )∈U

Etape 3 :

Faire S=S- Sk
Si S=∅ fin
Sinon faire k=k+1, retour à l’étape 2

9 Hanen Bouchriha
Cours de recherche opérationnelle
Problème de recherche du plus court chemin

Exemple

1
2 4
3
10

1 2 5
6

4
2
3 5
7

Plus court chemin de 1 à 6 ?

rg(1) =0, rg(3)=1, rg(2)=rg(5)=2, rg(4)=3, rg(6)=4.

π(1)=0, π(3)=4, π(2)=min (4+2, 3) =3, π(5)=min (4+7)=11, π(4)=min (3+1, 11+5)=4,
π(6)=min (4+10, 11+2)=13.

Le plus court chemin de 1 à 6 est : 1, 3, 5 et 6.

10 Hanen Bouchriha