Задача 1. Методика расчёта развозочных маршрутов
Потребность в мелкопартийных поставках продукции потребителям с баз и складов систематически возрастает. Поэтому организация маршрутов на отгрузку потребителям мелких партий груза имеет большое значение.
Введём значение:
Хi – пунки потребления (i = 1, 2… n);
Хо – начальный пункт (склад);
q – потребность пунктов потребления в единицах объёма груза;
Qd – грузоподъёмность транспортных средств;
d – количество транспортных средств;
Сij – стоимость перевозки (расстояние);
j – поставщики (j – 1, 2…М).
Имеются пункты потребления Хi (i = 1, 2…n). Груз необходимо развести из начального пункта Хо (склад во все остальные (потребители). Потребность пунктов потребления в единицах объёма груза составляет: q1, q2, q3…qn.
В начальном пункте имеются транспортные средства грузоподъёмностью Q1, Q2… Qd.
n
При этом d > n в пункте Хо количество груза Хо ³ å Хi , каждый пункт
i=1
потребления снабжается одним типом подвижного состава.
Для каждой пары пунктов (Хi, Хj) определяют стоимость перевозки (расстояние) Сij> 0, причём матрица стоимостей в общем случае может быть асимметричная, т.е. Сij ¹ Cij.
Требуется найти m замкнутых путей L1, L2… Lm из единственной общей точки Хо, так чтобы выполнялось условие:
m
å Lk ® min
k=1
Методика составления рациональных маршрутов при расчётах вручную.Схема размещения пунктов и расстояния между ними:
|

![]() | |||
![]() | |||
5,0
4,4 3,6 4,2 3,2 5,6
2,4
1,9 2,0
![]() | |||
![]() | |||
2,0 3,4 2,8
2,6 5,8
Потребители продукции | Б | В | Г | Д | Е | Ж | З | И | К |
Объём продукции, кг. | 375,0 |
Груз находится в пункте А – 4000 кг. Используется автомобиль грузоподъёмность 2,5 т.; груз – II класса (g = 0,8). Необходимо организовать перевозку между пунктами с минимальным пробегом подвижного состава.
Решение состоит из нескольких этапов:
Этап 1.Строим кратчайшую сеть, связывающую все пункты без замкнутых контуров.
Кратчайшая связывающая сеть («минимальное дерево»):
|
![]() | |||
![]() | |||
375 кг 3,2 км
2,2 км
500 500 кг
![]() |
2,0 км
3,6 км 300 кг
![]() | |||
![]() | |||
5,0
525 кг
425 кг
2,4 км 2,8 км
![]() | |||
![]() | |||
2,6 675 кг
575 кг 2,0
Затем по каждой ветви сети, начиная с пункта, наиболее удалённого от начального А (считается по кратчайшей связывающей сети), группируем пункты на маршрут с учётом количества ввозимого груза и грузоподъёмности единицы подвижного состава. Причём ближайшие с другой ветви пункты группируем вместе с пунктами данной ветви.
Исходя из заданной грузоподъёмности подвижного состава Q = 2,5, g = 0,8 все пункты можно сгруппировать так:
Маршрут 1 | Маршрут 2 | ||
пункт | объём завоза, кг. | пункт | объём завоза, кг. |
Б | Ж | ||
В | Д | ||
Е | И | ||
З | Г | ||
К | |||
Итого: | Итого: |
Сгруппировав пункты по маршрутам, переходим ко второму этапу расчётов.
Этап 2.Определяем рациональный порядок объезда пунктов каждого маршрута. Для этого строим таблицу-матрицу, в которой по диагонали размещаем пункты, включаемые в маршрут, и начальный пункт А, а в соответствующих клетках – кратчайшие расстояния между ними. Для примера матрица является симметричной Сij = Cji, хотя приведённый ниже способ применим для размещения несимметричных матриц.
А | 7,0 | 9,2 | 9,0 | 11,4 | 10,6 |
7,0 | Б | 2,2 | 4,2 | 6,6 | 7,6 |
9,2 | 2,2 | В | 3,6 | 4,4 | 6,4 |
9,0 | 4,2 | 3,6 | Е | 2,4 | 3,4 |
11,4 | 6,6 | 4,4 | 2,4 | З | 2,0 |
10,6 | 7,6 | 6,4 | 3,4 | 2,0 | К |
å 47,2 | 27,6 | 25,8 | 22,6 | 26,0 | 30,0 |
Начальный маршрут строим для трёх пунктов матрицы АКБА, имеющих наибольшее значение величины, показанных в строке (47,2; 30,0; 27,6), т.е. А; К; Б. Для включения последующих пунктов выбираем из оставшихся пункт, имеющий наибольшую сумму, например 3 (сумма 25,8), и решаем, между какими пунктами его следует включать,т.е. между А и К, К и Б или Б и А.
Поэтому для каждой пары пунктов необходимо найти величину приращениямаршрута по формуле:
kp = Cki + Cip – Ckp,
где С – расстояние, км.; i – индекс включаемого пункта; k – индекс первого пункта из пары; p – индекс второго пункта из пары.
При включении пункта 3 между первой парой пунктов А и К, определяем размер приращения DАК при условии, что i = 3, k = A, p = K. Тогда
DАК = САЗ + СЗК - САК.
Подставляя значения из таблицы на с. 127, получаем, что DАК = 11,4 + 2,0 – 10,6 = 2,8.
Таким же образом определяем размер приращения DКБ, если 3 включим между пунктами К и Б: DКБ = СКЗ + СЗБ + С КБ = 2,0 + 6,6 – 7,6 + 1,0 км., DБА, если 3 включить между пунктами Б и А:
DБА = СБЗ + СЗА – САБ = 6,0 + 11,4 – 7,0 = 11,0 км.
Из полученных значений выбираем минимальные, т.е. DКБ = 1,0. Тогда из А-К-Б-А®А-К-З-Б-А. Используя этот метод и формулу приращения, определяем, между какими пунктами расположить пункты В и Е. Начнём с В, т.к. размер суммы (см. табл.) этого пункта больше (27,6 > 22,6):
DАК = САБ + СВК – САК = 9,2 + 6,4 - 10,6 = 5,0,
DКЗ = СКВ + СВЗ – СКЗ = 6,4 + 4,4 – 2,0 = 8,8,
DЗБ = СЗВ + СВБ – СЗБ = 4,4 + 2,2 – 6,6 = 0.
В случае, когда D = 0, для симметричной матрицы расчёты можно не продолжать, т.к. меньше значение чем 0 получено быть не может. Поэтому пункт В должен быть между пунктами З и Б. Тогда маршрут получит вид: А-К-З-В-Б-А.
В результате проведённого расчёта включаем пункт Е между пунктами З и В, т.к. для этих пунктов мы получим минимальное приращение 1,6:
DАК = САЕ + СЕК – САК = 9,0 + 3,4 – 10,6 = 1,8;
DКЗ = СКЕ + СЕЗ – СКЗ = 3,4 + 2,4 – 2,0 = 3,9;
DЗВ = СЗЕ + СЕВ – СЗВ = 2,4 + 3,6 – 4,4 = 1,6;
DВБ = СВЕ + СЕБ – СВБ = 3,6 + 4,2 – 2,2 = 5,4;
DБА = СБЕ + СЕА – СБА = 4,2 + 9,0 – 7,0 = 6,1.
Таким образом, окончательный порядок движения по маршруту 1 будет А-К-З-Е-В-Б-А.
Таким же методом определим кратчайший путь объезда пунктов по маршруту 2. В результате расчётов получим маршрут А-Г-Д-И-Ж-А длиной 19,4 км. Порядок движения по маршрутам 1 и 2 приведён ниже:
7,0
2,2
![]() |
3,2
![]() | |||
![]() | |||
10,6 5,6
3,6 2,0
2
![]() | |||||
![]() | |||||
![]() | |||||
2,4 5,8
2,8
2,0
![]() |

Исходные данные для решения задачи 1. (по вар.) m = 69 т.
1.7,9 8,1 q = 23 т.
![]() | ![]() |
5,9 6,9
8,3 4,5 8,4 5,8 3,4
9,3 9,3
3,7 6,2 6,8 1,2 8,9 5,6
![]() | ![]() | |||||||||||||
![]() | ![]() | ![]() | ||||||||||||
![]() | ||||||||||||||
![]() | ![]() | ![]() | ||||||||||||
9,2 7,3 6,7 8,9 6,7 7,4 6,8 7,8
![]() | ![]() | ![]() | ![]() | ||||
10,8 3,3 3,5
![]() | ![]() | ||
3,4 5,6 9,1
![]() |
Б | В | Г | Д | Е | Ж | З | И | К | Л | М | Н | О | П | С |
2.m = 8 т. 6,3 9,1
|

![]() | ![]() | ![]() | ||||||||||||||
![]() | ||||||||||||||||
![]() | ![]() | ![]() | ![]() | ![]() | ||||||||||||
6,3 2,3 4,3 9,3 7,8 9,3
4,5
5,5 3,6
1,2 4,5
7,8 9,8 8,9
3,4
3,4
6,3 1,2 8,9 4,3
8,9 7,5
4,8 7,1
Б | В | Г | Д | Е | Ж | З | И | К | Л | М | Н | О | П | С |
|






q = 2800 9,7
7,3 6,9
3,8 4,3 2,2
8,1
![]() | ![]() | ![]() | |||||||||
![]() | ![]() | ![]() | |||||||||
2,1 3,0 7,1 1,2 1,1
3,7
2,4 8,7 9,3
4.
|
q = 3000 9,3 5,6
1,2 | ![]() ![]() | В | ||
![]() ![]() ![]() ![]() | Д | |||
Е | Ж | |||
6,8 3,6 3,4 | З | И | ||
8,9 | ![]() ![]() |
9,6 4,3 8,9
6,7
4,5 3,8
![]() |
3,44,5
8,7
![]() |
5,5 6,9
![]() |
5.m = 18.
|
8,6
8,9
9,3 10,1 9,1
![]() | ![]() | ||||
![]() | |||||
7,3 2,2
3,5 9,1 8,9
![]() | |||||||||
![]() | ![]() | ![]() | |||||||
![]() | |||||||||
9,2 5,5 3,4 6,8
8,1
![]() | ||||
![]() | ![]() |
7,5 3,3
Б | В | Г | Д | Е | Ж | З | И | К |
6.m = 9 мм.
q = 2,5 мм. 9,2
![]() | |||||
![]() | ![]() | ||||
5,5
3,5 3,4 2,8
3,0
4,3
9,7
9,3 8,5 7,5
![]() | |||||
![]() | ![]() | ||||
6,9 5,8 6,4 7,5
![]() | ![]() | ||
1,2
5,5 10,1
Б | В | Г | Д | Е | Ж | З | И | К |
7.m = 12 т.
q = 6 т.
4,6 8,9
|
![]() | ![]() | ![]() | |||||
![]() | |||||||
3,8 9,2 3,9 7,7
4,8 8,3
7,9
![]() |
5,6 1,2 6,7
![]() | |||
![]() |
9,5
4,3
Б | В | Г | Д | Е | Ж | З | И | К |
8.
|
q = 18 5,5 9,1
![]() | |||
![]() | |||
1,2 1,3
![]() |
9,7 4,8 3,7
4,1
4,5 8,9
2,1 6,1
6,5
3,4 7,7 7,2
3,8 9,7
4,2
4,8 3,1
Б | В | Г | Д | Е | Ж | З | И | К | Л |
9.
|
q = 5 т. 1,8
9,2
![]() | ![]() |
1,4 10,4 5,6
![]() | ![]() | ![]() |
8,9
8,7 2,1 5,3 3,8
3,2 3,6 7,4 5,5 4,5 4,1 8,8
5,4 10,6
Б | В | Г | Д | Е | Ж | З | И | К | Л |
10.
|
q = 17 т. 5,9 7,6
![]() | ![]() |
3,9
4,4 9,4 6,7
![]() | ![]() |
3,1 5,53,8 8,1
![]() |
7,1 9,34,1 7,9
7,8 7,7
11,3 4,7 5,9