Маршрутизация массовых крупнопартионных перевозок

Тема 6. Маршрутизация перевозок

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

Мелкопартионные перевозки (развозочные маршруты).

Маршрутизация массовых крупнопартионных перевозок

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

В первую очередь задача формулируется в общем виде. Определяются этапы решения задачи. Для решения задачи маршрутизации массовых крупнопартионных грузов – это:

· отбор грузов, перевозимых одной моделью автомобилей;

· анализ возможности совместной перевозки грузов;

· составление исходной матрицы;

· определение оптимального возврата порожняка;

· увязка груженых и порожних ездок;

· составление схем маршрутов и транспортной сети.

Возможно использование метода Квилна для составления кратчайшей связывающей сети.

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

2. Затем выделяются группы грузов, перевозимых универсальными автомобилями. Если одной моделью автомобиля могут быть перевезены группы четырех и боле наименований, то для их маршрутизации используются математические методы. Если грузы не удается сгруппировать по признаку однородности способа перевозки данной моделью автомобиля, то составляются маршруты без применения математических методов, но с учетом возможностей загрузки автомобилей в обратном направлении. На схеме маршрутов указываются те же данные, что и для маршрутов, обслуживаемых специализированным составом.

Маршрутизация массовых крупнопартионных перевозок

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

Пусть груз, сосредоточенный в пунктах А₁, А₂, …, А_i, …, А_m в количествах соответственно а₁, а₂, …, а_i, …, a_m, необходимо доставить в пункты B₁, B₂, …,B_j, …, B_n в количествах b₁, b₂, …, b_j, …, b_n тонн. Объем перевозок из i-го пункта отправления в j-й пункт назначения составляет P_ij тонн.

Не решая сначала задачи выбора и распределения подвижного состава, будем полагать, что для перевозок используются условные однотонные (q_нg_с=1) автомобили.

При выполнении перевозок в пункт B_j доставляется

тонн груза и соответственно прибывает такое же количество условных автомобилей, которые после разгрузки подаются в пункты погрузки A_i. Так как из пунктов A_i нужно вывезти

тонн груза, то для пунктов А₁, А₂, …, А_m необходимо осуществить соответственно а₁, а₂, …, a_m подач порожних автомобилей.

Расстояния (l_ij=l_ji) от каждого потребителя B_j до каждого поставщика А_i известны.

Требуется определить количество x_ji подач порожних условных однотонных автомобилей от j-го пункта разгрузки в i-й пункт погрузки, с тем чтобы общий пробег автомобилей был минимальным. Иными словами, задача сводится к нахождению оптимального плана возврата (подач) порожних автомобилей.

Порожний пробег при выполнении из j-го в i-й пункт подач условных однотипных автомобилей равен l_jix_ji. Тогда их суммарный пробег

Поскольку количество ездок равно x_ji/q_нg_c, то фактический пробег автомобилей с заданной грузоподъемностью q_н равен

Теперь можно дать математическую формулировку задач. Требуется определить совокупность величин x_ji³0 (план возврата порожних автомобилей), удовлетворяющих условиям

и минимизирующих функцию

Поскольку количество завозимых грузов равно количеству вывозимых, то справедливо равенство

Сформулированная задача представляет собой классическую транспортную задачу линейного программирования.

Составление рациональных маршрутов при перевозках массовых грузов

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

Рис. 1.Схема дорожной сети района перевозок

Таблица 1.1

Шахматная таблица грузопотоков, тыс.т

Пункы вывоза грузов	Пункты завоза грузов					Итого получено
Пункы вывоза грузов	А	Б	В	Г	Д	Итого получено
А	Х	Нефть 420	Зерно 320	Мука 270	Сено пресо-ванное 160	1170
Б	Патока 69	Х	Молоко 205	Обору-дование 180	Рыба вяленая 95	549
В	Одежда 79	Контейнер груженые 210	Х	Карто-фель 250	Игрушки 46	585
Г	Хлеб 99	Молоч-ные про-дукты 125	Книги в конт. 89	Х	Битум 68	381
Д	Бумага 105	Стираль-ные машины 190	Панели строи-тельные 165	Консер-вы в ящиках 75	Х	535
Всего отправ-лено	352	945	779	775	369	3220

Примечание: все грузы приведены к 1-му классу.

Построение маршрутов проводится в несколько этапов.

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

Таблица 1.2

Промежуточная матрица грузопотоков

	А	Б	В	Г	Д
