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.

Column generation is a widely used method for solving linear programming problems. It is very efficient but shows some weaknesses when faced with highly degenerate problems. Stabilization of dual variables and dynamic constraint aggregation are two examples of approaches used to damp the effects of degeneracy. This work shows how two combine the strength of both for set-partitioning problems. Degeneracy occurs when the polyhedron of feasible solutions contains degenerate extreme points. An extreme point is degenerate when it can be described by multiple basis, which means that these basic solutions contain basic variables with zero value. The idea behind dynamic constraint aggregation is to use a restricted problem with fewer constraints. Thus the size of the basis is reduced along with the number of zero variables. However some dual information is lost when reducing the number of constraints. The challenge of this method is to desaggregate the partial dual information and compute a dual solution for the original problem. For set-partitioning problems, Elhallaoui et al. (2005) shows that this computation can be done by solving a shortest-path problem. Dual variables stabilization consists of penalizing most of the dual space. Since every basis is associated with a dual solution, this amounts to prevent the exploration of most penalized basis. Yet such a “stabilized” problem is a relaxation of the original one. In order to find an optimal solution, a sequence of stabilized problems needs to be solved. Stabilization and dynamic constraint aggregation are brought together by reducing the number of constraints of stabilized problems. Unfortunately, this yields to partial dual information not only for the removed constraints, but also for penalty values. In this work, we show how to disaggregate dual information by solving a shortest-path problem for stabilized set-partitioning problems. This new method is applied to the multiple depot vehicle scheduling problem (MDVSP). It is a set-partitioning problem with side constraints that limit the number of vehicles used from each depot. Experiments were conducted on randomly generated instances which sizes range between 500 and 3000 tasks. Results show a reduction of computational times by a factor 2 approximately for large instances.

Résumé

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.