Оцінка обчислювальної складності задачі автоматизації розрахунку графіку руху поїздів

Abstract

UA: У статті досліджено теоретичну обчислювальну складність алгоритму вирішення задачі розрахунку графіку руху поїздів. Розглянуто можливість здійснення оцінки в межах теорії обчислювальної складності, що має велике практичне значення в умовах існування потужних електронно-обчислювальних машин. Задача розрахунку графіку руху поїздів може розглядатися як задача потокового календарного планування, доведено належність даної задачі до класу NP-повних відносно числа конфліктів у розкладі, тобто неможливо побудувати алгоритм рішення задачі, час роботи якого зростає не швидше, ніж деякий поліном від розміру вихідних даних.

EN: The paper studies the theoretical computational complexity of the algorithm for solving the problem of calculating the train schedule. We consider the complexity of the task of building the train schedule for single-and doubletrack section. Evaluation of the task can be performed within the computational complexity theory. The task of calculating the train schedule can be viewed as a problem of scheduling streaming, this task proved to belong to the class NP - complete with respect to the number of conflicts in the schedule, that it is impossible to construct an algorithm for solving the problem, the work which has been growing faster than a polynomial in the size of the original data. These results confirm the need to create an algorithm for the calculation of the train schedule, with the help of which we could find the schedule of trains, close to optimal, within a reasonable time frame and which can be implemented as a computer program and the possibility of using heuristic algorithms.