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

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

- возможность непосредственной доставки грузов, пассажиров «от двери до двери»;

- приспособленность к перевозке грузов различных габаритных размеров и массы;

- оперативность организации перевозок, малые первоначальные капитальные вложения;

- большая мобильность, высокая скорость доставки.

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

- определение кратчайших расстояний между пунктами сети;

- маршрутизация перевозок грузов;

- выбор подвижного состава для работы на линии, определение его потребного количества;

- определение технико-эксплуатационных показателей работы подвижного состава на линии и доходность от перевозки.

1. Анализ транспортной сети и объёма перевозок

Рассматриваемая транспортная сеть состоит из 18 пунктов. Общая длина транспортной сети составляет км. Из них дорог со щебеночным покрытием - км, а с асфальтобетонным - км.

На транспортной сети осуществляется перевозка щебня и керамзита. Щебень является грузом I класса с коэффициентом использования грузоподъемности г_с. = 1,0; керамзит - груз III класса, с коэффициентом использования грузоподъемности г_с = 0,6. Объем производства грузов в грузообразующих пунктах составил:

- щебень - т: А

- керамзит - т: А

Объем потребления грузов в грузопоглащающих пунктах составил:

- щебень - т: Б

- керамзит - т: Б

Перевозкой данных грузов занимаются три автотранспортных предприятия.

Техническая скорость автомобиля, при движении по дороге с асфальтобетонным покрытием составляет 45 км/ч, а при движении по дороге со щебеночным покрытием - 35 км/ч.

2. Определение кратчайших расстояний между пунктами транспортной сети

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

Решение задачи можно вести двумя методами:

- табличным;

- сетевым.

Алгоритм решения задачи табличным методом рассмотрим на примере определения кратчайших расстояний от точки 0 до всех остальных. Для этого составляем таблицу и заносим в нее расстояния от каждой точки до всех точек соседних с нею (таблица 1). Каждой j-ой точке соответствует некоторое число Lj, характеризующее расстояние от 0 до j-го пункта. При заполнении таблицы руководствуются правилом: Точке 0, от которой измеряется расстояние, соответствует число Lj = 0. Соответственно, в верхней строчке проставляется Li = 0. Затем, начиная с i = 0, просматриваются клетки i-го столбца с заполненными расстояниями Lij и если для некоторой клетки Li уже определено, а Lj еще нет, то полагается, что Lj = Li + Lij и вносится в клетку с номером j левого столбца и в клетку i верхней строки таблицы. В силу связанности сети можно найти все числа Li и Lj. Если в j-ой строке имеется несколько Lij и при этом соответствующие Li уже найдены, то находим Lj определяемые наименьшей суммой значений Li + Lij для всех возможных значений Li, т.е. Lj = min (Li + Lij). Далее просматриваются все заполненные клетки таблицы, начиная со строки 0 и сравниваются расстояния, которые указаны в этих клетках с разностью Lj - Li. При таком сравнении возможны следующие варианты Lj - Li ? Lij или Lj - Li > Lij. Для тех клеток, где Lj - Li ? Lij значения Lj и Li оставляем без изменения. В клетках, где Lj - Li > Lij, записываем откорректированное значение L'j = Li + Lij, а затем исправляем Li в соответствующем столбце. Этот процесс повторяется до тех пор, пока для всех клеток не станет Lj - Li ? Lij. В этом случае значения Lj и Li будут определять кратчайшие расстояния от точки 0 до всех остальных.

Таблица 1 - Определение кратчайших расстояний между пунктами табличным методом

Алгоритм решения задачи сетевым методом рассмотрим на примере определения кратчайших расстояний от точки 1 до всех остальных. Для этого выполним два шага:

Шаг 1. Начальному пункту, от которого определяются кратчайшие расстояния, присваиваем потенциал Vi = 0.

Шаг 2. Просматриваются все звенья, начальные пункты i которых имеют потенциалы Vi, а для конечных j потенциал определяем по формуле

Vj(i) = Vi + Lij,

где Lij - длина звена ij, км.

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

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

Данные расчеты являются громоздкими и занимают много времени. Для сокращения и упрощения процесса расчета можно воспользоваться программой KRTRSTO, результатом чего являются таблицы 2 и 3.

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

Задача оптимизации грузопотоков в общем виде формулируется следующим образом:

1) задано множество поставщиков (пункты погрузки) и потребителей (пункты выгрузки) однородных (взаимозаменяемых) грузов;

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

