Исходные данные (см. табл. 1 и схема 1).
Груз находится в пункте Ц – 240 коробок.
Используется автомобиль грузоподъемностью 120 коробок.
Таблица 1
Наименование показателя (коробок) Потребители продукции
I J H G W E A C 7
Объем продукции 33 15 19 27 37 24 14 12 59
Схема 1. Размещения пунктов потребления и расстояния между ними
Необходимо организовать перевозку между пунктами потребления с минимальным пробегом подвижного состава.
Решение
I этап. Строим кратчайшую сеть, связывающую все пункты без замкнутых контуров по принципу минимизации расстояний между двумя пунктами (рис. 2).
Рисунок 2. Кратчайшая сеть, связывающая потребителей («минимальное дерево»)
Расстояние L = 2,1 + 2,2 + 1,9 + 1,6 + 2,5 + 4,7 + 2,6 + 4,1 + 1,9 + 2,3 = 25,9 км.
II этап. По каждой ветви сети, начиная с пункта, наиболее удалённого от распределительного центра Ц, группируем пункты на маршрут с учётом количества ввозимого груза и грузоподъёмности единицы подвижного состава.
Исходя из заданной грузоподъемности собственного транспортного средства – 120 коробок и количества развозимого груза, все пункты можно сгруппировать в две группы (табл. 2).
Таблица 2
Распределение пунктов потребления по группам (маршрутам)
Группа 1 Группа 2
пункт объем заказа, коробок пункт объем заказа, коробок
I 33 J 15
C 12 G 27
A 14 H 19
E 24 7 59
W 37
Итого: 120 коробок Итого: 120 коробок
III этап. Определяем рациональный порядок объезда пунктов. Для этого строим таблица-матрица, в которой по диагонали размещены пункты, включаемые в маршрут, и начальный пункт Ц, а в соответствующих клетках – кратчайшее расстояние между ними (табл
. 3).
Таблица 3
Таблица-матрица для маршрута 1
Ц 2,3 4,2 8,3 10,9 9,3
2,3 I 1,9 6,0 8,6 7,0
4,2 1,9 C 4,1 6,7 5,1
8,3 6,0 4,1 A 2,6 7,3
10,9 8,6 6,7 2,6 E 4,7
9,3 7,0 5,1 7,4 4,7 W
35,0 25,8 22 28,4 33,5 33,4
Начальный маршрут строим для трех пунктов матрицы Ц-E-W-Ц, имеющие наибольшее значение суммы расстояния в итоговой строке: (35,0), (33,5) и (33,4).
Для включения оставшихся пунктов в маршрут выбираем из них тот, которому соответствует следующая наибольшая сумма – А (28,4). Необходимо решить между какими пунктами должен быть расположен пункт А, т. е. между пунктами Ц и E, между пунктами E и W или между пунктами W и Ц.
Для этого рассчитывается приращение:
Ц-А-Е=LЦА+LАЕ-LЦЕ=8,3+2,6-10,9=0 км.
Е-А-W=LЕА+LAW-LEW=2,6+7,3-4,7=5,2 км.
W-A-Ц=LWA+LАЦ-LWЦ=7,3+8,3-9,3=6,3 км.
Минимальное значение соответствуетЦ-А-Е, следовательно пункт F должен быть расположен между пунктами Ц и Е.
Получаем маршрут вида:
Ц – А – Е –W – Ц.
Выбираем пункт G.
Ц-I-A=LЦI+LIA-LЦА=2,3+6,0-8,3=0 км.
A-I-E=LAI+LIE-LAE=6,0+8,6-2,6=12 км.
E-I-W=LEI+LIW-LEW=8,6+7,0-4,7=10,9 км.
W-I-Ц=LWI+LIЦ-LWЦ=7,0+2,3-9,3=0 км.
Минимальное значение соответствуетЦ-I-A и W-I-Ц, расположим пункт I между пунктами Ц и A.
Получаем маршрут вида:
Ц – I – А – Е –W – Ц.
Ц-C-I=LЦC+LCI-LЦi=4,2+1,9-2,3=3,8 км.
I-C-A=LIC+LCA-LIА=1,9+4,1-6,0=0 км.
A-C-E=LAC+LCE-LAE=4,1+6,7-2,6=8,2 км.
E-C-W=LEC+LCW-LEW=6,7+5,1-4,7=7,1 км.
W-C-Ц=LWC+LCЦ-LWЦ=5,1+4,2-9,3=0 км.
Минимальное значение соответствуетI-C-A и W-C-Ц, расположим пункт C между пунктами I и A.
Окончательный маршрут имеет вид:
Ц – I – C – А – Е –W – Ц.
L = 2,3 + 1,9 + 4,1 + 2,6 + 4,7 + 9,3 = 24,9 км.
IV этап
Задать вопрос
на новый заказ в Автор24.
