Optimisation des tournées de véhicules combinées à la gestion de stock

Abstract

Dans le problème de la collecte des conteneurs de déchets recyclables, une flotte de véhicules est affectée à collecter un seul produit sur différents sites. Chaque site a son propre taux d’accumulation et sa capacité de stockage. A chaque visite, le stock est vidé. Dans la phase de planification tactique, nous cherchons une solution périodique qui est répétée dans le temps. L’objectif est de minimiser la taille de la flotte et les coûts de transport tout en donnant un découpage régional de l’espace par une partition des sites entre les véhicules. Au terme d’une analyse comparative nous proposons une modélisation adéquate. La structure du problème est exploitée pour développer une approche de décomposition de Dantzig-Wolfe. Des plannings périodiques sont générés pour les véhicules en résolvant un problème de sac-à-dos à choix multiple. L’élaboration des plannings de collecte pour les sites est traitée dans le programme maître. Ce dernier est reformulé en termes de variables agrégées pour éviter la symétrie en temps. Les bornes duales sont calculées par une méthode tronquée de Branch-and-Brice-and-Cut. Les bornes primales sont obtenues par des heuristiques d’arrondi et de recherche locale développées dans le contexte de la génération de colonnes. Des instances réelles sont résolues avec une déviation à l’optimalité raisonnable.