Le problème de tournées de véhicules est un problème d'optimisation
combinatoire NP-difficile classique aux nombreuses variantes et aux
nombreuses applications industrielles. Le but est de générer les
tournées d'une flotte de véhicules afin de réaliser des visites de
clients.

Les approches de résolution les plus répandues pour ces problèmes sont
des méthodes de recherche locale. À partir d'une solution réalisable,
un voisinage est défini, modélisant un ensemble de solutions
réalisables semblables à la première. Dans ce voisinage, une solution
est choisie, souvent de bonne qualité, parfois simplement la
meilleure.

Chez Kardinal, nous traitons des problèmes de tournées de véhicules
très riches et très différents. La richesse des contraintes rend
l'utilisation des méthodes exactes très complexes, c'est pourquoi nous
nous sommes tournés vers les méthodes de recherche locale. Bien que
rapides et efficaces dans la plupart des cas, elles ont leurs limites:
elles sont rarement efficaces pour la minimisation du nombre de
véhicules. C'est pourquoi nous nous sommes penchés sur la génération
de voisinages plus vastes, afin de pouvoir répondre, entre autres, à
cette problématique.