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

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

На правах рукописи

Петровец Юрий Олегович

ОПТИМАЛЬНОЕ ПЛАНИРОВАНИЕ РАБОТ ПО РЕМОНТУ ЖЕЛЕЗНОДОРОЖНОГО ПУТИ В ДОЛГОСРОЧНОЙ ПЕРСПЕКТИВЕ

08.00.13 - Математические и инструментальные методы экономики (математические методы)

Автореферат диссертации на соискание ученой степени кандидата экономических наук

1 8 СЕН 2014 005552634

Пермь-2014

005552634

Работа выполнена на кафедре информационных систем и математических методов в экономике ФГБОУ ВПО «Пермский государственный национальный исследовательский университет»

Научный руководитель: Андрианов Дмитрий Леонидович,

доктор физико-математических наук, профессор

Официальные оппоненты: Файзрахманов Рустам Абубакирович,

доктор экономических наук, профессор, заведующий кафедрой информационных технологий и автоматизированных систем ФГБОУ ВПО «Пермский национальный исследовательский политехнический университет», г. Пермь

Матушкина Наталья Александровна,

кандидат экономических наук, старший научный сотрудник отдела прогнозирования размещения производительных сил и пространственного развития экономики регионов ФГБУН Института экономики Уральского отделения РАН, г. Екатеринбург

Ведущая организация: ФГБОУ ВПО «Нижегородский государственный

университет им. Н.И. Лобачевского» (национальный исследовательский университет), г. Нижний Новгород

Защита состоится 22 октября 2014 года в 13-00 часов на заседании диссертационного совета Д 004.022.01 на базе ФГБУН Института экономики Уральского отделения РАН по адресу: 620014, г. Екатеринбург, ул. Московская, 29.

С диссертацией можно ознакомиться в библиотеке ФГБУН Института экономики Уральского отделения РАН.

Автореферат размещен на сайте ФГБУН Института экономики Уральского отделения РАН (www.uiec.ru) и на сайте Высшей аттестационной комиссии Министерства образования и науки РФ (www.vak.ed.gov.ru).

