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

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

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

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

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

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

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

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

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

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

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

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

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

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

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