Размещено на http://www.allbest.ru/

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

АНАЛИЗ И РАЗРАБОТКА СОВРЕМЕННЫХ ИНТЕЛЛЕКТУАЛЬНЫХ МЕТОДОВ МОДЕЛИРОВАНИЯ В СИСТЕМАХ ПРИНЯТИЯ РЕШЕНИЙ

Минашина Инна Константиновна

05.13.01 - Системный анализ, управление и обработка информации

(по отраслям)

Москва - 2018

Работа прошла апробацию на кафедре «Инфокоммуникационные системы и сети» Федерального государственного автономного образовательного учреждения высшего образования «Московский физико-технический институт (государственный университет)»

Научный руководитель

доктор технических наук,

профессор

Пащенко Федор Федорович

Работа представлена «15» марта 2018 г. в Аттестационную комиссию федерального государственного автономного образовательного учреждения высшего образования «Московский физико-технический институт (государственный университет)» для рассмотрения советом по защите диссертаций на соискание ученой степени кандидата наук, доктора наук в соответствии с п. 3.1 ст. 4 Федерального закона «О науке и государственной научно-технической политике»

Общая характеристика работы

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

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

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

Степень разработанности проблемы исследования. Необходимо отметить, что уже сложилась достаточная научная база для рассмотрения проблемы разработки интеллектуальных систем управления. Изучение научной литературы показало, что в центре внимания исследований ученых были следующие задачи:

· задача управления в реальном масштабе времени (Эйкхофф П., Кузнецов Н., Райбман Н., Пащенко Ф., Ionescu D., Trif I., Moore R., Hawkinson L., Knickerbocker C., Churchman L., Wright M., Green M., Fiegl G., Cross P.);

· задача интеллектуального управления (Заде Л., Цыпкин Я., Saridis G., Valavanis K., Пащенко Ф.);

· задача экспертного адаптивного управления (Эйкхофф П., Заде Л., Цыпкин Я., Аведьян Э., Кузнецов Н., Astrom K., Hang C., Persson P., Ho W., Arze K.-E., Пащенко Ф.);

· задача определения наилучших значений параметров или структуры объектов или задача оптимизации (Эйкхофф П., Райбман Н., Цыпкин Я., Аведьян Э., Вазан М., Hansen E.).

Тем не менее, анализ представленных исследований показал, что существует ряд недостаточно разработанных проблем, среди них:

· учет неопределенности в оптимизационных моделях;

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

· сокращение объема данных, хранимых при реализации методов идентификации систем управления и увеличение быстродействия и надежности разрабатываемых систем поддержки принятия решений (СППР);

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

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

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

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

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

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

В соответствии с целью, объектом и предметом диссертации были поставлены и решены следующие основные задачи исследования:

1. Исследование известных методов искусственного интеллекта и их применения к задаче планирования грузоперевозок и построения эффективного расписания. Программная реализация методов;

2. Анализ существующих подходов к задаче планирования содержания тяговых ресурсов на установленную потребность и обеспечения перевозочного процесса требуемым количеством тягового подвижного состава;

3. Исследование специфики сферы железнодорожных перевозок и формирование ограничений, связанных с характерными особенностями перевозочного процесса.

4. Разработка математической модели системы управления перевозочным процессом, ее программная реализация.

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

6. Разработка алгоритмов поиска эффективного расписания движения и обеспечения поездов локомотивами, а также их адаптация в соответствии с найденными ограничениями исследуемой задачи; программная реализация созданных методов;

7. Моделирование управления грузоперевозками на примере Восточного полигона, оценка эффективности созданной системы управления перевозочным процессом.

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

Научная новизна работы заключается в следующем:

1. Разработан метод формализации задач планирования содержания тяговых ресурсов на установленную потребность для обеспечения перевозочного процесса требуемым количеством тягового подвижного состава (ТПС) и локомотивных бригад (ЛБ) и построения эффективного расписания движения поездов и прикрепленных к ним тяговых ресурсов;

2. Сформулирована задача оптимизации планирования расписания грузоперевозок как задача поиска экстремума целевой функции;

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

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

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

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

