La planification des véhicules dans un environnement multi-dépôts est un problème important du transport public. Bien que de nombreuses approches de résolutions aient été publiées dans la littérature, les premières métaheuristiques pour traiter ce problème ne sont apparus que très récemment. [5] (recherche taboue et recherche locale à voisinage large).Dans ce travail, nous introduisons un algorithme de recherche locale itérée pour la planification des véhicules, intégrant plusieurs composants particuliers: -un puissant algorithme par enchères pour l'obtention de la solution initiale, -un opérateur de voisinage qui constitue une forme de chaîne d'éjections [2], -un mécanisme de perturbation en deux étapes. Cet algorithme a permis l'obtention de résultats compétitifs par rapport à ceux de l'état de l'art sur un ensemble de benchmarks de la littérature.