Кратчайшая связывающая сеть

Порядковый номер	Звено	Длина звена, км
1	А - Г	3,2
2	Г - Д	2,0
3	Д - И	2,8
4	И - К	2,6
5	К - З	2,0
6	З - Е	2,4
7	Е - В	3,6
8	В -Б	2,2
9	Д - Ж	5,0

КСС пунктов района перевозки, с указанием расстояний и объема завозимых грузов представлена на рис. 1.2.

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

Рис. 10.6. Кратчайшая связывающая сеть («минимальное дерево»).

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

В данном примере грузоподъемность автомобиля (2,5 т), с учетом характеристик груза (коэффициент статического использования грузоподъемности  = 0,8) позволяет объединять в маршруте пункты, суммарный завоз в которые не превышает 2,5 × 0,8 = 2,0 тонны.

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

Исходя из данной грузоподъемности подвижного состава все пункты можно сгруппировать на два маршрута (табл. 3.4).

Таблица 3.4

Группировка маршрутов исходя из грузоподъемности автомобиля

Маршрут 1		Маршрут 2
Пункт	Объем завоза, кг.	Пункт	Объем завоза, кг.
Б	375	Ж	525
В	500	Д	300
Е	425	И	675
З	575	Г	500
К	125	-	-
Итого	2000	Итого	2000

Этап 2. Определяется рациональный порядок объезда пунктов каждого маршрута. Для этого строится таблица-матрица (табл. 3.5), в которой по диагонали размещаем пункты, включаемые в маршрут, и начальный пункт А, а в соответствующих клетках - кратчайшие расстояния между ними.

Таблица 3.5

Матрица для определения рационального порядка объезда пунктов по маршруту № 1

Номер строки	А	7,0	9,2	9,0	11,4	10,6
1	7,0	Б	2,2	4,2	6,6	7,6
2	9,2	2,2	В	3,6	4,4	6,4
3	9,0	4,2	3,6	Е	2,4	3,4
4	11,4	6,6	4,4	2,4	З	2,0
5	10,6	7,6	6,4	3,4	2,0	К
	47,2	27,6	25,8	22,6	26,8	30,0

Начальный маршрут строится для трех пунктов матрицы, имеющих наибольшие суммы, показанные в строке «» (47,2; 30,0 и 27,6 км), т.е. А; К; Б. Первым пунктом (пунктом отправления) всегда будет распределительный центр (источник материалопотока), в данном случае пункт А, независимо от суммы. Получается маршрут вида: А  К  Б  А.

Для включения последующих пунктов выбирается из оставшихся пункт, имеющий наибольшую сумму - пункт З (сумма 26,8 км), и решается, между какими пунктами его следует включать, т.е. между А и К, К и Б или Б и А.

Поэтому для каждой пары пунктов необходимо найти величину приращения маршрута по формуле:

, (3.2)

где: С - расстояние, км;

i - индекс включаемого пункта;

k - индекс первого пункта из пары;

p - индекс второго пункта из пары.

При включении пункта З между первой парой пунктов А и К определяется размер приращения АК при условии, что i = З, k = А, p = К. Тогда:

АК = САЗ + СЗК – САК

Подставляются значения расстояний между пунктами из табл. 3.5.

Получается, что АК = 11,4 + 2,0 – 10,6 = 2,8 км.

Таким же образом определяется приращения КБ и БА, км:

КБ = СКЗ + СЗБ – СКБ = 2,0 + 6,6 – 7,6 = 1,0 км;

БА = СБЗ + СЗА – СБА = 6,6 + 11,4 – 7,0 = 11,0 км.

Из полученных значений выбирается минимальное, т.е. КБ = 1,0 км.

Следовательно, пункт З должен быть между пунктами К и Б.

Получается маршрут вида: А  К  З  Б  А.

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

2. В случае, когда = 0, для симметричной матрицы расчет можно не продолжать, так как меньшее значение, чем 0 получено быть не может.

Используя этот метод и формулу приращения, определяется, между какими пунктами расположить пункты В и Е. Начинать нужно с В, так как сумма этого пункта больше (25,8 > 22,6 км):

АК = САВ + СВК – САК = 9,2 + 6,4 – 10,6 = 5,0 км;

КЗ = СКВ + СВЗ – СКЗ = 6,4 + 4,4 – 2,0 = 8,8 км;

ЗБ = СЗВ + СВБ – СЗБ = 4,4 + 2,2 – 6,6 = 0 км.

Пункт В должен быть между пунктами З и Б. Тогда маршрут получит вид: А  К  З  В  Б  А.

Следующий пункт Е включается между пунктами З и В, так как для этих пунктов получено минимальное приращение:

АК = САЕ + СЕК – САК = 9,0 + 3,4 – 10,6 = 1,8 км;

КЗ = СКЕ + СЕЗ – СКЗ = 3,4 + 2,4 – 2,0 = 3,8 км;

ЗВ = СЗЕ + СЕВ – СЗВ = 2,4 + 3,6 – 4,4 = 1,6 км;

ВБ = СВЕ + СЕБ – СВБ = 3,6 + 4,2 – 2,2 = 5,6 км;

БА = СБЕ + СЕА – СБА = 4,2 + 9,0 – 7,0 = 6,2 км.

Таким образом, окончательный порядок движения по маршруту 1 будет:

А  К  З  Е  В  Б  А.

Определяется рациональный порядок объезда пунктов по маршруту II. Для этого строится таблица-матрица расстояний для маршрута №2 (табл. 3.6).

Таблица 3.6