5.2 Методика расчета развозочных маршрутов.

Потребность в мелкопартионных поставках продукции потребителям с баз складов систематически возрастает, поэтому организация маршрутов на отгрузку потребителям мелких партий груза имеет большое значение.

Основные обозначения методики расчета развозочных маршрутов

Гi- населенный пункт (пункт потребления) ; i= A-Z, 0-9;

Ц- распределительный центр (или склад, начальный пункт)

q- потребность заказов в единицах объема груза (стандартная коробка)

Q- грузоподъемность транспортного средства

Cij- стоимость перевозки (расстояние)

Формулировка задачи

Имеются пункты потребления Гi (i=A-Z,0-9). Груз необходимо развести из начального пункта (распределительного центра- Ц) во все остальные пункты, т.е.потребителям. Потребность пунктов потребления в единицах объема груза составляет : qA, qB…qZ; q0..q9

В начальном пункте (Ц) имеются транспортные средства грузоподъемностью Q1, Q2 …Qd. Для каждой пары пунктов (Гi, Гj)определяют стоимость перевозки Сij≥0.

Требуется найти количество замкнутых путей I1, I2…Im из единственной общей точки (Ц) так, чтобы выполнялось условие

Lĸ→min

Методика составления рациональных маршрутов при расчетах вручную

Смотрите в качестве исходных данных табл. 3 и схему 2

Таблица 3

Заявки потребителей продукции на один день 9-03-2003 г.

Показатели	Потребители продукции
К-во коробок	G	K	M	N	U	W	Z	1	2
Объем продукции	49	7	42	22	39	25	25	17	14

Груз находится в пункте Ц-240 коробок, используется автомобиль грузоподъемностью 120 коробок. Необходимо организовать перевозку между пунктами с минимальным пробегом подвижного состава.

Схема 2. Размещение пунктов потребления и расстояние между ними.

Решение(состоит из нескольких этапов)

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

Рис. 1 . Кратчайшая сеть, связывающая потребителей («минимальное дерево»)

Затем, по каждой ветви сети, начиная с пункта наиболее удаленного от распределительного центра Ц, группируем пункты по маршрутам с учетом :

• Количества ввозимого товара

• Грузоподъемности единицы подвижного состава

Исходя из заданной грузоподъемности собственного ТС- 120 коробок и количества развозимого груза, все пункты можно сгруппировать в 2 группы (табл. 4)

Таблица 4

Распределение пунктов потребления по группам (маршрутам)

Группа 1		Группа 2
пункт	Объем заказа,коробок	пункт	Объем заказа,коробок
2	14	G	49
1	17	N	22
U	39	K	7
Z	25	M	42
W	25
Итого:	120 коробок	Итого:	120 коробок

Сгруппировав пункты по группам, переходим ко второму ко второму этапу расчетов.

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

Таблица 5

Таблица-матрица для маршрута 1

Ц	5,5	7,9	7,4	12,5	10,6
5,5	2	2,4	4,9	7,0	8,1
7,9	2,4	1,	3,5	4,6	6,7
7,4	4,9	3,5	U	2,2	3,2
12,5	7,0	4,6	2,2	Z	2,4
10,6	8,1	6,7	3,2	2,4	W
49,3	27,9	25,1	21,2	28,7	31,0

Начальный маршрут строим для трех пунктов матрицы Ц-W-Z-Ц, имеющие наибольшее значение суммы расстояния в итоговой строке сообтветственно,

49,3 31,0 28,7 , т.е.

Ц- W- Z- Ц

Для включения последующих пунктов выбираем из оставшихся пункт, имеющий наибольшую сумму, например, 2 (сумма 27,9) и решаем, между какими пунктами следует включать, т.е. между

(Ц- W)- 1 пара, (W- Z)- 2 пара, (Z- Ц)- 3 пара

Поэтому для каждой пары пунктов необходимо найти величину приращения маршрута ∆kp по формуле

