Abstract FR:

Nous nous sommes intéressés dans ces travaux à un problème de composition d'une flotte hétérogène de véhicules et la conception des tournées associées respectant des contraintes telles, la capacité des véhicules, les fenêtres de temps chez le client, les temps d'attente, etc. Après description du problème et sa modélisation pour une application particulière à la collecte postale, ainsi que toutes les caractéristiques et difficultés dont il faut tenir compte pendant sa résolution, nous présentons deux méthodes de résolution : une méthode exacte et une autre approchée. La méthode exacte est fondée essentiellement sur les techniques de génération de colonnes avec comme difficulté majeure, la résolution du sous-problème- plus court chemin contraint- pour lequel nous avons élabore un algorithme qui repose sur la programmation dynamique et l'exploration A*. La difficulté des instances traitées nous a poussé à construire une méthode approchée - méthode tabou à voisinage variable - qui repose sur un ensemble de mouvements, locaux et globaux, susceptibles de modifier considérablement la structure de la solution et de pouvoir traiter par conséquent des instances beaucoup plus grandes contrairement à la méthode exacte.