Branch-cut-and-price methods for the inventory routing problem

Les problèmes de tournées de véhicules (VRP) constituent un volet essentiel de la planification logistique. Les méthodes exactes applicables à la version classique de VRP avec contraintes de capacité (CVRP) ont connu, au cours des dix dernières années, des avancées significatives qui ont augmenté considérablement la taille des instances pouvant être résolues à l’optimalité de manière efficace. Ainsi, des instances standard du CVRP comptant plusieurs centaines de clients sont aujourd’hui résolues de manière optimale en quelques minutes. La situation est différente pour d’autres variantes du CVRP, en particulier celles qui intègrent des décisions de quantité livrée dans leur modélisation : pour certaines d’entre elles, des instances de moins de cent clients – voire quelques dizaines – restent difficiles. Dans notre travail, nous avons développé des algorithmes Branch-Cut-and-Price (BCP), référence actuelle pour la résolution exacte du CVRP, pour deux variantes intégrant des décisions de livraison : le VRP à livraisons fractionnées sans fenêtres de temps (SDVRP) et avec fenêtres de temps (SDVRPTW), ainsi que le problème de inventory routing (IRP). Dans la littérature, les meilleures approches pour ces variantes reposent principalement sur des algorithmes de type Branch-and-Cut (B&C). Nous avons donc conçu des algorithmes BCP capables d’adapter les composants les plus avancés du CVRP, dont nous avons expérimentalement comparé la performance à celles de B&C spécialisés. Pour le SDVRP, nous avons proposé une famille de formulations partiellement discrétisées qui représentent différentes quantités livrées aux clients. Les quantités ne sont pas explicites et la validité est garantie par un ensemble exponentiel de contraintes non robustes. Nous introduisons de nouvelles inégalités valides non robustes – les inégalités de couverture à mémoire limitée et les inégalités fortes de k-chemins à mémoire limitée – et montrons comment les gérer efficacement dans le sous-problème de pricing qui génère dynamiquement les variables de tournée. Les résultats numériques établissent un nouvel état de l’art pour le SDVRPTW : de nombreuses instances-tests de 50 et 100 clients sont résolues optimalement pour la première fois. Pour le SDVRP, plusieurs instances sont également closes à l’optimalité. S’agissant de l’IRP, nous présentons des contributions théoriques : une formulation entièrement discrétisée avec variables de sous-livraison et une nouvelle famille d’inégalités qui généralise celles déjà connues. Les expérimentations numériques sont encore en cours au moment de la rédaction de ce document. Nos résultats montrent que des algorithmes BCP soigneusement élaborés peuvent se révéler compétitifs – voire meilleurs – face aux codes B&C sur les variantes à livraisons fractionnées de VRP. Nous comptons valider numériquement dans un futur proche l’approche que nous avons développée pour la version IRP du problème.