Note publique d'information : Nous considèrerons ici les modèles linéaires de multiflots, en mettant l'accent sur
leurs multiples applications, notamment dans les domaines de l'ordonnancement et de
la gestion de production. Il est bien connu que ces problèmes, présentés sous forme
de programmes linéaires, sont difficiles à résoudre, contrairement à leurs homologues
en flot simple. Les méthodes de résolution classiques proposent, déjà dans le cas
continu, des solutions approchées. On distingue: les méthodes de décomposition par
les prix, par les ressources, ainsi que les techniques de partitionnement. Si l'on
rajoute la contrainte d'intégralité sur les flots, ces problèmes deviennent extrêmement
difficiles. Nous nous sommes intéressés à un cas particulier des problèmes de multiflots,
à savoir: le biflot entier de coût minimum. Nous avons développé une approche de résolution
heuristique basée sur un principe de décomposition mixte, opérant itérativement, à
la fois par une allocation de ressources et par un ajustement des coûts. L'implémentation
de cette approche met en évidence des résultats prometteurs, obtenus sur des problèmes
de biflot purs, générés aléatoirement. Nous avons donc envisagé une deuxième application
sur des problèmes de biflot plus structurés. Ces problèmes de biflot ont été proposés
pour la modélisation du problème de voyageur de commerce. Cette application débouche
d'une part, sur l'utilisation d'un algorithme de recherche d'un circuit hamiltonien
dans un graphe, et d'autre part, sur le développement de techniques heuristiques pour
la construction de tournées intéressantes
paprika.idref.fr
data.idref.fr
Documentation
