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

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

Маршрут 1	Маршрут 2
Пункт	Объем завоза, кг.	Пункт	Объем завоза, кг.
Б		Ж
В		Д
Е		И
З		Г
К		-	-
Итого		Итого

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

Таблица 3.5

Номер строки	А	7,0	9,2	9,0	11,4	10,6
	7,0	Б	2,2	4,2	6,6	7,6
	9,2	2,2	В	3,6	4,4	6,4
	9,0	4,2	3,6	Е	2,4	3,4
	11,4	6,6	4,4	2,4	З	2,0
	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 - индекс второго пункта из пары.

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

DАК = САЗ + СЗК – САК

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А à К à З à Е à В à Б à А.

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

Таблица 3.6

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