Оптимизация мелкопартионных перевозок грузов

Среди задач планирования ГАП особо выделяются задачи плани­рования мелкопартионных перевозок, когда размер отправляемой или получаемой партии груза существенно меньше грузовмести­мости используемых АТС.

При мелкопартионных перевозках ПС, загрузившись у одного отправителя грузов, должен развезти груз нескольким получате­лям, разгружая у каждого из них определенное количество груза. В этом случае имеет место развозочный маршрут. Если необходимо объехать несколько пунктов и в каждом из них загрузить некоторое количество груза, а затем завезти его потребителю, то такой мар­шрут называется сборочным. Если автомобиль одновременно раз­возит и собирает мелкие партии груза, маршрут называется развозочно-сборочным.

Как правило, мелкопартионные перевозки выполняются при обслуживании организаций торговли и бытового обслуживания. На этих перевозках занято около 50 % грузового парка автомоби­лей, но на их долю приходится всего около 2 % грузооборота. Для мелкопартионных перевозок характерны следующие особеннос­ти, которые необходимо учитывать при их планировании:

время выполнения погрузочно-разгрузочных работ существен­но превышает время движения;

время движения зависит от загруженности транспортных маги­стралей, по которым проходит маршрут движения;

существенное значение имеет своевременность и гарантированность доставки груза;

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

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

Задачи планирования мелкопартионных перевозок относятся к классу задач дискретной оптимизации (в прикладной математике они называются конечными оптимизационными задачами, т.е. такими задачами, в которых конечность множества допустимых решений позволяет считать их всегда разрешимыми, так как мож­но перебрать все решения и выбрать лучшее из них). Однако пол­ный перебор вариантов часто нереален из-за слишком большого множества допустимых решений. Например, задача объезда деся­ти пунктов на маршруте имеет 3 628 800 вариантов решения. Вы бор методов решения задач маршрутизации мелкопартионных перевозок представлен на рис. 8.8.

Среди методов решения задач маршрутизации мелкопартионных перевозок, дающих точное решение, наибольшее распространение получил метод «ветвей и границ». Общая идея метода до статочно проста. Вначале для всего множества допустимых решений определяется нижняя граница, которая представляет число, меньше которого значение целевой функции быть не может. Решение задачи заключается в постепенном разбиении множества допустимых решений на все меньшие и меньшие подмножества, для каждого из которых определяется нижняя граница и выбирается подмножество с наименьшим ее значением. Выбранное мно­жество опять разбивается на подмножества, выбирается из одно с наименьшей границей и т. д. В итоге должно быть получено подмножество, содержащее одно единственное решение, граница которого совпадает со значением целевой функции.

 

Рис. 8.8. Методы маршрутизации мелкопартионных перевозок

Метод функций «выгоды» был предложен английскими специа­листами Кларком и Райтом для решения задачи автомобильных мелкопартионных перевозок с одним отправителем или получа­телем. Этот метод получил название метода Кларка—Райта. Метод основан на понятии эффекта (выгоды), который получается от объединения двух маятниковых маршрутов в один кольцевой.

Пусть есть два маятниковых маршрута 0 — i —0 и 0 — j —0. Каж­дый из них начинается и заканчивается в пункте 0, который явля­ется пунктом-отправителем или пунктом-получателем (будем на­зывать этот пункт центральным пунктом).

Эффект от объединения этих двух маршрутов в один равен

(8.1)

где lio — расстояние от центрального пункта до пункта i; lio — расстояние от пункта у до центрального пункта; 1ij— расстоя­ние между пунктами i и j.

Действительно, в результате объединения двух маршрутов от­падает необходимость возврата с i -го маршрута на центральный пункт и подачи автомобиля с центрального пункта на j -й марш­рут (т. е. из пробега автомобиля вычитаются расстояния lio и 1io). Но вместо этого появляется пробег от последней точки i -го маршрута до первой точки j -го маршрута (т. е. к пробегу автомобиля добав­ляется расстояние 1ij).

Таким образом, некоторые маршруты можно объединять, в со­ответствии с величиной «выгоды», в более крупные маршруты. Если при этом для возможных объединений использовать марш­руты, величина «выгоды» на которых имеет наибольшее значе­ние, то можно рассчитывать, что полученное решение будет близко к оптимальному.

Решение заканчивается, когда дальнейшее объединение мар­шрутов станет невозможно. Это может быть по двум причинам: либо не осталось ни одного положительного значения выгоды (т. е. объединять невыгодно), либо при объединении превышается гру­зовместимость автомобиля.

Рассмотрим следующий пример. Пусть необходимо развезти с центрального пункта продукцию нескольким потребителям, забрать и доставить на центральный склад возвратную тару от потребителей. Для обслуживания маршрутов используется два автомобиля грузо­вместимостью 240 и 160 единиц груза. Количество ввозимого и вывозимого груза для каждого потребителя представлено в табл. 8.11 (первый и второй столбцы). В остальных столбцах таблицы даны кратчайшие расстояния между пунктами.

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

Посчитаем значение эффекта от объединения двух маршрутов в один. Например, подсчитаем эффект от объединения 3-го и 5-го маршрутов.

 

Таблица 8.11

Исходные данные для построения маршрутов методом Кларка —Райта

 

 

Ввоз груза, ед.	Вывоз груза, ед.	ГОП	ГПП
ПО
			.8
60 •

 

Расстояние от 0-го пункта до 3-го пункта равно 8. Ра стояние от 0-го пункта до 5-го пункта равно 10. Расстояние меж пунктом 3 и пунктом 5 равно 5. Таким образом, эффект, получен ный от объединения маршрутов 0 —3—0 и 0—5 —0, будет равен (см. (8.1))

Полученное значение эффекта от объединения занесем в таб лицу (табл. 8.12). Рассчитаем эффекты от объединения всех пар маршрутов, результаты занесем в табл. 8.12.

Добавим в таблицу еще один столбец — столбец признака. При знак может принимать одно из трех значений:

2 — пункт включен в маятниковый маршрут вида 0— i —0;

1 — это значение признака говорит о том, что данный пункт является первым или последним пунктом кольцевого маршрута (при этом пункт 0 в развозочно-сборочном маршруте не учитывается);

О — данный пункт является внутренним пунктом кольцевого маршрута и его нельзя использовать для объединения маршрутов.

Из табл. 8.12 видно, что наибольший эффект, равный 27, получается при объединении маршрутов 0—4—О и О—6—О и маршрутов 0—4—0 и 0—9—0. Объединим маршруты 0—4—0 и 0—6—0 Суммарное количество ввозимого груза для объединенного маршрута равно 170 (75 + 95), а суммарное количество вывозимого груза будет равно 75 (45 + 30). Маршрут может быть выполнен автомобилем грузоподъемностью 240 единиц.

 

Таблица 8.12

Матрица выигрышей

Ввоз, ед.	Вывоз, ед.	Признак	ГПП
ПО
								б

После объединения маршрутов в ячейках первого столбца 4-й и 6-й строк будет стоять суммарное количество ввозимого груза, т.е. число 170, а второго столбца — суммарное количество выво­зимого груза, т.е. число 75.

Значение признака для этих строк равно 1, т.е. пункты 4 и 6 являются первым и последним пунктом на маршруте (табл. 8.13). В графу «Маршрут» для пунктов 4 и 6 запишем цифру 1 (это озна­чает, что эти пункты входят в первый кольцевой маршрут).

Таблица 8.13