Пример заполненной матрицы расстояний
|
Склад |
Магазин 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 |
Постановка задачи:
Заданы пункты потребления (табл. 5). Груз необходимо развести из начального пункта (склада) во все остальные пункты (потребители). Потребность (объем поставки) указана в табл. 5. На складе имеется транспортное средство грузоподъемностью 3 т. Известно расстояние между потребителями (табл. 6). Схема размещения пунктов и расстояния между ними приведены на рис. 1
Рис. 1. Пример схемы размещения потребителей
Этап 1. Строим кратчайший путь, связывающий все пункты без замкнутых контуров (рис. 2).
Рис. 2. Кратчайший путь
Этап 2. Определяем рациональный порядок объезда пунктов маршрута. Для этого строим матрицу (табл. 7), в которой по диагонали размещаем пункты маршрута (обратите внимание: пункты маршрута указываются в порядке кратчайшего пути на рис. 2), а в соответствующих клетках – кратчайшие расстояния между пунктами (в соответствии с рис. 1). Для примера матрица является симметричной, однако в курсовом проекте она может получиться несимметричной. Это связано с различными способами проезда по улицам города.
Таблица 7
Пример матрицы кратчайших расстояний, км
Номер |
Склад |
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. Разработанный маршрут