ИСТИНА

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