Файл: А.Ю. Тюрин Методы построения маршрутов перевозок. Методические указания к практическим занятиям.pdf

10

11

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

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

В нашем случае такому контуру соответствует маршрут

А1 В1 — В1 А2 — А2 В4 — В4 А4 — А4 В7 — В7 А1.

На нем каждому потребителю должно быть завезено 13 т грузов, так как минимальное значение загрузок по вершинам контура составляет именно 13. Уменьшив цифры в клетках, составляющих выбранный маршрут, на 13 единиц, получим данные для выбора второго кольцевого маршрута. Процесс составления маршрутов считается законченным, когда в матрице не остается ни одной загрузки.

Для каждого маршрута необходимо определить коэффициент использования пробега. Если на кольцевом маршруте коэффициент использования пробега β = 0,5, то такой маршрут не целесообразен, соответствующие перевозки лучше осуществлять на маятниковых маршрутах.

12

13

А1 В1 — В1 А2 — А2 В4 — В4 А4 — А4 В7 — В7 А1 - 13 т.

14

Практическое занятие №2 Маршрутизация мелкопартионных перевозок (метод Кларка-Райта)

Цель: определить рациональные маршруты при доставке грузов мелкими партиями.

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

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

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

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

15

объединения уменьшится значение суммарного показателя, либо нет соответствующего для объединения автомобиля).

Рассмотрим решение данной задачи на примере: имеется 8 потребителей груза, потребности завоза которых указаны в первом столбце табл. 2.1. Выделено пять автомобилей грузоподъемностью 4,5 т (Луаз890Б) и три автомобиля грузоподъемностью 1,75 т (ГЗСА-3702).

В каждом столбце Рi (табл. 2.1) указывают расстояние от i-го пунк-

та до любого другого (Рi+1, Рi+2...). Так как матрица кратчайших расстояний симметрична, то достаточно одной половины матрицы.

Таблица 2.1

Расстояния между пунктами

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

Таблица 2.2

Выигрыши при объединении пунктов

Расчет выигрыша в расстоянии рассмотрим на примере элемента, стоящего в столбце Р4 и строке Р8. Этот элемент соответствует объединению маршрутов Р0 - Р4 - Р0 и Р0 - Р8 - Р0, в результате которого получается маршрут Р0 - Р4 - Р8 - Р0 .

16

В новом маршруте вместо расстояния от пункта Р4 к пункту Р0 и от пункта Р0 к пункту Р8 (25+30=55 км) используют расстояние от пункта Р4 к пункту Р8 (3 км). Следовательно, выигрыш от объединения этих маршрутов в один составляет 55-3=52 км, что и указано в рассматриваемой клетке.

Поскольку для дальнейших расчетов необходимо знать только величины выигрышей, представляют их отдельно (см. табл. 2.2). Кроме того, присоединяют к матрице выигрышей отдельный столбец индикаторов (I) пунктов Рi. Величины, стоящие в этом столбце, принимают значения 0; 1 или 2. Индикатор строки Рi показывает, является пункт внутренним (0), первым или последним (1) в некотором развозочном маршруте, или он включается в маятниковый маршрут (2), т.е. маршрут

вида Р0 - Рi - Р0.

Из табл. 2.2 видно, что наибольший выигрыш (55 км) достигается при преобразовании (объединении) маятниковых маршрутов Р0- Р5 - Р0 и Р0 - Р8 - Р0 в развозочный Р0 - Р5 - Р8 - Р0 (табл. 2.3). Для развозочного маршрута Р0 - Р5 - Р8 - Р0 требуется автомобиль грузоподъемностью 1,91 т и более (1+0,91=1,91 т). Такой автомобиль имеется, поэтому объединение возможно.

Таблица 2.3

Выигрыши при объединении пунктов

После объединения в соответствующих строках меняют элементы первого и второго столбцов. В первых клетках обеих строк записывают число 1,91 (загрузка автомобиля на маршруте Р0- Р5 - Р8 - Р0). Индикаторы строк Р5 и Р8 примут значение 1 (вместо 2). Эти изменения в нашем примере вносят в исходную матрицу. Кроме того, необходимо следить за изменением числа свободных и занятых автомобилей различной грузоподъемности.

На следующем этапе объединяют в маршрут Р0 - Р5 - Р8 - Р4 - Р0 маршруты Р0 - Р4 - Р0 и Р0 - Р5 - Р8 - Р0. Это объединение дает наиболь-

17

ший теперь выигрыш - 52 км (табл. 2.4). При этом вместо двух автомобилей используют один грузоподъемностью 4,5 т (0,96+1,91=2,87 т).

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

Таблица 2.4

Выигрыши при объединении пунктов

Теперь максимальному выигрышу (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

Выигрыши при объединении пунктов

На следующих этапах объединяют маршруты Р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