А			320		160
Б	69			180	95
В	79			250	46
Д	105	190		75

Специализированным подвижным составом перевозятся:

нефть – 420 тыс.т, мука – 270 тыс.т, молоко – 205 тыс.т, контейнеры груженые 210 тыс.т, хлеб – 99 тыс.т, молочные продукты – 125 тыс.т, битум – 68 тыс.т, панели строительные – 165 тыс.т, книги в контейнерах – 89 тыс.т.

На этих маршрутах b=0,5

2 этап: из матрицы исключаются грузы, перевозимые во встречных направлениях, на этих маршрутах b=1,0.

Маршруты: с b=1,0, АВ-ВА: Q_год=79´2=158 тыс.т,

АД-ДА: Q_год=105х2=210 тыс.т,

БД-ДБ: Q_год=95х2=190 тыс.т.

После всех действий получаем фактический план перевозок грузов от поставщиков потребителям. Этот план изменениям не подлежит.

Результирующая матрица имеет следующий вид (табл.1.3).

Таблица 1.3

Результирующая матрица

	А	Б	В	Г	Д	Всего
А			241		55	296
Б	69			180		249
В				250	46	296
Д		95		29		124
Итого	69	95	241	459	101	965

3 этап: производится рациональное распределение порожних автомобилей по пунктам района перевозок.

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

Находим оптимальный план возврата порожних автомобилей. Производим распределение “груза” (загрузку клеток) методом двойного предпочтения. Это означает, что первыми будут заполняться клетки, имеющие наименьшее расстояние перевозки (цифры в правом верхнем углу каждой клетки). Заполненных клеток должно быть n+m-1.

Таблица 1.4

Первоначальное закрепление порожних автомобилей

	А		Б		В		Г		Д		Итого	U_i
А	69	0	15	15	5	25	227	35	25	25	296	0

Б	-15	15	95	0	-10	10	154	20	10	30	249	-15

В	-5	25	10	10	241	0	55	30	20	40	296	-5


Д	-25	25	-10	30	-20	40	23	10	101	0	124	-25

Всего	69		95		241		459		101		965
V_j	0		15		5		35		25

Проведя первоначальное распределение, проверяем его на оптимальность методом потенциалов. В каждой свободной клетке оптимального плана должно быть выполнено условие U_i+V_j£C_ij ,

где U_i – потенциал столбца;

V_j – потенциал строки;

С_ij – расстояние между пунктами, проставленное в клетке.

Для всех загруженных клеток должно быть выполнено условие

U_i+V_j=C_ij

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

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

4 этап: приступаем к построению рациональных маршрутов. Используем метод “совмещенных матриц”.

Таблица 1.5

План закрепления порожних автомобилей

	А	Б	В	Г	Д
А	69			227
Б		95		154
В			241	55
Г
Д				23	101

На полученную матрицу (табл. 1.5) накладывается план перевозок грузов по району. Наличие грузов показывается цифрами в кружках. Совмещенная матрица наличия грузов и порожних автомобилей выглядит следующим образом (табл. 1.6).

Таблица 1.6

Совмещенная матрица

	А	Б	В	Г	Д
А	69		241	227	55
Б	69	95		154 180
В			241	55 250	46
Г
Д		95		23 29	101

Построение рациональных маршрутов начинается с построения простых маятниковых маршрутов с b=0,5. Такие маршруты формируются в пунктах, где имеется груз и порожние автомобили (клетки, в которых есть цифры в кружочках и без них). Объем перевозок на таких маршрутах определяется наименьшим из двух чисел. Получаем следующие маршруты:

1) БГ-ГБ: Q = 154 тыс.т, l_ег= 20 км, l^е_общ= 40 км, b = 0,5

2) ДГ-ГД: Q = 23 тыс.т, l_ег= 10 км, l^е_общ= 20 км, b = 0,5

3) ВГ-ГВ: Q = 55 тыс.т, l_ег= 30 км, l^е_общ= 60 км, b = 0,5

Во включенных в маршрут клетках вычитается объем перевозок и цифры уменьшаются на эту величину.

Переходим к построению более сложных маятниковых маршрутов – с обратным не полностью груженым пробегом. Для этого строятся контуры маршрутов, при этом должны соблюдаться следующие правила:

1) контуры строятся только прямыми линиями, пересекающимися под прямым углом;

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

3) изменение направления прямых линий происходит только в загруженной клетке (клетка с цифрой).

Таблица 1.7

Схема построения маршрута 4