Матрица кратчайших расстояний между пунктами первого маршрута

Сгруппированные маршруты

Маршрут 1 Маршрут 2
пункт	пункт
Б	Ж
В	Д
Е	И
З	Г
К

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

Таблица 11.2

А		9,5	8,4	10,5
	Б	2,5	5,0	6,2	7,7
9,5	2,5	В	4,1	3,7	5,2
8,4	5,0	4,1	Е	2,1	3,7
10,5	6,2	3,7	2,1	З	1,5
	7,7	5,2	3,6	1,5	К
S 47,4	28,4		23,2		30,1

Начальный маршрут строим для трех пунктов матрицы, из которых один является пунктом отправления, а два других имеют наибольшие значения величины в строке суммы. Таким образом, в нашем примере начальный маршрут строим для трех пунктов матрицы АБКА. Пункт А входит, потому что является пунктом отправления грузов, а пункты Б и К имеют наибольшие значения величины, показанных в строке суммы (28,4; 30,1).

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

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

Dkp = Ckj + Cjp – Ckp,

где С – расстояние, км; j – индекс включаемого пункта; k – индекс первого пункта из пары; p – индекс второго пункта из пары.

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

При включении пункта В между первой парой пунктов А и Б, определяем размер приращения DАБ при условии, что j – В, k – А, p – Б. Тогда

DАБ = САВ + СВБ – САБ

Подставляя значения из таблицы, получаем, что

DАБ = 9,5 + 2,5 – 7 = 5

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

DБК = СБВ + СВК - СБК = 2,5 + 5,2 – 7,7 = 0

Поскольку значение приращения DБК получилось равным нулю, дальнейшие расчеты уже необязательны, потому что меньше нуля значения уже не будет. Тогда из начального маршрута А-Б-К-А мы получаем А-Б-В-К-А.

Используя этот метод и формулу приращения, определяем, между какими пунктами расположить пункты Е и З. Начнем с пункта З, так как размер суммы этого пункта больше.

DАБ = 10,5 + 6,2 – 7 = 9,7

DБВ = 6,2 + 3,7 – 2,5 = 7,4

DКВ = 3,7 + 1,5 – 5,2 = 0

Таким образом, пункт З включается между пунктами В и К, и из маршрута А-Б-В-К-А мы получаем маршрут А-Б-В-З-К-А.

И оставшийся пункт Е.

DАБ = 8,4 + 5 – 7 = 6,4

DБВ = 5 + 4,1 – 2,5 = 6,6

DВЗ = 4,1 + 2,1 – 3,7 = 2,5

DЗК = 2,1 + 3,7 – 1,5 = 4,3

DКА = 3,6 + 8,4 – 12 = 0

Минимальным значением является DКА = 0, значит пункт Е включается между пунктами К и А. В результате мы имеем оптимальный маршрут развоза продукции А-Б-В-З-К-Е-А.

Таким же методом определим кратчайший путь объезда пунктов по маршруту 2. В результате расчетов получим маршрут А-Ж-И-Д-Г-А. Порядок движения по полученным оптимальным маршрутам показан на рис.11.10.

Рис. 11.10. Схема полученных оптимальных маршрутов

Дата добавления: 2014-10-23