Conclusion et perspectives
Dans ce mémoire, nous nous sommes
intéressés aux possibilités d'hybridation entre des
méthodes exactes et des méthodes heuristiques. Ces
méthodes hybrides permettent de tirer avantage de chacune de deux
approches : systématicité et optimalité de la
résolution exacte, caractère moins déterministe et
rapidité de la composante heuristique. Nous nous sommes ainsi
focalisés dans les deux dernières parties de ce mémoire
sur la mise au point de procédures intégrant ces deux approches
au sein d'un processus incomplet unique.
Nous commençons par faire la synthèse des
différents aspects sur lesquels portent nos contributions, puis nous
évoquerons les perspectives de recherches.
Dans la première partie du mémoire, nous nous
sommes intéressés aux méthodes de résolution par
recherche arborescente. Nous avons introduit une nouvelle approche pour la
gestion des décisions de branchement, que nous avons appelée
Dynamic Learning Search. Cette approche, basée sur des techniques
d'apprentissage, présente l'intérêt de chercher à
diriger la recherche vers des sous-espaces prometteurs en définissant
dynamiquement des politiques de priorités de branchement sur les
variables, ainsi que sur les valeurs que peuvent prendre les variables. Cette
politique d'apprentissage est plutôt contraire aux techniques
d'apprentissage basées sur la notion de « NoGood », qui
cherchent quant à elles, à mémoriser les configurations
qui mènent à des échecs et à ne pas reproduire ces
échecs. Nous avons de plus montré qu'une phase de sondage,
permettant d'avoir un aperçu de l'arbre de recherche, pouvait
s'avérer intéressante afin d'initialiser la recherche. Enfin,
nous avons montré qu'il était possible d'appliquer cette approche
aussi bien sur des problèmes de satisfaction de contraintes que sur des
problèmes d'optimisation combinatoire. Pour cela, il suffit d'adapter
les critères d'apprentissage. Nous avons pu illustrer
l'intérêt de mettre en place des stratégies de branchement
sur les variables, ainsi que sur les valeurs, dans le but
d'accélérer la résolution d'un problème par
recherche arborescente.
Dans la deuxième partie de ce mémoire, nous nous
sommes intéressés à une classe de problèmes de
tournées de véhicules, que nous avons nommée
Problèmes de Tournées avec Couverture Partielle. Ces
problèmes sont caractérisés par le fait que la visite de
l'ensemble des sommets du graphe n'est pas obligatoire. Les problèmes
appartenant à cette classe sont NP-difficiles. Nous avons introduit un
nouvel opérateur de voisinage large, nommé Dropstar, qui
détermine par un algorithme de programmation dynamique la
sous-séquence optimale d'un chemin dans un graphe. Nous avons
montré
que la recherche d'une sous-séquence optimale pouvait
être un problème NP-difficile, sous certaines conditions. Nous
avons montré sur des exemples simples que l'opérateur que nous
présentons définit un voisinage de très grande taille. En
intégrant cet opérateur dans des algorithme basés des
métaheuristiques (algorithmes mémétiques et algorithmes
d'optimisation par colonies de fourmis), nous avons globalement obtenu de
meilleurs résultats que les résultats publiés à ce
jour. Nous avons enfin montré les moyens que nous avions à notre
disposition pour accélérer la résolution du
problème de recherche d'une sous-séquence optimale. Cette partie
illustre donc l'efficacité d'utiliser une approche d'hybridation entre
des méthodes heuristiques et un opérateur de grand voisinage,
basé sur une méthode exacte.
Dans la troisième partie du mémoire, nous avons
proposé une résolution par génération de colonnes
tronquée pour un problème complexe de transport. Il s'agit du
problème de Tournées de Véhicules avec Contraintes de
Chargement en Deux Dimensions, problème qui se retrouve
fréquemment en entreprise. La principale difficulté de ce
problème réside dans les contraintes de chargement. En effet, ce
sous-problème est un problème NP-difficile. Devant la
complexité de ce sous-problème qui intervient dans le
problème esclave du Branch & Price, ce problème
n'est pas résolu par une approche exacte. Nous avons alors montré
un aperçu des possibilités qu'il existait pour tronquer la
méthode de Branch & Price, qui est une méthode a priori
exacte. Les approches heuristiques que nous proposons ont permis
d'accélérer la résolution. Les résultats que nous
avons présenté sont comparables en terme de qualité et en
terme de temps d'exécution aux algorithmes publiés à ce
jour. Cependant, les heuristiques de chargement retenues ne permettent pas de
dépasser les meilleurs solutions connues.
Les résultats obtenus montrent l'intérêt
des méthodes proposées et laissent entrevoir les nombreuses
perspectives ouvertes par ce type d'hybridation. En ce qui concerne la
première partie, nous aimerions consacrer du temps à la recherche
de critères permettant de définir la qualité d'un
sous-arbre d'une recherche arborescente. Ces critères devront de plus
être génériques pour permettre une application aussi bien
dans le cas de problèmes de satisfaction de contraintes que dans celui
de problèmes d'optimisation combinatoire.
En ce qui concerne la deuxième partie, une
première perspective est de définir avec plus de
précisions la classe des problèmes de Tournées avec
Couverture Partielle. En particulier, les recherches pourront porter sur la
détermination de la complexité de la recherche d'une
sous-séquence optimale en fonction des ressources. Nous avons vu en
effet que la recherche d'une sous-séquence optimale pouvait aussi bien
être un problème NP-difficile que polynomial, ceci en fonction des
ressources. Enfin, nous aimerions travailler sur d'autres problèmes de
cette classe, dans l'objectif de mesurer l'efficacité de
l'opérateur de grand voisinage que nous avons proposé sur un plus
grand nombre de problèmes. La deuxième perspective de cette
partie concerne une extension de l'opérateur que nous avons
proposé. Nous pensons qu'il est possible de proposer un opérateur
d'insertion de sommets non visités, basé sur les mêmes
principes que l'opérateur Dropstar. Ainsi, une méthode
couplant les deux opérateurs pourrait explorer un voisinage de
très grande taille.
Enfin, en ce qui concerne la troisième partie,
l'application industrielle des travaux n'est pas encore
concrétisée. Nous aimerions cependant travailler sur une
résolution exacte du sous-problème de chargement, cela dans
l'objectif de proposer une résolution exacte du problème de
Tournées de Véhicules avec Contraintes de Chargement par
génération de colonnes.
Nous nous sommes efforcés dans ce mémoire
d'apporter des éléments de réponses
aux trois questions suivantes, en particulier pour une classe de
problèmes de transport: - Comment favoriser l'obtention rapide de
solutions dans les méthodes de recherche
arborescente?
- Comment utiliser des méthodes exactes au sein des
métaheuristiques? - Comment tronquer des méthodes exactes?
Une des perspectives les plus intéressantes et les plus
complexes serait de proposer des réponses à la question suivante
: Comment rendre exact un schéma de résolution heuristique pour
obtenir une garantie d'optimalité (ou de performance) des solutions
trouvées?
| 
