Маршрутизация перевозок грузов

Введение

 

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

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

К основным видам транспорта относятся:

§ автомобильный;

§ железнодорожный,

§ воздушный (авиационный),

§ водный (морской, речной),

§ трубопроводный.

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

Автомобильные перевозки–производственный процесс по перемещению грузов и пассажиров. Они подразделяются на грузовые и пассажирские.

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

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

 

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

Схема сети автомобильных дорог в масштабе с обозначением типа их покрытия приведены на рис.1.

Суточные объёмы перевозок грузов между пунктами транспортной сети (грузовые потоки) приведены в табл.1.

Месторасположение автомобильного транспортного предприятия – в пункте 5.

Режим работы автомобилей на линии – двухсменный, коэффициент выпуска автомобилей на линию в рабочие дни - 0,8.

 

Таблица 1. Грузовые потоки между пунктами транспортной сети

Вариант	Объёмы перевозок грузов между пунктами транспортной сети, т
1-17	3-5	6-19	8-12	14-4	17-6
1/2	200 А	200 Б	250 А	350 А	180 Б	220 Б

А - груз I класса;

Б - груз II класса.

 

 

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

 

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

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

По полученной модели транспортной сети находятся кратчайшие расстояния между её пунктами (табл.2).

Таблица 2. Кратчайшие расстояния между пунктами транспортной сети

Пункты транспорт-ной сети

 

По заданным объёмам перевозок грузов между пунктами и модели транспортной сети строится картограмма грузовых потоков.

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

Маршрутизация перевозок грузов

 

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

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

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

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

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

Объем перевозок из i-го пункта отправления в j-й пункт назначения составляет для k-го груза тонн. Указанные объемы перевозок приводятся к одному классу груза. Приведение объемов перевозок грузов к 1-му классу груза производится по следующей формуле:

, (1)

где - объем перевозок между пунктами i и j, приведенный к первому классу груза, усл. т.; - фактический объем (количество) k-го груза, т.; - коэффициент использования грузоподъемности при перевозке k-го груза; r – общее число видов перевозимого груза.

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

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

(2)

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

(3)

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

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

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

Данную задачу математически можно записать следующим образом: требуется

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

; (4)

(5)

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

(6)

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

(7)

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

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

Таблица 3. Подготовка исходных данных для маршрутизации

По данным табл.3 и формулам (2) и (3) рассчитываются значения и , которые равны числу ездок по возврату порожних условных однотонных автомобилей

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

 

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

 

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

Распределительная таблица составляется по данным табл.2; 3 и 4; в нее заносятся расстояния , число отправляемых условных однотонных автомобилей и число прибывающих уловных однотонных автомобилей .

Для отыскания оптимального закрепления грузоотправителей за грузополучателями по подаче порожних автомобилей необходимо сделать в распределительной таблице первоначальное закрепление, т.е. получить произвольный план закрепления (опорный), удовлетворяющий ограничениям (4), (5), (7) при числе загруженных клеток m + n - 1 и отсутствия циклов (контуров). Такой план, содержащий ровно m + n - 1 заполненных клеток без циклов, называется базисным. Цикл (контур) в распределительной таблице – это замкнутая ломаная линия, образованная прямыми отрезками, углы между которыми равны 90 градусов, а вершины углов лежат в загруженных клетках. Контур может быть четырехугольным, шестиугольным, восьмиугольным и т.д. Если число загруженных клеток – более m + n - 1, то среди них есть цикл.

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

выбирается минимальное расстояние по каждой строке распределительной таблицы, т.е. находится min . Такие клетки отмечаются значком, - например, звёздочкой (*). Если в одной строке несколько клеток имеют одинаковые минимальные расстояния, то отмечаются все эти клетки. То же самое проделывается по каждому столбцу, т.е. находятся и отмечаются клетки min ;

клетки в порядке возрастания указанных в них расстояний загружаются числом подач автомобилей , начиная с отмеченных дважды и последовательно переходя к отмеченным один раз и неотмеченным, пока не будут удовлетворены ограничения (3) и (4). Объём перевозки груза , заносимый в клетку , определяется как минимум от числа ездок по строке и по столбцу с учётом ранее назначенных других перевозок:

