Диссертация (Математическое моделирование в задачах планирования и организации железнодорожных перевозок методами теории графов и комбинаторной оптимизации и численные методы их решения)

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ (НАЦИОНАЛЬНЫЙИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)На правах рукописиРассказова Варвара АндреевнаМатематическое моделирование в задачах планированияи организации железнодорожных перевозок методамитеории графов и комбинаторной оптимизации ичисленные методы их решенияСпециальность 05.13.18 —«Математическое моделирование, численные методы и комплексы программ»Диссертация на соискание учёной степеникандидата физико-математических наукНаучный руководитель:доктор физико-математических наук, профессорКибзун Андрей ИвановичМосква — 20172ОглавлениеВведение. .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Глава 1. Математическое моделирование в задачахпланирования и организации железнодорожныхперевозок . . . . . . . . . . . . . . . . . . . . . . . . . .4. . . .171.1.Основные используемые понятия теории графов . . . .

. . . . . .171.2.Теоретико–графовые модели в задачах планирования иорганизации железнодорожных перевозок . . . . . . . . . . . . . .1.2.1.23Теоретико–графовая модель для решения задачиформирования бесконфликтного набора нормативныхниток. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .23. . . . . . . . . . . . . . . . . .23. . . . . . . . . . . . . . .28Ориентированный мультиграфНеориентированный граф конфликтов1.2.2.Теоретико–графовая модель для решения задачи оназначении и перемещении локомотивов. . . . . . . .

. .30Глава 2. Задача планирования железнодорожных перевозок наэтапе формирования бесконфликтного наборанормативных ниток . . . . . . . . . . . . . . . . . . . . . . .352.1.Постановка. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .352.2.Решение . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .392.2.1.Алгоритм «Бегущая волна»392.2.2.Алгоритм расшифровки монотонной булевой функции. . . . . . . . . . . . . . . . .. .43. . . . . . . . . . . . . . . . . . . . . . . . . .46. . . . . . . . . . . . . . . . . . . . . . . .53Жадный поискПоиск с возвратомГлава 3. Задача организации железнодорожных перевозок наэтапе назначения и перемещения локомотивов . .

. . .3.1.3.2..55. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .553.1.1.Теоретико–множественный подход . . . . . . . . . . . . . .553.1.2.Теоретико–графовый подход. . . . . . . . . . . . . . . . .60Решение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66Постановка33.2.1.Алгоритм назначения и перемещения локомотивов. . . .673.2.2.Алгоритм покрытия . . . . .

. . . . . . . . . . . . . . . . .72Глава 4. Проблемно–ориентированные программные комплексы844.1.Программный комплекс для решения задачи формированиябесконфликтного набора нормативных ниток . . . . . . . . . . . .4.2.84Программный комплекс для решения задачи о назначении иперемещении локомотивовЗаключение .Литература. . .

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

Как правило точное решение задач комбинаторной оптимизации большойразмерности является избыточным с точки зрения практической реализациирешения, и, кроме того, поиск точного решения требует колоссальных вычис­лительных затрат. В этой связи особый интерес представляет область разработ­ки эффективных вычислительных алгоритмов поиска приближённого решения.В то же время любой эвристический подход требует подтверждения работоспо­собности, и, таким образом, неотъемлемым этапом исследования выступает раз­работка комплекса прикладных программ, на основе которого осуществляетсяряд вычислительных экспериментов, подтверждающих эффективность предло­женных подходов к решению исследуемых задач.В работах [56], [64], [62], [28], [48], [47], [3], [55], [31], [19] получили обос­нование графовый и комбинаторный методы математического моделированияв приложении к решению прикладных задач управления железнодорожнымиперевозками.

Разработанные в диссертации теоретико–графовые модели, кро­ме структурных свойств железнодорожных сетей, учитывают также и комби­наторный характер исследуемых задач, что позволяет значительно расширитьобласть разработки вычислительных алгоритмов решения.Задача планирования железнодорожных перевозок исследуется, в том чис­ле посредством методов теории графов и комбинаторной оптимизации, в кон­тексте задач теории расписаний в работах [36], [37], [38], [52], [53].

В рамках раз­работанной теоретико–графовой модели исследуемая прикладная задача пла­нирования сводится к задаче расшифровки монотонной булевой функции, по­рождённой неориентированным графом. В работах [4], [5], [61], [6], [7], [8], [23],[24], [25], [26], [27], [39], [40], [41], [45], [42], [43], [44] получены важные резуль­5таты в теории противоречивых систем условий, множество максимальных сов­местных подсистем которых может быть специальным образом поставлено всоответствие множеству максимальных по размеру клик графа. Этот подходполучил продолжение в разработке вычислительных алгоритмов для форми­рования верхнего нуля монотонной булевой функции, особенностью которыхявляется оценка точности приближённого решения.В работах [30], [1], [29], [2] задача организации железнодорожных пе­ревозок на этапе назначения и перемещения локомотивов сводится к задачестохастического программирования.

Постановка задачи организации без учётаограничений на использование и техническое обслуживание локомотивов име­ет определённое практическое обоснование в части нижней оценки точностирешения. В рамках разработанной теоретико–графовой модели, исследуемаяприкладная задача организации сводится к задаче покрытия вершин ориенти­рованного графа минимальным числом путей. Структурные свойства специфи­ческого ориентированного графа совместимости заданий на перевозку позволя­ют ограничиться рассмотрением множества максимальных по включению пу­тей для покрытия вершин графа, и, таким образом, размерность задачи можетбыть существенно снижена.В области разработки алгоритмов комбинаторной оптимизации, линейно­го, целочисленного и динамического программирования, а также алгоритмовна графах, в том числе приближённых алгоритмов, существенные результа­ты получены в [21], [49], [34], [54].

Вычислительные алгоритмы формированияверхнего нуля монотонной булевой функции, порождённой неориентированнымграфом, и алгоритм покрытия вершин ориентированного графа — суть ком­бинаторный и комбинаторно–графовый алгоритмы, на основе которых в дис­сертационной работе разработаны проблемно–ориентированные программныекомплексы для решения исследуемых прикладных задач планирования и орга­низации железнодорожных перевозок.Целью работы является разработка математических моделей и вычисли­тельных алгоритмов для решения прикладных задач планирования и организа­ции железнодорожных перевозок.Для достижения поставленной цели решаются следующиезадачи:1) разработка математической модели для решения задачи планированияжелезнодорожных перевозок на этапе формирования бесконфликтного набо­ра нормативных ниток.

Исследование свойств неориентированного графа кон­6фликтов и сведение исходной задачи к задаче расшифровки монотонной буле­вой функции, порождённой неориентированным графом,2) исследование свойств максимального верхнего нуля и разработка вычис­лительного алгоритма формирования верхнего нуля монотонной булевой функ­ции, порождённой неориентированным графом,3) разработка математической модели для решения задачи организациижелезнодорожных перевозок на этапе назначения и перемещения локомотивовбез учёта ограничений на использование и техническое обслуживание локомо­тивов. Исследование свойств ориентированного графа совместимости заданийна перевозку и сведение исходной задачи к задаче минимального покрытия вер­шин ориентированного графа множеством путей,4) исследование свойств минимального покрытия и разработка вычисли­тельного алгоритма покрытия вершин ориентированного графа множествоммаксимальных по включению путей,5) разработка и тестирование программных комплексов, реализующих ал­горитм формирования верхнего нуля монотонной булевой функции, порождён­ной неориентированным графом, и алгоритм покрытия вершин ориентирован­ного графа множеством максимальных по включению путей.Научная новизна.