Практическая значимость. Результаты настоящего исследования могут быть применены для автоматизации пассажиро- и грузоперевозок на железнодорожном транспорте, а именно автоматизации планирования расписания грузоперевозок и прикрепления тяговых ресурсов к поездам, а также планирования содержания ТПС и ЛБ на установленную потребность для обеспечения перевозочного процесса. Построенные системы управления в настоящее время частично введены в опытную эксплуатацию на Восточном полигоне РЖД. Кроме того, исследование по моделированию пассажиропотоков, выполненное в данной работе, позволяет использовать полученные результаты для прогнозирования поведения транспортного потока на железнодорожном транспорте, том числе и на монорельсовом.

Основные научные положения, выносимые на защиту:

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

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

3. Формулировка задачи оптимизации для планирования эффективного расписания движения поездов и прикрепленных к ним тяговых ресурсов, а также разработанные критерии и структура функции полезности для оценки эффективности полученного графика движения поездов.

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

5. Комплекс программ для планирования расписания грузоперевозок (в частности для планирования привязки тяговых ресурсов к поездам на Восточном полигоне РЖД) с использованием разработанных алгоритмов оптимизации и решения задачи о назначениях;

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

Апробация работы. Материалы диссертационной работы были доложены и обсуждены на следующих международных конференциях и семинарах: 4th International Conference ICDQM-2013, Life Cycle Engineering and management, June 27-28 2013. Belgrade, Serbia; Управление развитием крупномасштабных систем (MLSD'2013), 30 сентября - 2 октября 2013 г., Москва; Международная молодежная научно-практическая конференция «Человек и космос», 9-11 апреля 2013г., Днепропетровск, Украина; The 5th International Conference on Emerging Ubiquitous Systems and Pervasive Networks (EUSPN-2014), Halifax, Nova Scotia, Canada on September 22-25, 2014; The 6th International Conference on Emerging Ubiquitous Systems and Pervasive Networks, September 27-30, 2015, Berlin, Germany; «10th International Conference on Application of Information and Communication Technologies (AICT2016)», Baku, Azerbaijan,12 - 14 of October 2016; The 7th International Conference on Emerging Ubiquitous Systems and Pervasive Networks (EUSPN), September 19-22, 2016, London, United Kingdom; The 8th International Conference on Ambient Systems, Networks and Technologies May 16-19, 2017, Madeira, Portugal; The 11th IEEE International Conference AICT2017 Application of Information and Communication Technologies, 20-22 Sep 2017 | Moscow, Russia.

А также на следующих Российских конференциях: 55-я научная конференция МФТИ, 19-25 ноября 2012, Долгопрудный; «Интеллектуальные системы управления на железнодорожном транспорте ИСУЖТ-2012», 15-16 ноября 2012, Москва; ИСУЖТ-2013, 21-22 октября 2013, Москва; «Управление большими системами» УБС-10, 5-7 июня 2013, Уфа; ИСУЖТ-2014, 19 ноября 2014г., Москва; 57-я научная конференция МФТИ, 24-29 ноября 2014, Долгопрудный; 58-я научная конференция МФТИ с международным участием, 23-28 ноября 2015 года, Долгопрудный; ИСУЖТ-2015, 18 ноября 2015 г., Москва; ИСУЖТ-2016, 17-18 ноября 2016, г. Москва.

Кроме того, построенные системы управления железнодорожными перевозками частично внедрены на Восточном полигоне в опытную эксплуатацию. Проведенное исследование по прогнозированию пассажиропотоков и содержанию тяговых ресурсов используется при разработке технических решений для транспортной системы типа H-BAHN (имеется акт о внедрении). Результаты диссертационной работы были получены и применены при разработке технических решений в рамках выполнения прикладных научных исследований и экспериментальных разработок - уникальный идентификатор RFMEFI58214X0003 при поддержке Министерства образования и науки РФ.

Публикации. По теме диссертации опубликовано 29 работ: 10 статей в центральных журналах, рекомендованных ВАК РФ для опубликования результатов диссертаций (в том числе 8 статей в журналах из перечня Scopus и WOS) и 19 статей опубликованных в изданиях, выпускаемых в Российской Федерации и за рубежом.

Структура и объем диссертации. Диссертационная работа состоит из введения, 5-ти глав, заключения, списка использованных источников и 3-х приложений. Общий объем работы составляет 249 страниц. Работа содержит 37 рисунков, 28 таблиц и библиографию из 123 наименований.

Основное содержание работы

математический интеллектуальный моделирование поезд

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

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

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

Во второй главе «Теоретические аспекты моделирования интеллектуальных систем управления» анализируются существующие подходы построения интеллектуальных систем управления. В ходе анализа научных трудов, посвященных технологиям разработки автоматизированных систем управления, особое внимание было уделено методам, способным показать эффективные результаты при адаптации к условиям и ограничениям сложной динамической системы российских железных дорог. Среди них: системы управления на основе знаний (Пащенко Ф. и др.), мультиагентные системы в свете их применения при оптимизации использования ресурсов железнодорожного транспорта (Скобелев П., Tornquist J., Davidsson P., Blum J., Eskandarian A., Narayanaswami S., Chen B., Cheng H., Palen J., Матюхин В., Шаров В., Шабунин А., Кузнецов Н.), методы выбора наиболее предпочтительного решения как экстремума целевой функции (Эйкхофф П., Цыпкин Я., Аведьян Э., Кузнецов Н., Вазан М., Hansen E.), адаптивные алгоритмы идентификации (Эйкхофф П., Райбман Н., Аведьян Э., Пащенко Ф.), нечеткая логика и нейронные сети (Заде Л., Альберт А., Пащенко Ф., Кудинов Ю., Larichev O., Бутенков С., Аль-Доуяни С., Гарднер Л., Воеводин Ю., Комарцова Л.).

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

Задачу построения эффективного расписания грузоперевозок на железнодорожном транспорте можно разбить на три подзадачи: планирование расписания поездов (то есть назначение поездов на нитки вариантного графика), планирование подвязки ТПС и планирование подвязки ЛБ. Указанные подзадачи можно решать как последовательно, так и одновременно в зависимости от выбранного метода решения.

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

Рассмотрим проблему подвязки ТПС к поездам. На вход модуля подается план составообразования, вариантный график, исходное положение ТПС, тяговые плечи (ТП), нормы проведения технического обслуживания второго вида (ТО-2), регулировочные задания и весовые нормы. Задача модуля состоит в назначении ТПС на поезда таким образом, чтобы обеспечить наилучшее выполнение плана перевозок с соблюдением заданных ограничений и технологических нормативов работы ТПС, а также сформировать задания на отправку ТПС резервом и на ТО-2. В дальнейшем при рассмотрении данной подзадачи для обозначения абстрактного плана перемещения ТПС между станциями будем использовать термин «локомотивный слот». Аналогичным образом была поставлена задача подвязки ЛБ под ТПС.

Разработка указанной системы включала в себя следующие стадии.

Прежде всего, были сформированы ограничения, отражающие основные требования и регламенты по формированию графика движения поездов и прикрепления к ним тяговых ресурсов. На данной стадии были описаны основные правила технологического процесса планирования расписания поездов (вычисление пропускных способностей, временные допуски, приоритеты пропуска грузовых поездов и др.), подвязки ТПС (технология движения ТПС, учета заданий на регулирования и др.) и подвязки ЛБ (технология движения ЛБ).

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

Ключевым вопросом формулировки задачи привязки поездов и тяговых ресурсов как задачи оптимизации и учета технологических ограничений является формирование функции полезности, на основе которой строится реализация рассматриваемого модуля. Приведем основные критерии функций полезности, разработанные в рамках создания модуля планирования расписания грузоперевозок. Каждому критерию ставится в соответствие нормированное численное значение uk, после чего вычисляется значение для функции полезности пары <локомотив (бригада, поезд), локомотивный слот (бригадный слот, нитка)> как , где ck - вес соответствующего k-го критерия.

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

Рассмотрим для примера основные идеи расчета критериев назначения того или иного ТПС на заданный локомотивный слот. В Таблице 1 приведены сведения по расчету критериев в функции полезности для задачи привязки ТПС к поезду.

Таблица 1. Сведения по расчету критериев функции полезности для задачи привязки ТПС к поезду

Название критерия	Порядок расчета	Знак коэффициента
Время работы	Разность между временем прибытия на конечную станцию слота и временем отправления с начальной станции.	+
Ожидание слота локомотивом	Разность между временем отправления слота и временем прибытия ТПС на станцию отправления. Если эта разность отрицательная, то брать значение критерия = 0.	-
Ожидание локомотива слотом	Разность между временем прибытия ТПС на станцию отправления и временем отправления слота на первый участок. Если эта разность отрицательна, то брать значение критерия = 0.	-
Время до станции проведения ТО-2	Время хода от конечной станции слота до ближайшей станции проведения ТО-2.	-
Оставшееся время до ТО-2	Время работы до ТО-2, которое ТПС будет иметь на момент времени прибытия на конечную станцию слота с учетом возможной пересылки ТПС по критерию 7. Если значение < 0, то значение критерия устанавливать .	-
Весовые ограничения	1. Выбрать из сообщений о весовых нормах те, которые относятся к ТПС той серии и с тем количеством секций, которые указаны для обрабатываемого ТПС, а также относящиеся ко всем участкам планирования на маршруте локомотивного слота. Пусть WT - вес поезда, соответствующего локомотивному слоту, WL - максимально допустимый вес поезда, который данный ТПС может провезти по данному маршруту. 2. Если , то значение по критерию . Дальнейших расчетов по этой ветке производить не требуется. 3. Если , то брать значение по критерию . 4. Если в п.0 не было найдено ни одного сообщения или если вес поезда не задан, то считается, что для ТПС не заданы весовые ограничения, и полезность устанавливается средняя по умолчанию.	+
Время на пересылку ТПС резервом	Время хода между станцией, на которой находится ТПС на момент подсчета, и станцией, с которой начинается локомотивный слот.	-
Будущие планы	Учет допустимых «будущих» слотов с конечной станции	+

Таким образом, были сформированы правила оценки эффективности какого-либо варианта решения описанных выше подзадач. Однако критерии функций полезности учитывают далеко не все ограничения системы. В связи с этим требовалось создать алгоритм планирования эффективного расписания, принимающий во внимание и соблюдающий все требования и регламенты по планированию расписания грузоперевозок. Для этого были разработаны и реализованы специальные алгоритмы планирования поездов, ТПС и ЛБ, учитывающие указанные технологические особенности. Основные идеи алгоритма планирования ТПС приведены на блок-схемах Рисунка 1. Привязка ТПС ведется отдельно по 6-часовым интервалам и отдельно по ТП, ЛБ - по 3-часовым интервалам и отдельно по ТП локомотивов (предполагается, что на станциях смены ТПС всегда меняется и ЛБ, поэтому граничные станции ТП всегда являются и граничными для оборота ЛБ). Общий горизонт планирования ТПС - 2 суток, ЛБ - 1 сутки. В дальнейшем под итерацией планирования мы будем понимать единичный, «элементарный» расчет, связанный с решением одной задачи назначения тяговых ресурсов на соответствующие слоты. Такая итерация планирования происходит для каждого ТП, временного интервала и типа планирования (привязка ТПС или привязка ЛБ).

Составив список локомотивных (бригадных) слотов для текущей итерации планирования и список ТПС (ЛБ), доступных для привязки, можно приступать к центральному моменту в планировании - решению задачи назначения тяговых ресурсов на соответствующие слоты. Для этого была поставлена задача оптимизации для поиска наилучшего прикрепления тяговых ресурсов к поездам (Kuznetsov N., Minashina I., Pashchenko F., Ryabykh N., Zakharova E.). Выше мы рассмотрели вид функций полезности для пар “i-й локомотивный (бригадный) слот - назначенный на него локомотив (бригада) xi” . Рассматривая оптимизацию прикрепления тяговых ресурсов к поездам в целом на всем участке планирования, использовалась суммарная целевая функция , которая равна сумме целевых функций составляющих график планов пересылки. Таким образом, суммарная целевая функция является многомерной функцией векторного аргумента X = [x1, x2, ... xm]Т, где вектор X - какое-либо решение задачи назначения локомотивов (бригад) на планы пересылки (с поездом или резервом), представленное в виде , где - номер локомотива (бригады), назначенного на i-й слот, m -- количество слотов на текущем участке планирования.

а. Общий алгоритм составления локомотивных слотов

б. Планирование ТПС(одна итерация)

Рисунок 1. Планирование ТПС

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

где X* - искомое решение; - заданные ограничения; l - количество ограничений.

Поиск производится на множестве ограничений, связанных с технологическими особенностями в железнодорожном комплексе. Тогда необходимо найти такой вид итерационного оператора поиска экстремума функции F(X), чтобы итерационный процесс сходился к наилучшему решению или, другими словами, к экстремуму суммарной целевой функции.

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

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

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

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

· Начальная температура и минимальная температура инициализируются вместе с функцией изменения температуры.

· Первое назначение тяговых ресурсов на поезда выбирается случайным образом, и рассчитывается его общая полезность.

· Пока температура больше минимального значения, рассчитывается новое состояние и его общая полезность (функция перехода в новое состояние будет определена ниже). Если полезность нового состояния больше, чем полезность текущего состояния, текущее состояние переключается на новое. Если новое состояние имеет более низкую полезность, переход осуществляется с определенной вероятностью, зависящей от температуры. Например: , где - это разница между суммарной полезностью нового и текущего состояний, а t - текущая температура.

· Переход к новой температуре в соответствии с функцией изменения температуры.

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

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

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

Объектом автоматизации задачи содержания тяговых ресурсов являются производственные процессы квартального планирования по управлению содержанием ТПС и ЛБ. Задачу можно описать следующим образом: необходимо сравнить ожидаемое на квартал количество содержания тяговых ресурсов в эксплуатируемом парке с установленной по норме величиной по каждой региональной дирекции, виду тяги, виду движения и другим параметрам. В случае если ожидаемое количество тяговых ресурсов не соответствует норме содержания, осуществить работу по исправлению данной ситуации за счет выполнения ряда операций над тяговым хозяйством. В ходе создания модуля планирования содержания тяговых ресурсов на установленную потребность для обеспечения перевозочного процесса были проведены следующие этапы работы.

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

Руководство процессом планирования происходит в объекте Resolver, отвечающего за один цикл планирования по всем проблемам в депо. Структура данного класса приведена на Рисунке 2. Метод solve(Step) выполняет планирование для заданного этапа Step, разделяя, где возможно, проблемы на параллельные депо-потоки. Планирование состоит из 3 этапов, представленных в диаграмме подклассом Step. Шаг Step.PREPLANNING отвечает за расчёт плановой и прогнозной списочной численности ЛБ, а шаги Step.DEFICIT и Step.SURPLUS за планирование и выполнение операций по устранению дефицита и профицита соответственно. На каждом шаге объект Resolver запускает параллельные процессы-помощники Helper для каждого депо, которые идентифицируют проблемы своего депо и решают их. На шаге Step.DEFICIT дополнительно после работы всех процессов-помощников запускается объект планирования командировок Relocation, призванный устранить оставшийся дефицит. Для решения транспортной задачи была выбрана мультиагентная модификация метода аукционов, способная контролировать действия между многочисленными участниками планирования с конфликтными интересами за относительно малое время.

Размещено на http://www.allbest.ru/

Для решения найденных проблем класс Resolver использует набор возможных операций над контингентом сотрудников operations. Рассмотрим строение предложенной структуры данных, отвечающей за возможные операции над контингентом ЛБ по устранению дефицита и профицита в депо (Рисунок 3). Операции разделены на 8 различных типов, отражающих основные свойства технологических процессов по нормализации состояния в депо. Для учета поставленных ограничений каждый тип операции реализует методы getPredicateTyped, getPredicateSuitable, которые содержат в себе правила фильтрации сотрудников, отвечающие критериям отбора той или иной операции, а также метод getComparator, сортирующий сотрудников по заданному в операции приоритету.



Размещено на http://www.allbest.ru/

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

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

Исследуемая задача прогнозирования пассажиропотока в целом может быть сформулирована следующим образом: дана плотность потока пассажиров за предыдущий период для данного поезда. Требуется дать прогноз для плотности потока пассажиров в текущий период времени, на основе которого оптимизируется необходимое количество тяговых ресурсов. Плотность потока N(t) - количество пассажиров в поезде в текущий момент времени t на единицу площади.

Данную задачу можно рассматривать как задачу нелинейного моделирования:

,

где e(t) - это разница между известной (измеренной) и оцениваемой плотностью потока в момент t, (t) - плотность потока пассажиров в предыдущий день, щ - неизвестная функция, m и l - временные задержки входа и ошибки соответственно. Это уравнение может быть аппроксимировано следующей рекуррентной моделью (Вазан М., Аксенов В., Пащенко Ф.):

,

где t - момент времени, , и - коэффициенты, - оцениваемый поток пассажиров, - это параметр и ц - нелинейная функция.

Используя обозначения модели рекуррентной нейро-сети (РНС), его можно записать в более общем виде:

,

где - весовой коэффициент связи между i-м скрытым элементом и j-м входным элементом в момент времени t, - весовой коэффициент между i-м скрытым элементом и выходным элементом.

В данной работе для моделирования процессов перевозок используется нечеткая разностная модель Такаги-Суджено-Канга, построенная на базе статистической нечеткой модели Такаги (Takagi) и Суджено (Sugeno).

где - нечеткие множества, характеризующиеся функциями принадлежности

Предлагается использовать гибридный подход идентификации модели: структурная и параметрическая идентификация. В работе в качестве алгоритма параметрической идентификации использован алгоритм Качмажа, максимальная скорость сходимости которого достигается, если входные векторы Vt в последовательных тактах 1, 2,…, t ортогональны. В этом случае для точного определения параметров объекта требуется не более l+m+1 шагов (Аведьян Э., Чадеев В., Пащенко Ф., Бернацкий Ф.).

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

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

В пятой главе «Оценка эффективности работы построенных систем управления грузоперевозками» приведены результаты работы созданных систем моделирования грузоперевозок на железнодорожном транспорте. Созданные системы были протестированы на реальных данных с Восточного полигона РЖД и частично внедрены в опытную эксплуатацию на указанном полигоне.

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

Для предварительного тестирования разработанных модулей была создана упрощенная модель полигона, отражающая его основные особенности, и тестовые сценарии, проверяющие критерии, которые должны учитываться при планировании. По полигону были заданы следующие объемы движения на первые сутки планирования: 140 поездов, от 99 до 115 ТПС и от 221 до 254 ЛБ.

Следующим этапом последовало проведение экспериментов на реальных данных, полученных с участка ответственности Центра управления тяговыми ресурсами (ЦУТР), управляющего Восточным полигоном. Указанный полигон включает в себя 4 железные дороги: Красноярскую (№88), Восточно-Сибирскую (№92), Забайкальскую (№94) и Дальневосточную (№96). Для проверки разработанной системы на реальных данных был создан набор автоматических тестов, анализирующих корректность выдаваемого решения, а также отобраны основные количественные и качественные показатели локомотивного парка. Анализ результатов был проведен для данных, имеющих следующие характеристики: в планируемый период длиной 24 часа планировалось отправление 1956 поездов, для которых было предоставлено 2101 ТПС и 5063 ЛБ.

Рассмотрим результаты работы построенного модуля планирования расписания. На выходе планировщика предоставляются: детальный план подвязки ЛБ к ТПС, включающий информацию о ТПС (номер, серия), поезде (индекс, станция формирования, станция назначения), времени отправления ЛБ и самой ЛБ; детальный план подвязки ТПС под поезд; план пропуска поезда по участку, включающий полную информацию о маршруте поезда, нитке вариантного графика и подвязанных к нему тяговых ресурсах; оборотные ведомости работы ТПС и ЛБ по участку.

Проанализируем проведенное тестирование на реальных данных Восточного полигона.

Полученные графики движения поездов были проверены на наличие расхождений времен хода поездов и времен хода в нитках. Среднее отклонение времен хода в поездах и в нитках (Рисунок 4а) составляет 0,31 мин., что является весьма приемлемым результатом для данных подобного объема.

Рассмотрим изучение других характеристик планирования поездов. Всего было запланировано 99% поездов. При подобном масштабе данных такой показатель является признаком корректной и продуктивной работы рассматриваемого модуля. Кроме того, были рассчитаны следующие показатели планирования поездов: совпадение четности номеров поездов и направления движения (100%), среднее время на смену ТПС и ЛБ (Рисунок 4б), среднее отклонение количества запланированных поездов от данных автоматизированной системы подготовки данных и обмена информацией для сквозного сменно-суточного планирования (АС ССП) по направлениям (нечетное -6.44, четное -0.47), отклонение времени отправления поезда на первый участок в маршруте от фактического (0%), скачки в расписании поездов по времени назад (0%). Как видно из приведенных результатов и рассчитанной статистики, модуль планирования поездов способен выдавать адекватный график движения поездов для масштабных данных Восточного полигона. Аналогично была проведена проверка основных моментов планирования ТПС, которая показала соответствие полученных планов движения ТПС принятым нормам и ограничениям движения ТПС.

а. Отклонение времен хода в поездах и в нитках

б. Распределение времени на смену бригады по станциям

Рисунок 4. Характеристики планирования поездов

Рассмотрим более подробно анализ результатов проверки планирования ЛБ. Приведем результаты расчета процента подвязки между локомотивами и бригадами: на горизонте 6 часов - 98%; на горизонте 12 часов - 97%; на горизонте 24 часа - 94%. Данные по проценту подвязки бригад показывают, что планирование бригад происходит без сбоев. Основные характеристики планирования ЛБ представлены на Рисунке 5.



а. График бригад с переработкой

б. Распределение бригад по временам на отдых

в. Распределение времен на явку бригад

г. График запаздывания времени явки бригад

Рисунок 5. Характеристики планирования локомотивных бригад

В ходе их анализа на соответствие основным ограничениям задачи планирования ЛБ были проверены следующие моменты: смена ЛБ не на приоритетных станциях (0.04%), аномально большой отдых (0%), планирование ЛБ к отправлению пассажиром ранее времени явки (0%), отклонение времен явок (0.03%), отсутствие планирования требуемых явок (0%), запаздывание времени явки бригад (в среднем -0.76 ч.). Указанная статистика свидетельствует об успешном учете ограничений планирования ЛБ.

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

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

Перед вводом построенной автоматизированной системы в опытную эксплуатацию для оценки эффективности работы построенной системы планирования расписания грузоперевозок был проведен анализ качественных показателей использования эксплуатируемых ТПС. Сводка результатов расчета качественных показателей для реальных данных представлена в Таблице 2.

Таблица 2. Качественные показатели работы системы управления перевозочным процессом

Качественный показатель	Значение
Среднесуточная производительность, WL, тыс. тонн*км	Для работающих локомотивов	1749.63
	Без учета отставленных в резерв	1821.15
	Без учета коротких	1813.99
	С учетом коэффициента на пробег объемных поездов	2812.97
Среднесуточный пробег, SL, км	Полезный пробег локомотивов	480.86
	Без учета отставленных в резерв	503.08
	Без учета коротких	510.59
Коэффициент эффективности использования эксплуатируемого парка локомотивов, K	0.8

С целью изучения зависимости указанных характеристик от внешних факторов планирования были рассчитаны рассматриваемые качественные показатели без учета резервных ТПС, без учета вывозных ТПС и с учетом коэффициента на пробег поездов из объемных заданий (заданий, которые получает планировщик на отправку заданного количества поездов с указанной станции в заданном направлении в конкретный временной период). Результаты расчета представлены графами в таблице «Без учета отставленных в резерв», «Без учета коротких» и «С учетом коэффициента на пробег объемных поездов», а также на Рисунке 6.



Рисунок 6. Сравнение среднесуточного пробега и производительности для разных групп ТПС по дорогам

Проанализировав представленные результаты, можно прийти к следующим выводам:

1. На среднесуточную производительность влияет сдвиг планирования объемных поездов в конец суток, который происходит из-за более высокого приоритета реальных поездов. Поэтому пробег локомотивов запланированных под объемные задания учитывается мало. Если ввести поправочный коэффициент, который учитывает эти погрешности в планировании, то значение производительности локомотивов становится правильным.

2. Множественная пересылка локомотивов резервом тоже влияет на производительность локомотивов (ПЛ), но слабее. Пересылаемые резервом локомотивы все же везут поезда и мало простаивают. Кроме того, для рассматриваемого расчета планировщик достаточно эффективно запланировал прикрепление локомотивов к поездам, так, что доля локомотивов резервом достаточно мала (всего 234 локомотива).

...