Кадура (Математическое моделирование процессов перевозки грузов железнодорожным транспортом на основе использования задачи коммивояжера), страница 10

А вот при =1, = 0 найденный оптимум отличен от предыдущих:

1. , 3,4, 2,1,

=994, =994, = 994.

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

Первое решение будет иметь вид:

1. , [13],3,[13,12], 9, [11], 1,[11],

2. , [17,15,16], 4, [16], 10, [16,15,17], 2, [17, ],

Другими словами локомотив, находящийся на пути П4 должен сначала сдвинуть «окна» на пути П3, затем устранить ситуацию «нет прохода» на пути П1 и П2, после чего отправиться в точку финиша на пути П2. А локомотив на пути П8 сначала посещает путь П5 чтобы сдвинуть «окна», потом заезжает на путь П6, берет там «чужаков», завозит их на путь П7 и отправляется обратно на путь П8.

Второе решение:

1) [13], 3, [13, 12, 14, 15, 16], 4, [16], 10, [16, 15, 17], 2, [17, 15, 14, 12], 9, [11], 1,[11],

То есть локомотив на пути П4 первым делом посещает путь ПЗ, потом П5, сдвигая «окна», после чего переставляет «чужаков» с пути П6 на П7, устраняет ситуацию «нет прохода» на пути П1 и П2 и отправляется на путь П2. Второй локомотив остается на месте - он не привлекается к выполнению работ.

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

Формирование и модификация графа на рис. 38 вручную вызовет суще­ственные затруднения. Потому и разработан описанный ниже редактор графов.

3.2 Разработка редактора графов

Графы служат математическими моделями сетей железнодорожного, ав­томобильного, а также других видов транспорта. Задачи нахождения маршру­тов транспортных средств в рамках заданной сети дорог формализуются с ис­пользованием теории графов и алгоритмов. Реальные транспортные сети часто имеют большие размеры, алгоритмы решения возникающих задач сложны и трудоемки, поэтому анализ и синтез сетей на практике, как правило, не осуще­ствляется без привлечения ЭВМ. Помимо самих алгоритмов, большое значение также имеет возможность быстрого и гибкого их использования. У людей- не математиков, занимающихся, к примеру, организацией маневровых передвиже­ний на железнодорожной станции, работа с программной реализацией алгорит­мов, берущих на входе данные, представленные посредством матрицы, вызовет существенные затруднения. Необходимо за короткое время безошибочно сфор­мировать исходную матрицу, а затем учитывать динамику изменения ситуации на станции модифицируя исходные данные в реальном времени. Изменение си­туации может приводить к добавлению в граф новых вершин и ребер, либо удалению уже имеющихся, к изменению номеров вершин и весов ребер, к вы­делению среди множества вершин и ребер подмножеств, обладающих задан­ными свойствами. Соответственно будут изменяться элементы матрицы весов, будут появляться, исчезать либо меняться местами ее строки и столбцы. Если, например, в графе поменять местами номера вершин с номерами 1 и 2, то в матрице первая строка поменяется со второй строкой, первый столбец - со вто­рым столбцом. Чем больше размеры матрицы, тем труднее производить преоб­разования подобного рода вручную. Чтобы максимально упростить и тем са­мым ускорить формирование и модификацию исходных данных, предлагается программа на ЭВМ - редактор графов.

Рисунок 39 -Иллюстрации графов, созданные посредством редактора графов

Рисунок 40 -Иллюстрации графов, созданные посредством редактора графов

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

Программная реализация имеет следующие основные возможности.

• Создать. При нажатии соответствующей кнопки на панели инстру­ментов (или в главном меню) программы в окне редактора создается белая пря­моугольная область для рисования графа. Предварительно пользователь опре­деляет тип графа - ориентированный либо неориентированный, взвешенный или нет, и цвет линий.

• Сохранить. При нажатии будет предложено сохранить нарисованный граф в файле. Открывается диалоговое окно записи на жесткий диск компьюте­ра файла с расширением «grf». Пользователь указывает имя файла и в какую папку его поместить.

• Открыть. Если кликнуть на кнопку и в появившемся диалоговом окне выбрать имя ранее сохраненного файла в формате граф будет загружен из файла.

• Кнопка «Сохранить рисунок» позволяет сохранить текущую иллюст­рацию графа в графический файл формата jpeg или bmp.

• Режимы добавления и удаления вершин активируются разовым нажа­тием кнопки «Добавить вершины» либо «Удалить вершины» соответственно. Добавляем требуемое количество новых вершин, щелкая мышью в тех точках области, где хотим их расположить, или удаляем ненужные вершины кликая на них. Чтобы деактивировать режим, отжимаем вдавленную кнопку повторным нажатием.

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

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

• Реализована удобная перенумерация вершин. В режиме перенумера­ции вершины нумеруются в том порядке, в каком пользователь щелкает по ним мышкой. К примеру, щелкнул первый раз по пятой, она стала первой, второй раз щелкнул по третьей, она стала второй и т.д. Вершины всегда занумерованы числами натурального ряда от единицы до максимального номера, равного ко­личеству вершин п. Если, к примеру, п = 5, то множество номеров: {1,2,3,4,5}. Все операции по добавлению, удалению, перенумерации вершин не приводят к нарушению этого условия. При удалении некоторой вершины, номера всех вершин с большими номерами становятся меньше на единицу. При изменении номера вершины* на номер вершины у номера * и у меняются местами.

