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

Риунок 31- Матрица кратчайших расстояний

Найдем на графе кратчайшие расстояния между каждой па­рой узлов по алгоритму Флойда [130,144]. Запишем их в виде матрицы размера n+2s на п+2s (рис. 31), где на пересечении строки i и столбца j стоит длина кратчайшего пути из вершины i в вершину у графа . Одновременно запомним и сами кратчайшие пути, т.е. звенья пути (матрица на рис. 32).

Рисунок 32- Звенья кратчайших путей в виде матрицы

Для того чтобы извлечь из этой матрицы кратчайший путь от вершины и к вершине v, находим ее элемент (и, v), стоящий на пересечении строки и и столбца v. Если он равен v - конец работы, иначе определен первый отрезок пу­ти: и, (и, v). Аналогично находим элемент ((и, v), v). Если он равен v, то путь найден, иначе определен второй отрезок пути: (и, v), ((и, v), v), и т.д. Предполо­жим, что требуется извлечь из матрицы путь между вершинами 2 и 8. Элемент (2, 8) равен единице, следовательно, определен первый отрезок - 2, 1. Далее, элемент (1, 8) равен а₂, значит второй отрезок - 1, а₂. Элемент (а₂, 8) равен 7, значит из а₂ надо идти в точку 7. Элемент (7, 8) равен 8, поэтому закапчиваем работу получив маршрут 2,1, а₂,7, 8.

Во множество вершин X полного графа G включаем все элементы множе­ства Х₀ графа G₀. Вес каждого ребра (и, v) множества и полагаем равным длине кратчайшего пути от вершины и к v в графе . Решаем задачу не­скольких коммивояжеров на сформированном полном графе . Точный минимум приведенной выше задаче будут доставлять указанные ниже наборы маршрутов.

При = = 1:

1. , 5, 6,3,4,

2. , 8, 7,

3. , 1,2,

со значением критерия качества, равным 119. Длина 1-го маршрута равна 7, 2- го - 6, 3-го - 4.

При =0, = 1:

1. , 6, 5,4,

2. , 8, 7,

3. ,3, 2,1,

со значением критерия качества, равным 7. Длина 1-го маршрута равна 7,2-го - 6,3-го-7.

При =1, = 0:

1. , 3,4,

2. , 8,7,6,5,1,2,

со значением критерия качества, равным 13. Длина 1-го маршрута равна 3, 2-го -10.

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

1) ,5, 6, [5, а₁], 3,4,

1. , [7], 8, 7, [ , ],

2. , [ ], 1,2, .

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

1. , [5], 6,5, [а_1,3],4,

2. ,,[7],8,7, [а₂, ],

3. ,, 3, [ , 1],2,1, [2], .

Третье решение:

1. , 3,4,

2. а₂,[7],8,7, 6, 5, [ ], 1,2, [ ], .

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

Рассмотрим теперь ситуацию, возникшую в маневровом районе, пред­ставляющем собой фрагмент подгорочного парка. Вид сбоку схематично изо­бражен на рисунках 32-35, а вид сверху - на рисунке 36. Далее удобно вос­пользоваться следующей терминологией. Условно разделим все участки стан­ции, которые нужно посетить для выполнения манёвров, на два типа. Назовем участок х точкой 1-го типа, если локомотив, после прибытия туда и выполнения маневра, находится приблизительно в той же точке х. К таким точкам относятся в основном «окна». Будем называть участок х точкой 2-го типа, когда после прибытия в х, локомотив вынужден проехать некоторый отрезок пути, и вы­ехать из другой точки у. Такая необходимость возникает благодаря «чужакам» и ситуациям «нет прохода». В нашем примере точки, требующие обслужива­ния, на путях ПЗ и П5 отнесем к точкам 1-го типа, остальные - к точкам второ­го типа.

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

Рисунок 32- Маневровый локомотив на пути П8

Рисунок 33- «Чужаки» на пути П6; «окно» на пути П5

Рисунок 34- «Нет прохода» на пути П1 и П2

Рисунок 35- Изображение рис. 4.5,4.6,4.7 и 4.8, вид сверху

Рисунок 36- Граф G₀ для ситуации на станции

