Составление матрицы расстояний

Расчетное задание 3.

Определение радиального маршрута доставки грузов

 

Задание:

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

1. Выбрать торговую сеть Санкт-Петербурга с крупным складом (количество магазинов в городе или в районе должно быть в диапазоне 6-10 магазинов). Дать краткое описание сети и предложить товар для развозки по магазинам. Адреса магазинов представить в виде табл. 1

2. Определите матрицу расстояний между магазинами и складом, на котором хранится груз, результаты представьте в табл. 2. В таблице должно быть заполнено более 60% расстояний между объектами. Если движение между объектами затруднено (постоянные пробки, ремонт дорог и т.д.) ставится прочерк, который говорит о том, что прямого пути между объектами нет.

3. Определить рациональный маршрут развозки груза по магазинам сети с помощью формулы приращений. Результат представить в виде карты, с указанием точек-магазинов и рационального маршрута.

4. Рассчитать разницу в расстоянии при рациональном маршруте движения и произвольным маршрутом развозки груза.

 

Таблица 1

Адреса магазинов в Санкт-Петербурге

 

	Наименование	Адрес	Объем поставки, кг
1			800
2			300
3			250
4			350
5			1300

Составление матрицы расстояний

Здесь рассмотрен пример, когда не между всеми парами объектов существует проезд. В курсовом проекте необходимо рассмотреть расстояния между всеми возможными парами объектов, тогда, табл. 7 будет заполнена полностью.

Для поиска информации о расстояниях внутри городов можно воспользоваться ресурсом: http://maps.google.ru/.

Необходимо определить порядок развозки грузов по магазинам, стоимость перевозки, и время доставки, если средняя скорость передвижения по городу составляет 23 км/час, а время на разгрузку в каждой точке маршрута – 0,5 часа.

Таблица 2

Пример заполненной матрицы расстояний

	Склад	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5
Склад	0	-	8	3	3,7	2
Магазин 1	-	0	6,2	12	8,2	-
Магазин 2	8	6,2	0	2,5	4,3	-
Магазин 3	3	12	2,5	0	2,5	1,5
Магазин 4	3,7	8,2	4,3	2,5	0	-
Магазин 5	2	-	-	1,5	-	0

 

Постановка задачи:

Заданы пункты потребления (табл. 1). Груз необходимо развести из начального пункта (склада) во все остальные пункты (потребители). Потребность (объем поставки) указана в табл. 1. На складе имеется транспортное средство грузоподъемностью 3 т. Известно расстояние между потребителями (табл. 2). Схема размещения пунктов и расстояния между ними приведены на рис. 1

 

Рис. 1. Пример схемы размещения потребителей

Этап 1. Строим кратчайший путь, связывающий все пункты без замкнутых контуров (рис. 2).

 

Рис. 2. Кратчайший путь

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

Таблица 3

Пример матрицы кратчайших расстояний, км

Номер	Склад	2,0	3,0	5,5	3,7	11,9
1	2,0	Магазин 5	1,5	4,0	5,7	10,2
2	3,0	1,5	Магазин 3	2,5	6,7	8,7
3	5,5	4,0	2,5	Магазин 2	4,3	6,2
4	3,7	5,7	6,7	4,3	Магазин 4	8,2
5	11,9	10,2	8,7	6,2	8,2	Магазин 1
Итого	26,1	23,4	22,4	22,5	28,6	45,2

Начальный маршрут строим для трех пунктов матрицы, имеющих наибольшие размеры сумм, показанных в строке «Итого», т.е. Магазин 1 – Магазин 4 – Склад.

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

- Магазин 1 – Магазин 4;

- Магазин 4 – Склад;

- Склад – Магазин 1.

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

 

 

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

При включении пункта – Магазин 5 (м5) между Магазин 1 (м1) и Магазин 4 (м4) определяем размер приращения:

 

 

Аналогично определяем приращения между парами м4 – с (склад) и с – м1.

 

 

Из полученных значений необходимо выбрать минимальное.

Таким образом, получилась последовательность:

Магазин 1 – Магазин 4 – Склад – Магазин 5

Используя этот метод и формулу определяем между какими пунктами расположить Магазин 2 (м2) и Магазин 3 (м3).

Добавление Магазина 2:

 

 

Маршрут: Магазин 1 – Магазин 4 – Склад – Магазин 5 – Магазин 2

 

Добавление Магазина 3:

 

 

Маршрут: Магазин 1 – Магазин 4 – Склад – Магазин 5 – Магазин 3 – Магазин 2

 

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

 

Рис. 3. Разработанный маршрут