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

• Remerciements
  
• Résumé
  
• Table des matières
  
• Introduction Générale
  
• Première partie
  
• Favoriser l'obtention rapide de
  
• solutions dans les méthodes de
  
• recherche arborescente
  
• Chapitre 1
  
• Dynamic Learning Search: une
  
• méthode par apprentissage
  
  • 1.1 Introduction
    
  • 1.2 État de l'art des recherches arborescentes
    
    • 1.2.1 Méthode de parcours de l'arbre de recherche
      
    • 1.2.2 Méthode de structuration de l'arbre de recherche
      
    • 1.2.3 Parcours réduit de l'arbre
      
    • 1.2.4 Ordre dynamique
      
    • 1.2.5 Apprentissage : look-back
      
    • 1.2.6 Métaheuristiques combinées à la recherche arborescente
      
  • 1.3 Dynamic Learning Search: une méthode par apprentissage
    
  • 1.4 Learning : une méthode basée sur un apprentissage
    
    • 1.4.1 Sondage
      
    • 1.4.2 Apprentissage
      
    • 1.4.4 Remise en question
      
  • 1.5 Dynamic : un ordre dynamique de choix des variables et de sélection des valeurs
    
  • 1.6 Search: un schéma de recherche adapté à la méthode
    
  • 1.7 Algorithme général de la méthode
    
  • 1.8 Méthode Dynamic Learning Search: critères de sélection
    
    • 1.8.1 Problèmes de Satisfaction des Contraintes
      
    • 1.8.2 Problèmes d'Optimisation Combinatoire
      
    • 1.8.3 Méthode commune aux deux types de problèmes
      
  • 1.9 Résultats expérimentaux
    
    • 1.9.1 Application au problème du Voyageur de Commerce
      
    • 1.9.2 Application au problème d'Emploi du Temps de Garde d'Infirmières
      
    • 1.9.3 Application à des problèmes de Satisfaction de Contraintes académiques
      
  • 1.10 Conclusion et perspectives
    
• Deuxième partie
  
• Utiliser des méthodes exactes au
  
• sein des métaheuristiques :
  
• méthodes de grands voisinages
  
• Chapitre 2
  
• La recherche à grand voisinage : un
  
• nouvel opérateur
  
  • 2.1 Introduction à la recherche locale
    
    • 2.1.1 Bases de la recherche locale
      
    • 2.1.3 Recherche locale à voisinage variable
      
    • 2.1.4 Algorithmes utilisant de la recherche locale
      
  • 2.2 Recherche à grand voisinage
    
    • 2.2.1 Notations et définitions de la recherche à grand voisinage
      
  • 2.3 Classe des problèmes considérés : Problèmes de Tournées avec Couverture Partielle
    
    • 2.3.1 Problèmes de Tournées avec Gains
      
    • 2.3.2 Autres variantes de Problèmes de Tournées à Couverture Partielle
      
    • 2.3.3 Complexité des Problèmes de Tournées avec Couverture Partielle
      
    • 2.3.4 Quelques opérateurs de recherche locale pour les Problèmes de Tournées avec Couverture Partielle
      
    • 2.4.2 L'opérateur de grand voisinage : Dropstar
      
    • 2.4.3 Plus court chemin avec contraintes de ressources (SPPRC)
      
    • 2.4.4 Résolution par un algorithme de programmation dynamique
      
  • 2.5 Perspectives : variantes possibles de la procédure Dropstar
    
• Chapitre 3
  
• Application au Problème de
  
• l'Acheteur Itinérant
  
  • 3.1 Introduction au problème de l'Acheteur Itinérant
    
  • 3.2 Notre algorithme : le DMD-ATA
    
    • 3.2.1 Fourmis Parallèles
      
    • 3.2.2 Fourmis Anamorphiques
      
    • 3.2.3 Plans Multi-Dimensionnels
      
    • 3.2.4 Dynamique
      
  • 3.3 Opérateurs de recherche locale
    
    • 3.3.2 Application de l'opérateur Dropstar
      
    • 3.3.3 Intégration de la recherche locale dans l'algorithme DMD-ATA
      
  • 3.4 Résultats expérimentaux
    
  • 3.5 Conclusion
    
• Chapitre 4
  
• Application au Problème du
  
• Voyageur de Commerce Généralisé
  
  • 4.1 Introduction au Problème du Voyageur de Commerce Généralisé
    
  • 4.2 État de l'art
    
  • 4.3 Algorithme mémétique
    
    • 4.3.1 Composants basiques de l'algorithme Individus
      
    • 4.3.2 Croisement
      
    • 4.3.3 Implémentation détaillée de l'opérateur de croisement
      
    • 4.3.4 Heuristiques de recherche locale
      
  • 4.4 Résultats expérimentaux
    
  • 4.5 Conclusion et perspectives
    
• Troisième partie
  
• Tronquer les méthodes exactes :
  
• méthode de Branch & Price
  
• heuristique
  
• Chapitre 5
  
• Application au problème de
  
• Tournées de Véhicules avec
  
• Contraintes de Chargement
  
  • 5.1 Préambule : Intérêt du problème
    
  • 5.2 Problèmes de calcul de tournées de véhicules
    
    • 5.2.1 Du problème du Voyageur de Commerce au problème de Tournées de Véhicules
      
    • 5.2.2 Le 2L-VRP parmi les problèmes de Tournées de Véhicules
      
  • 5.3 État de l'art
    
    • 5.3.1 Résolution du 2L-VRP
      
    • 5.3.2 Algorithmes de chargement
      
  • 5.4 Modèle classique du problème du 2|RO|L-VRP
    
  • 5.5 Génération de colonnes
    
    • 5.5.1 Modélisation d'un ESPPRC
      
    • 5.5.2 Résolution par programmation dynamique
      
  • 5.6 Notre approche : un schéma de Branch & Price
    
    • 5.6.1 Méthode de séparation
      
    • 5.6.2 Initialisation de Ù pour la génération de colonnes
      
    • 5.6.3 Remontées de colonnes
      
    • 5.6.4 Problème esclave : ESPPRC
      
    • 5.6.5 Problème de chargement séquentiel à deux dimensions
      
  • 5.7 Deux approches différentes pour la réalisabilité du chargement
    
    • 5.7.1 Vérification de la réalisabilité a posteriori
      
    • 5.7.2 Construction de routes réalisables dans le sous-problème
      
  • 5.8 Branch & Price heuristique
    
    • 5.8.1 Problème esclave heuristique
      
    • 5.8.2 Gestion des colonnes
      
    • 5.8.3 Méthode de séparation
      
  • 5.9 Résultats expérimentaux
    
    • 5.9.1 Paramètres retenus
      
    • 5.9.2 Classes d'instances
      
    • 5.9.3 Analyses des résultats
      
  • 5.10 Conclusions et perspectives
    
• Conclusion et perspectives
  
• Liste des illustrations
  
• Liste des tableaux
  
• Bibliographie