3) определены кратчайшие расстояния между поставщиками и потребителями грузов.

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

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

В математической форме поставленная задача имеет следующий вид:

W = ? ? Хij•Lij > min

где Хij - объем перевозок от i-го поставщика к j-му потребителю;

Lij - кратчайшее расстояние между поставщиком и потребителем;

? Хij•= а_i;

? Lij = в_j,

где а_i - то количество грузов, которым располагает i-тый поставщик;

в_j - потребность в грузе j-го потребителя.

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

Решение задачи начинается с построения опорного (исходного) плана перевозок. При этом по каждой строке распределительной таблицы находим минимальное расстояние между пунктами и эта клетка обозначается знаком (+). Аналогично действуем по каждому столбцу. Первоначальные объемы перевозок назначаются в клетки отмеченные дважды в порядке возрастания указанных в них расстояний. Затем переходим к отмеченным один раз и неотмеченным клеткам до тех пор пока не будут удовлетворены ограничения по вывозу и завозу груза. Полученное таким образом закрепление потребителей за поставщиками является базисным планом, который должен содержать m + n - 1 занятых клеток. Кроме того план должен отвечать условию ацикличности. Это означает, что в таблице нельзя построить замкнутый цикл все вершины которого лежат в занятых клетках. После этого план проверяется на оптимальность методом потенциалов. Их определение начинается со строки, имеющей максимальное расстояние. Если план является оптимальным, то ему соответствует система из m + n чисел удовлетворяющих условию:

Ui + Vj = Lij; Хij > 0 - для занятых клеток;

Ui + Vj ? Lij; Хij = 0 - для свободных клеток.

где Ui - потенциал поставщика;

Vj - потенциал потребителя.

Опорный план перевозки щебня и керамзита приведены в таблице 4 и таблице 5 соответственно.

Таблица 4 - Опорный план перевозки щебня

Проверяем план на базисность: 4 + 4 - 1 = 7 ? 6, в связи с этим вводим перевозку равную нулю. В этом случае план отвечает условию базисности. Так как объем производства продукции равен объему потребления, то это задача закрытого типа.

Находим потенциалы используя формулу

Ui + Vj = Lij:

Проверяем условие оптимальности:

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

Для построения опорного плана перевозки керамзита необходимо ввести фиктивного производителя (Аф), что вызвано неодинаковым объемом производства и потребления продукции. Объем производства составляет 400 тонн, и только в этом случае задача является задачей закрытого типа.

Таблица 5 - Опорный план перевозки керамзита

Проверяем план на базисность: 3 + 3 - 1 = 5 = 5. план отвечает условию базисности.

Находим потенциалы используя формулу

Ui + Vj = Lij:

Проверяем условие оптимальности:

Результат проверки показал, что условие оптимальности не нарушается, что говорит об оптимальном построении плана перевозки керамзита.

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

4. Закрепление потребителей и поставщиков отдельных видов грузов

перевозка груз картограмма кратчайший

Закрепление потребителей и поставщиков будем осуществлять для каждого из видов грузов в отдельности.

В первую очередь произведём оптимизацию закрепления поставщиков и потребителей щебня.

В соответствии с исходными данными:

1) Пункты и объёмы производства груза:

А₁₀ - 220 т;

А₁₇ - 200 т;

А₁₈ - 280 т;

2) Пункты и объёмы потребления груза:

Б₁ - 120 т;

Б₄ - 180 т;

Б₅ - 150 т;

Б₇ - 200 т;

Б₁₂ - 200 т;

Б₁₄ - 150 т.

3) Кратчайшие расстояния между пунктами производства и потребления груза рассчитаны в главе 2 и приведённые в таблице 2.

Задача открытого типа, так как объём производства щебня на 300 т меньше, чем объём потребления. Для того чтобы привести задачу к закрытому типу, вводится фиктивный производитель груза Б_ф с объёмом производства, равным 300 т. Расстояние от фиктивного поставщика ко всем потребителям принимаем равным 200 км. Исходные данные для решения данной транспортной задачи сведены в таблицу 3.1.

Таблица 3.1 - Исходные данные для построения оптимального плана

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

Таблица 3.2 - Опорный план перевозки щебня

Проверим план на вырожденность: , а в опорном плане 8 заполненных клеток, следовательно, он является вырожденным. Поместим базисную нулевую перевозку в клетке (17; 5). План ацикличен (нельзя построить замкнутого цикла).

Присвоим поставщику А₁₀ потенциал . Далее последовательно определим потенциалы остальных поставщиков и потребителей.

