Modification of Algorithm of Directed Graph Paths Decomposition with Schedule

30

Abstract

This study aims to refinement of the oriented graph paths decomposition algorithm. An additional constraint on the balance parameter is considered to take into account the locomotive departure schedule. Also new rule to compute Ns parameters is given. An example of the operation of the oriented graph paths decomposition algorithm with the schedule is given. The scientific and practical novelty of the work lies in a significant reduction in the dimension of the original problem, which is especially important in the conditions of transport networks of complex topology.

General Information

Keywords: optimization theory, graph optimization, algorithm of directed graph paths decomposition, strongly connected graph, scheduling theory.

Journal rubric: Optimization Methods

Article type: scientific article

DOI: https://doi.org/10.17759/mda.2021110203

For citation: Zolotarev I.A., Rasskazova V.A. Modification of Algorithm of Directed Graph Paths Decomposition with Schedule. Modelirovanie i analiz dannikh = Modelling and Data Analysis, 2021. Vol. 11, no. 2, pp. 51–58. DOI: 10.17759/mda.2021110203. (In Russ., аbstr. in Engl.)

References

  1. Gainanov D.N., Kibzun A.I., Rasskazova V.A. The Decomposition Problem for the Set of Paths in a Directed Graph and Its Application. Automation and Remote Control, 2018, vol. 79, no. 12, pp. 2217–2236
  2. Zolotarev I.A., Rasskazova V.A. Practical Realization of Algorithm of Oriented Graph Paths Decomposition. Modelling and Data Analysis, 2020. Vol. 10, no. 3, pp. 60–68.

Information About the Authors

Igor A. Zolotarev, Master's Student, Moscow Aviation Institute (NRU MAI), Moscow, Russia, ORCID: https://orcid.org/0000-0002-6437-2212, e-mail: yngvar.antonsson@gmail.com

Varvara A. Rasskazova, PhD in Physics and Matematics, Associate Professor of Department 804 "Probability Theory and Computer Modeling", Moscow Aviation Institute, (NRU MAI), Moscow, Russia, ORCID: https://orcid.org/0000-0003-4943-3133, e-mail: varvara.rasskazova@mail.ru