Графовые методы решения задачи об оптимальном назначении локомотивов на линейном участке железной дороги — без ограничений и с ограничениями

Предложена новая графовая модель перевозок на линейном участке железной дороги. На основе заданного графика перевозок грузовых составов строится ациклический граф, вершины которого обозначают перевозки, а дуги — возможность последовательного осуществления их некоторым локомотивом. Такая модель задачи позволяет применить для нахождения оптимального плана назначений локомотивов статические графовые алгоритмы. Поиск решения в задаче без временных ограничений на локомотивы сводится к поиску минимального покрытия ациклического графа путями. Каждый путь в покрытии соответствует последовательности перевозок, осуществляемых одним локомотивом. При наличии временных ограничений на локомотивы (их уход на техническое обслуживание) не все пути в найденном покрытии могут остаться допустимыми — для некоторых локомотивов ни одна из найденных последовательностей перевозок не может быть выполнена от начала до конца. В этом случае добавляется еще один этап решения, на котором найденное покрытие преобразуется таким образом, что все новые пути описывают последовательности перевозок, которые можно осуществить данным множеством локомотивов с заданными временными ограничениями.