Programmation primale en nombres entiers pour la résolution efficace d'un problème de tournées de véhicules riche : théorie et pratique

Concilier enseignement théorique et réalités professionnelles ; telle est la mission de la recherche opérationnelle. Résoudre une problématique complexe avec toutes les contraintes du monde réel est d'une grande difficulté, qui requiert une méthodologie de recherche rigoureuse doublée d'une perspective d'intervention toujours présente. Concrètement, les problèmes industriels sont beaucoup plus complexes dans la réalité que ce qu'ils sont en théorie. Une bonne solution réalisable au sens mathématique n'a pas la même signification en pratique. Un bon algorithme pour l'industrie doit réunir des capabilités telles la rapidité, la fiabilité, la flexibilité et la simplicité. Le problème de tournées de véhicules (VRP : vehicle routing problem) constitue un sujet impérieux de la recherche opérationnelle. Il représente en effet la traduction mathématique d'innombrables applications de la vie courante. Nous nous emploierons à résoudre une problématique de transport prépondérante chez la majorité des prestataires de services logistiques qui, rappelons-le, sont des facilitateurs intégrés dont la mission est de gérer les opérations logistiques de plusieurs donneurs d'ordre. Ils planifient notamment la circulation d'une légion de commodités le long de réseaux logistiques très complexes. C'est dans ce contexte que les VRPs sont particulièrement riches en contraintes, et très difficiles à résoudre. Un défi qui a progressivement édifié notre projet. Après une analyse approfondie des flux et une cartographie logistique, le maillon faible de la chaîne a été identifié, en l'occurrence la livraison du dernier kilomètre. Celle-ci implique la distribution d'une marchandise variée depuis un centre de distribution urbain vers une panoplie de clients finaux (grande distribution, détaillant, particulier, etc.). Jusqu'à ce jour, les efforts se sont plutôt concentrés à modéliser ces difficultés comme un VRP riche, incluant un large spectre de contraintes endogènes (capacité, véhicules hétérogènes, fenêtres de temps, etc.) et exogènes (règles de la profession, options de livraison, compatibilité, etc.). Toutefois, une solution ne peut être réellement implémentable que si elle est en concordance avec les configurations opérationnelles et managériales. Les méthodes de résolution des VRPs sont scindées en des méthodes heuristiques, et des méthodes exactes. Les méthodes heuristiques parviennent généralement à réaliser un bon compromis entre la qualité et le coût de la solution, mais tout en exigeant un effort substantiel pour raffiner les valeurs des paramètres. En contrepartie, les méthodes exactes garantissent l'optimalité, mais peinent à résoudre les variantes riches du VRP. L'examen de l'état de l'art montre que, à l'encontre des méthodes exactes de Branch-and-Price, les méthodes primales exactes sont très peu abordées. La présente thèse serait la première implémentation des méthodes primales exactes dans un contexte de VRP riche et réel. Nous avons utilisé et adapté un algorithme de génération de colonnes en nombres entiers dit ICG (ICG : integral column generation) qui combine un algorithme primal dans un schéma de génération de colonnes. Composé de quatre modules séquentiels, chacun coopère pour trouver une solution entière optimale ou presque optimale, sans avoir recours aux méthodes traditionnelles tels le branchement ou l'ajout des coupes. Cette capabilité est l'un des facteurs clés de réussite, qui a permis la résolution efficace d'un problème réel et difficile. Dans la première contribution, nous avons réussi une première implémentation de ICG dans le cadre d'un VRP réel avec fenêtres de temps, flotte hétérogène interne et externe, contraintes de compatibilité de sites et un éventail de règles de métiers. Le problème maître (PM) a été formulé comme un problème de partitionnement d'ensembles SPP (SPP : set partitioning problem), et le sous-problème (SP) a été modélisé comme un problème de plus court chemin avec contraintes de ressources, modélisé sur un graphe orienté cyclique. Dans ICG, le problème maître restreint (PMR) est résolu à l'aide de l'algorithme primal ISUD (ISUD : integral simplex using decomposition), tandis que le SP est résolu à l'aide de la programmation dynamique. ISUD décompose le PMR en deux sous-problèmes. Le problème réduit (PR) contient les colonnes compatibles avec la solution entière courante S, et cherche une solution entière améliorante. D'autre part, le problème complémentaire (PC) contient les colonnes incompatibles avec S et vise à trouver des directions de descente entières. Littéralement, une colonne est dite compatible avec S si elle peut s'écrire comme combinaison linéaire des colonnes de la solution, sinon elle est dite incompatible. Les résultats de l'expérimentation, conduite sur sept journées opérationnelles, ont fait surgir aussi bien le potentiel d'amélioration de la méthode, que la nécessité de répondre à des questions relevant du fondement théorique. Dans la deuxième contribution, la performance de ICG a été hissée en opérant deux stratégies d'amélioration : (i) au niveau du SP, nous avons proposé une modélisation intelligente et réaliste du réseau de distribution cyclique. Ceci a été performé grâce à une analyse affûtée des caractéristiques des clients et de l'historique des livraisons. Cette amélioration a permis d'économiser une partie considérable du temps investi pour résoudre les SPs. (ii) D'autre part, nous avons évité d'utiliser le branchement en implémentant une stratégie dite de multiphase, qui consiste à résoudre le PC uniquement pour les colonnes qui se trouvent à une certaine distance de la solution courante. Dans la majorité des itérations, le PC trouve directement des directions qui mènent vers des solutions entières. Pour le reste, le module de recherche de voisinage permet souvent d'aboutir rapidement à une solution entière dans le voisinage de la solution courante. Finalement, vu son éventuelle influence sur la performance de l'algorithme,il était crucial d'analyser, aussi bien théoriquement qu'empiriquement, la qualité de la solution duale que nous utilisons. La performance confirmée de l'algorithme a été démontrée sur 30 instances réelles d'un VRP riche, incluant jusqu'à 199 clients, et ce en comparaison avec une méthode duale fractionnaire de type Branch-and-Price. Tous les résultats ont fait l'objet de tests rigoureux et dont la réalisabilité a été testée et validée en pratique. À travers cette thèse, notre objectif ultime est de proposer non seulement un algorithme efficace, mais également la stratégie propice pour le mettre en place dans la pratique. La troisième contribution se veut d'apporter une brique manquante à la méthodologie de résolution des VRPs dans le milieu pratique. Nous avons capitalisé notre expérience dans une étude de cas réelle, qui étudie la problématique de VRP sous la perspective d'un prestataire logistique intégré. La stratégie expliquée et les outils exposés constituent un guide utile pour mener à bien la résolution d'un VRP en pratique tout en mettant à jour un savoir-faire bienvenu auprès de la communauté des chercheurs et des étudiants. Dans la dernière contribution, nous avons présenté une étude initiale portant sur deux pistes d'amélioration susceptibles de renforcer la performance de la méthode primale ICG. L'objectif ultime serait d'implémenter une technique efficace de telle sorte que la recherche des solutions entières se fasse dans des voisinages potentiels, et ce, sans pénaliser le temps total de calcul. Dans un premier temps, nous avons implémenté une première approche dite ZOOM, où le processus de recherche est guidé par une direction de descente fractionnaire. Les résultats numériques préliminaires ont clairement montré que ZOOM a considérablement amélioré la performance de ICG. Ceci nous a conduits à proposer une seconde approche, qui consiste à remplacer ZOOM par une heuristique. Dans un premier temps, nous avons testé la viabilité d'une heuristique hybride adaptative, dite H-ALNS (H-ALNS : Hybrid Adaptive Large Neighbourhood Search) sur nos instances. Les résultats obtenus ont révélé que l'heuristique n'est relativement performante que sur les petites instances. Ce constat nous a incités à proposer des dispositifs adéquats afin de réussir l'incorporation de H-ALNS à ICG. Ces techniques exploitent les informations de nature duale et primale pour décider des arcs à éliminer. En effet, les arcs coûteux, longs ou rarement empruntés seraient dynamiquement enlevés. L'implémentation d'une telle stratégie d'hybridation est une piste de recherche qui est en cours d'exploration. Les résultats des contributions réalisées jusqu'ici témoignent de la viabilité de la piste de recherche explorée dans le cadre de ce projet de recherche. Avec ces aboutissements, nous avons droit de penser que la programmation primale en nombres entiers est un paradigme facilement transférable en pratique, qui mérite d'être amplement employé afin de résoudre efficacement des VRPs riches.

