Lektsii_PDF / МАРШРУТИЗАЦИЯ ГРУЗОВЫХ ПЕРЕВОЗОК

МАРШРУТИЗАЦИЯ ГРУЗОВЫХ ПЕРЕВОЗОК

1.Маршруты перевозок грузов.

2.Составление маршрутов движения автомобильного транспорта.

1. Маршруты перевозок грузов

Важную роль при выполнении ГАП занимает организация движения ПС, так как от правильного выбора маршрута движения зависит доля порожнего пробега ЦС в общем пробеге. Маршрутом движения называется путь следования ПС при выполнении перевозок.

При выполнении ГАП можно выделить несколько типичных вариантов организации транспортного процесса.

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

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

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

Во всех трех рассмотренных вариантах автомобиль перемещается от пункта к пункту по одному и тому же маршруту в прямом и обратном направлениях (рис. 1).

Рис. 1. Челночное движение подвижного состава

впростейших вариантах организации транспортного процесса

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

Рис. 2. Кольцевое движение подвижного состава

1

5. Развоз или сбор груза от одного отправителя или к одному потребителю {малая система с развозом или сбором груза). Схема перемещения автомобиля аналогична схеме малой системы с кольцевым движением ПС, но за оборот происходит только одна загрузка автомобиля и постепенная его разгрузка в нескольких пунктах при развозе груза и постепенная многократная загрузка и однократная разгрузка при сборе груза. Схема этого варианта организации транспортного процесса представлена на рис. 3.

Рис. 3. Развоз или сбор груза

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

Рис. 4.Транспортный процесс обслуживания производственной структуры

7. Интегрированная транспортная система может обслуживать несколько производственных структур или определенный географический регион {большая система). В данном случае процессы перемещения грузов будут происходить между несколькими производственными предприятиями, складами или терминалами со сбором или развозкой груза отправителям и потребителям.

Пример данного варианта организации перевозок представлен на рис. 5.

2

Рис. 5. Транспортныйпроцесс обслуживания несколькихпроизводственныхструктур

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

Рис. 6. Классификация маршрутов для перевозки грузов

Характеристики основных видов маршрутов приведены в табл. 3.1.

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

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

3

4

2. Составление маршрутов движения автомобильного транспорта

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

классические задачи оптимизации математического программирования: линейного, динамического, целочисленного, стохастического и т.п.;

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

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

Экономическая постановка задачи маршрутизации перевозок

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

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

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

Данную задачу можно представить как транспортную задачу с ограничением по времени относящуюся к классу задач маршрутизации автотранспорта (VRP - Vehicle

Routing Problem).

Математически задачу можно представить в виде графа G = (N, А), где N – множество вершин, которые соответствуют набору клиентов и обозначаются 1, 2, ..., n, и вершина 0 соответствующая исходному складу отгрузки товаров. Из данного склада начинают и в нем заканчивают свой маршрут все автомобили; А – набор дуг соединяющих соответствующие вершины графа (соответствующих клиентов), если i – один клиент, a j – другой, то дуга их соединяющая обозначается (i, j) А . Обозначим С – множество клиентов │C│ = n и Cl – подмножество клиентов со спросом на однотипные товары l. │Cl│ = nl. Каждый клиент i, i Сl характеризуется определенным спросом dil на товары типа l (l = 1, 2, …, m), m – количество типов грузов (товаров сформированных в грузовые единицы), соответственно и типов подвижного состава. М – множество типов грузов и соответственно типов

подвижного состава. Каждой дуге (i, j) А соответствуют время tij – время перемещения от клиента i С к клиенту.j С, это время включает в себя время обслуживание клиента

i и clk – стоимость пути k-го автомобиля типа l из i в j. ñlk = L × H lk × ql / ql , Верхним

ij ij (i, j ) (i, j ) k Ôk

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

Vl ( qkl Vl ), k = 1, 2, …., Kl. Kl – количество автомобилей типа l. L(i,j) – длина пути из пункта i, i С в пунктj, j С или длина дуги (i,j), (i, j) А. H (lki, j ) – норма расхода топлива k-ого автомобиля l-ого типа на дороге (i,j). qФl k – фактический объем l-ого типа груза

