Маршрутизация
.pdf20
щей строки проставляют 0. Максимальный выигрыш отыскивают только в строках, которые соответствуют пунктам с индикаторами, имеющими отличные от нуля значения.
Теперь максимальному выигрышу (44 км) соответствует объединение маршрутов Р0 - Р6 - Р0 и Р0 - Р5 - Р8 - Р4 - Р0 в развозочный Р0 - Р6 - Р5 - Р8 - Р4 - Р0. Объем перевозок на маршруте при этом станет 0,17 + 2,87 = 3,04 т (таблица 2.5).
Таблица 2.5 – Выигрыши при объединении пунктов
Потр., |
I |
|
|
|
|
|
|
|
|
т |
|
|
|
|
|
|
|
|
|
0,89 |
2 |
P1 |
|
|
|
|
|
|
|
0,79 |
2 |
22 |
P2 |
|
|
|
|
|
|
0,84 |
2 |
19 |
27 |
P3 |
|
|
|
|
|
2,87 |
1 |
17 |
21 |
34 |
P4 |
|
|
|
|
2,87 |
1 |
38 |
35 |
35 |
51 |
P5 |
|
|
|
0,17 |
2 |
27 |
36 |
33 |
37 |
44 |
P6 |
|
|
0,61 |
2 |
21 |
27 |
34 |
32 |
43 |
31 |
P7 |
|
|
0 |
30 |
32 |
46 |
0 |
0 |
50 |
42 |
P8 |
На следующих этапах объединяют маршруты Р0 - Р2 - Р0 и Р0 - Р6 - Р5 - Р8 - Р4 - Р0 в развозочный Р0 - Р2 - Р6 - Р5 - Р8 - Р4 - Р0 (выигрыш 36 км) и Р0 - Р7 - Р0 и Р0 - Р2 - Р6 - Р5 - Р8 - Р4 - Р0 в развозочный Р0 - Р2 - Р6 - Р5 - Р8 - Р4 - Р7 - Р0 (выигрыш 32 км). В первом случае объем перевозок на маршруте составит 0,79 + 3,04 = = 3,83 т (таблица 2.6), а во втором случае – 0,61 + 3,83 = 4,44 т (таблица 2.7).
Таблица 2.6 – Выигрыши при объединении пунктов
Потр., |
I |
|
|
|
|
|
|
|
|
т |
|
|
|
|
|
|
|
|
|
0,89 |
2 |
P1 |
|
|
|
|
|
|
|
0,79 |
2 |
22 |
P2 |
|
|
|
|
|
|
0,84 |
2 |
19 |
27 |
P3 |
|
|
|
|
|
3,04 |
1 |
17 |
21 |
34 |
P4 |
|
|
|
|
|
0 |
38 |
35 |
35 |
51 |
P5 |
|
|
|
3,04 |
1 |
27 |
36 |
33 |
37 |
0 |
P6 |
|
|
0,61 |
2 |
21 |
27 |
34 |
32 |
43 |
31 |
P7 |
|
|
0 |
30 |
32 |
46 |
0 |
0 |
50 |
42 |
P8 |
21
Таблица 2.7 – Выигрыши при объединении пунктов
Потр., |
I |
|
|
|
|
|
|
|
|
т |
|
|
|
|
|
|
|
|
|
0,89 |
2 |
P1 |
|
|
|
|
|
|
|
3,83 |
1 |
22 |
P2 |
|
|
|
|
|
|
0,84 |
2 |
19 |
27 |
P3 |
|
|
|
|
|
3,83 |
1 |
17 |
21 |
34 |
P4 |
|
|
|
|
|
0 |
38 |
35 |
35 |
51 |
P5 |
|
|
|
|
0 |
27 |
0 |
33 |
37 |
0 |
P6 |
|
|
0,61 |
2 |
21 |
27 |
34 |
32 |
43 |
31 |
P7 |
|
|
0 |
30 |
32 |
46 |
0 |
0 |
50 |
42 |
P8 |
Дальнейшее объединение маршрутов невозможно, так как отсутствует автомобиль грузоподъемностью более 4,5 т, поэтому маршрут Р0 - Р2 - Р6 - Р5 - Р8 - Р4 - Р7 - Р0 считают законченным и за ним закрепляют автомобиль грузоподъемностью 4,5 т.
На следующем этапе объединяют оставшиеся маршруты Р0 - Р1 - Р0 и Р0 - Р3 - Р0 в развозочный Р0 - Р1 - Р3 - Р0 (выигрыш 19 км). Объем перевозок на маршруте при этом станет 0,89 + 0,84 = = 1,73 т (таблица 2.8). Так как нет больше пунктов для объединения, то маршрут Р0 - Р1 - Р3 - Р0 считают законченным и за ним закрепляют автомобиль грузоподъемностью 1,75 т. Следовательно, для перевозок используют один автомобиль грузоподъемностью 4,5 т (Луаз-890Б) и один автомобиль грузоподъемностью 1,75 т (ГЗСА-3702).
Таблица 2.8 – Выигрыши при объединении пунктов
Потр., |
I |
|
|
|
|
|
|
|
|
т |
|
|
|
|
|
|
|
|
|
0,89 |
2 |
P1 |
|
|
|
|
|
|
|
4,44 |
1 |
22 |
P2 |
|
|
|
|
|
|
0,84 |
2 |
19 |
27 |
P3 |
|
|
|
|
|
|
0 |
17 |
21 |
34 |
P4 |
|
|
|
|
|
0 |
38 |
35 |
35 |
51 |
P5 |
|
|
|
|
0 |
27 |
0 |
33 |
37 |
0 |
P6 |
|
|
4,44 |
1 |
21 |
27 |
34 |
0 |
43 |
31 |
P7 |
|
|
0 |
30 |
32 |
46 |
0 |
0 |
50 |
42 |
P8 |
Вместо использованных выигрышей и тех, которые не удалось использовать, в таблицах 2.4–2.8 проставляют нули.
22
Алгоритм Кларка и Райта не гарантирует получения оптимального решения. Поэтому следует проверять целесообразность перестановок пунктов, входящих в маршруты. Одним из методов, позволяющих это сделать, является метод суммирования по столбцам.
В качестве исходных данных необходима матрица кратчайших расстояний между точками маршрута. Для маршрута № 1 (Р0 - Р2 - Р6 - Р5 - Р8 - Р4 - Р7 - Р0) она приведена в таблице 2.9.
Таблица 2.9 – Матрица кратчайших расстояний
Пунк- |
|
Кратчайшие расстояния между пунктами, км |
|
||||
ты |
P0 |
P2 |
P6 |
P5 |
P8 |
P4 |
P7 |
P0 |
|
15 |
23 |
30 |
30 |
25 |
19 |
P2 |
15 |
|
2 |
10 |
13 |
19 |
7 |
P6 |
23 |
2 |
|
9 |
3 |
11 |
11 |
P5 |
30 |
10 |
9 |
|
5 |
4 |
6 |
P8 |
30 |
13 |
3 |
5 |
|
3 |
7 |
P4 |
25 |
19 |
11 |
4 |
3 |
|
12 |
P7 |
19 |
7 |
11 |
6 |
7 |
12 |
|
Сумма |
142 |
66 |
59 |
64 |
61 |
74 |
62 |
В итоговой строке таблицы 2.9 проставляют сумму расстояний в каждом столбце. Затем выбирают три начальных пункта, имеющих максимальные суммы в столбцах (пункты 0, 4 и 2). Они образуют кольцевой маршрут 0 - 4 - 2 - 0. В него включают следующий пункт с максимальной суммой в столбце – пункт 5. Чтобы определить, между какими пунктами его следует вставить, необходимо найти минимально возможное увеличение длины маршрута lij, обусловленное включением пункта 5. Величину lij находят по формуле
|
lkj = lki + li j -lkj, |
(2.1) |
где lki, |
lij, lki – расстояние между соответствующими пунктами, |
|
км; k, j – пункты, между которыми предполагается вставка; |
||
i – |
вставляемый пункт. |
|
В данном случае пункт 5 можно вставить между парами пунктов (0,4), (4,2) и (2,0). Например, для первой пары формула (2.1) будет иметь вид l0-4 = l0-5 + l5-4 - l0-4.
23
При подстановке расстояний из матрицы (таблица 2.9) получим l0-4 = 30 + 4 – 25 = 9. Для остальных двух пар l4-2 = 4 + 10 – 19 = -5; l2-0 = 10 + 30 -15 = 25. Минимальное значение ( l4-2 = -5) определяет место вставки: пункт 5 включают в маршрут между пунктами 4 и 2. Маршрут примет вид 0 - 4 - 5 - 2 - 0. Следующее по величине значение в итоговой строке матрицы соответствует пункту 7. Его можно вставить между парами пунктов (0,4), (4,5), (5,2) и (2,0). Подсчитаем изменения длины маршрута: l0-4 = = l0-7 + l7-4 - l0-4 = 19 + 12 – 25 = 6; l4-5 = 12 + 6 – 4 = 14; l5-2 = 6 + + 7 – 10 = 3; l2-0 = 7 + 19 – 15 = 11. Пункт 7 вставляют между пунктами 5 и 2. Получают маршрут 0 - 4 - 5 - 7 - 2 - 0.
На следующем этапе вставляют пункт 8. Производят аналогичный расчёт. Минимальное значение имеет l4-5 = 4. Следовательно, пункт 8 вставляют между пунктами 4 и 5 и получают маршрут 0 - 4 - 8 - 5 - 7 - 2 - 0.
В заключение вставляют пункт 6. Произведя вычисления, получают, что минимальное значение имеет l7-2 = 6. Поэтому пункт 6 вставляют между пунктами 7 и 2 и окончательно получают маршрут 0 - 4 - 8 - 5 - 7 - 6 - 2 - 0.
Аналогичным образом определяют порядок объезда пунктов на маршруте №2 (Р0 - Р1 - Р3 - Р0).
3.СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
1.Горев, А. Э. Грузовые автомобильные перевозки: учеб. пособие. – М.: Издат. центр šАкадемияŸ, 2004. – 288 с.
2.Глухов, В. В. Математические методы и модели для менеджмента / В. В. Глухов, М. Д. Медников, С. Б. Коробко. – СПб.: Лань, 2000. – 480 с.
3.Воркут, А. И. Грузовые автомобильные перевозки. – 2-е изд., перераб. и доп. – Киев: Вища школа, 1986. – 447 с.
4.Геронимус, Б. Л. Экономико-математические методы в планировании на автомобильном транспорте. – М.: Транспорт, 1977. – 160 с.
24
5.Геронимус, Б. Л. Экономико-математические методы в планировании на автомобильном транспорте / Б. Л. Геронимус,
Л.В. Царфин. – М.: Транспорт, 1988. – 192 с.
6.Ванчукевич, В. Ф. Грузовые автомобильные перевозки: учеб. пособие / В. Ф. Ванчукевич, В. Н. Седюкевич, В. С. Холупов. – Минск: Вышейшая шк., 1989. – 272 с.
7.Исследование операций в экономике / Н. Ш. Кремер, Б. А. Прутко, И. М. Тришин, М. Н. Фридман; под ред. Н. Ш. Кремера.
– М.: Банки и биржи, ЮНИТИ, 1997. – 407 с.
Составители
Алексей Юрьевич Тюрин Юлия Николаевна Тимощенко
ПОСТРОЕНИЕ МАРШРУТОВ ПЕРЕВОЗОК ГРУЗОВ КРУПНЫМИ И МЕЛКИМИ ПАРТИЯМИ
Методические указания к практическим занятиям по курсу šГрузовые перевозкиŸ для студентов специальности
190701.01 šОрганизация перевозок и управление на транспорте (автомобильный транспорт)Ÿ очной формы обучения
Рецензент А. В. Косолапов
Печатается в авторской редакции
Подписано в печать 20.11.2008.
Формат 60 84/16. Бумага офсетная. Отпечатано на ризографе. Уч.-изд. л. 1,3. Тираж 135 экз.
Заказ ГУ КузГТУ. 650000, Кемерово, ул. Весенняя, 28.
Типография ГУ КузГТУ. 650000, Кемерово, ул. Д. Бедного, 4а.