Couplage des méthodes d'agrégation dynamique de contraintes et de stabilisation pour résoudre le problème d'horaires de véhicules avec dépôts multiples.

La méthode de génération de colonnes est très utilisée pour résoudre des problèmes de programmation linéaire. Cependant elle présente des faiblesses face aux effets de la dégénéréscence rencontrée sur certains problèmes de grande taille. Plusieurs approches ont été proposées pour contrer ses effets négatifs, en particulier l'agrégation dynamique de contraintes et la stabilisation des variables duales. Ce travail propose une méthode permettant de coupler ces deux approches pour les problèmes de partitionnement d'ensemble afin de tirer parti de leurs effets combinés. La dégénéréscence apparaît lorsque le polytope des solutions réalisables contient des points extrêmes associées à plusieurs bases, ou de manière équivalente lorsque des solutions basiques contiennent des variables en base nulles. L'idée de l'agrégation dynamique de contraintes est de travailler avec une restriction du problème original qui comporte moins de contraintes. En conséquence, la taille des bases est réduite ainsi que le nombre de variables de base nulles. Cependant, la réduction du nombre de contraintes entraîne une perte d'information duale. Une des difficultés majeures de cette méthode est de désagréger l'information duale partielle disponible afin d'obtenir une solution duale au problème original. Elhallaoui et al. (2005) montrent que pour les problèmes de partitionnement d'ensemble, il est possible d'effectuer cette opération en résolvant un problème de plus court chemin. La méthode de stabilisation des variables duales propose quant à elle de pénaliser une grande partie de l'espace dual. Comme chaque base est associée à une solution duale, on évite ainsi l'exploration des bases les plus pénalisées. Cependant, le problème ainsi « stabilisé » est une relaxation du problème original. Pour résoudre ce dernier à l'optimalité, il faut résoudre une suite de problèmes stabilisés. Coupler les méthodes d'agrégation dynamique de contraintes et de stabilisation des variables duales revient à réduire le nombre de contraintes des problèmes stabilisés. Malheureusement, l'information duale ainsi obtenue est partielle non seulement pour les contraintes du problème original, mais aussi pour la pénalité. Dans ce travail, nous montrons comment désagréger l'information duale par la résolution d'un problème de plus court chemin pour les problèmes de partitionnement d'ensemble stabilisés . Cette nouvelle méthode est appliquée au problème d'horaires de véhicules avec dépôts multiples (MDVSP). C'est un problème de partitionnement d'ensemble auquel s'ajoutent des contraintes supplémentaires limitant le nombre de véhicules disponibles par dépôt. La taille des instances utilisées varie entre 500 et 3000 tâches. On obtient une réduction des temps de calcul d'un facteur d'environ 2 pour la résolution de la relaxation linéaire sur les instances de grande taille.