10.3 Оптимизация транспортных маршрутов

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

Э та задача решается с помощью алгоритма Свира или метода “дворника-стеклоочистителя”, который можно пояснить на следующем примере (см. рис. 10.3).

Рисунок 10.3 Пример составления кольцевых маршрутов

методом “дворника-стеклоочистителя”

Двенадцать потребителей, например, торговых точек, снабжаются с одного центрального склада (ЦС). Пусть в данном примере, товары поставляются контейнеровозом МАЗ 5440АЭ-320-030, вмещающем 12 контейнеров. Средняя масса загруженного контейнера составляет 1 т. Допустимая грузоподъемность автомобиля – 14350 кг. Масса снаряженного автомобиля – 12 т. (Пример носит чисто иллюстративный характер.).

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

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

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

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

ГП1=(14+12)*4+(10+12)*6+(7+12)*7+(2+12)*6+12*5=513 т*км,

для второго сектора:

ГП2=(17+12)*3+(5+12)*6+12*9=309 т*км.

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

ΣГП=513+309+372+770+260=2224 т*км.

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

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

В результате загрузка автомобиля стала более равномерной и число ездок уменьшилось на одну. Суммарный грузопоток определится следующим выражением: ГП=974+260+468+544=2263 т.км. Однако в этом случае суммарный грузопоток даже увеличился за счет увеличения расстояний в первом секторе.

Рисунок 10.4 Пример плана перевозок при искривлении лучей, отсекающих секторы

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

Рисунок 10.5 Пример улучшения плана перевозок за счет изменения

положения первоначального луча

Суммарный грузопоток в этом случае составит ГП=719+309+432+646=2106 т*км, что существенно меньше, чем в исходном плане.

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

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

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

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

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

а) б) в) г)

Рисунок 10.6 Возможные варианты прокладки маршрута

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

Для оптимизации транспортных маршрутов обычно решается «задача коммивояжера», в которой исходными данными являются координаты источника (склада) и потребителей, т.е. расстояния от склада до каждого из потребителей и расстояния между последними. На рисунке 10.7 приведено решение задачи коммивояжера не по расстояниям, а по транспортным массам при собственной массе автомобиля 5 т.

Рисунок 10.7 Решение задачи коммивояжера по векторной транспортной массе

Кольцевой маршрут, приведенный на рис. 1а, действительно обеспечивает минимальный пробег автомобиля (в данном случае – 44 км.), однако минимальная векторная транспортная масса обеспечивается маршрутом, изображенном на рис. 1в (540 т*км., что на 10% меньше, чем при кольцевом маршруте).

Для построения математической модели задачи оптимизации перевозок введем обозначения:

Р_i – потребности i-того потребителя, т;

i = 1,…,n. n – число потребителей;

j – номер кольцевого маршрута;

G_ам – грузоподъемность автомобиля, т;

V_j – средняя скорость автомобиля на j-том маршруте, км/час;

R_j – средний расход топлива на j-том маршруте, л/км.

Тогда модель будет иметь вид:

загрузка автомобиля (т) не должна превышать его грузоподъемности:

(j=1.,,,.m) (10.5)

загрузка автомобиля (т) на каждом маршруте должна быть максимальной:

(j=1.,,,.m) (10.6)

транспортная масса (т*км) должна быть минимальной:

(10.7)

расход топлива (л*час) за весь производственный цикл должен быть минимален

(10.8)

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

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

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

Д орожная обстановка существенно меняется в зависимости от сезона и в течение суток (часы пик, аварии на дорогах и пр.), поэтому в алгоритм введен блок “Корректировка средней скорости V_i”.

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

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

Начало

Ввод исходных данных (координаты потребителей, их потребности, характеристика транспортного средства)

Построение секторов маршрутов М_j (j=1,…,m)

Введение средней скорости по маршрутуV_j (j=1,…,m) на данный момент времени

Выбор маршрутов с V_max

Анализ дорожной обстановки, корректировка средней

скорости V_i

Выбор маршрутов с максимальным количеством потребителей

Решение задачи коммивояжера

Печать М_j с V_max и максимальным количеством потребителей.

Печать маршрута

Исключение обслуженных потребителей из базы данных.

Нет

N=0

Да

Рис. 10.8 Алгоритм оптимизации маршрутов перевозок от одного склада