Le problème NP-difficile de l'ordonnancement de véhicules a fait l'objet d'une attention particulière ces dernières années. Alors qu'une approche directe par programmation linéaire en nombres entiers ou programmation par contraintes s'avère très souvent inefficace, plusieurs méthodes d'optimisation locale ont au contraire démontré leur efficacité. Nous décrivons ici une nouvelle approche par recherche locale à voisinage large basée sur la programmation linéaire en nombres entiers. Cette approche a notamment été éprouvée lors du Challenge ROADEF'2005 sur un problème d'ordonnancement de véhicules proposé par le constructeur RENAULT, plus complexe que le problème habituellement traité dans la littérature. Pour comparaison, nous décrivons aussi une méthode de recherche locale à petit voisinage, en l'occurrence la méthode qui nous a permis de remporter le Challenge ROADEF'2005.