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

. . ,} характеризует множествостанций, и множество дуг ⊆ {( , ) : | − | = 1} характеризует множе­ство ориентированных перегонов, связывающих соседние станции.Для каждого ориентированного перегона ( , ) , соответствующегонекоторой дуге ориентированного графа сети, полагаются заданными:1) профиль дороги ℎ, ,2) вес брутто поезда , допустимый к перевозке на перегоне,3) максимальная допустимая скорость max ( , ) движения по ориентированному перегону ( , ) ,−4) скорость →н ( , ) отправления поезда со станции ,→−5) скорость к ( , ) прибытия поезда на станцию ,6) время н ( , ) отправления поезда со станции ,7) время , движения поезда по ориентированному перегону ( , ) ,и, при заданных 1 − 7 , можно выбрать график движения , () , как функ­цию расстояния, пройденного от станции , таким образом, что каждомуграфику(︀)︀ , () соответствуют минимальные энергозатараты на перевозку , (·) , способ расчета которых, также как и способ задания графикадвижения, в рамках работы не рассматривается.Энергоэффективная стратегия движения по ориентированному пере­гону ( , ) определяется набором параметров:(︀−)︀→−− ( , ) = →н ( , ) , →к ( , ) ,н ( , ) ,, , , (·) ,и для различных заданных и расчетных значений параметров множествоэнергоэффективных стратегий движения по ориентированному перегону7графа сети определяется множеством:{︁→− ( , ) = ( , ) =}︁(︀− )︀−= →н ( , ) , →к ( , ) ,н ( , ) , , , ,(·) , = 1,2, .