погруженного в k-ый автомобиль l-ого типа (тип автомобиля и тип груза, для перевозки которого он предназначен, обозначаются одинаковым индексом «l»). Каждый клиент должен быть обслужен в определенный промежуток времени, так называемое "временное окно", обозначаемый [ai, bj], i С. Время прибытия соответствующего автомобиля в оп-

ределенную вершину графа обозначается Sil , tîáilk – время обслуживания k-ого автомобиля l-ого типа для i Nl. Время обслуживания автомобиля включает время на маневриро- 5

вание в пункте погрузки, время разгрузки и погрузки и время на оформление документов. Время отправления из склада отгрузки для всех автомобилей равно 0, т. е. S0l = 0, время

движения соответствующего автомобиля из i в j обозначим tijlk .Переменные X ijl принимают значения [0, 1], 1 означает, что автомобиль движется от вершины i к вершине j, 0 обратное. Хранилище текущих маршрутов обозначим ХМl. Порядковые номера вершин

графа маршрута по ходу движения автомобиля обозначается р = 1, 2, …,																				nl – 1 [5 – 9] Гра-
фически данную задачу можно представить следующим образом (см. рис. 1.).
												3
	2
	4
																5
							Маршрут 2-го
						1	автомобиля
	3	4														1				2
			Маршрут 1-го
			автомобиля
								0
																Маршрут k-го
																				3
2																автомобиля

1

5 4

Рис. 1. Графическое представление ТЗ

Используя выше приведенные обозначения, по аналогии с математической формулировкой статической ТЗ приведенной в работе [5] и руководствуясь рекомендациями, приведенными в работах [7 – 9], осуществим математическую постановку задачи формирования кольцевых маршрутов с ограничением по времени.

Минимизировать целевую функцию (1), при ограничениях (2) – (9).

Z = ∑∑ ∑cijlk Xijl					→ min		(1)
		l M kl Kl (i, j) C
∑Xijl =1, i M							(2)
(i, j) a
∑dil			∑Xijl ≤ qkl , k Kl , l M				(3)
i Cl		(i, j) a
∑X0l			j	=1, l Vl			(4)
j N
∑Xirl			−∑Xrjl = 0, r Cl , l M				(5)
j N				j N
∑X lj,0				=1, l M			(6)
j N
∑Xijlk (Silk + tîáilk + tij − Slkj ) ≤ 0, (i, j) A, k Kl							(7)
j N
a	≤ S lk			≤ b , N , k K		l	(8)
i		i		i
X ijlk {0,1}, (i, j) A, k Kl							(9)

6

Целевая функция (1) определяет цену всех маршрутов всех транспортных средств (общая цена транспортного плана). Ограничение (2) полагает, что каждый клиент обслуживается только одним транспортным средством и только один раз. Ограничение (3) определяет, что транспортное средство не может обслужить больше клиентов, чем позволяет его грузоподъемность (грузовместимость). Ограничение (4) означает, что каждый автомобиль покидает склад отгрузки один раз. Ограничение (5) показывает, что автомобиль может покинуть вершину h, только если он прибыл в эту вершину. Аналогично ограничению (4), ограничение (6) означает, что все транспортные средства возвращаются в склад отгрузки, причем один раз. Это ограничение следует из ограничений (4) и (5). Ограничение

(7) означает, если автомобиль k движется из вершины i в j , то время прибытия автомобиля k в j не может быть меньше суммы времени прибытия автомобиля k в пункт i ( Silk ) и вре-

мени движения автомобиля k из пункта i в пункт j ( S lkj ). Ограничение (8) – это ограниче-

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

Как отмечалосьлось выше, первичная цель минимизация общего количества требуемого автотранспорта, вторичная, при одном и том же количестве транспортных средств – минимизация общего количества пройденного пути или общего затраченного времени (минимизация общей стоимости маршрутов). Временные ограничения делятся на "мягкие" (soft time windows) - нарушать которые разрешается (нарушение таких ограничений наказывается штрафом, выраженным в количественной форме и добавляемом к ЦФ) и "жесткие" (hard time windows) - нарушение которых не допускается ни при каких обстоятельствах. Как правило, алгоритмы для "жестких" и "мягких" ограничений различаются [5], [7].

7