Нахождение кратчайшего пути в транспортной сети - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих случаев разработаны две разновидности алгоритма решения задачи. Рассмотрим первый из случаев. Транспортная сеть представлена графом G1, в котором длины ребер одинаковы и равны некоторой постоянной величине (l1=const). Для простоты изложения будем считать, что l1=1. Каждому узлу xI графа G1 приписываем индекс I, равный длине кратчайшего пути из xI в конечный узел xN.

Алгоритм основан на последовательном приписывании индексов, последовательно проходя в обратном направлении (от xN до x0) следующим образом.

    - Узлу xN приписывается индекс N=0. - Всем узлам (еще не имеющим индексов), от которых идет ребро в конечный узел, приписываем индекс I=1. - Всем следующим узлам, от которых идут ребра в только что помеченные узлы приписываем индекс (I+1).

Этот процесс продолжается, концентрическими кругами расширяясь от xN, до тех пор, пока не будет помечен начальный узел x0 графа G1. Значение индекса 0 у начального узла x0 и будет равно длине кратчайшего пути.

Пример. Относительно КУП "СПЕЦКОММУНТРАНС" задача формулируется, как нахождение кратчайшего пути следования автомобиля, производящего работу по вывозу мусора на свалку. В общем виде задача звучит так. Пусть дан граф G1, представленный на рисунке 5. Сеть состоит из десяти узлов. Необходимо найти кратчайший путь от x0 до xN. На рисунке 5 показаны значения индексов I для каждого i-го узла. Начинается расчет узла xN (для которого N=0) и завершается установкой индексов у всех остальных узлов. Индекс при x0 равен 0=3. Поэтому длина кратчайшего пути равна LКр=3. Само направление кратчайшего пути находим путем составления последовательности узлов по направлению убывания у них индексов от 0=3 до N=0. Для графа G1 кратчайший путь составляют узлы: x0, x1, x7, xN. На рисунке 5 кратчайший путь выделен жирными стрелками.

транспортная сеть равных расстояний

Рисунок 4. Транспортная сеть равных расстояний

Рассмотрим случай 2, когда длины lIj ребер (xI, xJ) транспортной сети различны. Задача усложняется, поскольку часто путь, проходящий через минимальное число вершин, может иметь бльшую длину (стоимость или время продвижения), чем обходные пути. Алгоритм расчета индексов похож на предыдущий. Однако, есть различия.

    - Первоначально конечному узлу приписываем индекс N=0, а для остальных узлов устанавливаем индекс, равный бесконечно большому числу (I=). - Ищем такую дугу (xI, xJ), для которой справедливо неравенство:

(30)

И заменяем индекс у xJ узла:

(31)

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

Правило нахождения кратчайшего пути при вычисленных индексах I формулируется следующим образом: при обратном проходе по графу G от x0 к xN выбираем тот из узлов, для которого I минимально.

Пример. По аналогии с предыдущим примером относительно КУП "СПЕЦКОММУНТРАНС" задача формулируется, как нахождение кратчайшего пути следования автомобиля, производящего работу по вывозу мусора на свалку. В общем виде задача звучит так. Пусть дан граф G2, представленный на рисунке 6 Сеть состоит из шестнадцати узлов. Расстояния между узлами различны и каждое из ребер графа G2 помечено величиной расстояния между узлами, соединенными данным ребром. На рисунке 6 также указаны значения индексов I для каждого i-го узла. Расчет начинаем с узла xN, имеющего индекс N=0, и завершаем установкой индексов у всех остальных узлов. Индекс при x0 равен 0=26, что означает LКр=26. Само направление кратчайшего пути находим аналогично первому случаю путем составления последовательности узлов по направлению убывания у них индексов от 0=26 до N=0. Для графа G2 кратчайший путь составляют узлы: x0, x5, x8, x11, x13, xN. На рисунке 6 кратчайший путь также выделен жирными стрелками. Обратим внимание на формирование индексов у x12: 12=11 как результат сложения индекса 13=6 с длиной l(x13, x12)=5. Как видим, работает правило минимизации длины возможных путей от x12 до xN.

транспортная сеть с разными расстояниями между узлами

Рисунок 5. Транспортная сеть с разными расстояниями между узлами

Похожие статьи




Нахождение кратчайшего пути в транспортной сети - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

Предыдущая | Следующая