Algorithmes de génération de colonnes avec plans coupants pour des problèmes de tournées de véhicules à deux échelons

L’étude de la distribution de marchandises en zones urbaines a suscité beaucoup d’intérêt ces dernières années au sein de la communauté de la recherche opérationnelle. En effet, une planification minutieuse de ces activités contribue à réduire les charges sociales et environnementales placées sur les centres-villes tout en permettant de réaliser des économies d’échelle. Un moyen efficace pour atteindre ces objectifs est de diviser les chaînes d’approvisionnement en deux échelons, ce qui permet d’utiliser de gros véhicules en dehors du centre-ville et de plus petits dans le centre-ville. Cette thèse porte sur le développement d’approches de résolution exactes pour trois variantes du problème de tournées de véhicules à deux échelons : le problème de tournées de véhicules à deux échelons avec fenêtres de temps (2E-VRPTW) et deux de ses extensions, à savoir le problème de tournées de véhicules à deux échelons avec fenêtres de temps et commodités multiples (MC-2E-VRPTW) et le problème de tournées de véhicules à deux échelons avec fenêtres de temps, collectes et livraisons simultanées (2E-VRPTW-SPD). Dans ces problèmes, les véhicules de premier échelon assurent le transport des marchandises des dépôts centraux vers des dépôts intermédiaires, appelés satellites. Les véhicules de second échelon, plus petits que ceux de permier échelon et affectés à des routes commençant et terminant à un même satellite, desservent les clients à l’intérieur de leurs fenêtres de temps. En outre, les satellites n’ont pas de capacité d’entreposage et ne permettent pas la consolidation de fret, ce qui nécessite une synchronisation exacte des opérations (c’est-à-dire que les véhicules de premier et de second échelon doivent être présents simultanément aux satellites afin de permettre le transfert de marchandises). L’objectif est de déterminer un ensemble de routes de premier et de second échelon de moindres coûts, de sorte que chaque client soit desservi par un seul véhicule de second échelon pendant sa fenêtre de temps et que les contraintes liées à la2synchronisation des opérations au niveau des satellites soient satisfaites. Pour résoudre le 2E-VRPTW, nous développons un algorithme exact de génération de colonnes avec plans coupants (branch-price-and-cut, BPC) basé sur une formulation impliquant un grand nombre de routes de second échelon. Les sous-problèmes sont résolus à l’aide d’un algorithme d’étiquetage ad hoc qui génère des routes de second échelon, tout en respectant le schéma de synchronisation considéré aux satellites. Nous décrivons les ajustements nontriviaux à apporter à l’algorithme d’étiquetage afin de générer des variables associées à des routes de second échelon alimentées par des routes de premier échelon uniques. Pour accélérer le processus de résolution, nous proposons des inégalités duales, appelées inégalités de transfert, qui exploitent des informations spécifiques au problème afin de couper une partie de l’espace dual et de réduire le nombre d’itérations de génération de colonnes. L’algorithme BPC développé est capable de résoudre à l’optimalité, en trois heures de temps de calcul, des instances comportant jusqu’à trois dépôts, cinq satellites et 100 clients. De plus, de nouvelles solutions optimales sont trouvées pour 41 instances précédemment non résolues parmi 180 instances testées. Le MC-2E-VRPTW est une extension du 2E-VRPTW qui prend en compte un cas de figure rencontré en pratique où la demande de chaque client n’est disponible qu’à partir d’un dépôt central spécifique. Dans ce problème, les contraintes de synchronisation impliquent que la demande de chaque client doit être satisfaite par exactement un véhicule de premier échelon et un véhicule de second échelon. Cependant, il est possible qu’un véhicule de second échelon reçoive sa marchandise à partir de plusieurs véhicules de premier échelon. Pour résoudre ce problème, nous proposons un algorithme BPC adapté dans lequel la synchronisation des opérations est prise en compte au niveau des sous-problèmes. Pour résoudre ceux-ci, nous développons un algorithme d’étiquetage ad hoc générant des routes de second échelon tout en spécifiant la route de premier échelon ayant fourni la demande de chaque client visité. Nous proposons une règle de branchement adaptée au contexte de commodités multiples ainsi qu’une procédure de récupération assurant la faisabilité des solutions entières lorsque l’on considère les inégalités de transfert. Des instances comportant jusqu’à trois dépôts, cinq satellites et 100 dépôts sont résolues à l’optimalité en trois heures de temps de calcul. Enfin, le 2E-VRPTW-SPD aborde l’aspect des collectes et livraisons simultanées dans un contexte de deux échelons. Dans ce problème, chaque client a une demande de livraison, de collecte, ou les deux. De plus, la demande totale livrée (collectée) par un véhicule de second échelon est fournie (collectée) par un seul véhicule de premier échelon. Nous proposons un algorithme exact de type BPC pour ce problème. Nous considérons un sous-problème par satellite que nous résolvons via un algorithme d’étiquetage spécialisé. Chaque variable générée est associée à une route de second échelon et à une paire de routes de premier échelon. Nous appliquons des inégalités valides connues afin de renforcer les bornes inférieures obtenues et utilisons des inégalités de transfert pour accélérer la convergence de la génération de colonnes. Des instances comportant jusqu’à deux dépôts, trois satellites et 100 clients sont résolues à l’optimalité en trois heures de temps de calcul.