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