. . ,где отвечает мощности множества различных энергоэффективных стра­тегий движения по ориентированному перегону.Ориентированный мультиграф:(︁{︀}︀)︁→−G = V = {vi }, E = (v , v ) ),V : {1 , . . . , } ,{︁→}︁}︁⋃︁ {︁−E: ( , ) = ( , ) : | − | = 1 ,имеет множество дуг, соответствующее множеству энергоэффектив­ных стратегий движения по всем ориентированным перегонам участка(1 , 2 , . . .

, ) графа сети, и служит теоретико–графовой моделью в зада­че планирования на этапе формирования множества энергоэффективныхнормативных ниток графика движения поездов.→−В ориентированном мультиграфе G для < допустимые(v , v )-пути определены как последовательности дуг графа таким об­разом, чтобы для энергоэффективных стратегий движения, соответствую­щих дугам(v1 , v2 )1 , (v2 , v3 )2графа, следующим друг за другом в допустимом (v , v )-пути, выполнялисьусловия:{︃→−−н 2 (2 ,3 ) = →к 1 (1 ,2 ) ,н2 (2 ,3 ) > н1 (1 ,2 ) + 1 ,2 ,и аналогично определяются допустимые (v , v )-пути.Нормативной ниткой графика движения поездов назы­вается любой допустимый (v , v )- или (v , v )-путь, и множество{︀(︀)︀}︀ = n = н (n) ,н (n) ,к (n) ,к (n) ,Определение 1.где н , н , к , к отвечают параметрам энергоэффективных стратегий, со­ответствующих первой и последней дугам, входящим в путь, содержитвсе нормативные нитки графика движения поездов.Если для каждого ориентированного перегона ( , ) и нормативнойнитки n ∈ однозначно определен номер пути ( , ,n) , допустимого8для движения, и задано min — некоторое минимальное расстояние, допу­стимое между поездами при движении по одному и тому же ориентирован­ному перегону, то для рассматриваемого периода планирования [0 , ] , где0 и – время начала и время окончания периода планирования, соответ­→−ственно, в ориентированном мультиграфе G = (V, E) определены понятияоднонаправленного и разнонаправленного конфликтов, и отношение кон­фликтности.Неориентированный граф конфликтов = ( , ) , где {n ,n } ∈ ,если нормативные нитки n и n конфликтны, служит теоретико–графо­вой моделью в задаче планирования на этапе формирования множествабесконфликтных наборов нормативных ниток графика движения поездов,′и любое подмножество ⊂ , такое что индуцированный граф конфлик­тов пуст:(︁ ′ )︁′⟨ ⟩ = , ∅ ,(1)есть бесконфликтный набор нормативных ниток, и может служить допу­стимым расписанием для практической организации железнодорожных пе­ревозок.→−В ориентированном графе сети Γ определены размеры движения напланируемый период времени в виде матрицы корреспонденций:⃦⃦ℛ = ⃦ ( , )⃦ , = 1, 2, .

. . , , = 1,2, . . . , ,где ( , ) – количество поездов, необходимое к отправке из станции встанцию в планируемый период времени, и план поездоформирования⋃︁=p ( , ) ,( , )∈→−где p ( , ) – путь в Γ , допустимый для выполнения перевозки из станции в станцию .Для заданного бесконфликтного набора () нормативных нитокграфика движения поездов, каждый элемент которого соответствует неко­торому пути из плана поездоформирования , и матрицы ℛ вариантныйграфик движения поездов (,ℛ) ⊆ () устроен таким образом, чтодля каждого элемента ( , ) > 0 существует не менее ( , ) норматив­ных ниток:n ∈ (,ℛ) : н (n) = , к (n) = ,и аналогично, для матрицы ℛ* вида:⃦⃦ℛ* = ⃦* ( , )⃦ , = 1,2, .

. . , , = 1,2, . . . , ,такой, что* ( , ) = 0 , если ( , ) = 0 , = 1,2, . . . , , = 1,2, . . . , ,9вариантный график движения поездов (,ℛ* ) ⊆ () устроен такимобразом, что для каждого элемента * ( , ) > 0 существует не менее* ( , ) нормативных ниток:n ∈ (,ℛ* ) : н (n) = , к (n) = ,и любые нормативные нитки n ∈ (,ℛ) , n ∈ (,ℛ* ) являютсябесконфликтными.Множество возможных перемещений по ориентированным перего­нам:{︀(︀)︀}︀ = (,ℛ) ∪ (,ℛ* ) = n = н (n ) ,н (n ) ,к (n ) ,к (n ) ,упорядочено лексикографически относительно н (n) ,к (n) , и является бес­конфликтным набором нормативных ниток n ∈ (,ℛ) , соответствую­щих заданиям на перевозку, и нормативных ниток n ∈ (,ℛ* ) , соответ­ствующих допустимым перемещениям локомотивов по ориентированнымперегонам сети, и, при заданном действительном положительном ∆ , по­→−рождает ориентированный граф совместимости заданий на перевозку Gтакой, что(︀)︀→−G = , ,{︃к (n ) = н (n ) ,( , ) ∈ ⇔к (n ) 6 н (n ) + ∆ ,(2)где каждая нормативная нитка n ∈ взаимно однозначно соответствуетнекоторой вершине ∈ графа.→−Ориентированный граф G служит теоретико–графовой моделью взадаче организации железнодорожных перевозок.Во второй главе разработаны теоретико–графовый и комбинатор­ный вычислительные алгоритмы для решения задачи планирования же­лезнодорожных перевозок на этапе формирования бесконфликтного набо­ра нормативных ниток.Теоретико–графовый подход к решению исследуемой прикладной за­дачи планирования основан на свойствах неориентированного графа кон­фликтов.

Задан период планирования дней, разбитый на трёхчасовыеинтервалы(1 , 2 , . . . , ) , = 8 ,(3)и параметр init ( ) характеризует интервал, в котором начинается дви­жение по всем нормативным ниткам n ∈ . Алгоритм для начальнойпоследовательности интервалов (1 , . . . , ) и некоторого бесконфликтногонабора′′ ⊆ : init( ) ⊆ 1 ∪ . . .

∪ ,10определяет поднабор∆ ⊆ :{︃init(∆ ) = +1(︁,′′⟨ ∪ ∆ ⟩ = ∪ ∆ , ∅)︁,и алгоритм ℬ для набора ∆ фиксирует некоторым образом поднабор′′∆ ⊆ ∆ такой, что набор ∆ подлежит исполнению.Последовательная реализация алгоритмов и ℬ названа алгоритмом«Бегущая волна» и устроена таким образом, что для очередных суток изпериода планирования, заданных последовательностью интервалов+1 , +2 , . . . , +8 : = 8( − 1) , = 1,2, . . . , ,и плана перевозок, заданного по направлениям в каждые суткиvol→, vol→необходимо выполняются условия⃒(︁)︁′′⃒⃒ ∆ (+1 ) ∪ . . .

∪ ∆ (+8 ),→⃒⃒⃒ = vol→;⃒(︁⃒)︁′′⃒⃒⃒ ∆ (+1 ) ∪ . . . ∪ ∆ (+8 )⃒ = vol → ;→)︁(︁′′′′⟨∆ (1 ) ∪ . . . ∪ ∆ (+8 )⟩ = ∆ (1 ) ∪ . . . ∪ ∆ (+8 ), ∅ , () = : init ( ) = физический смысл которых состоит в формировании набора, равномощ­ного плану перевозок, и бесконфликтного с набором нормативных ниток,актуальным для исполнения в текущие сутки.Схема алгоритма «Бегущая волна» для решения задачи планирова­ния железнодорожных перевозок:1) Период планирования = (1 , 2 , .

. . , 8 )′2) Начальный набор интервалов пуст, = 0, = ∅Пока < 8 :3) Применяя алгоритм , получаем ∆ такой, что init(∆ ) = +1′4) Применяя алгоритм ℬ , получаем ∆ ⊆ ∆′′′5) ← ∪ ∆ , ← + 1Конец условияДругой подход основан на сведении исходной задачи к задаче рас­шифровки монотонной булевой функции. Для заданных вариантного гра­фика⟨︀ (,ℛ)⟩︀ = {n1 ,n2 , . . . ,n } и неориентированного графа конфликтов (,ℛ) = (,) определена булева функция : {0, 1} → {0, 1} ,11такая что () = 1 тогда и только тогда, когда индуцированный подграф⟨︀⟩︀ { ∈ : ∈ supp()} ,где supp() = { : = 1} , имеет по меньшей мере одно ребро, с множе­ством нулей ( ) = { : () = 0} ,множеством верхних нулейmax ( ) = { : () = 0 , (′ ) = 1 ∀ ′ > } ,⊆и множеством максимальных верхних нулей{︂}︂max max ( ) = : || = max{supp() ∈ max ( )} ,|·|⊆⊆порождённая неориентированным графом.Пусть ∈ и для окрестности ( ) индуциро­ванный подграф ⟨ ( )⟩ графа является полным.

