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

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

К классу таких задач относятся следующие задачи: стратегическое проектирование инфраструктуры железнодорожной транспортной сети, управление парком вагонов и локомотивов, планирование расписаний и маршрутизации перевозок, повышения перевозочных возможностей железнодорожной системы, поиска узких мест и переформирование существующих расписаний (маршрутов движения) в случае временной недоступности части участков железной дороги.

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

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

В рамках предыдущих проектов была построена математическая модель формирования грузовых составов и составления расписания их движения. Данная задача была решена с помощью метода «генерации колонок». Решение задачи протестировано на примерах, основанных на реальных данных (свыше 15 тысяч вагон-заказов). Работы в данном направлении будут продолжены.

Фундаментальная научная проблема

Моделирование и оптимизация пассажирских и грузовых перевозочных процессов на РЖД. Разработка методов объемно-календарного планирования, маршрутизации пассажиро- и грузопотоков в железнодорожных сетях, управление трафиком. Разработка многоуровневых параллельных алгоритмов решения задач оптимального планирования. Оптимальное вложение алгоритмов обработки данных и вычислений в архитектуру распределенных информационно-управляющих многопроцессорных вычислительных систем (МВС).

Конкретная фундаментальная задача в рамках темы

Разработка эффективных методов решения прикладных задач оптимизации грузовых и пассажирских перевозок РЖД, в частности:

1. Оптимизация структуры железнодорожной транспортной системы для решения задачи максимизации объемов перевозок и минимизации времени доставки грузов, оптимизация структуры транспортных маршрутов для обеспечения большого объёма грузоперевозок;
2. Разработка алгоритмов эффективной диспетчеризации и маршрутизации потоков в железнодорожных сетях с учетом ограниченности ресурсов обслуживания (пути, разъезды, составы и др.);
3. Оптимизация времени выполнения операций формирования грузовых составов на сортировочных узлах;
4. Оптимизация движения железнодорожного транспорта при закрытых (например, ремонт или техническое обслуживание) сегментах железной дороги;
5. Оптимизация расписания работы экипажей и обслуживающего персонала с учетом производственных потребностей, прав и личных предпочтений работников РЖД;
6. Оптимизация использования порожних вагонов.

 Предлагаемые методы и подходы

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

Для решения поставленных задач будут использоваться современные эффективные методы программирования в ограничениях (Constraint programming), целочисленного программирования и графического подхода.

Укрупненный план работ на весь срок выполнения проекта:

Разработка модели транспортной системы и построение математических моделей для рассматриваемых задач формирования грузовых составов в сортировочных узлах и управления вагонопотоками в железнодорожных сетях, анализ эффективности использования существующей сети дорог, определение узких мест и оценка возможностей развития (октябрь 2013 - апрель 2014).

• Оптимизация структуры транспортной системы для решения задач максимизации объема перевозок и минимизации времени доставки грузов (декабрь 2013 - октябрь 2014).
• Управление формированием железнодорожных составов в узлах транспортной сети (январь 2014 - октябрь 2014).
• Разработка алгоритмов эффективной диспетчеризации и маршрутизации потоков в транспортных сетях (январь 2014 - ноябрь 2014).
• Задача управления грузовыми вагонопотоками в железнодорожных сетях (январь 2014 - декабрь 2014).
• Задача распределения групп исполнителей (локомотивных бригад и обслуживающего персонала РЖД) по дислокациям выполнения работ (апрель 2014 - декабрь 2014).
• Реализация разработанных алгоритмов (апрель 2014 - декабрь 2014).

Ожидаемые в конце 2013 года научные результаты

Будут разработаны:

• Математическая модель железнодорожной транспортной системы;
• Математическая модель для задачи составления плана формирования грузовых поездов;
• Математическая модель для задачи изменения маршрутов и расписания поездов в случае недоступности части путей вследствие ремонтных работ;
• Алгоритмы решения случая задачи изменения маршрутов и расписаний поездов на двухпутной железной дороге в случае временной недоступности некоторой части одной железнодорожной линии.

Результаты исследований будут опубликованы в ведущих отраслевых и научных журналах и представлены на научных конференциях.

Современное состояние исследований

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

