New Algorithm Permitting the Construction of an Effective Spanning Tree

• Autorzy: Belkacem Salima Nait , Abbasy Moncef

Identyfikatory

DOI

10.2478/fcds-2023-0012

• Języki publikacji: EN

Abstrakty

EN

In this paper, we have done a rapid and very simple algorithm that resolves the multiple objective combinatorial optimization problem. This, by determining a basic optimal solution, which is a strong spanning tree constructed, according to a well-chosen criterion. Consequently, our algorithm uses notions of Bellman’s algorithm to determine the best path of the network, and Ford Fulkerson’s algorithm to maximise the flow value. The Simplex Network Method that permits to reach the optimality conditions manipulates the two algorithms. In short, the interest of our work is the optimization of many criteria taking into account the strong spanning tree, which represents the central angular stone of the network. To illustrate that, we propose to optimize a bi-objective distribution problem.

Słowa kluczowe

EN

bi-objective minimum cost flow problem; network flows; linear programming; minimum spanning tree; efficient extreme point

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2023
• Tom: Vol. 48, No. 3
• Strony: 313--329
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Belkacem Salima Nait

• Département de Recherche Opérationnelle, Faculté de Mathématiques, Université des sciences et de la Technologie Houari Boumedienne, Bab-Ezzouar (Algérie)
• Faculté des Hydrocarbures et de la Chimie, Université M’Hamed Bougara, Boumerdes (Algérie)

autor

Abbasy Moncef

• STHB, Faculté des Mathématiques, / Laboratoire AMCD&RO

Bibliografia

• [1] Ahuja R. K., Magnanti T. L., Orlin J. B., Network flows: Theory, algorithm, and applications. Prentice-Englewood Cliffs, 1993.
• [2] Cunningham W. H., A network simplex method, Mathematical Programming, 11, 1976, 105-116.
• [3] Eusébio A., Figueira J. R., Ehrgott M., On finding representative non-dominated points for the bi objective integer network flow problems, Computers & Operations Research, 48, 2014, 1-10.
• [4] Geoffrion A. M., "Proper efficiency and the theory of vector maximization", Journal of Mathematical Analysis and Application, 22, 1968, 618-630.
• [5] Hamacher H. W., Pedersen C. R., Ruzika S., Multiple objective minimum cost flow problems: a review, European Journal of Operational Research, 176, 2007, 1404-1422.
• [6] Lee H., Pulat S., Bi criteria network flow problems: continuous case, European Journal of Operational Research, 51, 1991, 119-126.
• [7] Lee H., Pulat S., Bicriteria network flow problems; Integer case, European Journal of Operational Research, 66, 1993, 1488-157.
• [8] Nait Belkacem S., An Algorithm for Choosing Ordering a New Criteria of a Bi Objective Flow Problem, Foundations of Computing and Decision Sciences, 46, 2021, 11-26. DOI: 10.2478/fcds-2021-0002.
• [9] Nait Belkacem S., Contribution à la Résolution du Problème de Flot Multi Objectif URI, Mémoire de Magister, Mathématique, Université des Sciences et Technologie Houari Boumedienne Algérie, 2007, 81. http://hdl.net/123456789/3195.
• [10] Raith A., Ehrgott M., A two-phase algorithm for the bi objective integer minimum cost flow problem, Computers and Operations Research, 36, 2009, 1945-1954.
• [11] Sedeno-Noda A., Gonzalez-Martin C., An algorithm for the bi-objective integer minimum cost flow problem, Computers and Operations Research, 28, 2001, 139-156.
• [12] Sedeno-Noda A., Gonzalez-Martin C., The bi-objective minimum cost flow problem, European Journal of Operational Research, 124, 2000, 591-600.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).