Le problème de la planification des mouvements de terre par engins de terrassement est une extension d'un des tous premiers problèmes de recherche opérationnelle connu sous le nom de problème de transport optimal de masse, encore appelé problème de Monge-Kantorovich. Ce problème, initialement introduit par Monge en 1781 dans son Mémoire sur la théorie des déblais et des remblais, est revisité par Kantorovich en 1942 et formalisé par Dantzig en 1949. Dans notre cas, il s'agit de planifier des ressources réalisant des mouvements de terre entre des ouvrages placés sur un axe linéaire pendant plusieurs mois.
Ce problème d'optimisation a été soumis en 2009 au Bouygues e-lab par DTP Terrassement, qui est l'un des leaders du terrassement en France. Egalement présente à l'international, cette filiale de Bouygues Construction conduit des projets de terrassement en Afrique, en Europe de l'Est, etc. Ses activités vont du chantier de proximité au terrassement de routes, d'autoroutes, de lignes ferroviaires à grande vitesse ou encore de mines à ciel ouvert. L'entreprise gère une flotte de 900 engins dont 600 à l'étranger. Afin d'optimiser ces matériels et les plannings de réalisation des opérations, DTP Terrassement souhaitait planifier de la meilleure facon possible les mouvements de terre à réaliser pendant la durée de ses chantiers linéaires (routes, autoroutes et lignes ferroviaires), c'est-à-dire respecter les contraintes du cahier des charges tout en minimisant le nombre de ressources à mobiliser pour effectuer ces mouvements de terre.
Un chantier linéaire peut être vu comme un axe horizontal composée de 50 à 400 ouvrages. Les ouvrages sont de deux types : les déblais d'où l'on doit extraire des matériaux et inversement les remblais où l'on doit ramener des matériaux. Chaque ouvrage est défini par son centre de gravité sur l'axe, la liste des couches de matériaux le composant ou devant le composer. Pour chaque couche, on connaît la quantité de matériaux associée. Un mouvement de terre consiste à déplacer une certaine quantité du matériau d'une couche origine vers une couche destination, pendant une période inclue dans les fenêtres de temps autorisées pour ce mouvement. La durée d'un mouvement de terre peut varier de quelques jours à plusieurs mois. Pour les réaliser, on utilise des ressources appelées échelons, qui sont des engins de terrassement combinant des fonctions d'extraction et de transport. On connaît la liste des échelons permettant de réaliser chaque mouvement de terre. Le rendement d'un échelon est exprimé en volume traité par unité de temps et considère l'ensemble des moyens de terrassement associé à l'échelon pour le définir. Chaque ressource est disponible suivant un calendrier journalier tenant compte des contraintes de disponibilité de les engins, des heures de travail des compagnons habilités à les conduire, ainsi que des prévisions météorologiques.
Une des difficultés majeure du problème réside dans le fait que les matériaux constituants les ouvrages en déblais et en remblais doivent être déplacés et mis en oeuvre dans un ordre qui ne correspond pas toujours à l'ordre d'extraction (la couche inférieure rocheuse d'un déblais, c'est à dire la dernière extraite, peut-être utilisée en fond de remblais, c'est-à-dire la première mise en oeuvre). Ces précédences croisées vont nécessiter l'utilisation de dépôts provisoires où l'on va stocker les matériaux récupérés afin de les utiliser plus tard une fois les autres matériaux déplacés. à partir de la description du chantier et des ressources disponibles, le problème consiste à déterminer l'emploi du temps quotidien de chaque ressource affectée à chaque activité. Ce problème global d'optimisation comprend plusieurs enjeux : minimiser le moment total de transport (le produit de la quantité transportée par la distance entre les ouvrages source et destination), et minimiser le nombre de ressources utilisées tout en garantissant l'équilibrage du volume de travail quotidien et l'enchainement continu des échelons. Un chantier peut contenir jusqu'à 400 ouvrages, 2000 mouvements de terre, 30 échelons sur une échelle temporelle pouvant dépasser les 2 ans, ce qui rend le problème extrêmement difficile à résoudre sans outil informatique adapté.
L'algorithme produit des solutions quasi optimales en quelques minutes de temps de calcul sur un ordinateur standard. Cet algorithme repose sur une technique de résolution connue en optimisation combinatoire sous le nom de "recherche locale". Développé en partenariat avec DTP Terrassement, le logiciel de planification intégrant cet algorithme est aujourd'hui en exploitation. Ce logiciel, outil d'aide à la décision pour les ingénieurs des Méthodes, permet de planifier efficacement un grand chantier de terrassement en testant divers scénarios de données (disponibilité des engins, conditions météorologiques, etc.).