Возникающие на практике задачи важны и для развития самой теории расписаний, поскольку многие из них стимулируют появление новых моделей, обогащающих не только теорию расписаний, но и дискретную оптимизацию в целом. Такие задачи постоянно привлекают к себе пристальное внимание исследователей. Теории расписаний и ее приложениям посвящена обширная литература, включающая десятки монографий и обзоров, опубликованные за последние 10 – 15 лет (см.: Brucker P. Scheduling Algorithms. Springer, 2007, 371 p.; Brucker P., Knust S. Complex Scheduling. Springer, 2006, 288 p.; Pinedo M.L. Scheduling: Theory, Algorithms, and Systems. Springer, 2008, 678 p.; Pinedo M.L. Planning and Scheduling in Manufacturing and Services. Springer, 2009, 537 p.; Herrmann J.W. (Editor) Handbook of Production Scheduling. Springer, 2006, 318 p.; Leung J.Y.-T. (Editor) Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall, 2004, 1120 p.; Chretienne P., Coffman E.G., Lenstra J.K., Liu Z. (Editors) Scheduling Theory and Its Applications, Wiley, 1995, 382 p.; Conway R.W., Maxwell W.L., Miller L.W. Theory of Scheduling. Dover Publications, Inc. 2003, 292 p.; Blazewicz J., Ecker K.H., Pesch E., Schmidt G., Weglarz J. Scheduling Computer and Manufacturing Processes. Springer, 2001, 472 p.; Scholl A. Balancing and sequencing assembly lines. Physica -Verlag, 1999, 318 p.; Tanaev V.S., Gordon V.S., Shafransky Y.M. Scheduling Theory. Single-Stage Systems. Kluwer Academic Publ., 1994, 372 p.). Работы в этом направлении ведутся практически во всех развитых европейских странах (Германия, Франция, Великобритания, Голландия, Италия, Испания, Польша, Португалия, Норвегия), США, Канаде, Мексике, Аргентине, КНР, Японии, Австралии и др. При этом в таких странах, как, например Германия, Франция, Великобритания, США количество соответствующих научных центров насчитывает несколько десятков. Участники проекта имеют давние и прочные связи (командировки, совместные исследования и публикации) со многими зарубежными центрами в
перечисленных странах.

Оценки оптимального значения дискретных задач оптимизации широко используются при построении численных методов оптимизации (типа branch-and-bound) а также при исследовании качества решений, полученных эвристическими алгоритмами. В настоящее время работы в этой области наиболее интенсивно ведутся в научных центрах Америки (Аргентина, Бразилия, Мексика, США) и Европы (Германия, Дания, Норвегия, Франция). Исследовательская группа поддерживает тесные контакты с этими научными коллективами, участники проекта неоднократно выступали с лекциями в этих научных центрах по тематике проекта.

Имеющийся у коллектива научный задел по предлагаемому проекту

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

Исполнителями проекта предложен "графический" метод решения задач комбинаторной оптимизации, который является развитием классического метода динамического программирования, основанного на принципе оптимальности Беллмана, и обоснована его теоретическая и практическая значимость (Лазарев А.А. Графический подход к решению задач комбинаторной оптимизации // Автоматика и телемеханика, 2007, №4, С. 13-23). Для трех классических комбинаторных задач (Ранец, Разбиение, задача минимизация суммарного запаздывания для одного прибора) на основе данного метода предложены точные алгоритмы решения, имеющие ряд преимуществ перед классическими алгоритмами динамического программирования, а также показавшие эффективность в ходе экспериментальных исследований (Lazarev A., Gafarov E. Werner F. A Modification of Dynamic Programming Algorithms to Reduce the Running Time or/and Complexity // Magdeburg, Germany, 2010, 24 c.).

Предложенный "графический" метод, был успешно применен для решения ряда задач теории расписаний. Оказалось, что при помощи данного метода для некоторых задач комбинаторной оптимизации можно значительно сократить трудоемкость их решения, если задача представима в виде задачи с булевыми переменными и известен псевдополиномиальный алгоритм решения. Более того, показано, что для некоторых таких задач, трудоемкость решения которых была неизвестна, можно построить полиномиальный алгоритм решения. Таким образом, например, была доказана полиномиальная разрешимость задачи максимизации суммарного запаздывания для одного прибора, а для задачи минимизации количества запаздывающих требований с различными моментами поступления требований предложен лучший из известных полиномиальный алгоритм нахождения приближенного решения (Lazarev A.A., Werner F., A Graphical Realization of the Dynamic Programming Method for Solving NP-Hard Combinatorial Problems // Computers and Mathematics with Applications, 2009, Vol. 58, No. 4, 619 -- 631; Lazarev A., Gafarov E., Werner F., A Polynomial Time Graphical Algorithm for Maximizing Total Tardiness on a Single Machine // Otto-von-Guericke Universitaet Magdeburg, Germany, 2010, 15 c.).

Для построения приближенных решений задач объемно-календарного планирования был разработан метод изменения параметров, который позволяет находить наилучшие приближенные решения из области допустимых (полиномиально разрешимых) решений. Имеются разработки графического метода решения задач дискретной оптимизации. Предлагается подход нахождения оценок значений целевой функции для решений задач дискретной оптимизации и теории расписаний на основе интерполяционных полиномов Лагранжа (на основе корней полинома Чебышёва) и сплайн функций.

В 2010 году коллектив ИПУ РАН по договору с Центральной дирекцией управления движением ОАО РЖД выполнил разработку предложений в Минтранс России по совершенствованию порядка оказания пользователям услуг железнодорожного транспорта и услуг инфраструктуры железнодорожного транспорта общего пользования. Разработанные предложения легли в основу нового нормативного документа федерального значения, определяющего механизмы и правила взаимодействия собственников железнодорожного транспорта и владельцев инфраструктуры. Исследованы вопросы взаимодействия разных уровней оперативного управления перевозочным процессом; цели и задачи каждого уровня управления; единая сквозная технология управления. Результаты исследования опубликованы в монографии.