Abstract

The mission of operational research is to reconcile theoretical knowledge and practical business realities. Solving a complex problem with real-world constraints is very difficult, requiring a rigorous research methodology coupled with an unfailing intervention perspective. In practice, industrial problems are much more complex than they are in theory. A good feasible solution in the mathematical sense is not the same in practice. A practical algorithm for industry must combine capabilities such as speed, reliability, adaptability and simplicity. The vehicle routing problem (VRP) is a compelling topic for operational research. It represents the mathematical description of countless applications in everyday life. We aim to solve a major transport problem arising within most logistics service providers. The latter have the mission to manage the logistics operations of several contractors. In particular, they schedule the routing of a huge number of commodities across extremely complex logistics networks. In this context, VRPs are particularly rich in constraints, and very difficult to tackle. Such a challenge has gradually built up our project. After an extensive flow analysis and logistics mapping, the weak leg of the value chain was identified, namely the last mile delivery. This involves the distribution of a variety of goods from urban distribution centers to a range of end consumers (supermarkets, retailers, individuals, etc.). To date, efforts have tended to focus on modeling this problem as a rich VRP, encompassing a wide range of constraints such as time windows, heterogeneous fleet, business rules, delivery options, and compatibility. Nevertheless, a proper solution can be implemented only if it is in line both with operational and managerial configurations. The methods for solving VRPs are split into heuristic methods and exact methods. Heuristic methods generally manage to achieve a good compromise between the quality and the cost of the solution, but require a substantial effort to refine the parameters values. On the other hand, exact methods guarantee optimality, but are struggling to solve the rich variants, and are restricted to tractable problems. Examination of the state of the art showed that, in contrast to dual fractional methods, very little attention has been devoted to exact primal methods. The present thesis would be the first successful deployment of exact primal methods in a rich and real VRP context. We have used and adapted the integral column generation (ICG) algorithm, which combines a primal algorithm in a column generation scheme. Composed of four modules, each one cooperates to find an optimal or near-optimal integer solution, without using traditional methods such as branching or adding cuts. This capability is one of the key success factors, which enabled the effective resolution of a difficult real-world problem. In the first contribution, we successfully performed a first implementation of ICG in the context of a real VRP problem with time windows, internal and external heterogeneous fleet, site compatibility constraints and a range of business rules. The master problem was formulated as a set partitioning problem (SPP), and the sub-problem (SP) was modeled as a shortest path problem with resource constraints, modeled on a cyclic oriented graph. ICG is a sequential algorithm where the restricted master problem (RMP) is solved using the integral simplex using decomposition (ISUD) algorithm, while the SP is solved using dynamic programming. ISUD decomposes the RMP into two sub-problems. The complementary problem (CP) contains the incompatible columns, and aims at finding integer descent directions. On the other hand, the reduced problem (RP) deals with the compatible columns and looks for an improving integer solution. Literally, a column is said to be compatible with a solution S if it can be written as a linear combination of its columns, otherwise it is said to be incompatible. The computational results, conducted over seven operational days, highlighted both the potential for improvement of the method and the need to address theoretical underlying issues. In the second contribution, ICG's performance was enhanced by operating two improvement strategies: (i) at the SP level, we proposed an intelligent and realistic modeling of the cyclic distribution network. This was achieved through a careful analysis of the customers' characteristics and the historical delivery records. This improvement saved a considerable amount of time invested in solving the SPs. On the other hand, (ii) we avoided using branching by implementing a so-called multiphase strategy, which consists in solving the CP only for columns which are at a specific distance from the current solution. In the majority of iterations, the CP directly found directions leading to integer solutions. For the rest, the Neighborhood Search module generally leads quickly to an integer solution in the neighborhood of the current solution. Finally, given its possible impact on the performance of the algorithm, it was crucial to analyze, both theoretically and empirically, the quality of the dual solution we have used. The well-proven performance of the algorithm was demonstrated on 30 real instances of a rich VRP, with up to 199 clients, in comparison with a Branch-and-Price method. All results have been carefully tested and practically validated for feasibility. Through this thesis, our main purpose is to propose not only an efficient algorithm, but also the appropriate strategy to put it into practice. The third contribution aims to provide a methodology of solving VRPs in the practical environment. We have capitalized on our experience through a real-life case study, which explores the problem of VRP from the perspective of an integrated logistics provider. The strategy outlined and the described tools provide a useful guide to successfully resolve a VRP in practice, while at the same time updating a know-how that is welcomed by the research community and its students. In the last contribution, we presented an introductory study for further improvements to enhance the performance of the primal ICG method. The idea is to implement an efficient technique so that the search for integer solutions is conducted in potential neighborhoods, yet without penalizing the total computing time. As a first step, we have deployed a first technique called ZOOM, where the search process is guided by a fractional descent direction. Preliminary numerical results clearly showed that ZOOM has significantly improved ICG performance in terms of computing time. Next, we applied a hybrid adaptive heuristic called H-ALNS (H-ALNS: Hybrid Adaptive Large Neighbourhood Search). To begin with, we tested the viability of the heuristic on our instances. The results achieved then prompted us to consider a suitable hybridization strategy, offering a good compromise between the heuristic's properties and those of an exact primal method. This subject is still an ongoing research topic. The results of the contributions made so far testify to the viability of the research topic that was explored in this thesis. Thus, we believe that integer primal programming paradigm is easily transferable in practice and that merits to be widely employed in solving rich VRPs models.