И пунктами обслуживания, км

Объемы поставки в пункты потребления

Потребители продукции	Б	В	Г	Д	Е	Ж	З	И	К
Объем продукции, кг

Рис. 1.1. Схема размещения пунктов и расстояния между ними.

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

Решение.

Этап 1. Определяется кратчайшая связывающая сеть пунктов района перевозки. Два пункта транспортной сети дорог, разделенные наименьшим расстоянием, образуют первичное звено, к которому, на каждом следующем шаге составления КСС, добавляют звено самой малой длины. При его присоединении к уже выбранным звеньям не должно образовываться замкнутого пути (контура). Кратчайшая сеть, связывающая n пунктов, должна иметь n -1 звеньев.

Для построения КСС формируется таблица расстояний между пунктами (табл. 3.2).

Таблица 3.2

Таблица расстояний между распределительным центром

	А	Б	В	Г	Д	Е	Ж	З	И	К
А	-	7,0	9,2	3,2	5,2	9,0	5,6	11,4	8,0	10,6
Б	7,0	-	2,2	5,0	7,0	4,2	12,0	6,6	9,8	7,6
В	9,2	2,2	-	7,2	7,4	3,6	12,4	4,4	9,0	6,4
Г	3,2	5,0	7,2	-	2,0	5,8	7,0	8,2	4,8	7,4
Д	5,2	7,0	7,4	2,0	-	3,8	5,0	6,2	2,8	5,4
Е	9,0	4,2	3,6	5,8	3,8	-	8,8	2,4	6,0	3,4
Ж	5,6	12,0	12,4	7,0	5,0	8,8	-	10,4	5,8	8,4
З	11,4	6,6	4,4	8,2	6,2	2,4	10,4	-	4,6	2,0
И	8,0	9,8	9,0	4,8	2,8	6,0	5,8	4,6	-	2,6
К	10,6	7,6	6,4	7,4	5,4	3,4	8,4	2,0	2,6	-

Отправной пункт – распределительный центр (пункт А). Поэтому построение КСС начинают с первой строки А (табл. 3.2). Выписав эту строку с номерами столбцов, обозначают все числа (расстояния перевозок) буквой (А), указывающей на их принадлежность к исходной строке. Получается ряд I:

	А	Б	В	Г	Д	Е	Ж	З	И	К
А		7,0	9,2	3,2	5,2	9,0	5,6	11,4	8,0	10,6
		(А)	(А)	(А)	(А)	(А)	(А)	(А)	(А)	(А)

Из чисел первого ряда выбирают наименьшее расстояние (3,2 км). Это расстояние до пункта Г - он является вторым в КСС: А à Г. Соответствующее ему звено А - Г вносится в табл. 3.3.

Затем попарно сравниваются числа (расстояния) в строке Г (табл. 3.2), где находится это наименьшее число, с соответствующими числами ряда I. Выберется наименьшее из каждой сопоставляемой пары и обозначается буквой (номером) соответствующей строки. Получается ряд II:

	А	Б	В	Г	Д	Е	Ж	З	И	К
А		7,0	9,2	3,2	5,2	9,0	5,6	11,4	8,0	10,6
Г	3,2	5,0	7,2		2,0	5,8	7,0	8,2	4,8	7,4
ряд II		5,0 (Г)	7,2 (Г)		2,0(Г)	5,8 (Г)	5,6 (А)	8,2 (Г)	4,8 (Г)	7,4 (Г)

Из этого ряда выбирается наименьшее расстояние 2,0 км до пункта Д, который является третьим пунктом КСС: А à Г à Д. Соответствующее звено Г - Д вносится в табл. 3.3.

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

Сравнив числа строки Д с числами ряда II, получаем новый ряд:

	А	Б	В	Г	Д	Е	Ж	З	И	К
ряд II		5,0 (Г)	7,2 (Г)		2,0 (Г)	5,8 (Г)	5,6 (А)	8,2 (Г)	4,8 (Г)	7,4 (Г)
Д		7,0	7,4			3,8	5,0	6,2	2,8	5,4
ряд III		5,0 (Г)	7,2 (Г)			3,8 (Д)	5,0 (Д)	6,2 (Д)	2,8 (Д)	5,4 (Д)

В этом ряду наименьшее число 2,8. Звено Д - И вносят в табл. 10.9.

А à Г à Д à И.

Сравнивая числа строки И с числами ряда III, получают ряд IV:

	А	Б	В	Г	Д	Е	Ж	З	И	К
ряд III		5,0 (Г)	7,2 (Г)			3,8 (Д)	5,0 (Д)	6,2 (Д)	2,8 (Д)	5,4 (Д)
И		9,8	9,0			6,0	5,8	4,6		2,6
ряд IV		5,0 (Г)	7,2 (Г)			3,8 (Д)	5,0 (Д)	4,6 (И)		2,6 (И)

А à Г à Д à И à К

	А	Б	В	Г	Д	Е	Ж	З	И	К
ряд IV		5,0 (Г)	7,2 (Г)			3,8 (Д)	5,0 (Д)	4,6 (И)		2,6 (И)
К		7,6	6,4			3,4	8,4	2,0
ряд V		5,0 (Г)	6,4(К)			3,4 (К)	5,0 (Д)	2,0 (К)

А à Г à Д à И à К à З

	А	Б	В	Г	Д	Е	Ж	З	И	К
ряд V		5,0 (Г)	6,4 (К)			3,4 (К)	5,0 (Д)	2,0 (К)
З		6,6	4,4			2,4	10,4
ряд VI		5,0 (Г)	4,4 (З)			2,4 (З)	5,0 (Д)

А à Г à Д à И à К à З à Е

	А	Б	В	Г	Д	Е	Ж	З	И	К
ряд VI		5,0 (Г)	4,4 (З)			2,4 (З)	5,0 (Д)
Е		4,2	3,6				8,8
ряд VII		5,0 (Г)	3,6 (Е)				5,0 (Д)

А à Г à Д à И à К à З à Е à В

	А	Б	В	Г	Д	Е	Ж	З	И	К
ряд VII		5,0 (Г)	3,6 (Е)				5,0 (Д)
В		2,2					12,4
ряд VIII		2,2 (В)					5,0 (Д)

А à Г à Д à И à К à З à Е à В à Б

	А	Б	В	Г	Д	Е	Ж	З	И	К
ряд VIII		2,2 (В)					5,0 (Д)
В							12,4
ряд IХ							5,0 (Д)

Итоговая КСС имеет следующий вид:

А à Г à Д à И à К à З à Е à В à Б

â

Ж

Таблица 3.3

Дата добавления: 2014-11-29