Modification of the label method for problems of multicriterial optimization

Occupation: Senior Research Scholar
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Moscow, Russian Federation

Alina Belova

Occupation: undergraduate student
Affiliation: Moscow Power Engineering Institute
Address: Russian Federation

Journal name

Ekonomika i matematicheskie metody

Edition

Volume 56 Issue 1

Pages

95-99

Abstract

The label method (Deikstra method) allows to find the shortest way between two vertices of a graph with given lengths of edges. A modification of the method is proposed for the case when several characteristics are given for each edge, for example the time and the cost of the way. In multicriterial optimization problems different decision makers can choose different solutions, and as usually the preferences of decision maker are not formalized. So it is necessary to construct a sufficiently large set of Pareto-optimal ways. Such problems can be solved by interacive procedures formalizing the decision maker’s preferences and forming Pareto-optimal solutions. One approach to constructing of such procedure is proposed in the paper. This approach is based on the search of the way having the minimal value of one of the given criteria and satisfactory values of the remaining chiteria. If the obtained way is not satisfactory for the decision maker he formulates new conditions for the values of the criteria. The effecivity of the proposed procedure will be examined by calculating experiments.

Keywords

graph, label method, multicriterial optimization, Pareto-optimality

Received

05.03.2020

Publication date

20.03.2020

Number of characters

8386

Cite

GOST	Zaslavsky A., Belova A. Modification of the label method for problems of multicriterial optimization // Ekonomika i matematicheskie metody – 2020. – V. 56. – Issue 1 C. 95-99 [Electronic resource]. URL: https://emm.jes.su/S042473880008559-3-1 (circulation date: 20.04.2024). DOI: 10.31857/S042473880008559-3
MLA	Zaslavsky, Alexey, Belova, Alina "Modification of the label method for problems of multicriterial optimization." Ekonomika i matematicheskie metody 56.1 (2020):95-99. DOI: 10.31857/S042473880008559-3
APA	Zaslavsky A., Belova A. (2020). Modification of the label method for problems of multicriterial optimization. Ekonomika i matematicheskie metody 56(1), pp.95-99 DOI: 10.31857/S042473880008559-3

100 rub.

When subscribing to an article or issue, the user can download PDF, evaluate the publication or contact the author. Need to register.

Number of purchasers: 0, views: 992

Readers community rating: votes 0

1. Bellman R. (1958). On a routing problem (íåîïð.) // Quarterly of Applied Mathematics. 1958. Ò. 16. Ñ. 8790.

2. Cherkassky B.V., Goldberg A.V., Radzik T. (1996), Shortest past algorithms. // Math.Prog. Springer Science+Business Media 1996. Vol. 73, Iss. 2. P. 129174.

3. Galkina V.A.. (2003). Construction of shortest path in the oriented graph //Discrete Mathematics. Combinatort optimization in the graphs. Moscow, 2003. P. 7594. 232 p. (In Russian).

4. Hu T.C. (1970). Integer Programming and Network flows. Addison-Wesley Publishing Company. California-London.

5. Levit B.Ju., Livshits V.N. (1972). Non-linear transport problems. Moscow. 144 p. (In Russian).

6. Moore E.F. (1957) The shortest path through a maze// Proceedings of an International Symposium on the Theory of Switching 1957 Harvard University Press, 1959. Vol. 2. P. 285292. 345 p. Annals of the Computation Laboratory of Harvard University. V.30.

7. Podinovskij V.V., Nogin V.D. (1982). Paeto-optimal solutions of multicriterial problems. Moscow, Nauka. (In Russian).