• В редактор графов заложен алгоритм Флойда, строящий по генери­руемой редактором матрице весов нарисованного взвешенного графа его мат­рицы кратчайших расстояний и кратчайших путей. На панели инструментов редактора имеется специальная кнопка «Сохранить матрицы», записывающая матрицы весов, кратчайших расстояний и кратчайших путей в текстовые файлы «SourceGraphMatrix.txt», «FullGraphMatrix.txt» и «PathsMatrix.txt» соответст­венно, создаваемые на жестком диске. Таким образом производится переход от исходного графа полному графу G. Матрица «FullGraphMatrix.txt» интер­претируется как матрица весов полного графа G, полученного из добавле­нием к недостающих ребер между каждой парой несмежных вершин х и у. Вес каждого ребра (х, у) полагается равным длине кратчайшего пути от х к у в . Разработанные алгоритмы берут на входе матрицы «FullGraphMatrix.txt» и «PathsMatrix.txt». Находится решение задачи нескольких коммивояжеров на полном графе G - для этого необходима матрица весов G. Затем, когда решение получено, каждое звено входящих в него маршрутов представляется посредст­вом ребер исходного графа с использованием матрицы «PathsMatrix.txt». В ре­зультате получаем оптимальный порядок обхода небазовых вершин исходного графа с указанием пути, по которому следует двигаться от одной вершины к другой (этот путь является кратчайшим).

Примеры иллюстраций графов, созданные в редакторе см. на рис. 39

3.3 Учет специфики железнодорожного транспорта

Ранее предполагалось, что каждый локомотив в любое время может дое­хать до любой, требующей обслуживания, точки чтобы выполнить необходи­мые маневровые операции. Нужно было указать локомотивам наилучшие в не­котором смысле маршруты движения, проходящие через все выделенные уча­стки станции. Никаких дополнительных ограничений на структуру искомых маршрутов не накладывалось. Ранее рассматривалась ситуация «нет прохода» на пути П1 и П2, хотя точек для выполнения маневров П1 и П2 не содержали. Предположим, что П1 и П2 содержат такие точки. Тогда локомо­тив не сможет в них побывать, не устранив предварительно имеющуюся ситуа­цию «нет прохода». Таким образом, одни обслужива­ния иногда должны быть выполнены строго раньше, чем некоторые другие. Благодаря данному обстоятельству появляется необходимость частичного упо­рядочения всех маневровых операций. Вводятся условия предшествования, вы­текающие из технологии нормализации процесса роспуска, т.е. условия вида «работа х должна быть сделана прежде, чем начнется работа у». При этом бу­дем говорить, что операция х предшествует операции x, либо что у следует за x и коротко записывать х у. Заметим, что отношение порядка < транзитивно при :x<у и у <z выполнено также х<z. Будем говорить, что операция х не­посредственно предшествует операции у (или у непосредственно следует за x), если х<у и не существует такой работы z, что x<z<y. Обозначение х<<у. Всю совокупность условий предшествования удобно изобразить в виде бескон­турного графа типа того, что представлен на рис. 40. Каждому отношению д: x<< у соответствует дуга, идущая от вершины х к вершине у. Граф может иметь несколько компонент связности. На рисунке две компоненты связности.

Рисунок 41- Граф приоритетов в обслуживании

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

Помимо условий предшествования вводятся дополнительные критерии эффективности решения рассматриваемой задачи. Дело в том, что маршруты, составляющие решение, могут иметь общие части. Поскольку тепловозы не мо­гут одновременно находиться в одной точке, объективным условием является прохождение общих отрезков пути в различное время. В случае, когда, соглас­но полученному решению, общий отрезок проходится приблизительно в один и тот же момент времени, некоторые локомотивы будут вынуждены делать оста­новки, пропуская другие, что нежелательно. Снизится ожидаемый эффект от привлечения к работе нескольких локомотивов вместо одного. Возможно воз­никновение «пробок», недопустимое увеличение времени выполнения манев­ров. Работы станут менее безопасными, повысится вероятность ошибочных действий и сбоя. Новый критерий J₃ минимизирует общее количество пересе­чений маршрутов независимо от времени, а критерий J₄ не позволяет локомо­тивам одновременно находиться в одном и том же месте.

Чтобы подсчитать значения критериев J₃ и J₄ полученного на некото­ром шаге множества маршрутов, а также обеспечить выполнение условий предшествования, нам понадобятся множества чисел vn(i, х) и , i = 1,m, х = 1,size. Здесь i представляет номер маршрута, m - текущее количество мар­шрутов, через х мы обозначили вершину начального графа G₀, size - количест­во всех вершин Go (базовых, небазовых и остальных). Будем также пользовать­ся обозначением x(i,j): вершина x, находящаяся в маршруте i по порядковому номеру j. . Каждая вершина x встречается в маршруте i, 0, 1 или не­сколько раз. Найдем число попаданий x в i. Результаты запишем в виде матри­цы vn. Элементы vn(i, х) равны количеству вхождений вершины x в маршрут i.

Величины Т_х представляют время прибытия i-го локомотива в вершину х. На­чальные значения и являются исходными данными, и должны быть заданы до начала работы алгоритма. Начальные величины интерпретируются как время старта локомотивов, стартующих, вообще говоря, не одновременно. В связи с этим формула вычисления длины L маршрута i изменится, и примет вид