Оптимизация трафика движения на железнодорожном узле: применение подходов, основанных на временных сетях Петри

Введение

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

С другой точки зрения, выделение повторяющихся сценариев (расписания движения ежедневного автобуса, метро или поезда) является одной из форм циклического планирования. Данные темы вызывают возрастающий интерес нескольких команд в регионе Нор-Па-де-Кале во Франции (LAMIH/ROI, LAGIS/SED, LABOGP), а сами темы были предметом нескольких исследований, применяющих различные модели (сети Петри, задачи удовлетворения граничных условий, линейные задачи оптимизации), методы (анализ сетей Петри, программирование с учетом ограничений, линейная оптимизация), а также инструменты

Глава написана Томасом Бордедчу и Бенуа Трулле.

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

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

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

Данная проблема является фактором, который ограничивает применение некоторых алгоритмов анализа, например, тех, которые вызывают множественные ложные решения. Это особенно пагубно сказывается на методах, основанных на построении и пересечении графа достижимости сети Петри, так как данная проблема может возникнуть позднее в последовательности выполнения сети Петри. Примечательно, что данное явление является сильным ограничением для классических алгоритмов планирования и являлось предметом диссертации Dama- sceno lDAM 99J. Мы решили обратиться к ней, поскольку считаем, что наш подход способен справиться с данной проблемой естественным образом.

Для решения задачи достижимости в сетях Петри были использованы различные методы. Среди данных методов мы даем ссылку заинтересованному читателю на работу Rauhamaa [РАУ 90J. В данной главе мы подробно остановимся на двух взаимодополняющих подходах, которые позволяют нам решить задачу достижимости в синхронизированных сетях Петри.

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

В разделах 5.4 и 5.5 мы развили два подхода предлагаемого решения, проведя некоторое количество экспериментов для проверки подхода. В заключение мы приведем некоторые научно-исследовательские перспективы.

Остальная часть главы организована следующим образом: в разделе 5.2 мы обозначили вопросы, касающиеся проблем планирования, и показали, как решение железнодорожных задач корреляции может быть сведено к решению задачи планирования в универсальных системах. Мы формально определили временные сети Петри в разделе 5.3 и показали, как они могут отображать задачу корреляции железнодорожного узла естественным образом.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >