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

Введение
Задание:
Со склада, на котором хранится груз, необходимо распределить часть груза (3 тонны) по магазинам Санкт-Петербурга. При этом необходимо определить оптимальный маршрут движения транспортного средства. В качестве критерия оптимальности использовать минимум пройденного расстояния.
1. Выбрать торговую сеть Санкт-Петербурга с крупным складом (количество магазинов в городе или в районе должно быть в диапазоне 6-10 магазинов). Дать краткое описание сети и предложить товар для развозки по магазинам. Адреса магазинов представить в виде табл. 1
2. Определите матрицу расстояний между магазинами и складом, на котором хранится груз, результаты представьте в табл. 2. В таблице должно быть заполнено более 60% расстояний между объектами. Если движение между объектами затруднено (постоянные пробки, ремонт дорог и т.д.) ставится прочерк, который говорит о том, что прямого пути между объектами нет.
3. Определить рациональный маршрут развозки груза по магазинам сети с помощью формулы приращений. Результат представить в виде карты, с указанием точек-магазинов и рационального маршрута.
4. Рассчитать разницу в расстоянии при рациональном маршруте движения и произвольным маршрутом развозки груза.
Таблица 1
Адрес магазинов в Санкт-Петербурге
Номер склада Наименование организации Адрес
1 ООО «Интертерминал-Предпортовый» Санкт-Петербург, ул. Кубинская, 75
2 ООО «Предприятие Алиди» Санкт-Петербург, ул. Домостроительная, д. 1
3 ООО «Северный легион» п. Новое Девяткино, Токсовское шоссе, 48
4 ООО «Складской комплекс Царское село» Санкт-Петербург, г. Пушкин, Кузьминское шоссе, 66
5 ООО «Энерго» Санкт-Петербург, ул. Киевская, д. 5, корпус 3
Груз хранится на первом складе ООО «Интертерминал-Предпортовый», Санкт-Петербург, ул. Кубинская, 75.

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

Со склада на улице Кубинской, на котором хранится груз, необходимо распределить часть груза (3 тонны) по магазинам Санкт- Петербурга. При этом необходимо определить оптимальный маршрут движения транспортного средства. В качестве критерия оптимальности использовать минимум пройденного расстояния.
1. Определим возможные адреса поставки в зависимости от специфики груза, данные представим в табл. 2.
Таблица 2
Адреса магазинов в Санкт-Петербурге
Наименование Адрес Объем поставки, кг
1 Спектр Большой Сампсониевский, 76 800
2 Клеенка Московский, 147 300
3 Улыбка радуги Я.Гашека, 9, корп.1 250
4 Альянс Парголовская, 7 350
5 Шарм Металлистов, 88 1300

2. Определим матрицу расстояний между магазинами и складом, на котором хранится груз, результаты представим в табл. 4
Для поиска информации о расстояниях внутри городов воспользуемся ресурсом: http://maps.yandex.ru/.
Необходимо определить порядок развозки грузов по магазинам, стоимость перевозки, и время доставки, если средняя скорость передвижения по городу составляет 23 км/час, а время на разгрузку в каждой точке маршрута - 0,5 часа.

Таблица 3
Заполненная матрица расстояний
Склад Магазин 1 Магазин 2 Магазин 3 Магазин 4 Магазин 5
Склад 21 4,5 11 19 19
Магазин 1 21 20 15 1,6 17
Магазин 2 4,5 20 7,6 17 17
Магазин 3 11 15 7,6 15 11
Магазин 4 19 1,6 17 15 11
Магазин 5 19 17 17 11 11

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

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

Этап 2. Определяем рациональный порядок объезда пунктов маршрута. Для этого строим матрицу (табл. 4), в которой по диагонали размещаем пункты маршрута (обратите внимание: пункты маршрута указываются в порядке кратчайшего пути на рис. 3), а в соответствующих клетках - кратчайшие расстояния между пунктами (в соответствии с рис. 1).
Таблица 4
Матрицы кратчайших расстояний, км
Номер Склад 4,5 11 19 19 21
1 4,5 Магазин 2 7,6 17 17 20
2 11 7,6 Магазин 3 11 15 15
3 19 17 11 Магазин 5 11 17
4 19 17 15 11 Магазин 4 1,6
5 21 20 15 17 1,6 Магазин 1
Итого 74,5 66,1 59,6 75 63,6 74,6
Начальный маршрут строим для трех пунктов матрицы, имеющих наибольшие размеры сумм, показанных в строке «Итого», т.е. Магазин 1 - Магазин 4 - Склад.
Для включения последующих пунктов берем следующий по убыванию суммы пункт - Магазин 5 и решаем между какими пунктами его включить: