СПОСОБ ДЛЯ ПЛАНИРОВЩИКА ДВИЖЕНИЯ НА ОСНОВЕ МОДЕЛИРОВАНИЯ
METHOD OF SCHEDULING MOTION USING SIMULATION

Область техники
Это раскрытие направлено на планировщика движения, разработанного для решения задач планирования скрещений-обгонов или планирования движения.
Уровень техники
План движения представляет собой подробный план для движения составов в железнодорожной сети за предопределенный промежуток времени. План движения начинается со списка запланированных действий, таких как моменты времени, соответствующие началу движения, завершению движения, смене бригады поезда, замене локомотива, остановке состава, назначенной работе, инспекции и т.п. На основе запланированных действий планировщик движения формирует такие события, как скрещения, обгоны, пересечение путей на одном уровне, запланированная задержка и безопасный интервал. Скрещение-обгон включают в себя планирование местоположений скрещений, в которых составы, движущиеся в противоположных направлениях, могут разойтись друг с другом. Он также включает в себя определение местоположений обгонов, в которых быстрый состав может обогнать более медленный состав, движущийся в том же направлении. В настоящее время диспетчеры обычно разрабатывают планы движения вручную. Однако такая ручная разработка планов движения не отвечает требованиям эффективного планирования движения для работы крупномасштабной железной дороги.
Деятельность современных железных дорог класса 1 обычно включает в себя от тридцати до шестидесяти тысяч миль путей и управление от одной до пяти тысяч составов в день. Железные дороги обрабатывают смешанные перевозки, в том числе перевозки бестарного груза, контейнерные перевозки, грузовые перевозки с ограничениями по номенклатуре грузов, перевозки автомобилей, пассажирские и другие перевозки, каждые из которых имеют свои собственные характеристики расписания. Обычно работа железной дороги разбита на географические участки с централизованными диспетчерскими центрами, управляющими каждым участком. Таким образом, один состав, пересекающий много участков, встречает много диспетчеров на своем пути. Общая проблема, связанная с этим типом планирования составов, состоит в том, что цели могут не иметь связь между участками, и план движения, который выглядит хорошо для одного диспетчера, может фактически повредить деятельности всей железной дороги в целом.
Для вычисления плана движения требуется множество данных, в том числе расписание поездов и эксплуатационные расходы, топология железнодорожной сети, ограничения скорости и блокировки путей, текущий статус составов и ввод данных диспетчером. Алгоритм планирования использует все эти данные для формирования близкого к оптимальному способа движения составов.
Один подход предшествующего уровня техники, использующий компьютеризированный планировщик движения, использует методику, известную как модельная "закалка". Согласно этому способу внесенные в расписание поездки для всех составов располагают с использованием времени выполнения без препятствий. Затем планировщик итерационно вставляет или удаляет случайную задержку в случайные моменты времени поездки, выполняя поиск максимального полного планового значения. Затем планировщик выполняет поиск более хорошего плана, пока не будет достигнуто максимальное количество попыток или пока отличие полного планового значения от предыдущего плана не станет статистически несущественным.
Настоящее раскрытие направлено на компьютеризированного планировщика движения, который использует компьютерное моделирование для моделирования подробностей задачи, в том числе топологии путей, расписаний поездов и действий. Компьютеризированный планировщик создает план движения, начинающийся в текущий момент времени, всегда гарантируя выполнимость. Она достигает этого посредством пошагового перемещения составов по одному за короткий промежуток времени и повторяет этот процесс, пока составы не достигнут своих пунктов назначения или пока не будет достигнут конец горизонта планирования.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Фиг.1 - упрощенное иллюстрированное представление цикла планирования движения для одного варианта воплощения настоящей заявки.
Фиг.2 - упрощенное иллюстрированное представление графика составов, обеспеченное одним вариантом воплощения настоящей заявки.
Фиг.3 - упрощенная блок-схема последовательности операций одного варианта воплощения настоящей заявки.
ПОДРОБНОЕ ОПИСАНИЕ
Для вычисления плана движения требуется множество данных, в том числе расписание поездов и эксплуатационные расходы, топология железнодорожной сети, ограничения скорости и блокировки пути, текущий статус составов и ввод данных диспетчером.
Как показано на Фиг.1, оперативные задачи 100 могут включать в себя расписания поездов, приоритеты составов и эксплуатационные расходы. Настоящее раскрытие гарантирует, что составы достигают своих пунктов назначения вовремя при соблюдении приоритетов составов, которые могут быть динамическими по природе, для минимизации общих расходов, понесенных при движении составов. Чтобы гарантировать, что оперативные цели достигаются, планировщику в качестве входных данных нужны расписания поездов, включающие в себя пункты отправки и назначения, приоритеты составов, моменты времени смен бригад поездов и желательные местоположения замен бригад поездов.
Планировщик также гарантирует, что он соблюдает несколько ограничений 110 при разработке плана движения. Частичный список таких ограничений включает в себя:
Ограничения на основе топологии путей:
• Блокировки путей (бессрочные или зависящие от времени)
• Ограничения скорости (бессрочные или зависящие от времени)
• Ограничения переключений (бессрочные или зависящие от времени)
• Ограничения по высоте, весу и ширине
• Ограничения вспомогательных путей (множество составов, пересечения)
Ограничения, зависящие от составов:
• Приоритеты составов
• Изменения расписания поездов
• Требования производительности - максимально возможные скорости
• Специальные составы - специальное управление составами, перевозящими опасные материалы и т.д.
Требования по управлению деятельностью:
• Замены бригад поездов
• Действия на станциях
• Другие действия на пути и вне пути, в том числе комбинированные, связанные и вспомогательные составы.
Планировщик может принимать статус 120 в реальном времени пути и действий на станции, в том числе отчеты о местоположении, отчеты о задержке, преграды пути и отчеты о составе и бригаде. Планировщик должен также учитывать инициированные диспетчером ограничения 130, такие как разрешения для состава и фиксированные местоположения скрещения и обгона, при формировании плана движения. На основе этих входных данных технический эффект состоит в том, что настоящее раскрытие формирует подробный план 140 движения всех включенных в расписание составов по топологии путей по горизонту планирования для каждого состава. План включает в себя расписание для выполнения всех действий над составами, в том числе скрещения, обгоны, пункты отправления и назначения составов, назначенная работа, инспекция, замена бригад поездов, замена локомотивов и т.д.
Фиг.2 иллюстрирует один пример плана движения, сформированного посредством настоящего раскрытия. График составов представляет собой инструмент для визуализации плана движения. Путь, проходящий от одного конца к другому, представлен вдоль оси у 200. Метки на оси у представляют собой станции вдоль пути. Время представлено вдоль оси x 210. Каждая линия на графике показывает местоположения одного состава в различные моменты времени. Направленные снизу вверх линии 220 представляют составы, движущиеся в направлении вверх, и направленные сверху вниз линии 230 представляют составы, движущиеся в направлении вниз. Наклон линий в любой заданный момент времени представляет собой скорость состава в этот момент времени. Местоположения скрещений и обгонов также могут быть выявлены из графика составов, на котором ожидающие составы имеют нулевую скорость 240.
Настоящее раскрытие использует подробную имитационную модель, которая моделирует топологию пути и движение составов. Затем оно строит расписания для каждого состава в этой среде моделирования, перемещая составы систематическим образом из их текущих местоположений в начале цикла планирования в направлении их соответствующих пунктов назначения. При разработке планов движения должно быть принято много решений. Эти решения включают в себя путь, по которому каждый состав должен следовать от пункта отправления до пункта назначения, местоположения скрещений и обгонов в горизонте планирования, местоположения, в которых должны выполняться такие действия, как замена бригады поезда, и т.д. Для каждого из этих решений имеется много возможных вариантов выбора. Задача составления реального плана движения чрезвычайно сложна. Формирование хорошо выполнимых и устойчивых решений является очень трудным. Многие попытки, которые были сделаны ранее для решения этой задачи, имели ограниченный успех. Настоящее раскрытие систематически исследует область поиска в среде моделирования для получения хорошего решения, которое является надежным.
Как показано на Фиг.3, в одном варианте воплощения настоящее раскрытие разрабатывает предпочтительный маршрут для каждого состава (этап 300). Предпочтительный маршрут представляет собой наилучший возможный маршрут, которым должен следовать состав для достижения всех своих целей оптимальным образом. В дополнение к предпочтительному маршруту формируют несколько альтернативных маршрутов, которые обходят участки предпочтительного маршрута (этап 310). Выбирается один из составов (этап 320) для моделирования его движения. Состав для движения может быть выбран на основе нескольких критериев, в том числе приоритета состава, задержки, которой состав уже подвергся, степень продвижения состава и т.д. В одном варианте воплощения состав может перемещаться до тех пор, пока он не достигнет пункта принятия решения (этап 330). Пункт принятия решения представляет собой пункт, в котором для состава могут быть доступны более одного маршрута, в том числе переключатель, где у состава имеется выбор следовать по одному из двух или более различных участков пути, которые доступны в том пункте, таких как запасной или дополнительный пути. В других вариантах воплощения состав может быть перемещен на предопределенное количество модельного времени, или пока не возникнет ситуация, когда он не может быть перемещен далее по его предпочтительному маршруту из-за отсутствия пути вследствие одной из многих причин. Эти причины включают в себя блокировки путей, пути, занятые другими составами, и т.д. Когда состав перемещен в пункт принятия решения, выполняется оценка относительно дальнейшего движения состава (этап 340). Например, одна оценка может представлять собой определение относительно того, доступна ли следующая часть предпочтительного маршрута, если путь доступен, планировщик выбирает этот состав для перемещения в следующий пункт принятия решения (этап 320). Если выполнимого решения нет, планировщик либо задерживает состав в пункте назначения, либо выполняет возврат и выбирает альтернативный маршрут (этап 350). Планировщик повторяет этот процесс для всех составов, пока все составы не достигнут своих соответствующих модельных пунктов назначения или пока не будет достигнут конец горизонта планирования.
В одном варианте воплощения, когда состав сталкивается с ситуацией, в которой он больше не может быть перемещен по его предпочтительному маршруту, планировщик разрешает ситуацию систематическим образом. Для разрешения таких ситуаций могут использоваться многие методики, в том числе эвристические методы, математическое программирование и другие методы локальной оптимизации. Используемые методики могут привести к возврату составов, к их задержке в их текущих местоположениях и/или перемещению составов по путям, которые являются альтернативными по отношению к предпочтительному маршруту. Технический эффект состоит в том, что планировщик будет продвигать составы в среде моделирования систематическим образом до тех пор, пока все составы не достигнут своих модельных пунктов назначения или пока не будет достигнут конец горизонта планирования.
Следующий пример иллюстрирует работу одного варианта воплощения настоящего раскрытия. Планировщик может сортировать составы в порядке возрастания на основе времени, до которого они уже внесены в расписание для перемещения от начального пункта. Затем она выбирает первый состав в отсортированном списке и пытается переместить состав по его предпочтительному маршруту. Если выполнимый сегмент существует, она перемещает состав до следующего пункта принятия решения. Если выполнимого решения нет, она либо задерживает состав в его текущем местоположении, либо выполняет возврат и выбирает следующий наилучший сегмент. Система планирования повторяет этот процесс до тех пор, пока все составы не достигнут своих модельных пунктов назначения или пока не будет достигнут конец горизонта планирования.
Чтобы гарантировать оптимальное движение составов, в модельном движении рассматриваются несколько показателей. При определении движения состава планировщик рассматривает следующие показатели:
Количество переключателей для каждого состава: количество раз, когда состав переключается со своего предпочтительного маршрута на альтернативный маршрут. Планировщик пытается минимизировать этот показатель.
Количество обгонов с равными значениями: количество раз, когда состав обгоняет другой состав с равным значением. Планировщик пытается минимизировать этот показатель.
Количество случаев истечения времени смен бригад поездов: количество раз, когда смена бригады поезда заканчивается во время расписания. Планировщик пытается минимизировать этот показатель.
Процент скрещений и обгонов, сохраняющихся между планами: это показатель процента скрещений и обгонов, которые остаются неизменными от одного плана к следующему плану. Планировщик пытается максимизировать этот показатель.
Планировщик также может выдавать показатели в качестве выходных данных цикла планирования, которые могут использоваться для сравнения со статистическими нормами или для сравнения с другими методиками предшествующего уровня техники. Такие выходные показатели включают в себя:
Время выполнения алгоритма: время (в секундах), которое было затрачено планировщиком для формирования решения.
Средняя скорость состава: средняя скорость всех составов с расписаниями поездов, сформированными планировщиком. Этот показатель полезен для клиента, который может интересоваться как средней скоростью по всем составам, так и средней скоростью по группе составов. Он может использоваться для определения пробега составов, отслеженного за каждый день.
Средняя задержка на состав: измеряется с самого позднего времени, когда состав достигает своего пункта назначения.
Максимально возможная скорость: средняя скорость составов, если все составы должны были следовать по своим основным маршрутам без какого-либо другого движения, препятствующего их продвижению.
Количество неразрешенных конфликтов: количество случаев, когда два или более составов находятся на одном и том же сегменте.
Процент надежности: показатель стабильности плана движения.
Как следует понимать, выходные данные любых из вышеупомянутых способов/систем представляют собой план движения, который используется для планирования фактического движения составов в железнодорожной сети. Когда план движения сформирован и сообщен составам (часть плана движения или весь план движения сообщается либо в один момент времени, либо в разные моменты времени), составы следуют плану движения для фактического (физического) движения составов по железнодорожной сети.
Варианты воплощения предмета изобретения и функциональные операции, описанные в этом описании, могут быть реализованы в цифровой электронной схеме или в программном обеспечении, встроенном программном обеспечении или аппаратном оборудовании, включающем в себя структуры, раскрытые в этом описании, и их структурные эквиваленты, или в комбинациях одного или большего количества из них. Варианты воплощения предмета изобретения, описанного в этом описании, могут быть реализованы как один или более компьютерных программных продуктов, то есть, один или более модулей программных команд, закодированных на материальном программном носителе, для выполнения посредством устройства обработки данных или для управления его работой. Материальный программный носитель может являться распространяемым сигналом или машиночитаемым носителем. Распространяемый сигнал представляет собой искусственно сформированный сигнал, например, сформированный с помощью машины электрический, оптический или электромагнитный сигнал, который формируется для кодирования информации для передачи на подходящее приемное устройство для выполнения посредством компьютера. Машиночитаемый носитель может представлять собой машиночитаемое запоминающее устройство, машиночитаемую запоминающую плату, устройство памяти, смесь веществ, воздействующую на машиночитаемый распространяемый сигнал, или комбинацию одного или большего количества из них.
Термин "устройство обработки данных" охватывает все устройства и машины для обработки данных, в том числе, в качестве примера, программируемый процессор, компьютер или несколько процессоров или компьютеров. В дополнение к аппаратному оборудованию устройство может включать в себя код, который создает среду выполнения для рассматриваемой компьютерной программы, например, код, который формирует встроенное программное обеспечение процессора, набор протоколов, систему управления базами данных, операционную систему или комбинацию одного или большего количества из них.
Компьютерная программа (также известная как программа, программное обеспечение, приложение, сценарий или код) может быть написана на языке программирования любого вида, в том числе на компилируемых или интерпретируемых языках, или на декларативных или процедурных языках, и она может быть развернута в любой форме, в том числе как автономный модуль или как модуль, компонент, подпрограмма или другой блок, подходящий для использования в вычислительной среде. Компьютерная программа не обязательно соответствует файлу в файловой системе. Программа может быть сохранена в части файла, который содержит другие программы или данные (например, один или более сценариев, сохраненных в документе на языке разметки), в одном файле, специально предназначенном для рассматриваемой программы, или в нескольких согласованных файлах (например, файлах, которые хранят один или более модулей, подпрограмм или частей кода). Компьютерная программа может быть развернута для выполнения на одном компьютере или на нескольких компьютерах, которые располагаются в одном месте или распределены по нескольким местам и связаны посредством сети связи.
Процессы и логические потоки, описанные в этом описании, могут быть выполнены посредством одного или более программируемых процессоров, исполняющих одну или более компьютерных программ для выполнения функции посредством воздействия на входные данные и формирования выходных данных. Процессы и логические потоки также могут быть выполнены посредством специализированной логической схемы, например, программируемой вентильной матрицы (FGPA) или специализированной интегральной схемы (ASIC), и устройство также может быть реализовано как специализированная логическая схема.
Процессоры, подходящие для исполнения компьютерной программы, включают в себя, в качестве примера, как микропроцессоры общего назначения, так и специализированные микропроцессоры и любой один или более процессоров цифровой вычислительной машины любого вида. В общем случае, процессор будет принимать команды и данные от постоянного запоминающего устройства или оперативного запоминающего устройства или от них обоих. Основные элементы компьютера представляют собой процессор выполнения команд и одно или более запоминающих устройств для хранения команд и данных. В общем случае, компьютер также будет включать в себя одно или более запоминающих устройств большой емкости для хранения данных, например, магнитные, магнитооптические или оптические диски, и/или будет функционально присоединен для приема данных от одного или более запоминающих устройств большой емкости для хранения данных или передачи данных на них. Однако компьютер не обязательно должен иметь такие устройства. Кроме того, компьютер может быть встроен в другое устройство, например, помимо прочего, мобильный телефон, карманный компьютер (PDA), мобильный аудио- или видеопроигрыватель, игровую консоль, приемник глобальной системы позиционирования (GPS).
Машиночитаемые носители, подходящие для хранения команд компьютерной программы и данных, включают в себя все виды энергонезависимой памяти, носители и запоминающие устройства, включающие в себя, в качестве примера, полупроводниковые запоминающие устройства, например, стираемое программируемое постоянное запоминающее устройство (СППЗУ; EPROM), электрически стираемое программируемое постоянное запоминающее устройство (ЭСППЗУ; EEPROM) и перепрограммируемые запоминающие устройства; магнитные диски, например, внутренние жесткие или сменные диски; магнитооптические диски; и компакт-диски (CD-ROM) и универсальные цифровые диски (DVD-ROM). Процессор и память могут быть дополнены специализированной логической схемой или включены в нее.
Для обеспечения взаимодействия с пользователем варианты воплощения предмета изобретения, описанного в этом описании, могут быть реализованы на компьютере, имеющем устройство отображения, например, монитор с электронно-лучевой трубкой (ЭЛТ; CRT) или на жидких кристаллах (ЖК; LCD) для отображения информации пользователю, и клавиатуру и указательное устройство, например, мышь или шаровой манипулятор, посредством которых пользователь может обеспечить ввод данных в компьютер. Также для обеспечения взаимодействия с пользователем могут использоваться другие виды устройств; например, ввод от пользователя может быть принят в любой форме, в том числе акустический, речевой или тактильный ввод.
Варианты воплощения предмета изобретения, описанного в этом описании, могут быть реализованы в вычислительной системе, которая включает в себя серверный компонент, например, сервер данных, или включает в себя компонент промежуточного программного обеспечения, например, сервер приложений, или включает в себя интерфейсный компонент, например, клиентский компьютер, имеющий графический пользовательский интерфейс или веб-обозреватель, через который пользователь может взаимодействовать с реализацией предмета изобретения, описанного в этом описании, или любую комбинацию одного или более таких серверных компонентов, компонентов промежуточного программного обеспечения или интерфейсных компонентов. Компоненты системы могут быть связаны посредством любого вида носителя или передачи цифровых данных, например, посредством сети связи. Примеры сетей связи включают в себя локальную сеть (LAN) и глобальную сеть (WAN), например, Интернет.
Вычислительная система может включать в себя клиенты и серверы. Клиент и сервер, в общем случае, удалены друг от друга и обычно взаимодействуют через сеть связи. Взаимоотношения клиента и сервера возникают на основе компьютерных программ, работающих на соответствующих компьютерах и имеющих друг с другом взаимоотношение клиент-сервер.
Хотя это описание содержит много специальных конкретных подробностей, они должны рассматриваться не как ограничения объема какого-либо изобретения или того что может быть заявлено, а как описания отличительных признаков, которые могут являться специфическими для конкретных вариантов воплощения конкретных изобретений. Некоторые отличительные признаки, которые описаны в этом описании в контексте отдельных вариантов воплощения, также могут быть реализованы в комбинации в одном варианте воплощения. И наоборот, различные отличительные признаки, которые описаны в контексте одного варианта воплощения, также могут быть реализованы в нескольких вариантах воплощения отдельно или в любой подходящей субкомбинации. Кроме того, хотя отличительные признаки могут быть описаны выше как действующие в некоторых комбинациях и даже первоначально заявленные как таковые, один или более отличительных признаков из заявленной комбинации могут в некоторых случаях быть изъяты из комбинации, и заявленная комбинация может быть направлена на субкомбинацию или варианты субкомбинации.
Аналогичным образом, хотя операции изображены на чертежах в конкретном порядке, это не следует понимать как требование, что такие операции должны выполняться в конкретном показанном порядке или в последовательном порядке, или что для достижения желаемых результатов должны быть выполнены все проиллюстрированные операции. При некоторых обстоятельствах может быть эффективной многозадачная и параллельная обработка. Кроме того, разделение различных элементов системы в описанных выше вариантах воплощения не следует понимать как требование такого разделения во всех вариантах воплощения, и следует подразумевать, что описанные программные компоненты и системы могут в общем случае быть интегрированы вместе в едином программном продукте или упакованы в нескольких программных продуктах.
Хотя выше были подробно описаны несколько вариантов воплощения, возможны другие модификации. Другие варианты воплощения могут находиться в объеме следующей формулы изобретения.