Автореферат разослан ■) ( 2014 года.

Ученый секретарь

диссертационного совета ¡..¡, О.А.Козлова

I. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Износ основных фондов железных дорог России составляет свыше 50%. В ежегодном отчете ОАО «РЖД» за 2011 год сказано, что почти для 17% путей просрочена дата капитального ремонта, для 77% стрелочных переводов превышен срок полезного использования, для 38% инфраструктурных сооружений превышен срок эксплуатации. Такая ситуация характерна для очень большого числа стран, включая страны с развитой экономикой. Так, например, в Белой книге Европейского Союза по транспорту сформулирована стратегия развития транспортной системы в Европе. Ввиду ряда преимуществ, таких как возможность массовых перевозок грузов и пассажиров, высокая пропускная и провозная способность железнодорожных линий, относительно невысокая себестоимость, высокая безопасность и экологичность, ж.-д. транспорту определена одна из ведущих ролей в решении инфраструктурных проблем Европы. Вместе с тем подчеркивается, что инфраструктура железных дорог многих стран нуждается в совершенствовании и модернизации. Таким образом, признается, что повышение конкурентоспособности железнодорожных перевозок невозможно без коренной переориентации экономической инвестиционной политики отрасли в сторону снижения издержек, стимулирования инновации, т.е. технических, технологических и организационных новшеств, обеспечивающих рост коммерческого успеха и укрепление позиций отрасли на общетранспортном рынке. Обслуживание на высоком уровне - это обязательное условие для привлечения новых грузоотправителей и основание для повышения тарифов.

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

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

Все вышесказанное обусловливает актуальность настоящего диссертационного исследования.

Степень разработанности проблемы. Теоретические и методологические вопросы экономики ж.-д. транспорта рассмотрены в работах таких авторов, как И.В. Белов, Б.А Волков, В.Г. Галабурда, А.Е. Гибшман, Б.М. Лапидус, Н.П. Тере-шина, М.Ф. Трихунков, Е.Д. Хануков и др.

Моделированием динамики износа верхнего строения пути (далее ВСП) занимались Г.М. Шахунянц, А.П., Лемановский, Ю.Л. Пейч, К. Рисбергер и др. Оптимизации среднесрочных планов обновления пути посвящены исследования В.ГГ. Бельтюкова, А.И. Гасанова, В.В. Мишина, С.А. Телегина и др.

Вопросы замены оборудования предприятиями разных отраслей промышленности изучали Р.З. Акбердин, АЛ. Гапоненко, A.C. Консон, В.П. Корнеенко, А. Кофман и др.

Нахождение оптимальных организационных и производственных программ с учетом ресурсных ограничений и соответствующих методов математической экономии занимались JI.B. Канторович, Дж. Данциг, с учетом несовместных ограничений - И.И. Еремин, В.Д. Мазуров, Н.Н, Астафьев.

Оптимизации многошаговых процессов управления посвящены работы Р. Беллмана, С. Дрейфуса, Р. Калаба.

Методам дискретной оптимизации для задач большой размерности посвящены работы А. Ланда, А. Дойга, Дж. Литла, Д. Холланда, Д. Голдберга, Б. Мур-тафа, К. Де Йонга.

Теоретические аспекты использования экономико-математических методов и моделей в управлении нашли отражение в трудах С.А. Айвазяна, К.А. Багриновского, А.Г. Гранберга и других авторов.

Вопросы информационного обеспечения и автоматизации процессов управления широко освещены в отечественной и зарубежной литературе. Прежде всего, это труды Т. Конноли, В. Львова, А.И. Мишенина, A.A. Сахарова, М.И. Семенова, Г.К. Скрипкина, Э. Спирли, Л.В. Щавелева и других авторов.

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

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

Предметом диссертационной работы являются процессы управления состоянием железнодорожного (далее ж.-д.) пути.

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

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

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

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

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

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

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

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

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

Результаты, полученные лично автором, и их научная новизна:

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

2. Предложен алгоритм поиска оптимальных решений, основанный на применении точных методов дискретной оптимизации, а именно - метода ветвей и границ и динамического программирования. Доказана возможность применения алгоритма для решения задач большой размерности (п. 1.1. Паспорта спегрииъно-сти 08.00.13 ВАК РФ).

3. Предложены авторские декомпозиционные алгоритмы нахождения оптимальных планов работ, позволяющие не только учесть ресурсные ограничения, но и, не меняя методов оптимизации или экономических составляющих модели, дополнить процесс расчета анализом трудно формализуемых управленческих решений {п. 1.1. Паспорта специальности 08.00.13 ВАК РФ).

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

Апробация результатов исследования осуществлена в компании Вапес1аптагк в 2010-2013 гг. Основные положения работы докладывались на семинарах Лаборатории конструктивных методов исследования динамических моделей (г. Пермь, февраль, март 2012 г.), четырех международных научно-практических конференциях: «Совершенствование стратегического управления

корпоративными образованиями и региональная промышленная политика перехода к новой инновационной экономике» (г. Пермь, ноябрь 2011 г.), «Экономика и управление в XXI веке» (г. Ставрополь, март 2012 г.), «Финансовые проблемы и пути их решения» (г. Санкт-Петербург, апрель 2012 г.), «Наука XXI век: новый подход» (г. Санкт-Петербург, декабрь 2012 г.), открытом семинаре ВШБ ГУУ «Перспективные информационно-аналитические технологии в управлении на транспорте, перевозками и логистике» (г. Москва, апрель 2012 г.), научном семинаре компании ЗАО «ПРОГНОЗ» (г. Пермь, июль 2012 г.).

Публикации. По материалам диссертации опубликовано 8 работ общим объемом 8,84 п.л. (в т.ч. 8,55 авторских п.л.), включая 3 работы общим объемом 1,86 (в т.ч. 1,57 авторских п.л.) в рецензируемых научных журналах, рекомендованных ВАК РФ для публикации научных результатов диссертации: «Проблемы управления», «Вестник ПГУ. Серия «Экономика», «Управление экономическими системами».

Объем и структура диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы, содержащего 161 источник, и двух приложений. Диссертации состоит из 137 страниц, содержит 25 рисунков и 7 таблиц.

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

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

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

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

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

II. ОСНОВНЫЕ НАУЧНЫЕ ПОЛОЖЕНИЯ И РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

Ж.-д. компания влияет на состояние пути с помощью проведения ремонтных работ. Перечень видов работ может незначительно различаться в разных странах. Он также может изменяться в зависимости от развития новых технологий. Так, например, в Положении о системе ведения путевого хозяйства ОАО «РЖД» (утвержденного распоряжением ОАО «РЖД» 30 октября 2009 г. № 2211р) определено 27 основных видов работ относимых на ремонт и текущее содержание пути (капитальный ремонт пути, средний ремонт пути, подъемочный ремонт пути, шлифовка рельсов, осмотр и диагностика и т.д.). В Дании принято выделять 24 основных вида работ, часть из которых в точности совпадает с принятыми в России, а часть специфичны с точки зрения применяемых технологий и терминологии. Несмотря на возможные различия и изменения перечня организационно-технических мероприятий целесообразно разделить все виды работ на две категории: работы, связанные с обновлением элементов ВСП (физическая замена старых рельсов, шпал, балластного слоя и т.д.), и работы, связанные с техническим обслуживанием (далее ТО) (устранение дефектов элементов ВСП без их замены).

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

его состояние приводит к вводу временных ограничений на скорость передвижения поездов (далее TSR, от англ. temporary speed restriction).

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

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

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

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

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

- чрезмерный износ значительно увеличивает стоимость работ, связанных с ТО, и оказывает негативное влияние на качество и пунктуальность перевозок;

- чрезмерный износ может стать причиной ввода TSR, что приводит к снижению пропускной способности ж.-д. сети;

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

- применение новых видов рельсов и шпал позволяет не только увеличить их срок службы, но и уменьшить стоимость работ по ТО;

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

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

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

Пронумеруем все элементы сети. Будем обозначать L - количество линий; S - множество номеров всех сегментов; - множество номеров всех сегментов линии £; А - множество номеров всех элементов ВСП; а - количество всех элементов ВСП; Aj — множество номеров элементов ВСП, расположенных на сегменте j; - количество элементов ВСП на линии i; cij - количество элементов ВСП на сегменте j; äj/äj - наименышш/наиболыций номер элемента ВСП на сегменте j; а;/а(- - наименьший/наибольший номер элемента ВСП на линии i.

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

Этапами МПУ нужно считать моменты времени 1, ...,Т. Т.к. речь идет не о текущем, а о долгосрочном перспективном планировании (несколько десятков лет), то мы считаем, что один момент времени - это один календарный или финансовый год.

Управление - это решение обновить или не обновить конкретный элемент ВСП в определенный момент времени. В работе вводится оператор управления и: (1, ...,Т} -* {0,1}а, который каждому моменту времени ставит в соответствие булев вектор с размерностью, равной общему числу элементов ВСП. При этом если itfc(t) = 1, то элемент ВСП к обновляется в момент времени t, если uk(t) = О, то нет.

Основной фазовой переменной является возраст элемента ВСП в годах. Т.к. мы считаем, с одной стороны, известными все инженерные характеристики элементов ВСП, с другой стороны, строго формализованными нормы назначения работ по ТО, а также заданными оценки трафика, ожидаемый уровень цен и т.д., то все характеристики, связанные с износом конкретного элемента ВСП (стоимость работ, вероятность ввода TSR и пр.), могут быть однозначно определены по его возрасту. По аналогии с управлением вводится фазовый оператор износа х: {О, ...,Г} -» Ма, для которого xk(t) трактуется как возраст элемента ВСП к в момент времени t. Динамика фазовой переменной однозначно определяется выбран-

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

Хк(0 = 4>(uk(t),xk(t - D) = {J(t - 1} + г' ^ : °'к Е АЛ е {1.....n (1)

хк(0) = х%, к Е А, ' (2)

где хк - возраст элемента ВСП к на начало периода прогнозирования.

На возраст элементов ВСП накладываются ограничения, в первую очередь, на максимальный нормативный срок службы. Логично также предположить, что чересчур раннее обновление априори не выгодно (также, такие ограничения целесообразно ввести и для сокращения количества допустимых состояний системы): Гцйе^сМ, к Е А, t Е {1,..., Т]. (3)

Анализ мировой практики показывает, что работы, связанные с обновлением ВСП лучше объединять в проекты, которые целесообразно проводить не чаще, чем один раз в 5-10 лет. Это позволяет сократить суммарное время, в течение которого участок пути функционирует неполноценно (работы по замене ВСП зачастую приводят к изменению расписания, дополнительной нагрузке на альтернативные маршруты, задержкам поездов и т.д.). Кроме того, при организации более крупных проектов можно снизить стоимость работ за счет эффекта масштаба. Нельзя забывать и о возможной негативной реакции пользователей ж.-д. услуг на решение компании проводить работы ежегодно. Поэтому в работе вводится ограничение на множество допустимых управлений: ub{t) + uc{t - гр~) < 1,

b,c Е {äi,..., aj, i E {1,... ,L},t E {1.....T],lp E {1,..., p;}, t — t/) > 0, 1 '

где pi> 1 — «пауза» в годах между обновлениями на линии i. Разумеется, если подобная практика не применяется компанией, то ограничения исключаются.

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

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

//r(^(t),t), jES,te{ 1.....Г},

здесь и далее u;(t) = (uäj(t),...,uä.(t)), j E S, t E {1, ...,Г}; аналогичные обозначения будут введены для фазовых переменных.

Стоимость подавляющего большинства работ, направленных на ТО элементов ВСП, зависит от состояния этих элементов. При этом, чем больше возраст

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

/;sm<y(t),t) = £ /Г'СгДг),О, j es,t е {i.....г},

keAj

где f£m{xk(jt), t) - приведенная стоимость работ по ТО элемента ВСП к.

Чрезмерный износ может привести к вводу временных ограничений на скорость передвижения. Причина ввода ограничений заключается в необходимости соблюдать требования по безопасному движению поездов. При значительном износе пути передвижение на максимальной скорости становится небезопасным, поэтому поезда вынуждены снижать скорость. Это приводит к снижению пропускной способности, т.е. фактически означает, что за фиксированный промежуток времени количество перевезенных пассажиров и объем груза будет меньше. Поэтому при планировании работ важно учитывать потери, которые в результате ввода TSR могут понести пользователи: пассажиры (потеря трудочасов), перевозчики (потеря пассажиров, грузоотправителей), грузополучатели (пени и штрафы за задержку товаров) и т.д. Несмотря на то, что данные потери, скорее всего, не отразятся на показателях компании, тем не менее, их можно включить в модель, т.к. основной задачей компании является «удовлетворение рыночного спроса на перевозки, повышении эффективности деятельности и качества услуг» (из миссии ОАО «РЖД»),

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

fjsh(xj(t), t) = P (ATSRäjX или ... или ATSRäjX) ff$r(t), j E S,t E {1.....T],

где P(ATSRkt) = fkh(xk(t),t), к E A,t E {1, ...,T} - вероятность ввода TSR по причине чрезмерного износа элемента ВСП к в момент времени t, а //5r(t) - величина потерь при гарантированном вводе TSR на сегменте j в момент времени t.

Рассмотрим пример, поясняющий причины ввода штрафа за раннее обновление элемента ВСП (рис. 1). Пусть некий элемент ВСП последний раз был заменен в момент времени А, при известных параметрах износа срок службы истекает в момент времени С. Сравним два плана обновления: в первом случае элемент ВСП заменяется в момент времени С, а во втором - в моменты времени В и D, при этом D выходит за пределы исследуемого периода. Суммарная приведенная стоимость работ по ТО во втором случае будет меньше, т.к. состояние элемента ВСП более новое. При этом стоимость работ, связанных с заменой, будет сопоставимой

и

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

А - Последнее обновление В - Раннее обновление С - Рекомендуемый момент с-ЕноЕяения □ -Рекомендуемый момент обновления Се случаеЕ

А 8 С О t

Рис. 1. Случай раннего обновления элемента ВСП

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

ВСП рекомендованного срока службы. Заметим, что мы вынуждены в записи использовать фазовую переменную с лагом, т.к. в момент обновления возраст сбрасывается. Для того чтобы остаться в рамках МПУ без последействия мы должны ввести дополнительную фазовую переменную г, динамика которой не зависит от управления:

гк(0 = ш(хк(с - I)) = хк(С - 1) + 1, кеА,1е{1,...Т}. (5)

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

= £ С0, ) 6 5,£ е {1.....Т],

кед у

где /кр (ик (С), гк (О, О - величина штрафа за раннее обновление элемента ВСП к в момент времени Ь.

Таким образом, запишем целевой минимизируемый критерий:

т

где = /ГСи'СО, С) + /7т(х'(0,0 + 0 +

/Ди'ки>(0,0. } е5,се{1.....т}.

Когда речь идет о материальных, трудовых или иных ресурсах, неизбежно встает вопрос их ограниченности. Поэтому необходимо ввести ряд ресурсных ограничений, а именно: ограничения на суммарную стоимость работ по обновле-

нию (7), на суммарную стоимость работ по ТО (8), на суммарную длину пути, на которых выполнялись работы по ТО определенных видов (9), на суммарную длину обновляемых элементов ВСП (10):

> //г(и;(0,0<Ь[, teil,... (7)

¡es

t e {1,... Jl (8)

j€S

I t e {l,. ..T},pe{ l, (9)

Jewp,t

Ё l<- t e {l,.. ■ T},Z E {1,. ...zi (10)

где р - вид работы; Р - число рассматриваемых видов работы; Wp t - множество всех сегментов, на которых в момент времени t выполняется работа р; lj - длина сегмента у; Ь{ - максимальная суммарная длина сегментов, на которых может быть проведена работа р в момент времени t; z — вид элемента ВСП; Z - число рассматриваемых видов элементов ВСП; Rz t - множество всех сегментов, на которых в момент времени t обновляется элемент ВСП z; brtz - ограничение на суммарную длину обновляемых элементов ВСП вида z в момент времени t.

Не все эти ограничения могут быть актуальны для разных ж.-д. компаний, поэтому какие-то из них можно опустить или объединить между собой. Так, например, в Дании формируется единый бюджет на ТО, куда входят все виды работ, а в Нидерландах бюджет планируется по отдельным видам работ. Ограничения на объем работ могут быть неактуальны для таких крупных путевых хозяйств как в России.

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

min{(6)|(l)-(5),(7)-(10)}, (П)

min{(6)|(l)-(5)}. (12)

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

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

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

Очевидно, что при отсутствии «связывающих» ресурсных ограничений решение задачи (12) сводится к поиску оптимального плана работ для отдельных ж,-д. линий. Поэтому вместо (12) будем рассматривать локальную задачу для некоторой линии i (12') (по сравнению с (12) изменена размерность области действия операторов управления и износа):

min{(6")| (u,x,z)eG}, (12')

где С = {(u,x,z):u: {1,...,Г} -> {0,1}а',х,z: {0.....Т] -* 1Г',(Г) - (5')},

*k(t) = 0(uk(t).*k(t- 1)), к е {1, ...aj,t е {1.....Т], (Г)

^fc(O) = ^fe+a,-!. ке{1....а,}, (2')

Ле{1,...а,ие{1.....т], (3')

Ub(t) +uc(t-xp) < 1, /4-ч b,c е{1.....af}, t Е {1,...,Т},гр е {1.....Pii.t-Tp > 0, '

zfc(t) = Cü(xk(t-1)), ke{l,...allte{l,...T}, (5-)

т

.....(6-)

t=l j€Si

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

Несмотря на то, что задача (12') является задачей динамического программирования, в которой Т - число этапов, и — управляющее воздействие, х и z — фазовые переменные, применить напрямую принцип оптимальности Беллмана не представляется возможным ввиду т.н. «проклятия размерности». Тем не менее, отметим несколько особенностей, которые позволят преодолеть это препятствие:

- количество состояний зависит от количества элементов ВСП (а¿): с помощью принципа оптимальности за разумное время можно найти решение только при ai не больше трех-четырех;

- количество состояний ограниченно из-за условия (3');

- количество состояний можно резко сократить, если для некоторого подмножества моментов времени В с {1, ...,Т} дополнительно ввести ограничения вида: u(t) = (О, ...,0)т, t S В.

Проиллюстрируем эти особенности на примерах. На рис. 2а представлена динамика числа состояний для одного сегмента из 1-3 элементов ВСП при следующих условиях: хк(0) = = 5,xk(t) < 50, V/c, t. Число состояний системы для 3 элементов много больше, чем для двух и одного. Начиная с некоторого момента число состояний стабилизируется. Максимальное число состояний равно 68660. Если запретить проводить обновления в некоторые моменты времени В =

{1,... 7,}\{8Д6,24,32,40,48}, то максимальное число состояний системы из 3 элементов будет равно 216 (рис. 26), что значительно меньше, чем в первом случае.

3 элемента 2 элемента — 1 элемент Момент времени

а. б.

Рис. 2. Пример динамики числа допустимых состояний

Введем два определения. Под проектами допустимого управления и будем понимать булев вектор р = (maxu(l), ...,maxu(T))T. Т.е. проект применительно к отдельному элементу ВСП означает лишь возможность или разрешение провести обновление, а не сам факт обновления. Процессом управления, удовлетворяющим вектору проектов р = (р1,р2> ■■■•Pt)T> t ^ Т, будем называть такой процесс (u,x,z), который принадлежит множеству Gp, определяемого равенством

Gp = {(u,x,z) е G:u(t) = (0,... ,0)т, Vt: pt = 0}. Т.е. накладывается дополнительное ограничение - производить обновление можно только в те моменты времени, для которых соответствующий элемент вектора проектов р не равен нулю. Очевидно тождество:

min{(6")l(u,x,z) е G} = min jmin{(6~)|(u,x,z) £ Gp}|.

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

Возникает естественный вопрос: сколько векторов проектов может быть? К сожалению, экстенсивным образом подобрать оптимальный вектор проектов практически невозможно (например, при Т = 50 годам и pi = 5 их свыше 150 тыс.). Осуществить поиск наилучшего вектора проектов можно с помощью метода ветвей и границ. Данный метод, впервые описанный А. Ландом и А. Дойгом, получил признание после того, как Дж. Литл показал, как с его помощью решать задачу коммивояжёра высокой размерности. Для использования метода необходимо определить рекурсивную процедуру ветвления множества допустимых решений и способ получения оценки для ветви. Несмотря на простой принцип работы метода, найти эффективное его применение к реальным задачам получается далеко не так часто, что зачастую связано со сложностью получения нижних оценок и нахождения процедур не слишком разветвляющих дерево решений.

В диссертации предложены два варианта процедуры ветвления. Условно говоря, первая процедура отвечает на вопрос «Что должно произойти в следующий момент времени?». Деление множества допустимых процессов представлено на рис. За. Вторая процедура отвечает на вопрос «Когда необходимо организовать следующий проект?». Для того, что сузить перечень моментов времени, в которые может быть организован проект, но при этом не исключить оптимального решения, можно использовать процедуру ветвления, представленную на рис. 36. Данной процедурой исключаются из рассмотрения все векторы проектов, в которых число подряд идущих нулевых элементов превосходит 2р. Это допустимо ввиду следующего свойства задачи (Г)-(б'): если р°,рг £ {ОД}Т:р° < Рг.^Г £ {1, ...,Т}, то гшпи{(6") | (и, х, г) £ Сро} > 1гппи{(6")|(и,х,2) £ Ср1}, которое справедливо, т.к. Сро с с 1,

а. б.

Рис. 3. Процедуры ветвлення

Для получения оценки часто искусственно расширяют область допустимых процессов управления таким образом, чтобы на более широкой области было проще найти решение. Полученное решение используется в качестве нижней оценки, т.к. оно гарантированно не больше решения исходной задачи. Рассмотрим произвольную ветвь Ь. Используя этот прием, в диссертации предложено искать оценку в следующем виде: т1п{(6л)|(и, х, г) в Сь} >

и

!<1ь

1=1 где

- йь — количество элементов в векторе Ь;

- прогнозный период разбивается на две части: в «левой» части (С £ {1, ...,йь}) уже известны даты работ - они определены вектором проектов (ветвью) Ь, а всю суммарною дисконтированную стоимость работ «правой» части ([ £ {(1Ь + 1,... ,Т}) мы заменяем неким терминальным слагаемым Му(х5/(йь), йь), которое должно гарантировать, что оценка окажется не больше искомого минимума (условие (13)):

МДхт,т) < т]п

и >

(Е С ,

4 ' ' Xх,Г

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

- множество F*' определяется по аналогии с Gb с поправкой на области определения и действия операторов (рассматривается только «левая» часть периода, вместо всей линии рассматривает отдельный сегмент):

F*J = {{u,x.z):u:{l.....db} - {0,l}a>,x,z:{0, ...,db] -» №, (14) - (17)},

u(t) = (0.....0)T, te{ 1.....db}:bt = 0, (14)

xk(t) = 0(uk(t),xfc(t-l)), zk(t) = a>(xk(t- 1)),

1.....aj},te{ 1.....db], {П)

*k(0 ) = x°k+ärl, ke{ 1.....aj], (16)

xk(t) E X£+äj_v fee{l.....üj},t E {l,...,db}; (17)

- множество GSxlr определяются по аналогии с G с поправкой на начальное состояние элементов ВСП (условие (18)) и области определения и действия операторов (рассматривается только «правая» часть периода, вместо всей линии рассматривает отдельный сегмент):

GSJr = {(u,x,z):u: [т + 1,7*} -» {0,l}a),x,z: {т.....Т) -> №4(18) - (21)},

х(т) = х\ (18)

XfcCO = 0(ufc(t),xk(t — 1)), zk(t) = 0){xk(t- 1)),

kE{ 1.....aj},tE{ T+l.....П

u„(t) + uc(t-ip) < 1,

b,ce {1.....üj], t E {r + 1.....T},xp€ {1.....pil t-ip>r, ( '

Xk(t) e x£+äj_v ke{ 1.....а;}де{т + 1.....Т]. (21)

Ключевым становится вопрос, каким образом определить терминальное слагаемое, т.к., несмотря на то, что точный минимум в формуле (13) также является оценкой, для его определения могут потребоваться ресурсоемкие вычисления (например, как случай трех элементов ВСП на рис. 2а). В диссертационной работе для сокращения объема вычислений было предложено использовать сепарабель-ные по и, х и z функции, всюду не превосходящие слагаемых целевого критерия (функция f(xv ...,хп) называется сепарабельной по аргументам х1,...,хп, если 3gt(x),i = 1, ...,n:f(xlß ...,xn) = Zf=i В этом случае для получения оцен-

ки нужно решить локальные задачи оптимизации для каждого отдельного элемента ВСП, размерность которых принципиально меньше (случай одного элемента ВСП на рис. 2а). Функции fjm(x,t) сепарабельны, т.к. представляют собой сумму дисконтированной стоимости работ по ТО по соответствующим элементам ВСП. То же самое касается функций fjP{u,z,t)- Дисконтированная стоимость работ по замене ВСП на сегменте не превосходит суммарной стоимости работ по замене отдельных элементов ВСП за вычетом максимально возможной экономии от совместного обновления в пересчете на один элемент ВСП:

ai

fjsr(u, 0 > £ uk (ffr(e'(k), t) - Bj(t)), j 6 Si, k=1

где e': fl,..., аЛ -> {0,l}aJ определяется равенством e;(i) = j6^ ^ а

vejiCO = 0, к Ф i,

ZaJJfrie4m),t)vm-f^v,t)) Bj(t) = max^gjg 0)т---âj-. Используя свойства вероят-

ности для функции ffh(x, t) методом мат. индукции доказано, что ftsr(t) / / \аЛ

//" (*, t) > ^^ 2,(i - (i - (Хк, t)) ), je s^

1 k=1

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

Данный метод оптимизации был проверен на реальных данных, описывающих ж.-д. сеть Дании. Были определены оптимальные проекты на прогнозном периоде: 2012-2061 гг. Общее количество неизвестных равняется 5249950. Чистое время расчета задач оптимизации для 49 линий составило 20 мин. 23 сек. Расчет производился в четыре потока на компьютере с параметрами: Intel® Core™ i5 CPU К 655 @ 3.20 GHz 3.19 GHz; 16Gb RAM; x64. Приложение1 написано на языке С# под .NET Framework 4 и интегрировано в АК «Прогноз-5». В табл. 1 показаны основные параметры и время 10 наиболее продолжительных расчетов. Видно, что пауза между обновлениями оказывает большее влияние, чем число неизвестных.

Таблица 1

Параметры и время расчета__

Линия Время Неизвестные Pi

71 448" 331 600 5

16 244" 249 700 5

98 1'38" 150 250 5

21 1'06" 263 200 8

15а 43" 102 550 5

23Ь 36" 337 800 10

32 35" 191 050 10

83 32" 146 350 10

55 32" 132 400 10

85 30" 148 650 10

Полученные результаты были также исследованы на изменчивость в зависимости от длины прогнозного периода. Для этого был проведен расчет на укороченном периоде: 2012-2054 гг. В первой части периода (2012-2028 гг.) результаты

1 Свидетельство Российского агентства по патентам и товарным знакам №2012618706 от 24.09.2012

об официальной регистрации программы для ЭВМ: «Программный комплекс моделирования и оптимизации состояния железнодорожной инфраструктуры в долгосрочном периоде» (ПК МОСЖИДП).

оказались практически неизменны: только для 2 из 61 проектов суммарная стоимость проекта изменилась более чем на 5%. Данный период достаточен для принятия так тактических, так и стратегических решений. Поэтому все ключевые показатели эффективности посчитаны именно на этом периоде и по договоренности с заказчиками проекта приведены в работе в относительных показателях.

Для проверки эффективности принимаемых решений полученные результаты (далее план работ В) сравнили с планом, в котором замена элементов ВСП происходит сразу по истечении нормативного срока эксплуатации (далее план работ А). Разумеется, план работ А не удовлетворяет ограничениям (4") и не может быть принят ЛПР. При использовании плана работ В можно сократить расходы на обновление на 15%. Это достигается благодаря экономии от совместного обновления, которая учитывается в процессе оптимизации. На рис. 4а приведена структура работ по обновлению при использовании плана А. Доля работ, при которых меняется только один элемент ВСП (выдвинутые секторы), превышает 70%. На рис. 46 показано распределение работ при использовании плана В. Доля работ, при которых обновляется несколько элементов ВСП, резко возросла и превысила 55%. Однако в результате превышения рекомендованных сроков эксплуатации на 67% возросли расходы на ТО и появились потери, вызванные вводом TSR.

ш Балласт (только) Шпалы (только) Рельсы, шпалы и бзлласт Щпалы и балласт Рельсы (только) Рельсы и балласт Рельсы и шпалы Рис. 4. Структура работ по обновлению

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

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

1. На практике зона с TSR «накладывается» и на соседние участки, на которых не наблюдается чрезмерного износа. Это связано с тем, что поезду требуется время на то, чтобы изменить скорость. Поэтому, если после реализации проекта останутся элементы ВСП с чрезмерным износом, то зоны с TSR могут распространяться, в том числе, и на только что обновленные участки пути.

2. Если из проекта будет исключен ряд элементов ВСП, то из-за ограничения на паузы между обновлениями в следующий раз они могут быть заменены только через несколько лет. Если какой-то элемент ВСП изначально был включен в проект, то, скорее всего его возраст близок к сроку службы. Если не обновлять такой элемент ВСП в течение нескольких лет, то расходы на ТО и потери, вызванные вводом TSR, начнут стремительно возрастать.

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

Алгоритм 1. Приняв данную особенность в качестве дополнительной предпосылки, можно предложить следующий алгоритм для нахождения решения задачи (11):

1. Для каждой линии решается своя задача (12"). В результате формируется исходный перечень проектов, не учитывающий ограничений на ресурсы.

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

3. Для тех линий, на которых были отклонены проекты, повторно решается задача (12'). Рассматриваемые моменты времени: т + 1, ...,Т. Начальное состояние берется из условия, что в момент времени г ни один элемент ВСП не был обновлен.

4. С учетом скорректированного перечня проектов повторяются этапы 2 и 3 до тех пор, пока не будут утверждены проекты для всех моментов времени.

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

Рис. 5. Блок-схема Алгоритма 1

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

Рассмотрим подробнее процедуру отбора проектов (этап 2). Пусть в момент времени t найдено множество проектов Р = {р1; р2,... pn}, п < L. Каждый проект р; характеризуется стоимостью и объемами необходимых ресурсов. Обозначим полный набор используемых ограничений вида (7) и (10) вектором

b = (b1,b2, ...,ЬтУ, а ограничений (8) и (9) вектором е = (е1,е2, ....е^)7. Все элементы векторов bue должны быть положительными. Через а^ > 0 обозначим объем ресурса типа г, необходимого для реализации проекта j. Обозначим как dkj > 0 экономию ресурса к в случае выполнения проекта j. Также определим

вектор е° = (е°,е°, ...,е°)Т, каждый элемент которого е° > 0 равен суммарному объему ресурса к при условии, что на сети не выполняется ни один проект. Если ввести вектор с = (с1(с2,..., сп)т, каждый элемент которого Су означает относительную ценность проекта j в смысле минимизации целевого критерия (6), то можно сформулировать следующую задачу линейного целочисленного программирования (ЗЛЦП):

п

CjXj -> max, (22)

7=1

п

^аиХ]<Ьи i = l,2.....m, (23)

7=1

Xj £ {0; 1}, j = 1,2.....п, (24)

П

dkjXj >e°-ek, к = 1,2,..., q. (25)

7 = 1

Здесь для искомых переменных использовано следующее обозначение:

(0, если проект i не выполняется, X, = / . У = 1,2,...,л.

1 (1, если проект j выполняется, J

Для нахождения вектора с можно использовать один из следующих вариантов:

1. Учитывая, что выполнение проекта позволяет избежать дополнительных расходов на ТО, вызванных превышением элементов ВСП рекомендованных сроков эксплуатации, то чем больше эта величина, тем выше, при прочих равных условиях, должна быть относительная ценность проекта.

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

3. Можно использовать разницу между минимумами (или оценками минимумов) целевой функции задачи (12') при выполнении/невыполнении проекта.

Заметим, что ограничения (25) зачастую не оказывают влияния на решение задачи. Во-первых, очевидно, если ек — ек < 0,к = 1,2, ...,q, то шах{(22)|(23) — (25)} = тах{(22)|(23),(24)}. Такая ситуация возникает, если бюджетное или ресурсное ограничение, связанное с ТО, не меньше, чем максимально возможный

объем требуемого ресурса. Ж.-д. компании могут довольно точно оценить как гарантированный, так и максимальный объем работ, связанных с ТО, т.к. их приходится проводить каждый год. Поэтому нарушение этих ограничений априори маловероятно. Во-вторых, для выполнения ограничений (25), необходимо, чтобы как можно больше проектов было реализовано. Аналогичное поведение заложено и в целевой функции (22): для того, чтобы её значение было больше, нужно выполнить как можно больше проектов. Однако достижению этой цели мешают ограничения (23). И наконец, множество допустимых решений задачи (22)-(25) может оказаться пусто, в то время как задача (22)-(24) всегда имеет решение. Таким решением может являться тривиальное (нулевое) решение или решение задачи (22),(23),(26), в котором дробные значения Xj заменяются нулевыми (число дробных значений в оптимальных решениях линейных задач не превосходит т). Этот факт относится к вопросу принятия решений: в случае невозможности получить допустимое решение важно знать «хорошее» недопустимое решение.

О < Xj < 1, j =1,2,...,п. (26)

Таким образом, вместо задачи (22)-(25) бывает целесообразно решать задачу (22)-(24), известную как задача о ранце. Ее свойства хорошо изучены и разработаны многочисленные эффективные методы решения (И.Х. Сигал, A.A. Корбут и др.)

Алгоритм 2. При решении задачи (12') методом ветвей и границ может быть получено некоторое количество допустимых решений, близких к оптимальному. Существует вероятность того, что оптимальное решение задачи (11) может представлять собой комбинацию из этих решений.

Пусть для каждой линии был получен набор допустимых «неплохих» решений задачи (12'): {й\,й\, ...üyj, ...,\u[,Ü2, — Tij/L}, где - вариант управления v на линии I, допустимый с точки зрения задачи оптимизации работ на этой линии и оптимальный для некоторого предустановленного вектора проектов. Количество вариантов решений для разных линий может отличаться: V1 Ф V2 Ф •■■ Ф VL. Пронумеруем ограничения, участвующие в задаче: i = 1,...,/. Введем обозначения: cj, - значение целевой функции задачи (12') для линии I при использовании управления ul; Ь{ - ограничение на показатель t в момент времени t; - значение показателя i в момент времени t, при использовании управления ulv; xlv £ {0,1} - признак использования решения v на линии I (если xj, = 1, то используется, если xl = 0, то не используется). Если ограничиться рассмотрением выбранных вариантов управления, то можно сформулировать следующую ЗЛЦП:

L V,

c^xj, -» min, (27)

( = 1 V = 1

L Vt

t= 1.....T,i = l...../, (28)

¡ = 1 V=1

Vi

= 1. l = l.....L, (29)

V = 1

xj, e {0,1}, Vl,v:l = l,...,L,v=l,...,Vl. (30)

В отличие от Алгоритма 1, Алгоритм 2 не гарантирует нахождение решения, т.к. множество решений (27)-(30) может оказаться пусто. Поэтому он может быть малоэффективен при наличии жестких ресурсных ограничений. Однако Алгоритм 1 не рассматривает возможности досрочного выполнения проектов. С этой точки зрения с помощью Алгоритма 2, возможно, удастся получить более предпочтительный ответ.

В работе на теоретическом уровне также рассмотрен подход, позволяющий при помощи специальных преобразований свести задачу (11) к виду ЗЛЦП.

В табл. 2 приведены результаты вычислительного эксперимента, в котором сравнивается план работ В (не учитывающий ресурсные ограничения) и план работ С, полученный с помощью Алгоритма 1 (учитывающий эти ограничения). В результате того, что часть работ была отложена из-за нехватки ресурсов, возникли дополнительные расходы на ТО и потери, связанные с вводом TSR. Кроме того, стоит отметить общее снижение качества оказываемых услуг: возросло число задержанных поездов, увеличилось количество участков с TSR и т.д.

Таблица 2

Сравнение планов работ В и С _

Показатель План С/план В

Расходы на ТО, DKK 1,16

Потери, связанные с вводом TSR, DKK 1,29

Количество задержанных поездов, шт 1,24

Количество участков с TSR, шт 1,23

«Потеря времени» пассажиров, мин 1,27

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

Заключение

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

III. ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в журналах и изданиях, рекомендованных ВАК:

1. Петровец Ю.О. Оптимальное планирование работ по обновлению железнодорожной инфраструктуры (на примере компании Banedanmark) // Вестник Пермского университета. Серия «Экономика». 2012. №3(14). С. 24-31. (0,73 п.л.)

2. Петровец Ю.О., Андрианов Д.Л. Задача оптимального планирования работ по обновлению железнодорожной линии: постановка, алгоритмы решения // Проблемы управления. 2013. №1. С. 50-56. (авт. 0,29 п.л.)

3. Петровец Ю.О. Задача оптимального планирования работ по обновлению железнодорожных мостов: постановка, методы оптимизации, вычислительный эксперимент // Управление экономическими системами: электронный научный журнал. 2012. №12(48). URL: http://www.uecs.ru. (0,55 п.л.)

Монография:

4. Петровец Ю.О. Оптимальное планирование работ по обновлению железнодорожной инфраструктуры: монография. Пермь: Перм. гос. нац. исслед. ун-т., 2013. 108 с. (6,28 п.л.)

Публикации в других журналах и изданиях:

5. Петровец Ю.О. Об одной задаче оптимизации для железнодорожного транспорта // Наука XXI век: новый подход: сб. ст. IV междунар. научно-практической конференции. Петрозаводск: Петропресс, 2012. С. 57-62. (0,2 п.л.)

6. Петровец Ю.О. Об одной особенности организации проектов по обновлению железнодорожной инфраструктуры // Экономика и управление в XXI веке: сб. ст. II Международной научной конференции. Ставрополь: Центр научного знания «Логос», 2012. С. 221-223. (0,15 п.л.)

7. Петровец. Ю.О. О применении генетического алгоритма для решения задач линейного программирования с булевыми переменными // Информационные системы и математические методы в экономике: сб. науч. тр. / общ. ред. М.В. Радионовой; Перм. гос. нац. иссл. ун-т. Пермь, 2011. Вып.4. С. 225-231. (0,25 п.л.)

8. Петровец Ю.О. Проблемы и перспективы долгосрочного планирования при разработке программ по модернизации железнодорожной инфраструктуры // Финансовые проблемы и пути их разрешения: теория и практика : сб. науч. тр. 13-й Междунар. науч.-практ. конференции. Спб.: Изд-во Политехи, ун-та, 2012. С. 121-122. (0,1 п.л.)

Подписано в печать 25.08.14. Формат 60x84/16. Усл. печ. л. 1. Тираж 150 экз. Заказ№ 1082

ООО «Типография «Растр» 614000, Пермь, ул. Стахановская, 54, лит. М.