1. Разработка модели транспортной сети

1. Определение расстояния между вершинами транспортной сети

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

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

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

Площадь городского микрорайона принимается в пределах 3-5 км², а участков севооборота 0,5-1,0 км².

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

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

0, если i=j

l_ij =  l_ij , если вершины i и j соединены между собой;

, если i и j не соединены между собой дугой непосредственно.

Таблица 1.1. Расстояние между вершинами транспортной сети, км

	1	2	3	...	n
1
2
3
...
n

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

1.2. Определение кратчайших расстояний между грузообразующими и грузопоглощающими пунктами

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

Таблица 1.2. Кратчайшие расстояния между грузообразующими и грузопоглощающими пунктами, км

Грузопоглощаю-	Грузообразующие пункты
щие пункты	А1	А2	А3	...	Аm
B1
B2
B3
...
Bn

Для определения кратчайших расстояний дорожной сети показанной на рисунке 1.1., в качестве примера, применим метод потенциалов.

5 6 8

Д З

2 3 5

5 Ж 9 3

4 4

Б 3 И

6 5

А

9 0 4

2 2 5

3 В 4 Г 4

6 3

5 Е К 6

6 2 5

7 Л М 10

Рисунок 1.1. Схема транспортной сети

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

Полное решение задачи включает столько этапов, сколько вершин включает транспортная сеть, поскольку каждый раз определяют кратчайшее расстояние от начальной точки до остальных.

Потенциалы рассчитывают

_j = _i + l_ij ,

где _j - потенциал предшествующей (соседней вершины);

l_ij - длина звена (дуги) соединяющего вершины i и j.

На первом этапе за начальную точку принята вершина А. Ее потенциал равен нулю, т.е. _А = 0. Соседними к точке А являются вершины: Б, Ж, И, Г, К, В, З. Их потенциалы:

_А = 0; _Б = _А+l_АБ = 0+6=6; _Ж = _А+l_АЖ = 0+3=3;

_И = _А+l_АИ = 0+5=5; _Г = _А+l_АГ = 0+4=4; _К = _А+l_АК = 0+5=5;

_В = _А+l_АВ = 0+2= 2 ; _З = _А+l_АЗ = 0+9=9.

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

Затем определяют потенциалы точек Е и К, соединенных к точке В:

_Е = _В + l_ВЕ = 2+3 = 5 ; _К = _В + l_ВК = 2+4 = 6.

Из совокупности потенциалов (кроме _А и _В, которые уже выбраны) наименьший потенциал соответствует точке Ж и равен 3. Это число проставляют у вершины Ж, отмечают кратчайшую связь от точки А к точке Ж.

Потенциалы точек Б, Д, З, И, рассчитанные через потенциал точки Ж, равны

_Б = _Ж + l_ЖБ = 3+4=7; _Д = _Ж + l_ЖД = 3+2= 5 ;

_З = _Ж + l_ЖЗ = 3+5= 8 ; _И = _Ж + l_ЖИ = 3+4=7.

Из невыбранных потенциалов наименьший 4 соответствует точке Г. Его присваивают этой точке и делают соответствующие отметки.

Используя потенциал точки Г, определяют значения потенциалов для соседних с ней точек К, И, М.

_К = _Г + l_ГК = 4+3=7; _И = _Г + l_ГИ = 4+5=9;

_М = _Г + l_МГ = 4+6= 10 .

Следующий по значению потенциал 5, характерен для нескольких точек сети. В этом случае значение присваивают любой из возможных вершин, например точке К. Определим потенциалы соседних с точкой К вершин Л, Е, М

_Л = _К + l_КЛ = 5+2= 7 ; _Е = _К + l_КЕ = 5+6=11;

_М = _К + l_КМ = 5+5= 10 .

Такой же потенциал, равный 5 присваивают точкам И, Е, Д и определяют потенциалы соседних с ними вершин

_З = _И + l_ИЗ = 5+3= 8 ; _Б = _Д + l_ДБ = 5+5=10;

_Б = _Б + l_ЕБ = 5+9=14; _З = _Д + l_ДЗ = 5+6=11.

Следующий по порядку потенциал присваивают точке Б. Он равен 6. Соседних с ней вершин без потенциалов нет, соответствующих вычислений поэтому не выполняют. Чтобы продолжить решение задачи, рассматривают оставшуюся совокупность потенциалов. Наименьшим в совокупности является потенциал 7 для точки Л.

Потенциалы соседних к ней точек уже рассчитаны, поэтому никаких вычислений не производят, а выбирают следующий потенциал из уже рассчитанных. Это потенциал точки З. Причем этой вершине соответствуют два одинаковых потенциала, равные 8. Это значит, что из начальной точки А в пункт З можно попасть двумя путями через вершину Ж и вершину И с одинаковым расстоянием 8 км. Одинаковым по значению потенциалам для одной и той же точки присваивают одинаковый порядковый номер.

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

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

По результатам вычислений составляют таблицу кратчайших расстояний, по форме таблицы 1.1., заменив цифры буквенным обозначением вершин транспортной сети.