Resolution par decomposition d’un probleme de transport special
Joint Authors
Source
Sciences et Technologie : Sciences Exactes
Issue
Vol. 2003, Issue 20 (31 Dec. 2003), pp.39-44, 6 p.
Publisher
Publication Date
2003-12-31
Country of Publication
Algeria
No. of Pages
6
Main Subjects
Topics
Abstract EN
A special transportation problem is addressed.
We show it is NP-hard.
Using Lagrangian decomposition of part of the constraints, we transform it into an integer minimum cost flow with homologous arcs problem that we solve by a Branch-and-Bound technique.
A Lagrangian dual is defined by relaxing the coupling constraints.
A standard subgradient algorithm is employed to solve the latter, the value of which provides a lower bound on the value of the objective function value of the original problem.
A least-lower-bound-next dichotomous branching strategy is utilized for generating the decision tree.
Our algorithm is tested on a set of twenty-five randomly generated instances.
Abstract FRE
Dans cet article, on étudie un problème de transport spécial qu’on appelle problème de transport à destinations groupées.
On montre qu’il est NP-dur.
On propose ensuite une décomposition lagrangienne d’une partie des contraintes qui permettra de le réduire à un problème équivalent de flot entier à arcs homologues.
On présente alors une méthode par séparation et évaluation pour résoudre ce dernier.
La procédure d’évaluation est fondée sur la résolution du dual lagrangien par une méthode de sous-gradients.
La fonction lagrangienne considérée est obtenue en relaxant les contraintes d’arcs homologues.
Des résultats numériques obtenus sur plusieurs problèmes engendrés aléatoirement sont présentés.
American Psychological Association (APA)
Haddadi, S.& Benchettah, A.. 2003. Resolution par decomposition d’un probleme de transport special. Sciences et Technologie : Sciences Exactes،Vol. 2003, no. 20, pp.39-44.
https://search.emarefa.net/detail/BIM-540568
Modern Language Association (MLA)
Haddadi, S.& Benchettah, A.. Resolution par decomposition d’un probleme de transport special. Sciences et Technologie : Sciences Exactes No. 20 (Dec. 2003), pp.39-44.
https://search.emarefa.net/detail/BIM-540568
American Medical Association (AMA)
Haddadi, S.& Benchettah, A.. Resolution par decomposition d’un probleme de transport special. Sciences et Technologie : Sciences Exactes. 2003. Vol. 2003, no. 20, pp.39-44.
https://search.emarefa.net/detail/BIM-540568
Data Type
Journal Articles
Language
French
Notes
Includes bibliographical references : p. 44
Record ID
BIM-540568