Рассмотрение расположения в пространстве участков станции, где надо побывать, подсказывает, что некоторые из них удобно рассматривать как один обобщенный город. К примеру, точки 1-го типа на пути ПЗ практически не ог­раничивая общности задачи можно рассматривать как одну точку; вагоны на пути П5 тоже будем считать одним участком станции, требующем посещения; и, наконец, представим единственным обобщенным городом вагоны-«чужаки» на пути П6, поскольку их перестановка будет производиться не поочередно, а одновременно - заехав на путь П6 локомотив сразу возьмет обоих «чужаков». Граф G₀ формируется из всех точек 1-го и 2-го типов с учетом обобщений, то­чек начального и конечного местоположения локомотивов, точек, соответст­вующих стрелочным переводам, а также отрезков пути их связывающих. Для каждой точки второго типа, помимо ее самой, в граф G₀ необходимо включить и ту точку, из которой локомотив выезжает после выполнения данного обслу­живания. К примеру, переставив «чужаков» с пути П6 на путь П7, локомотив будет находиться в некоторой точке пути П7, подлежащей включению в граф. Окончательный вид графа представлен на рисeyrt 37.

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

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

2. Нумеруем вершины, соответствующие точкам 1-го типа (вершины 3 и 4 получают свои номера).

3. Затем - точки начального и конечного расположения локомотивов (5, 6,7, 8 или а₁, b₁, а₂, b₂ соответственно).

4. Нумеруются точки 2-го типа, причем в том порядке, в каком получали номера вершины на первом этапе (точкам 2-го типа ставятся в соответствие но­мера 9 и 10).

5. Точки стрелочных переводов нумеруются в произвольном порядке (11, 12,13,14,15,16,17).

Вершины, получившие свои номера на 1-м и 2-м этапах, назовем небазо­выми, а те, что получили свои номера на 3-м шаге, будут базовыми.

Взвесив все ребра графа посредством измерения отрезков пути (в метрах) между каждой парой смежных вершин.

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

Когда матрица весов уже имеется, находим матрицы кратчайших рас­стояний и кратчайших путей (рис. 37 и 38) используя алгоритм Флойда.

Рисунок 37- Матрица кратчайших расстояний графа G₀

Рисунок 38- Матрица кратчайших путей графа G₀

Чтобы воспользоваться одним из описанных выше алгоритмов определе­ния оптимального порядка обхода требующих посещения пунктов, нам понадо­бится в матрице кратчайших расстояний выделить подматрицу, образованную первыми п+2s строками и столбцами. Видно, что эта подматрица как раз и свя­зывает все базовые и небазовые вершины, а, следовательно, может интерпрети­роваться как матрица весов полного графа G(X,U) со взвешенными ребрами и п+2s вершинами. Однако заметим, что в точку 2 в нашем примере локомотив должен прибыть не по кратчайшему пути, поскольку непосредственно перед ее посещением он должен побывать в вершине 10, где находится «чужак», а стро­ки и столбца, соответствующих вершине 10 обсуждаемая подматрица не со­держит. Поэтому для любой точки х, увязанной в подматрице, длину пути в точку у, где, осуществив перестановку из точки второго типа z, должен нахо­диться локомотив, будем вычислять по формуле

где - вычисляемая длина пути от точки х до точки y;

- кратчайшее расстояние от х до z;

- кратчайшее расстояние от z до у;

- коэффициент загруженности на участке пути от z до у.

Значения и возьмем из матрицы кратчайших расстояний (рис. 37).

В случае, когда минимизируемым критерием является фактическая длина пути, измеряемая, например, в метрах, коэффициент загруженности можно не учитывать (положить равным единице для всех точек). Если же минимизирует­ся затрачиваемая энергия (или время), то коэффициент загруженности можно положить равным количеству единиц подвижного состава, перемещаемого из пункта z в пункт у. Если, к примеру, локомотиву предстоит проделать путь от z до у с двумя вагонами-«чужаками», то =3, если с тремя, то =4, и т.д.

Решив задачу при = = 1, получим оптимальный набор маршрутов:

1. , 3,1,

2. ,4,2,

=1001, =637, = 637637.

При =0, = 1 получено то же решение, =1001, =637, = 637637.