∆kp=Cki+Cip+Ckp,

Где С- расстояние, км; К-индекс первого пункта пары; i-индекс включаемого пункты; р-индекс второго пункта пары.

А) При включении пункта 2 между первой парой пунктов Ц и W определяем размер приращения ∆цw, исходя из условия i=2; k=Ц ;p=W.

∆цw=Сц2+С2w-Cцw, подставляя значения из табл 2, находим:

∆цw=5,5+8,1-10,6=3,0

Б) Таким же образом определим приращение ∆wz , если пункт 2 включить между пунктами W и Z:

∆wz=Cw2+C2z-Cwz= 8,1+7,0-2,4=12,7

В) Приращение ∆ZЦ, если пункт 2 включить между пунктами Z и Ц:

∆ZЦ=Cz2+C2ц-Czц= 7,0+5,5+-12,5= 0

Из полученных значений выбираем минимальное приращение ∆ZЦ=0, тогда маршрут Ц-W-Z-Ц преобразуется в маршрут Ц-W-Z-2-Ц.

Начнем с пункта 1, т.к. размер суммы в итоговой таблице 25,1>21.2

∆цw=Сц1+C1w-Cцw= 7,9+6,7-10,6=4,0

∆wz=Сw1+C1z-Cwz=6.7+4.6-2.4=8.9

∆z2=Cz1+C12-Cz2=4.6+2.4-7.0=0,0→min

∆2ц=C21+C1ц-С2ц= 2,4+7,9-5,5=4,8

Пункт 1 должен быть между пунктами Z и 2. Тогда маршрут получит вид

Ц-W-Z-1-2-Ц

Определяемся с пунктом U

∆цw= Cцu+ Сuw-Cцw= 7,4+3,2-10,6=0

Поскольку матрица симметрична и ∆цw=0, то дальнейшие расчеты можно не продолжить, т.к. меньшее значение, чем 0, получено быть не может. Поэтому пункт U должен находиться между пунктами Ц и W. Таким образом, окончательный порядок движения по маршруту : Ц-U-W-Z-1-2-Ц.

Рис.2 Порядок движения по маршруту 1

Таким же методом определяется кратчайший путь объезда пунктов по маршруту 2.

Определяем рациональный порядок объезда пунктов маршрута 2. Для этого формируется табл. 6, таблица-матрица для маршрута 2, в которой по диагонали размещаются пункты, включаемые в маршрут 2 и начальный пункт Ц, а в соответствующих клетках- кратчайшие расстояния между ними.

Начальный маршрут строим для трех пунктов матрицы Ц-К-G-Ц, имеющих наибольшие значения в итоговой строке 24,4-19,9-19,3, т.е. Ц-К-G. Для включения последующих пунктов выбираем из оставшихся пункт, имеющий наибольшую сумму- 15,7 (пункт М) и решаем, между какими пунктами его следует включать : Ц-К, К-G или G-Ц. поэтому для каждой пары пунктов необходимо найти величину приращения маршрута.

Таблица 6

Таблица-матрица для маршрута 2

Ц	6,7	5.8	8.3	3.6
6,7	G	3.0	4.4	5.2
5,8	3.0	N	2.5	2.2
8,3	4.4	2.5	K	4.7
3,6	5.2	2.2	4.7	M
24,4	19.3	13.5	19.9	15.7

А) включение маршрута М между парой пунктов Ц и К

∆цк= Сцм+Смк-Сцк= 3,6+4,7-8,3=0

Пункт М следует включить между пунктами Ц и К, т.е. маршрут Ц-К-G-Ц превращается в маршрут Ц-М-К-G-Ц.

Б) Пункт N включаем в маршрут Ц-М-К-G-Ц:

∆мк=Смn+Сnk-Смk= 2,2+2,5-4,7=0

Пункт N следует включить между М и К : Ц-М-N-К-G-Ц