Тогда существуетмаксимальный верхний нуль ′ ∈ max max ( ) функции такой, чтоУтверждение 1.|·|⊆′ = 1 .На основании Утверждения 1 разработан вычислительный алгоритм (,0 ) формирования максимального верхнего нуля:Входные данные: , 0Выходные данные: 0 , = 0 для всех = 1, 2, .

. . , таких, что ∈ 0для ∈ 0 выполнятьесли − | ( , 0 )| – вершина в подграфе ⟨0 ⟩// вершина назы­вается –вершиной для целого числа , если | () = | и ⟨ ()⟩ –полный// то ←− 1 (︀)︀0 ←− 0 ∖ { } ∪ ( ,0 )// множество (,0 ) – окрестностьвершины в индуцированном подграфе ⟨0 ⟩ //(, 0 )конец условияконец циклаРеализация алгоритма (,0 ) позволяет определить двоичный на­бор, отвечающий некоторому элементу множества максимальных верхнихнулей функции , или, в случае 0 ̸= ∅ , свести исследование к анало­гичной задаче сниженной размерности для функции ′ ⊆ .12Пусть {1 , 2 , .

. . , } – семейство попарно различныхребер, не являющихся ребрами графа . ТогдаУтверждение 2.max0 ∪{1 ,2 ,..., } > max0 − |{1 , 2 , . . . , }| ,⃒⃒⃒⃒⃒где max0 = ⃒supp() : ∈ max max ( )⃒⃒.|·|⊆На основе Утверждения 2 разработан вычислительный алгоритмℬ (, 0 ) , реализация которого позволяет определить двоичный набор, от­вечающий некоторому элементу множества верхних нулей, или двоичныйнабор, отвечающий некоторому элементу множества верхних нулей, коли­чество единиц в котором служит оценкой для числа единиц в максималь­ном верхнем нуле. В работе представлены подходы, основанные на «жад­ном поиске» и «поиске с возвратом», из которых реализация последнеготребует большего числа итераций, однако позволяет, в случае приближён­ного решения, получить лучшую оценку числа единиц в максимальномверхнем нуле.В третьей главе разработаны теоретико–множественный и теоре­тико–графовый вычислительные алгоритмы для решения задачи органи­зации железнодорожных перевозок на этапе назначения и перемещениялокомотивов без учёта ограничений на использование и техническое обслу­живание локомотивов.Для заданных периода планирования (3), и некоторого бесконфликт­ного набора нормативных ниток графика движения поездов{︁(︀)︀}︁∆ = = н (n ) , н (n ) , к (n ) , к (n ), = 1,2,...

,упорядоченного относительно н , к , вводятся понятие графа зависимостейниток(︁{︀}︀ )︁Γ = n : n ∈ ∆ , ,{︃н (n ) = к (n ) ,(n , n ) ∈ ⇔н (n ) ≥ к (n ) + ∆,где ∆ – некоторое действительное положительное число, и обозначенияΓ (n ) = {n ∈ ∆ : (n , n ) ∈ , init(n ) = } ,Γ0 (n ) = {n ∈ ∆ : (n , n ) ∈ , mark(n ) = 0, init(n ) = } ,где массив mark длины |∆ | характеризует актуальность исполнения нит­ки n ∈ ∆ , и задача организации железнодорожных перевозок состоит вформировании отображения : ∆ −→ 2ℒ∪{0 } ,13(4)такого, что для упорядоченного множества⃒{︀}︀⃒⃒⃒ −1⃒ ( ) () = {n1 ,n2 . . .

} = n : н (n ) 6 6 к (n ) ⃒ 6 1 ,выполняются условия допустимого отображения⎧00⎪⎨н (n1 ) = ( ) , ( ) 6(︀н (n1)︀) ,к (n1 ) = н (n2 ) , . . . , к n−1 = н (n ) ,⎪(︀)︀⎩к (n1 ) 6 н (n2 ) + ∆ , . . . , к n−1 6 н (n ) + ∆ ,при этом множество локомотивов задано начальными условиями доступ­ности локомотивов{︀(︀)︀}︀ℒ = = 0 ( ) , 0 ( ) , = 1,2, . . . ,(︀)︀где 0 ( ) , 0 ( ) – станция и время, начиная с которого соответству­ющий локомотив доступен для назначения, и локомотив 0 полагаетсяназначенным на все нитки, исполнение которых невозможно посредствомзаданного множества локомотивов.Алгоритм (n , n ) поиска ближайшей нитки, актуальной для испол­нения:Входные данные: (1 ,2 , . .