Модели транспортных сетей экономического региона и расчеты кратчайших расстояний перевозок

6.1. Принципы формирования моделей транспортных сетей

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

Транспортная сеть представляет собой систему дорог (улиц города), которые пригодны по качеству дорожного покрытия, ширине проезжей части и открыты для движения.

Базой для формирования модели транспортной сети является карта экономического региона с указанием дорог, грузообразующих (пассажирообразующих) и грузопоглощающих (пассажиропоглощающих) пунктов. Пример карты района Ленинградской области показан на рис. 1.1.

Транспортная сеть состоит из отдельных элементов. Этими элементами являются вершины (пункты) и звенья сети. Вершины – это точки на карте города или местности (перекрестки, крупные грузообразующие и грузопоглощающие пункты, площади), наиболее важные для определения расстояний или маршрутов движения автомобилей. Каждой вершине присваивается порядковый номер или другое условное обозначение.

Две соседние вершины (два соседних пункта) можно соединить линией, по которой осуществляется непосредственная связь между этими вершинами с указанием расстояния между ними. Эти линии называются звеньями сети. Совокупность вершин и звеньев называется сетью.

Так формируется граф (модель) транспортной сети экономического региона (города).

Примеры моделей (графов) транспортной сети показаны на рис. 6.1 и 6.2. При составлении модели необходимо учитывать ограничения, которые налагают правила движения транспортных средств по улицам и дорогам (например, наличие перекрестков с запрещенными поворотами или участков с односторонним движением). Также учитывается категория дороги. Построив модель транспортной сети, замеряют расстояния между ближайшими вершинами. Результаты заносятся в табл., например, типа табл. 1.2.

Размер задачи зависит от числа вершин и звеньев сети. Этот размер определяет необходимый объем операций памяти ЭВМ, используемой для расчетов.

При числе вершин и звеньев примерно до 50 можно использовать ручной счет. Для больших объемов необходима ЭВМ.

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

В настоящем разделе рассмотрены два метода определения кратчайших расстояний – табличный и метод потенциалов. В следующем разделе 7 рассмотрен также метод динамического программирования для определения кратчайших расстояний между пунктами транспортной сети.

6.2. Табличный метод определения кратчайших расстояний

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

На рис. 6.1 представлена модель участка транспортной сети, сформированная на основе карты экономического региона.

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

G = (x, y).

Каждому ребру графа приписано некоторое число (длина ребра) lij ≥ 0. Тогда любая цепь μ, составленная из нескольких ребер, характеризуется длиной l_μ. Требуется для двух произвольных вершин найти такой путь, чтобы его длина была наименьшей:

Рассмотрим решение задачи с нахождением кратчайшего пути на конкретном примере.

Пример 6.1. Дана модель участка транспортной сети экономического региона (рис. 6.1). Требуется табличным методом определить кратчайшее расстояние между пунктами К₁ и К ₁₄.

Решение:

Аналитическая модель решаемой задачи имеет вид

.

Составляем матрицу (табл. 6.1) решения (исходный вариант) и заносим в нее расстояние от каждой вершины отсчета К_i (i=1,2,3,…14) до всех вершин К_i, соседних с ней.

После занесения в рабочую часть матрицы величин видно, что имеется , но нет величины . Тем самым учитывается, что на ребре К₄К₅ наложено ограничение – одностороннее движение и передвижение возможно только со стороны К ₄ (см. рис. 6.1).

При дальнейших расчетах пользуются следующим правилом.

Каждой вершине К_i соответствует некоторое число , характеризующее расстояние от вершиныК₁ до вершины К_j.

Вершине К _j = К _i,т.е. точке, от которой измеряются расстояния, соответствует . Соответственно и Получаем в строке К₁ и в столбце К ₁ величины расстояний

Затем, начиная с первого столбца (К _i) i =1, рассматриваем клетки с записанными расстояниями (в данном примере клетки К ₁ К ₂ и клетки К ₁ К ₄), для которых известно и равно нулю.

Для определения (для строк К ₂ и К ₄) используют правило

. (6.1)

Согласно (6.1) для строки К ₂ имеем ; для строки К ₄имеем =0+3=3, что и заносится в клетки столбца , а в силу связанности транспортной сети для рассмотренных соседних вершин имеем , поэтому можно заполнить две клетки в верхней строке (К ₂и К ₄).

Получив значения в столбцах К ₂и К ₄, по клеткам К ₂, К ₃и К ₄, К ₆, где записаны величины , аналогично находим для строк К₃ и К₆.

Для ; .

И опять в силу связанности сети заполняем две клетки в верхней строке (К ₃и К₆).

Аналогично находим для строк К ₅, К ₇, К ₈и столбцов К ₅, К ₇ и К ₈, но после нахождения столбцов К ₇и К ₈ в строке К ₉ оказались две клетки с заполненными (К ₇, К ₉ и К ₈, К ₉), для которых уже известно. Поэтому для того, чтобы найти для строки К ₉, используется другое правило: если в j-й строке имеются несколько клеток с указанными величинами и для этих клеток уже известно, то определяется меньшей суммой значений ( + ) для всех известных , т. е.

.

Применяя данное правило для строки К ₉, получаем