Использование передовых методов составления маршрутов перевозок грузов пищевой промышленности
Скачать PDF | Загрузок: 12
Статья в журнале
Вопросы инновационной экономики (РИНЦ, ВАК)
опубликовать статью | оформить подписку
№ 1 (11), Март 2012
Цитировать:
Тюрин А.Ю. Использование передовых методов составления маршрутов перевозок грузов пищевой промышленности // Вопросы инновационной экономики. – 2012. – Том 2. – № 1. – С. 40-47.
Эта статья проиндексирована РИНЦ, см. https://elibrary.ru/item.asp?id=17712747
Аннотация:
Рассматриваются вопросы применения метода раздельной доставки для составления маршрутов перевозок грузов пищевой промышленности. Отмечаются преимущества и недостатки использования некоторых эвристических методов для решения задач маршрутизации. На конкретном примере показывается преимущество применения метода раздельной доставки, приводящее к сокращению транспортных расходов, пробега автомобилей и повышению степени загрузки подвижного состава.
Ключевые слова: пищевая промышленность, раздельная доставка, задача маршрутизации, эвристический алгоритм, транспортные расходы
В издательстве открыта вакансия ответственного редактора научного журнала с возможностью удаленной работы
Подробнее...
Введение
Так как продукция пищевой промышленности чаще всего доставляется потребителям мелкими партиями, то эффективность доставки товаров зависит от своевременной подготовки отгрузочных партий, разработки сроков завоза продукции и маршрутизации перевозок. При этом особую трудность вызывает составление развозочных маршрутов доставки грузов, так как для больших сетей решение этой задачи точными методами приводит к значительным затратам времени.
В связи с этим рассмотрим применение эвристических методов решения задачи развоза продукции. Среди известных методов широко применяется метод Кларка-Райта [1], построенный на экономии при объединении маятниковых маршрутов в развозочные. Однако данный метод имеет ряд существенных недостатков, среди которых можно выделить нечеткий выбор транспортного средства при формировании маршрута, неправильное построение порядка объезда пунктов на маршруте, приводящее к увеличению общего пробега подвижного состава, возможность зацикливания (отсутствие конечного результата) при решении задачи на ЭВМ.
Данные недостатки можно частично устранить, используя метод сумм при решении задачи коммивояжера, перестановкой пар пунктов в предварительном маршруте.
Дальнейшим развитием метода Кларка-Райта стал эвристический способ решения задачи развозки на основе обобщенной задачи назначения, разработанный Фишером и Якумаром [2].
Рассмотрим данный алгоритм подробнее. В нем вводятся следующие обозначения: n — число пунктов сети, отправитель (склад) имеет номер n; p — число неоднородных транспортных средств различной грузоподъемности; Qk — грузоподъемность автомобиля с номером k; qi — заявка на перевозку от потребителя с номером i; ||cij||— матрица стоимости переезда между смежными пунктами транспортной сети G = (V,E).
Решение задачи маршрутизации начинается с разбивки множества пунктов на p подмножеств (зон), где в каждой зоне обслуживать потребителей будет k-й автомобиль. После этого выбирается p резидентных пунктов и подсчитывается коэффициент dik. После вычисления коэффициентов dik решается обобщенная задача назначения и формируется p предварительных замкнутых маршрутов перевозки. В заключение решается задача коммивояжера для каждого маршрута, и формируются окончательные маршруты доставки мелкопартионных грузов потребителям.
Существенный недостаток метода Фишера и Якумара состоит в том, что резидентные пункты в процессе действия метода не могут быть передвинуты, и поэтому суммарная длина всех маршрутов является завышенной.
Чтобы ликвидировать этот недостаток был предложен эвристический алгоритм Коскосидиса и Пауэлла [3], в котором выбор начального пункта для маршрута может изменяться в процессе действия алгоритма.
В данном алгоритме не решается обобщенная задача назначения, а вычисляются потери в связи с включением пары пунктов в маршрут. После того как предварительно сформированы все маршруты, возможен обмен пунктами между двумя маршрутами, который не превышает грузоподъемности автомобиля и снижает общие издержки (пробег) подвижного состава. Дополнительно в алгоритме может быть использована возможность включения пар пунктов в уже сформированные маршруты и пересмотр маршрутов с целью снижения критерия оптимальности (расстояния, стоимости проезда и т.д.)
В рассмотренных выше алгоритмах предполагалась доставка всей партии груза потребителю за один рейс, в связи с чем на некоторых маршрутах наблюдалась неоптимальная загрузка подвижного состава и излишний пробег автомобилей, приводящий к повышенным транспортным расходам по доставке продукции.
Сократить пробег и, соответственно, снизить транспортные расходы по поставке продукции можно с использованием метода раздельной (дробной) доставки [4]. При этом методе партия поставки одному потребителю делится на несколько завозов, и за счет этого наблюдается лучшая «упаковка» продукцией транспортного средства, сокращаются пробег и транспортные расходы.
Решение задачи. Рассмотрим применение этого метода на следующем примере. Осуществляется обслуживание одного кластера (группы) потребителей хлебопекарной промышленности, состоящей из 15 пунктов. Продукция доставляется в картонных ящиках. Для доставки используются ящики различной формы и массы. Средняя масса одного ящика составляет8 кг. Перевозка продукции осуществляется автомобилями различной грузоподъемности (вместимости), максимальная загрузка которых в пересчете на картонные ящики составляет 150, 170 и 200 ящиков (физических единиц).
Для уточнения эффекта от раздельной доставки были смоделированы различные ситуации обслуживания потребителей, различающиеся объемами поставок продукции. Исходные данные представлены в табл. 1.
Таблица 1
Исходные данные для маршрутизации методом раздельной доставки
Варианты поставок
|
Потребители
| ||||||||||||||||||||||||||||
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
| |||||||||||||||
Объем поставки в ящиках
| |||||||||||||||||||||||||||||
Автомобиль с максимальной загрузкой в 150 ящиков
| |||||||||||||||||||||||||||||
Вариант 1
|
87
|
115
|
90
|
100
|
57
|
36
|
73
|
60
|
100
|
90
|
54
|
63
|
55
|
77
|
75
| ||||||||||||||
Вариант 2
|
78
|
7
|
31
|
37
|
106
|
40
|
77
|
84
|
130
|
68
|
14
|
45
|
96
|
35
|
120
| ||||||||||||||
Автомобиль с максимальной загрузкой в 170 ящиков
| |||||||||||||||||||||||||||||
Вариант 1
|
87
|
22
|
20
|
86
|
12
|
14
|
73
|
21
|
20
|
90
|
26
|
23
|
32
|
77
|
98
| ||||||||||||||
Вариант 2
|
87
|
44
|
120
|
86
|
57
|
36
|
73
|
60
|
20
|
90
|
54
|
33
|
32
|
77
|
98
| ||||||||||||||
Вариант 3
|
87
|
115
|
90
|
86
|
57
|
36
|
73
|
60
|
100
|
90
|
54
|
63
|
55
|
77
|
75
| ||||||||||||||
Вариант 4
|
87
|
115
|
90
|
100
|
57
|
36
|
73
|
60
|
100
|
90
|
54
|
63
|
55
|
77
|
75
| ||||||||||||||
Автомобиль с максимальной загрузкой в 200 ящиков
| |||||||||||||||||||||||||||||
Вариант 1
|
87
|
22
|
20
|
86
|
12
|
14
|
73
|
21
|
20
|
90
|
26
|
23
|
32
|
77
|
98
| ||||||||||||||
Таблица 2
Сравнение методов Кларка-Райта и раздельной доставки
Варианты
|
Комплексный метод Кларка-Райта
|
Метод раздельной
доставки |
Выигрыш, %
|
Общий пробег автомобилей по маршрутам, км
| |||
Автомобиль с максимальной загрузкой в 150 ящиков
| |||
Вариант 1
|
174,29
|
154,82
|
11,17%
|
Вариант 2
|
123,29
|
130,89
|
-6,17%
|
Автомобиль с максимальной загрузкой в 170 ящиков
| |||
Вариант 1
|
103,93
|
90,51
|
12,91%
|
Вариант 2
|
120,04
|
112,76
|
6,07%
|
Вариант 3
|
157,44
|
131,20
|
16,66%
|
Вариант 4
|
161,37
|
148,84
|
7,76%
|
Автомобиль с максимальной загрузкой в 200 ящиков
| |||
Вариант 1
|
87,28
|
81,77
|
6,31%
|
Результаты, приведенные в табл. 2, показывают неоспоримое превосходство применения метода раздельной доставки при проектировании маршрутов, кроме 2 варианта при использовании автомобиля с загрузкой в 150 ящиков. Выигрыш от сокращения пробега автомобилей изменяется от 6% до 13% и в среднем по всем вариантам с учетом отрицательного эффекта составляет примерно 7%.
Таким образом, применение метода раздельной доставки улучшает показатели транспортного обслуживания потребителей по пробегу автомобилей и расходам по доставке при сохранении объемов поставок в течение отведенного периода завоза продукции.
При проектировании маршрутов перевозок методом раздельной доставки изменяется конфигурация объезда пунктов. Пример порядка объезда пунктов для комплексного метода Кларка-Райта и метода раздельной доставки для 3 варианта при использовании автомобиля с загрузкой в 170 ящиков отражен на рисунках 1 и 2 соответственно.
Как видно из приведенных рисунков, во втором случае при применении метода раздельной доставки коренным образом меняются маршруты перевозок за счет перераспределения поставок между маршрутами и за счет этого сокращается пробег автомобилей и повышается степень загрузки подвижного состава.
Рис.1. Конфигурация маршрутов, полученных комплексным методом Кларка-Райта для 3 варианта при использовании автомобиля с загрузкой в 170 ящиков
Рис. 2. Конфигурация маршрутов, полученных методом раздельной доставки для 3 варианта при использовании автомобиля с загрузкой в 170 ящиков
Рассмотрим другой пример порядка объезда пунктов для комплексного метода Кларка-Райта и метода раздельной доставки для 2 варианта при использовании автомобиля с загрузкой в 170 ящиков. Полученные маршруты отражены на рисунках 3 и 4 соответственно.
Рис.3. Конфигурация маршрутов, полученных комплексным методом Кларка-Райта для 2 варианта при использовании автомобиля с загрузкой в 170 ящиков
Рис. 4. Конфигурация маршрутов, полученных методом раздельной доставки для 2 варианта при использовании автомобиля с загрузкой в 170 ящиков
На рис. 4 также изменяются маршруты доставки по сравнению с рис. 3. Дополнительно происходит деление партии поставки в 10-й пункт на 2 завоза, т.е. пункт 10 обслуживается двумя маршрутами: 0-11-12-10-0 и 0-1-5-10-0. За счет таких действий сокращается пробег автомобилей и повышается степень загрузки подвижного состава, но необходимо учесть в графике работы автомобилей эти два завоза в пункт 10 и согласовать время приема продукции с потребителем 10.
Выводы
Применение метода раздельной доставки позволяет сократить транспортные расходы по доставке товаров потребителям, улучшить загрузку автомобилей, и, как следствие, снизить средний уровень запасов у потребителей за счет частных и мелких поставок заказанной продукции. Использование частых поставок уменьшает стоимость разовой покупки продукции и, при определенных условиях, может привлечь дополнительных потребителей и расширить рынок сбыта. Если сбытовая сеть довольно сложная, включает оптовых и мелкооптовых покупателей, распределительные склады и т.д., которые управляются поставщиком (предприятием), то применение частых поставок снизит уровень запасов в каждом звене сети и, следовательно, уменьшит расходы на распределительную логистику.
Источники:
2. Fisher M., Jaikumar R. A generalized assignment heuristic for vehicle routine // Net-works. – 1981. – 11, № 1. – P. 109-124.
3. Koskosidis Y. A., Powell W.B. Clustering algorithms for consolidation of customer orders into vehicle shipments // Transpn. Res-B. – 1992. – 26B, № 5. – P. 365-379.
4. Dror M., Trudeau P. Savings by split delivery routing // Trans. Sci. – 1989. – 23. – P. 141-145.
Страница обновлена: 22.01.2024 в 19:07:06