Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité

Integral Flows and Aggregated Multicommodity Flows

Bât. ISIMA, BP 125, Campus des Cézeaux, Université Blaise Pascal, 63173 Aubiere, France ; alain.quilliot@isima.fr

Reçu : 2002
Accepté : 12 Septembre 2005

Résumé

Nous modélisons ici plusieurs problèmes de Transport et de Gestion de Flux à l'aide d'un flot entier et d'un multiflot fractionnaire couplés par une contrainte de capacité. Pour le problème ainsi obtenu, nous proposons différents schémas de résolution par relaxation et décomposition, qui induisent la recherche d'un flot auxiliaire dont la partie entière supérieure doit minimiser un certain coût, et qui requièrent la mise en œuvre d'un processus d'agrégation. Nous en déduisons diverses heuristiques que nous testons.

Abstract

We present here a Flow/Multicommodity Flow model for Transportation and Production Planning problems. We deal with this model through Lagrangean Relaxation and Hierarchical Decomposition techniques, which involve the resolution of a specific flow with least integral cost sub-problem, and which require the design of some agregation process. We deduce from this analysis several heuristic schemes, and we conclude by discussing numerical experiments.