10.14489/vkit.2017.05.pp.051-056

DOI: 10.14489/vkit.2017.05.pp.051-056

Гайнанов Д. Н., Кибзун А. И., Рассказова В. А.
ТЕОРЕТИКО-ГРАФОВЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ О НАЗНАЧЕНИИ И ПЕРЕМЕЩЕНИИ ЛОКОМОТИВОВ
(c. 51-56)

Аннотация. Представлен алгоритм решения прикладной задачи о назначении и перемещении локомотивов, основанный на решении теоретико-графовой задачи о покрытии вершин ориентированного графа множеством путей. Разработаны алгоритм формирования множества максимальных (по включению) путей ориентированного графа и алгоритм покрытия вершин ориентированного графа множеством максимальных путей. Приведены результаты программной реализации алгоритма покрытия вершин ориентированного графа множеством максимальных путей.

Ключевые слова: назначение локомотивов; перемещение локомотивов; алгоритм; множество максимальных путей; покрытие вершин графа.

Gainanov D. N., Kibzun A. I., Rasskazova V. A.
THEORETICAL-GRAPH ALGORITHM IN THE PROBLEM ON THE ASSIGNMENTS AND TRANSPORTATIONS OF LOCOMOTIVES
(pp. 51-56)

Abstract. The article deals with the application problem on the assignments and transportations of locomotives. By the methods of graph theory, the problem on the assignments and transportations of locomotives can be reduced to a graph-theoretical problem of covering of vertices of a directed graph by the set of maximal by inclusion simple directed paths. It is introduced the directed graph of compatibility of transportations, and it is considered an approach to modelling of the application problem, which based on the properties of the directed graph of compatibility of transportations. In the view of the specific structure, the graph of compatibility of transportations has certain structural and combinatorial properties. It is proved an important statement, based on the properties of the directed graph, which is about the possibility of consideration of the set of binary sets a predetermined length, which corresponds to a set of simple directed paths of the graph. An algorithm for the constructing a set of simple directed paths of the graph is developed. For a given set of simple directed paths of the graph, there is settled the problem of constructing a set of maximal by inclusion simple directed paths, and an algorithm for solving the problem is developed. The set of maximal by inclusion simple directed paths is the basis of the algorithm of the covering of vertices of the directed graph of compatibility of transportations by the set of maximal by inclusion simple directed paths. The software complex, which implements the developed algorithms, is described by Visual Basic. The article presents the results of the computer implementation of software complex in the application problem on the assignments and transportations of locomotives.

Keywords: Assignments of locomotives; Transportations of locomotives; Algorithm; Set of maximal paths; Covering of vertices.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

Д. Н. Гайнанов (Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, Екатеринбург, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
А. И. Кибзун, В. А. Рассказова (Московский авиационный институт (национальный исследовательский университет), Москва, Россия)

Eng

D. N. Gainanov (Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
A. I. Kibzun, V. A. Rasskazova (Moscow Aviation Institute (National Research University), Moscow, Russia)

+ - Библиографический список (References) Click to collapse

Рус

1. Лазарев А. А. Оценки абсолютной погрешности и схема приближенного решения задач теории расписаний // Журнал вычислительной математики и математической физики. 2009. Т. 49, № 2. C. 14 – 34.
2. Лазарев А. А., Гафаров Е. Р. Преобразование сетевого графика задач теории расписаний с ограничениями предшествования // Доклады Академии Наук. 2009. Т. 424, № 1. C. 7 – 9.
3. Burdett O., Kozan E. A Disjunctive Graph Model and Framework for Constructing New Train Schedules // Eur. J. Oper. Res. 2010. V. 200. P. 85 – 98.
4. Gholami O., Sotskov Y. N. Mixed Graph Model and Algorithms for Parallel Machine Job shop Scheduling Problems // Int. J. Production Research. 2015. V. 8. P. 1 – 16.
5. Lusby R., Ryan D. Railway Track Allocation: Models and Methods // Oper. Res. Spektrum. 2011. V. 33. P. 843 – 883.
6. Гайнанов Д. Н., Рассказова В. А. Математическое моделирование в задаче оптимального назначения и перемещения локомотивов методами теории графов и комбинаторной оптимизации [Электронный ресурс] // Труды МАИ. 2017. № 92. URL: http://www.mai.ru/science/ trudy/published.php?ID=77259 (дата обращения: 18.04.2017).
7. Осипов С. И, Осипов С. С. Основы тяги поездов. М.: УМК МПС, 2000. 592 с.
8. Гайнанов Д. Н. Комбинаторная геометрия и графы в анализе несовместных систем и распознавании образов. М.: Наука, 2014. 152 с.
9. Гайнанов Д. Н., Рассказова В. А. Алгоритм расшифровки монотонных булевых функций, порожденных неориентированными графами // Вестник ЮУрГУ. 2016. Т. 9, № 3. С. 17 – 30.

Eng

1. Lazarev A. A. (2009). Evaluations of the absolute error and the scheme of the approximate solution of problems in scheduling theory. Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki, 49(2), pp. 14-34. [in Russian language]
2. Lazarev A. A., Gafarov E. R. (2009). Transformation of the network graph of the scheduling tasks with precedence constraints. Doklady Akademii Nauk, 424(1), pp. 7-9. [in Russian language]
3. Burdett O., Kozan E. (2010). A disjunctive graph model and framework for constructing new train schedules. Eur. J. Oper. Res, 200, pp. 85-98. doi: 10.1016/j.ejor.2008.12.005
4. Gholami O., Sotskov Y. N. (2015). Mixed graph model and algorithms for parallel machine job shop scheduling problems. Int. J. Production Research, 8, pp. 1-16.
5. Lusby R., Ryan D. (2011). Railway track allocation: models and methods. Oper. Res. Spektrum, 33, pp. 843-883. doi: 10.1007/s00291-009-0189-0
6. Gainanov D. N., Rasskazova V. A. (2017). Mathematical modeling in the problem of optimal assignment and displacement of locomotives using methods of graph theory and combinatorial optimization. Trudy MAI, 92. Available at: http://www.mai.ru/science/trudy/published.php?ID=77259 (Accessed: 18.04.2017). [in Russian language]
7. Osipov S. I, Osipov S. S. (2000). Traction of the trains. Basics. Moscow: UMK MPS. [in Russian language]
8. Gainanov D. N. (2014). Combinatorial geometry and graphs in the analysis of incompatible systems and pattern recognition. Moscow: Nauka. [in Russian language]
9. Gainanov D. N., Rasskazova V. A. (2016). Algorithm for decoding monotone Boolean functions generated by undirected graphs. Vestnik IuUrGU, 9(3), pp. 17-30. [in Russian language]

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2017.05.pp.051-056

и заполните ФОРМУ

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2017.05.pp.051-056

and fill out the FORM