Таблица 3.3 - Нахождение потенциалов

Далее опорный план проверяется на оптимальность:

Условие нарушено в клетках (17; 5) и (17; 14), в которых нужно назначать новую перевозку. Для оптимизации выбираем клетку с наибольшим отклонением от условия оптимизации, т.е. клетку (17; 5). Процесс оптимизации плана представлен в таблице 3.4.

Таблица 3.4 - Оптимизация опорного плана перевозок

Из клеток полученного замкнутого контура, обозначенных знаком «-», выбираем минимальный объём перевозки (в данном случае - в клетке (10; 1), объём - 20 т.) и прибавляем это значение к клеткам со знаком «+», а в остальных клетках со знаком «-» уменьшаем объём перевозки на эту же величину. Получаем оптимизированный план, который также должен быть подвергнут проверке на оптимальность. Полученный новый план перевозок изображён в таблице 3.5, в которой также показаны потенциалы поставщиков и получателей груза при новом плане.

Таблица 3.5 - Новый план отправок и нахождение потенциалов

Проверим полученный план на оптимальность:

Нарушение оптимальности обнаружено только в клетке (18; 7), в которой требуется назначать новую перевозку. Процесс оптимизации плана представлен в таблице 3.6.

Таблица 3.6 - Оптимизация опорного плана перевозок

В результате оптимизации получаем новый план, который представлен в таблице 3.7.

Таблица 3.7 - Новый план отправок и нахождение потенциалов

Проверим полученный план на оптимальность:

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

Таблица 3.8 - Оптимальный план перевозок щебня

Аналогичным способом решается транспортная задача по закреплению поставщиков и потребителей керамзита. В таблице 3.9 представлено решение этой транспортной задачи.

Таблица 3.9 - Оптимальный план перевозок керамзита

5. Построение картограммы грузопотоков

6.1 Постановка задачи маршрутизации перевозок грузов

Маршрутизация перевозок - это составление маршрутов движения подвижного состава или его порядка следования между корреспондирующимися пунктами.

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

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

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

6.2 Решение задачи маршрутизации с использованием метода совмещённых планов

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

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

Перед составлением плана возврата порожних автомобилей объём перевозок необходимо привести к одному 1-ому классу:

,

где - фактический объём перевозки, т;

- статический коэффициент использования грузоподъёмности автомобиля (щебень - 1,0; керамзит - 0,6).

Расчёты по приведению объёмов перевозок удобнее производить в табличной форме. Исходные данные для приведения объёмов выбираются из оптимальных планов перевозок грузов (таблицы 3.8 и 3.9). Расчёт приведённых объёмов показан в таблице 5.1.

На основании таблицы 5.1 и принятых выше допущений о том, что грузы перевозятся условными однотонными автомобилями, составляется сводный план ездок автомобилей с грузом, который приведён в таблице 5.2. Строки таблицы обозначают пункты отправления , столбцы - пункты назначения , на пересечении соответствующего столбца и строки проставляется приведённый к первому классу объём перевозок (количество условных однотонных автомобилей, необходимых для перевозки для перевозки приведённого объёма груза).

Таблица 5.1 - Приведение объёмов перевозок к 1-ому классу

Таблица 5.2 - Сводный план ездок автомобилей с грузом

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

Далее в соответствующие клетки сводного плана ездок автомобилей с грузом (таблица 5.2) переносятся значения из оптимального плана возврата порожних автомобилей. Эти цифры для удобства подчёркиваются. Таким образом, будет построена таблица, которая называется «совмещённой матрицей» или иначе совмещённый план перевозок груза и возврата порожних автомобилей.

Таблица 5.3 - Оптимальный план возврата порожних автомобилей

Таблица 5.4 - Совмещённый план перевозок груза и возврата порожних автомобилей

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

Таблица 5.5 - Список маятниковых маршрутов

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

Пример определения кольцевых маршрутов приведён в таблице 5.6.

Таблица 5.6 - Определение кольцевых маршрутов

Условные обозначения:

- «А9 - Б8 - А10 - Б12 - А9» (167 т);

- «А17 - Б5 - А4 - Б17 - А17» (100 т);

- «А18 - Б4 - А4 - Б16 - А18» (164 т);

- «А18 - Б7 - А9 - Б15 - А18» (50 т);

Таблица 5.7 - Список кольцевых маршрутов

Таблица 5.9 - Рациональные маршруты перевозок грузов

Список литературы