, (8)

где - число порожних ездок к i-му отправителю с учётом ранее назначенных подач от других, кроме j-го, получателей;

- число порожних ездок от j-го получателя с учётом ранее назначенных перевозок к другим, кроме i-го, отправителям.

 

Из сравниваемых величин и вычитаем значение , в результате чего все клетки строки (если ) либо столбца (если ) полностью исключаются из дальнейшего рассмотрения, а значимая разность соответственно () или () подлежит дальнейшему распределению по клеткам таблицы. Если , то оставляется к рассмотрению i-я строка с нулевым либо j-й столбец с нулевым ограничениями. Оставляют столбец или строку с меньшими значениями расстояний в клетках, куда может попасть нулевая загрузка. В дальнейшем этой нулевой загрузкой оперируют как значимой положительной величиной.

Полученное таким образом закрепление является одним из возможных базисных планов.

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

Наиболее широкое применение при ручном счете получил модифицированный распределительный метод (МОДИ). При использовании данного метода в распределительную таблицу вводятся вспомогательные строки и столбец, в которые вносятся специальные показатели, называемые потенциалами. Метод основан на том, что если к расстояниям любой строки (столбца) распределительной таблицы прибавить или отнять одно и то же произвольное число, то оценка оптимальности относительно не изменится. Если, например, от расстояний каждой i-й строки отнимать число и от расстояний каждого j-го столбца – , то тогда относительной оценкой любой клетки ji может служить параметр вместо , рассчитываемый по формуле:

(9)

Принимая для загруженных клеток = 0 и используя выражение (9), определяют потенциалы и по следующему правилу:

потенциал для первой строки таблицы принимается равным нулю;

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

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

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

Все расчёты сведены в распределительную таблицу (табл.5).

 

Таблица 5. Распределительная таблица

 

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

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

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

Составление рациональных маршрутов возможно двумя способами: методом «таблиц связей» и методом «совмещенных планов». Наиболее широкое применение получил последний из них.

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

В тех клетках ij полученной таблицы совмещенных планов, где имеются 2 цифры (выделенная и невыделенная), получаются маятниковые маршруты , число

ездок на которых равно минимуму , где – число ездок с грузом из в ; – число ездок без груза из в . Включенное число в маршрут ездок с грузом или без груза из дальнейшего рассмотрения исключается.

Когда все маятниковые маршруты найдены, в таблицы совмещенных планов начинают строить четырехугольные, а затем – шестиугольные и т. д. контуры, все углы которых лежат в загруженных клетках, причем углы в клетках с гружеными ездками должны чередоваться с углами в клетках с порожними ездками. Каждый из полученных контуров составляет маршрут, число оборотов на котором определяется наименьшим числом в клетках, соответствующих углам контура. Число ездок, включенное в маршрут, при дальнейшем рассмотрении не учитывается. Шифр маршрута состоит из шифров клеток углов контура. Решение ведется до полного исключения всего числа ездок из таблицы совмещенных планов (табл.6).

Таблица 6. Таблица совмещенных планов

 

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

Разработанные маршруты приведены в табл.7

Таблица 7. Маршруты перевозок груза

 

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

фактическое количество k-го груза , перевозимого между пунктами , определяется по формуле:

, (10)

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

Для каждого маршрута перевозки грузов должно соблюдаться условие:

. (11)

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

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

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

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

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

Поэтому критерием выбора начального пункта маршрута (первого пункта погрузки) и прикрепление его к АТП является оценочный параметр, рассчитываемый по формуле:

, (12)

где - скорректированный нулевой пробег, км.;

- расстояние от k-го АТП до i-го первого пункта погрузки, км.;

- расстояние от j-го последнего пункта выгрузки до k-го АТП, км.;

- расстояние между j-ым последним пунктом выгрузки и i-ым первым пунктом погрузки, км.

При закреплении маршрутов за АТП рассчитываются значения оценочного параметра для всех возможных вариантов начала выполнения маршрута и по каждому АТП.

Все расчеты приведены в таблице 8.

Таблица 8.Скорректированные нулевые пробеги

 

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

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

123Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: