Optimisation de Tourn�es de V�hicules Et de Personnels de Maintenance

Cette these, fruit d'un contrat de recherche avec Generale des Eaux, porte sur le probleme de tournees de service multi-periodes avec fenetres de temps et flotte limitee. Nous proposons plusieurs methodes de resolution approchees, ainsi qu'une methode optimale. La methode optimale est basee sur la generation de colonnes. Une des methodes approchees est un algorithme memetique base sur une heuristique egalement developpee dans cette these. Enfin, la methode optimale est derivee en methode approchee par l'utilisation d'une heuristique pour la resolution du sous-probleme. Les algorithmes proposes permettent d'apporter des solutions efficaces a des problemes comportant jusqu'a 300 clients, dans des temps variant de quelques secondes a quelques dizaines de minutes. Dans un second temps, nous appliquons ces methodes a des scenarios issus de problematiques reelles, dans une logique d'aide a la decision.