L'OPTIMISATION DE LA
TRAJECTOIRE DES VÉHICULES
Mohammed Akram NEJJARI
Présenté par :
Ouiame MAKHOUKH
Mohamed MZIOUD
Groupe N°: 7
Encadré par : Mr Omar SEFRAOUI
11
INTRODUCTION ET PROBLÉMATIQUE
2
2
PLAN
1)Description et modélisation mathématique
2)Résolution du problème dans le premier cas
3)Résolution du problème dans le deuxième cas
4) Conclusion
5) Annexes
2
3
1) Description et modélisation
mathématique
Description du
problème :
Premier cas :
2
4
1) Description et modélisation mathématique
Description du
problème :
Deuxième
cas :
2
5
Modélisation du problème :
Quelques notions de la théorie des graphes :
Un chemin hamiltonien d'un graphe
est un chemin qui passe par tous les
sommets une fois et une seule.
2
6
Modélisation du problème :
Quelques notions de la théorie des graphes :
Un cycle hamiltonien est un chemin
hamiltonien qui est un cycle.
Un graphe hamiltonien est un graphe qui
possède un cycle hamiltonien.
2
7
Modélisation du problème :
Modélisation mathématique du problème :
Le problème peut être modélisé à l'aide d'un graphe tel que ces sommets sont les
places (villes,maisons,…) , et les arêtes sont les routes , donc le problème consiste
à chercher :
o Dans le premier cas : le cycle hamiltonien de poids minimum .
o Dans le deuxième cas : le chemin de poids minimum entre le point de
départ et le point d’arrivé .
2
8
Modélisation du problème :
Modélisation mathématique du problème :
Supposant qu’on a N places :
𝐺 = (𝑉, 𝐸) un graphe avec : 𝑉 = 1,2,3, 𝑒𝑡 𝐸 = {(𝑖, 𝑗 )Τ𝑖 , 𝑗 ∈ 𝑉}
…,𝑁
𝑖: la place d’indice i
𝐴 = (𝑎𝑖𝑗 )1≤𝑖,𝑗≤𝑁 : la matrice adjacente associé à G
= la distance entre i et j (dans le sens i vers j)
𝑎 𝑖𝑗
Remarque :
𝑎 𝑖𝑗 ≠ 𝑎𝑗𝑖 13
9
2) Résolution du problème dans le premier
cas Algorithme
:
14
10
ANNEXE 1 :
27
11
Simulation Python : CODE PYTHON : (ANNEXE
1) OUTPUT :
INPUT :
CONCLUSION :
Le chemin optimale : 1 →3 →2 →4
→1
L = 31
14
12
Formulation
mathématique:
Pour N=4 : on pose , A =
Puisque N=4 alors on a (4-1)! = 6 chemins
𝑇1 = [1,2,3,4,1] ⇒ 𝑀1 = 𝑎12 + 𝑎23 + 𝑎34 +
𝑎41
𝑇2 = [1,2,4,3,1] ⇒ 𝑀2 = 𝑎12 + 𝑎24 + 𝑎43 +
𝑇3 = [1,3,4,2,1] ⇒ 𝑀3 = 𝑎13 + 𝑎34 + 𝑎42 + 𝑎31
𝑇4 = [1,3,2,4,1] ⇒ 𝑀4 = 𝑎13 + 𝑎32 + 𝑎24 +
𝑎21
𝑇5 = [1,4,3,2,1] ⇒ 𝑀5 = 𝑎14 + 𝑎43 + 𝑎32 +
𝑇6 = [1,4,2,3,1] ⇒ 𝑀6 = 𝑎14 + 𝑎42 + 𝑎23 + 𝑎41
Alors L = min(𝑀1 , 𝑀2 , 𝑀3 , 𝑀4 , 𝑀5 , 𝑀6) 𝑎21
14
13
𝑎31
Formulation
mathématique:
Dans le cas général ( N places ) :
𝐴 = (𝑎 𝑖𝑗 )1≤𝑖,𝑗≤𝑁
V’ = {2,3,4,…,N}
S = P(V’) : ensemble des permutations de V’
Card(S) = (N-1)!
J = {1,2,3,…,(N-1)!}
𝑇𝑖 = [ 1 , list(𝑆𝑖 ) , 1 ] , avec : 𝑆𝑖 ∈ 𝑆 𝑝𝑜𝑢𝑟 𝑡𝑜𝑢𝑡 𝑖 ∈ 𝐽
14
14
3) Résolution du problème dans le deuxième
cas
Algorithme de Dijkstra :
C’est un algorithme qui permet de trouver le plus court chemin entre deux sommets d’un
graphe
(orienté ou non orienté).
Explication par un exemple :
o On considère le graphe suivant , donné par sa
representation graphique
o Le graphe 𝐺 = (𝑆, X) est ici défini par :
• L’ensemble des sommets 𝑆 = {𝐴, 𝐵, 𝐶,
𝐷, 𝐸, 𝐹}
• L’ensemble des arêtes X= {(𝐴, 𝐶), … ,
(𝐸, 𝐶), … , (𝐹, 𝐴)} 14
15
ANNEXE 2 :
27
16
ANNEXE 2 :
27
17
ANNEXE 2 :
27
18
Simulation Python : CODE PYTHON : (ANNEXE 2)
27
19
Simulation Python : CODE PYTHON : (ANNEXE 2)
27
20
Simulation Python : CODE PYTHON : (ANNEXE 2)
27
21
Simulation Python : CODE PYTHON : (ANNEXE 2)
27
22
Simulation Python : CODE PYTHON : (ANNEXE 2)
Le plus court chemin de 𝐷 vers 𝐴 est
réalisé par 𝐷 → 𝐸 → 𝐵 → 𝐶 → 𝐹 → 𝐴
avec L = 6 .
27
23
MERCI DE VOTRE ATTENTION!
27
24
