Оптимизация мелкопартионных перевозок грузов (2008, 288с.)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

….

где … — расстояние от центрального пункта до пункта …; … — расстояние от пункта … до центрального пункта; …. — расстояние между пунктами … и ….

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

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

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

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

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

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

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

….

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

Таблица 8.12 - Матрица выигрышей

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

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

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

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

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

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

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

Таблица 8.13 - Матрица выигрышей при включении в маршрут двух пунктов

На следующем шаге рассматриваем объединение маршрутов 0 —4 —6 —0 и 0—9—0, так как величина соответствующей им выгоды является наибольшей. Для объединенного маршрута количество ввозимого груза будет равно 230 (170 + 60), а количество вывозимого груза составит 85 (75 + 10) единиц. Для выполнения маршрута 0 — 9 — 4 — 6 — 0 будет достаточно автомобиля грузоподъемностью 240 единиц. Запишем суммарное количество ввозимого и вывозимого груза в табл. 8.14.

Таблица 8.14 - Матрица выигрышей при включении в маршрут трех пунктов

Пункт 4 становится внутренним пунктом маршрута, и значение признака для этого пункта устанавливается равным 0. Соответствующие этому пункту строка и столбец вычеркиваются и далее не рассматриваются. Пункты 6 и 9 — начальный и конечный пункты маршрута, значение признака для этих пунктов равно 1.

Значение следующей наибольшей выгоды равно 25; это эффект, который получается при объединении маршрутов 0 — 7 — 0 и 0 — 8 — 0. Суммарное количество ввозимого груза для этого объединенного маршрута составит 130 единиц, а суммарное количество вывозимого груза — 30 единиц. Маршрут может быть выполнен на автомобиле грузоподъемностью 160 единиц, это второй маршрут. Заносим данные в табл. 8.15. Значение признака для этих пунктов становится равным 1.

Таблица 8.15 - Матрица выигрышей при составлении двух маршрутов

Эффект от объединения пунктов 6 и 9 в маршрутах равен 24, это следующая наибольшая выгода в таблице. Но эти пункты уже входят в один и тот же маршрут, поэтому полученную выгоду рассматривать не будем.

Дальнейшие вычисления будут заноситься в табл. 8.15. На следующем шаге видно, что наибольший эффект, равный 23, получается при объединении пунктов 6 и 7 или пунктов 7 и 9. Так как пункты 6 и 9 уже входят в один объединенный маршрут, можно на этом шаге просто рассмотреть возможность объединения маршрутов 0-6-4-9-0 и 0-7-8-0.

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

Следующий по убыванию эффект равен 22, он может быть получен при объединении пунктов 6 и 8 или пунктов 8 и 9, но это также означает, что необходимо объединить маршруты 0 — 6 — 4 — 9 — 0 и 0 — 7 — 8 — 0, а это сделать невозможно. Можно заметить, что суммарное количество ввозимого груза для маршрута 0 — 6 — 4 — 9 — 0 составляет 230 единиц. Так как максимальная грузовместимость автомобиля составляет 240 единиц и больше нет пунктов с объемом ввозимого груза менее чем 10 единиц, то рассматривать любые варианты объединения маршрута 0 — 6 — 4 — 9 — 0 с другими маршрутами не имеет смысла. Поэтому можно исключить из рассмотрения сроки и столбцы, соответствующие пунктам 4, 6 и 9.

Значение следующей наибольшей выгоды равно 20; это эффект, который получается при объединении маршрутов 0 — 5 — 0 и 0 — 8 — 7 — 0. Суммарное количество ввозимого груза для этого объединенного маршрута 0 — 7 — 8 — 5 — 0 составит 210 единиц, а суммарное количество вывозимого груза — 50 единиц. Маршрут может быть выполнен на автомобиле грузоподъемностью 240 единиц, поэтому включаем пункт 5 во второй маршрут.

Заносим эти данные в табл. 8.16. Значение признака для пунктов 5 и 7 становится равным 1. Пункт 8 является внутренним пунктом маршрута, и значение признака для него равно 0. Соответствующие этому пункту строка и столбец исключаются из рассмотрения.

Таблица 8.16 - Матрица выигрышей после составления маршрутов

Так как максимальная грузовместимость автомобиля составляет 240 единиц и больше нет пунктов с объемом ввозимого груза менее чем 30 единиц, то можно исключить из рассмотрения любые варианты объединения маршрута 0—7—8—5—0 с другими маршрутами.

Из оставшихся для рассмотрения вариантов максимальный эффект, равный 8, может быть получен при объединении маятниковых маршрутов 0 — 2 — 0 и 0 — 3 — 0. Суммарное количество ввозимого груза при этом составит 140 единиц, а вывозимого груза — 80 единиц. Организуем маршрут 3 и для его выполнения выбираем автомобиль грузовместимостью 160 единиц.

Возможный последний вариант объединения маршрутов 0 — 2 — 3 — 0 и 0—1 — 0 может дать эффект, равный 6. Но суммарное количество ввозимого груза при таком объединении составит 250 единиц. Так как автомобиля соответствующей грузовместимости нет, от этого варианта придется отказаться.

Таким образом, остается последний маятниковый маршрут 0—1 — 0 — маршрут 4. На этом построение маршрутов методом Кларка —Райта закончено.

Получены следующие результаты. Для выполнения развозочно-сборочных маршрутов согласно заданию необходимо:

- два автомобиля грузовместимостью 240 единиц для выполнения маршрутов 1: 0 — 6 — 4 — 9 — 0 (загрузка автомобиля при ввозе 230 единиц, а при вывозе 85 единиц) — и 2: 0 — 7 — 8 — 5 — 0 (загрузка при ввозе 210 единиц, при вывозе 50 единиц);

- два автомобиля грузовместимостью 160 единиц для выполнения маршрутов 3: 0 — 2 — 3 — 0 (загрузка при ввозе 140 единиц, при вывозе 80 единиц) — и 4: 0— 1 — 0 (загрузка при ввозе 110 единиц, при вывозе 25 единиц).

Пробег по объединенным маршрутам составляет 54 км (маршрут 1), 31 км (маршрут 2), 16 км (маршрут 3), 20 км (маршрут 4).

Таким образом, суммарный пробег по объединенным кольцевым маршрутам равен 121 км; суммарный пробег по маятниковым маршрутам равен 228 км. Пробег автомобилей сократился на 107 км.

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

Источник: Грузовые автомобильные перевозки: Учеб. пособие для студ. высш. учеб. заведений / А. Э. Горев. — 5-е изд., испр. — М.: Издательский центр «Академия», 2008. — С. 209-217 (288 с.)