Прогнозирование перевозок грузов

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

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

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

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

Транспортная сеть состоит из пунктов А₁,А₂...А_i и дорог её соединяющих. Длины участков между каждой парой пунктов известны и равны l_ij. Из начального пункта в конечный можно попасть по множеству маршрутов, требуется найти путь наименьшей протяжённости.

Рассмотрим процедуру вычислений, определив кратчайшее расстояние от пункта А₁ до всех остальных по сети дорог, представленных на рисунке 5.

Рис. 5. Схема транспортной сети

Построив модель транспортной сети, замеряем расстояния между ближайшими (соседними) пунктами. Составим матрицу (табл.15)

Таблица 15

Матрица условий

(исходный вариант), заполняя расстояния между соседними пунктами. При дальнейших расчётах пользуемся следующим правилом. Каждому пункту A_j соответствует некоторое число V_j, характеризующее расстояние от пункта A_j до пункта А_j.

Приступаем к нахождению индексов, используя правила

V_j = U_i; V_j= U_i+l_ij.

1. Принимаем индекс U₁=V₁=0.

2. По правилу находим через А₁А₂, A₁A₄ и А₁А₆ V₂=0+12=12, V₄=0+4=4, V₆=0+8=8 и V_j= U_i. U₂=V₂=12, U₄=V₄=4, U₆=V₆=8 и заносим в таблицу 16.

3. Находим V₃ через А₂А₃ с известным U₂:

V₃=U₂+1₂₃=12+6=18 и V₃=U₃=18.

4. V₅ =min (по столбцу) =11, V₅ =U₅ =11.

5. V₇=min (по столбцу) =16, V₇=U₇ =16.

6. V₈=min (по столбцу) =A₆A_S =15, V₈=U₈=15.

Проверяем заполненные клетки таблицы на оптимальность по критерию l_{ij j} – U_i.

В таблице 15 1₄₂ <V₂ – U₄ 7<12–4=8, критерий не соблюдается, поэтому решение не оптимально.

Рассчитываем новый индекс V₂ по вышеуказанному критерию V_j = U_i+l_ij=4+7=11.

Получаем U₂=V₂=11.

Получаем новую таблицу (со значениями V₂ U₂ в кружках) и проверяем её на оптимальность. Она не оптимальна, так как l_{53 3} -U₅ 6<18-11.

Определяем новый индекс V₃=U₅+l₅₃ =11+6=17, U₃=V₃=17.

Проверка таблицы 15 (с индексом кружочек и квадратик) показывает, что решение оптимально.

Следовательно, кратчайшее расстояние от точки А₁ задано числами V₂...V₈, т. е. А₁ - А₂=11 км, A₁ - А₃=17 км........А₁ - А₈=15 км.

Таблица (оптимальная) даёт также последовательность прохождения промежуточных пунктов, например из А₁ в А₇, и определяется следующим образом:

1. В столбце, соответствующему конечному пункту А₇ отыскиваем заполненную клетку, у которой расстояние равно разности индексов столбца и строки l_ij=V_j-U_i (у нас А₅А₇). Она означает последнее звено маршрута А₅-А₇.

2. Для определения предпоследнего операция повторяется для столбца А₅. Это будет звено А₄-А₅.

3. Затем перед ним по столбцу А₄ звено А₁-А₄.

Итак, А₁®А₄®А₅®А₇ кратчайший путь найден.

Затем повторяем все решения с самого начала (всю матрицу), принимая:

а) исходный пункт А₂ (т.е. V₂=U₂=0);

б) исходный пункт А₃ (V₃=U₃=0) и т. д. определяем все кратчайшие расстояния.

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

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

В настоящее время ярко выраженная разница в технологии перевозок разделяет методы маршрутизации на два класса: маршрутизация помашинных отправок грузов и маршрутизация мелких партий грузов.

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

Решение состоит из двух этапов: оптимального решения транспортной задачи и формирования набора маршрутов.

Технология конструирования маршрутов может быть выполнена методом совмещённых планов, разработанным на базе линейного программирования. Идея метода совмещённых планов (матриц) состоит в следующем. На первом этапе ищем оптимальный план холостых пробегов автомобилей (как это делалось при решении задачи по закреплению потребителей за поставщиками). На втором этапе в одну матрицу записываем два плана: заданный и полученный, после чего путём специальной процедуры выбираем маршруты движения автотранспорта.

В простейшей постановке задача маршрутизации грузовых перевозок состоит в следующем.

