Recherche locale pour l'optimisation en variables mixtes :
Méthodologie et Applications industrielles

Thèse sous la direction scientifique de Philippe Baptiste du Laboratoire d'Informatique de Polytechnique (Equipe "SYSMO" du LIX) - Soutenance : 23 Septembre 2011.

Ce projet de thèse s'inscrit dans la continuité des travaux de recherche opérationnelle débutés en Master à l'Université d'Oklahoma (USA) avec Suleyman Karabuk et poursuivis ces dernières années au sein du Bouygues e-lab, département de R&D en informatique du Groupe Bouygues.

Soutenue publiquement le 10 Octobre 2011 devant un jury composé de :

Philippe Baptiste & Directeur de recherche, CNRS LIX (Directeur de Thèse)

Thierry Benoist & Ingénieur, Bouygues e-lab (Co-directeur de Thèse)

Jacques Carlier & Professeur, Université Technologique de Compiègne (Rapporteur)

Frédéric Gardi & Ingénieur, Bouygues e-lab (Co-directeur de Thèse)

Léo Liberti & Professeur chargé de cours, Ecole Polytechnique (Examinateur)

Alain Quilliot & Professeur, ISIMA, Université Clermont II (Examinateur)

Francis Sourd & Ingénieur (HDR), SNCF Innovation & Recherche (Rapporteur)

Michel Vasquez & Enseignant-chercheur (HDR), Ecole des Mines d'Alès (Rapporteur)

Voir Le manuscrit de thèse

Voir Les slides de la soutenance

Résumé

De nombreux problèmes industriels comportent à la fois des dimensions combinatoire et continue. Lorsqu'ils sont de grande taille, ces problèmes mixtes sont souvent résolus par décomposition en sous-problèmes. Les décompositions les plus fréquentes reposent sur les spécificités ``métier'' du problème. La programmation mathématique fournit également des méthodes formelles de décomposition. Toutefois, ces approches ont des inconvénients en pratique : difficulté de garantir la qualité voire l'admissibilité des solutions, complexité technique de mise en oeuvre et complexité logicielle en cas d'utilisation de solveurs de programmation mathématique. Dans cette thèse, nous proposons une approche directe, par recherche locale, des problèmes d'optimisation en variables mixtes. Notre méthodologie se focalise sur deux points : la définition d'une large variété de mouvements assurant une diversification combinatoire et une évaluation incrémentale fondée sur des algorithmes approchés mais très efficaces en temps, traitant simultanément les dimensions combinatoire et continue du problème.

Après une introduction détaillant cette méthodologie, nous en présentons une premi ère application dans un cadre purement combinatoire : l'optimisation de la gestion de stock de banches sur les chantiers de construction (Bouygues Habitat Résidentiel). Puis, nous l'appliquons sur un problème d'ordonnancement de mouvements de terre pour le terrassement d'autoroutes et de voies ferrées (DTP Terrassement). Il s'agit de planifier sur un horizon de plusieurs années des tâches avec précédences à l'aide de ressources contraintes par des fenêtres de temps. Ce problème est résolu par recherche locale, une de ses caractéristiques étant que les quantités de terre déplacées peuvent passer d'une tâche à une autre tandis que les dates d'affectation de celles-ci sont simultanément modifiées. Le logiciel, aujourd'hui en exploitation, permet la planification de grands chantiers linéaires en quelques minutes. Nous étudions également le cas à une ressource correspondant à un problème de voyageur de commerce linéaire avec précédences. Ce dernier est prouvé NP-complet ; nous proposons alors un algorithme par programmation dynamique, exponentiel mais efficace en pratique. Les solutions obtenues nous ont permis d'apprécier l'effectivité de la recherche locale.

Enfin, nous traitons un problème de tournées de véhicules avec gestion des stocks, posé par un client industriel du Groupe Bouygues. Ce problème consiste en l'optimisation des coûts de distribution d'un produit fluide par camion, sur des zones géographiques comptant plusieurs centaines de clients dont la gestion des stocks est confiée au fournisseur. Une heuristique de recherche locale est proposée pour résoudre le problème à court terme (15 jours) en quelques minutes. Afin d'assurer une optimisation sur le long terme, nous introduisons une fonction objectif de remplacement fondée sur un calcul de bornes inférieures. L'originalité de notre approche réside dans le fait que les quantités livrées au cours des tournées peuvent varier alors même que ces dernières sont modifiées géographiquement ou temporellement. Nous nous appuyons également sur un algorithme approché de réaffectation des volumes, un millier de fois plus rapide en pratique qu'un algorithme exact de flot maximum. L'exploitation de ce logiciel, quotidienne et à l'échelle mondiale, a permis une réduction des coûts logistiques de l'ordre de 15%.

Mots clés. Recherche locale, optimisation en variables mixtes, ordonnancement de tâches, tournées de véhicules avec gestion des stocks.

Local search for mixed-integer optimization methodology et industrial applications

Many industrial problems today combine continuous and combinatorial dimensions. These mixed variable optimization problems are often solved by decomposing them into sub-problems, especially when they are large. Most of the common decomposition techniques are based on practical specificities of the problem. Mathematical programming also provides formal decomposition methods. However, these decomposition approaches have practical drawbacks: difficulties in guaranteeing the quality or even feasible solutions, high technical complexities of development projects, and high software complexities while using mathematical programming solvers. In this thesis, we propose a direct approach for solving these mixed variable optimization problems using a local search method. Our methodology focuses on two points: the definition of a large pool of varied moves to ensure combinatorial diversification and an incremental evaluation based on approximate, yet time efficient, algorithms. The combinatorial and continuous dimensions are addressed simultaneously.

Following the introduction of our methodology, Chapter 2 presents the application in a pure combinatorial context, the minimization of formwork stocks on construction sites (Bouygues Habitat Residentiel). In Chapter 3, we rely on this methodology to optimize earthwork scheduling for highway and railway projects (DTP Terrassement). The schedules count hundreds of earthmovings planned over a horizon of several years, using resources constrained by time windows. This problem is solved by a local search heuristic with a special feature: the amounts of soil displaced can move from one task to another, while the assignment dates of these tasks are also changed simultaneously. Within minutes, the algorithm computes an earthwork plan in such real-life projects. We also investigate a single-resource case corresponding to a line traveling salesman problem with precedences, proved here as NP-hard. Then, we introduce a dynamic programming algorithm which is exponential, but effective in practice. The analysis of this single-resource case helps to assess the effectiveness of the local search.

Finally, we consider a inventory routing problem, posed by the industrial customer group, Bouygues. Inventory routing refers to the optimization of transportation costs for the replenishment of customers' inventories: based on consumption forecasts, the vendor organizes delivery routes. A local search heuristic is able to provide a proposed solution the problem for the short term (15 days) in minutes. In order to ensure savings in the long term, we introduce a new surrogate objective function based on long-term lower bounds. The approach is original in that the quantities delivered during tours can vary even when they are geographically or temporally altered. We also use a volume allocation algorithm which is a thousand times faster in practice than an exact maximum flow algorithm. Confirming the promised gains in operations (15% on average), the resulting decision support system is progressively deployed worldwide.

Key words. Local search, mixed-variable optimization, task scheduling, inventory routing.