University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Bensedira,Houria |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Les algorithmes approchés pour le probléme de voyageur de commerce Type de document : texte imprimé Auteurs : Bensedira,Houria, Auteur ; Refoufi,A, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (42 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : TSP (PVC)
heuristique
PPV (Plus Proche Voisin)
2-OptIndex. décimale : 004 - Informatique Résumé :
Résumé
Un voyageur veut visiter certain nombre de villes, débutant et finissant son parcours dans la même ville en visitant chacune des villes une et une seule fois. Ce problème est connu sous le nom du problème de voyageur de commerce (PVC).
Le problème de voyageur de commerce (TSP) est un problème classique d’optimisation combinatoire NP-complet. Des heuristiques ont été proposées permettant de trouver des solutions presque optimales, on distingue trois classes d’heuristiques : de construction, d’amélioration et métaheuristiques. D’après l’étude sur le PVC, nous proposons une hybridation de deux méthodes, nous avons choisi parmi les heuristiques de construction l’algorithme de plus proche voisin (PPV), et parmi les heuristiques d’amélioration on a l’euristique 2-OptNote de contenu : Sommaire
Introduction générale…………….………………………………………………………………….1
Chapitre 1………………………………………………………………………………………………3
1. Introduction..................................................................................................................3
2. Définition de base..........................................................................................................3
2.1. classe P .................................................................................................................4
2.2. Problème de classe NP :..............................................................................................................4
2.2.1. Classe NP-complet : .............................................................................................................4
2.3. Classe NP-difficiles : .............................................................................................4
2.4. Notions sur les graphes :..............................................................................................5
a. Un graphe .................................................................................................................5
b. Graphe complet......................................................................................................................5
c. Cycle hamiltonien...............................................................................................................5
d. Un graphe pondéré ............................................................................................................5
2.5. Notion de complexité algorithmique : ...................................................................................6
3. Problème de voyageur de commerce :..........................................................................................7
3.1. Définition : .......................................................................................................7
a. Domaines d’applications : .....................................................................................................8
b. Exemple : ................................................................................................................................8
4. Méthodes de résolution du TSP :................................................................................................10
4.1. Les algorithmes exacts :............................................................................................................10
4.1.1. Méthodes des plans sécants (Cutting plane) :..................................................................10
4.1.2. Algorithme Branch & Bound (séparation-évaluation) ...................................................11
4.1.2.1 Branch and Bound pour le problème de TSP : .........................................................12
5. Conclusion ....................................................................................................................................12
Chapitre 2…………………………………………………………………………………….13
1. Introduction .......................................................................................................................... 13
2. C’est quoi les heuristiques : .................................................................................................. 13
3. Les algorithmes d’approximation du TSP : .......................................................................... 13
3.1 Heuristiques de construction : ............................................................................................. 14
3.1.1 L’euristique de plus proche voisin (Nearest Neighbor) : .............................................. 14
3.1.2 L’euristique de Greedy : ............................................................................................... 14
3.1.3 Heuristique de Christofides : ................................................................................. 15
a. Principe : .................................................................................................................... 15
3.2 Les heuristiques d’amélioration : ........................................................................................ 18
3.2.1 Algorithme de recherche local ...................................................................................... 18
a. 2-opt heuristique : ...................................................................................................... 18
b. 3-opt heuristique : ...................................................................................................... 18
c. k-Opt : ........................................................................................................................ 19
3.3 Les métaheuristiques :......................................................................................................... 20
3.3.1 Algorithme génétique : .............................................................................................. 20
a. Principe : .................................................................................................................... 21
b. L’algorithme génétique pour TSP : ........................................................................... 21
3.3.2 Recherche de tabou : ................................................................................................. 21
3.3.3 L’euristique de colonie de fourmis : .......................................................................... 22
a. Principe : .................................................................................................................... 23
4. Conclusion ............................................................................................................................. 24
Chapitre 3……………………………………………………………………………………..25
1. Introduction...................................................................................................................................25
2. Conception de TSP: ......................................................................................................................25
2.1. Description de TSP : .............................................................................................................25
2.2. Description de notre approche : ..........................................................................................26
2.2.1. Description d’heuristique de plus proche voisin :......................................................26
2.2.2. Description d’heuristique 2-Opt :................................................................................28
2.2.3. L’heuristique 3-opt : .....................................................................................................30
2.2.4. Diagramme de classe : ..................................................................................................30
2.2.5. La complexité des algorithmes :...................................................................................32
3. Implementation .............................................................................................................................33
3.1. Outils de développement ..................................................................................................33
Java .......................................................................................................................33
NetBeans ......................................................................................................................34
3.2. Description du prototype réalisé : ...................................................................................34
4. Conclusion ...............................................................................................................41
Conclusion générale………………………………………………………………………….42Côte titre : MAI/0259 Les algorithmes approchés pour le probléme de voyageur de commerce [texte imprimé] / Bensedira,Houria, Auteur ; Refoufi,A, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (42 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : TSP (PVC)
heuristique
PPV (Plus Proche Voisin)
2-OptIndex. décimale : 004 - Informatique Résumé :
Résumé
Un voyageur veut visiter certain nombre de villes, débutant et finissant son parcours dans la même ville en visitant chacune des villes une et une seule fois. Ce problème est connu sous le nom du problème de voyageur de commerce (PVC).
Le problème de voyageur de commerce (TSP) est un problème classique d’optimisation combinatoire NP-complet. Des heuristiques ont été proposées permettant de trouver des solutions presque optimales, on distingue trois classes d’heuristiques : de construction, d’amélioration et métaheuristiques. D’après l’étude sur le PVC, nous proposons une hybridation de deux méthodes, nous avons choisi parmi les heuristiques de construction l’algorithme de plus proche voisin (PPV), et parmi les heuristiques d’amélioration on a l’euristique 2-OptNote de contenu : Sommaire
Introduction générale…………….………………………………………………………………….1
Chapitre 1………………………………………………………………………………………………3
1. Introduction..................................................................................................................3
2. Définition de base..........................................................................................................3
2.1. classe P .................................................................................................................4
2.2. Problème de classe NP :..............................................................................................................4
2.2.1. Classe NP-complet : .............................................................................................................4
2.3. Classe NP-difficiles : .............................................................................................4
2.4. Notions sur les graphes :..............................................................................................5
a. Un graphe .................................................................................................................5
b. Graphe complet......................................................................................................................5
c. Cycle hamiltonien...............................................................................................................5
d. Un graphe pondéré ............................................................................................................5
2.5. Notion de complexité algorithmique : ...................................................................................6
3. Problème de voyageur de commerce :..........................................................................................7
3.1. Définition : .......................................................................................................7
a. Domaines d’applications : .....................................................................................................8
b. Exemple : ................................................................................................................................8
4. Méthodes de résolution du TSP :................................................................................................10
4.1. Les algorithmes exacts :............................................................................................................10
4.1.1. Méthodes des plans sécants (Cutting plane) :..................................................................10
4.1.2. Algorithme Branch & Bound (séparation-évaluation) ...................................................11
4.1.2.1 Branch and Bound pour le problème de TSP : .........................................................12
5. Conclusion ....................................................................................................................................12
Chapitre 2…………………………………………………………………………………….13
1. Introduction .......................................................................................................................... 13
2. C’est quoi les heuristiques : .................................................................................................. 13
3. Les algorithmes d’approximation du TSP : .......................................................................... 13
3.1 Heuristiques de construction : ............................................................................................. 14
3.1.1 L’euristique de plus proche voisin (Nearest Neighbor) : .............................................. 14
3.1.2 L’euristique de Greedy : ............................................................................................... 14
3.1.3 Heuristique de Christofides : ................................................................................. 15
a. Principe : .................................................................................................................... 15
3.2 Les heuristiques d’amélioration : ........................................................................................ 18
3.2.1 Algorithme de recherche local ...................................................................................... 18
a. 2-opt heuristique : ...................................................................................................... 18
b. 3-opt heuristique : ...................................................................................................... 18
c. k-Opt : ........................................................................................................................ 19
3.3 Les métaheuristiques :......................................................................................................... 20
3.3.1 Algorithme génétique : .............................................................................................. 20
a. Principe : .................................................................................................................... 21
b. L’algorithme génétique pour TSP : ........................................................................... 21
3.3.2 Recherche de tabou : ................................................................................................. 21
3.3.3 L’euristique de colonie de fourmis : .......................................................................... 22
a. Principe : .................................................................................................................... 23
4. Conclusion ............................................................................................................................. 24
Chapitre 3……………………………………………………………………………………..25
1. Introduction...................................................................................................................................25
2. Conception de TSP: ......................................................................................................................25
2.1. Description de TSP : .............................................................................................................25
2.2. Description de notre approche : ..........................................................................................26
2.2.1. Description d’heuristique de plus proche voisin :......................................................26
2.2.2. Description d’heuristique 2-Opt :................................................................................28
2.2.3. L’heuristique 3-opt : .....................................................................................................30
2.2.4. Diagramme de classe : ..................................................................................................30
2.2.5. La complexité des algorithmes :...................................................................................32
3. Implementation .............................................................................................................................33
3.1. Outils de développement ..................................................................................................33
Java .......................................................................................................................33
NetBeans ......................................................................................................................34
3.2. Description du prototype réalisé : ...................................................................................34
4. Conclusion ...............................................................................................................41
Conclusion générale………………………………………………………………………….42Côte titre : MAI/0259 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0259 MAI/0259 Mémoire Bibliothéque des sciences Français Disponible
Disponible
