Я. А. Зиндер, А. А. Лазарев, Е. Г. Мусатова, И. А. Тарасов, “Построение расписаний двухстороннего движения на однопутной железной дороге с разъездом”, Автомат. и телемех., 2018, выпуск 3,страницы 144

Эта публикация цитируется в 8 статьях

Оптимизация, системный анализ и исследование операций

Построение расписаний двухстороннего движения на однопутной железной дороге с разъездом

Я. А. Зиндер^a, А. А. Лазарев^bcde, Е. Г. Мусатова^b, И. А. Тарасов^bc

^a Технологический университет, Сидней, Австралия
^b Институт проблем управления им. В. А. Трапезникова РАН, Москва
^c Московский государственный университет им. М. В. Ломоносова
^d Национальный исследовательский университет "Высшая школа экономики", Москва
^e Московский физико-технический институт (государственный университет)

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

Ключевые слова: динамическое программирование, полиномиальный алгоритм, железнодорожное планирование, теория расписаний.

Статья представлена к публикации членом редколлегии: В. М. Вишневский

Поступила в редакцию: 17.05.2017