Разнородный груз сосредоточен в пунктах отправления А₁, A₂...A_i...A_m в количествах соответственно а_1, a₂...a_i…a_m единиц. Его необходимо доставить в пункты назначения В₁,B₂...B_j...B_n в количествах в₁, в₂…в_j...в_n соответственно.

Объём перевозок из i-го пункта отправления в j-й пункт назначения составляет q_ijединиц и известен для всех пунктов.

Расстояние от i-ro пункта отправления до j-ro пункта назначения равно l_ij и известно для всех комбинаций ij.

В процессе выполнения перевозок в пунктах назначения В₁, B₂...B_j...B_n после разгрузки автомобилей будет образовываться порожняк в количествах , … … единиц.

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

Величины а_i, в_j, q_ij, , могут выражаться либо в тоннах, либо в ездках автомобиля. Для существа задачи это безразлично, тем более что тонны всегда можно перевести в ездки. Однако с методической точки зрения удобнее пользоваться ездкой автомобиля с грузом и без груза.

Количество прибывающих в пункт назначения гружёных автомобилей представляет ресурсы порожняка в данном пункте. Количество убывающих из пункта отправления гружёных автомобилей - потребность этого пункта в порожняке.

По смыслу рассматриваемой задачи всегда имеет место условие

Расстояние от B_j до А_i, равное l_ji=l_jj, известно для всех сочетаний i, j.

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

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

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

Обозначим количество порожняка в автомобилеездках, подаваемого из пункта B_j в пункт A_i, через x_ij. Суммарный холостой пробег автомобилей из всех пунктов наличия порожняка во все пункты его подачи при этом составит

Условие полного удовлетворения спроса на порожняк каждого пункта отправления за счёт подачи из разных пунктов наличия порожняка записывается следующим образом:

Весь порожняк из каждого пункта назначения должен быть подан в пункты отправления под погрузку. Формально это означает, что

Количество автомобилей не может быть отрицательным, т. е.

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

и минимизирующих суммарный холостой пробег автомобилей

 

По смыслу задачи имеет место равенство

Сформулированная задача (11 - 14) называется задачей минимизации холостых пробегов автомобилей. Это транспортная задача линейного программирования, имеющая n∙m число переменных, связанных посредством n+m линейных уравнений.

Далее рассмотрим постановку указанной задачи на конкретном примере - задания на перевозку грузов на известные расстояния. Исходные данные приведены в таблице 16.

Таблица 16

Исходные данные

Расстояния между всеми пунктами заданы в табл.17 (матрица расстояний).

 

Таблица 17

Матрица расстояний

Решение поставленной задачи рассматриваемым методом совмещённых планов включает три этапа.

Этап 1. Минимизация холостых пробегов автомобилей и нахождение оптимального плана возврата порожних автомобилей под погрузку после их выгрузки.

Используя данные таблицы 16 и таблицы 17, составляем матрицу условий (табл. 18)

Таблица 18

Матрица условий

 

В соответствии с алгоритмом метода потенциалов находим допустимый план холостых пробегов.

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

Таблица 19

Оптимальный план возврата порожняка под погрузку

Этап 2. Составляем матрицу совмещённых планов (табл.20).

 

Таблица 20

Матрица совмещённых планов

Для этого в матрицу возврата порожняка (т.е. холостых пробегов) таблицу 19 записываем число гружёных ездок из таблицы16 исходных данных. В разбираемом примере ездки с грузом обозначены жирным шрифтом, а порожние - обычным. Вспомогательные и итоговые строки и столбцы для дальнейших расчётов не нужны, и поэтому они исключены из матрицы.

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

Маятниковые маршруты определяют клетки с двойной загрузкой, т. е. клетки, в которых записаны одновременно ездки с грузом и без груза. В нашем примере двойные загрузки имеют клетки А₂В₃, А₂В₅ и А₄В₂, которые обозначают следующие маятниковые маршруты:

маршрут 1 А₂ - В₃ - А₂ на 28 ездок;

маршрут 2 А₂ - В₅ - А₂ на 16 ездок;

маршрут 3 А₄ - В₂ - Ад на 14 ездок.

Количество ездок по каждому маятниковому маршруту определяется наименьшей из загрузок рассматриваемой клетки. Запланированные на маршруты 1 - 3 гружёные и порожние ездки исключаются из матрицы, после чего продолжается составление маршрутов. Поскольку в матрице теперь отсутствуют клетки с двойной загрузкой, приступаем к составлению кольцевых маршрутов.

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

Таблица 21