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

определяют приведенные длины маршрутов;

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

если для полученной кратчайшей связывающей сети условие не выполнено, то ее дополняют звеньями так, чтобы каждый раз в результате дополнения сумма дорожно-транспортных затрат на сети уменьшалась;

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

(далее...)

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

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

Схематическое представление о характере распределения суммарных удельных дорожно-транспортных затрат по отдельным группам маршрутов, где обозначено, что минимум суммарных удельных дорожно-транспортных затрат имеет место при количестве Р звеньев в сети. Ордината, характеризующая наименьшую сумму приведенных длин маршрутов, состоит из трех отрезков: первый соответствует минимуму суммы приведенных длин маршрутов между смежными точками кратчайшей связывающей сети, второй  - минимуму сумм приведенных длин между смежными точками на маршрутах, состоящих из дополнительных звеньев, третий - сумме приведенных длин между несмежными точками оптимальной связывающей сети. С помощью графика   можно пояснить принцип отбора дополнительных звеньев. Добавление дополнительного звена вызывает приращение Ах кривой 1 и уменьшение ординат кривой 2 на величину А2. В оптимальную связывающую сеть можно и нужно включать только те дополнительные звенья, для которых

(далее...)

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

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

(далее...)

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

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

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

(далее...)

Основными данными для проектирования сетей дорог являются перечень транспортных связей и карта района проектирования с указанием корреспондирующих точек.

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

(далее...)

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

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

(далее...)

Изменение дорожной составляющей становится плавным лишь для периода больше 10-15 лет, а для меньшего периода сравнения оно носит резкий характер.

Для периода суммирования, равного 5-10 годам, дорожная составляющая значительно превосходит транспортную, особенно для дорог IV и V категорий. Затем для дорог I - III категорий значения обеих составляющих сближаются и дорожная составляющая становится меньше транспортной. Для дорог IV и V категорий дорожная составляющая остается, как правило, большей даже при 40-летнем периоде сравнения.

Одновременно с этим рассмотренный пример убедительно показывает, что для дорог I и II категорий наиболее эффективным является решение, которое обеспечивает наименьшие транспортные затраты, а для дорог IV и V категорий - которое обеспечивает наименьшие капиталовложения.

(далее...)

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

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

(далее...)

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

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

(далее...)

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

изолированная точка (вершина) -точка, которая на данном этапе построения еще не связана с другими точками;

фрагмент-подмножество точек, связанных между собой звеньями,  каждое из которых соединяет точки этого подмножества;

изолированный    фрагмент , который на данном этапе построения еще не связан с другими точками или фрагментами;

расстояние точки от изолированного фрагмента, элементом;

ближайшим соседом точки является точка, которая находится от данной точки на расстоянии не большем, чем любая другая точка;

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

(далее...)