Маршрутизация перемещения мелких партий ресурсов

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

,

где l_oj – длина оборота транспортного средства на j-м маршруте;

n – общее число маршрутов для освоения заданных объемов перевозок ресурсов.

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

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

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

Этап 1. Находится кратчайшая связывающая сеть

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

Этап 2. Набор пунктов в маршруты

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

Результаты набора пунктов в маршруты сводятся в таблице 3.15.

Таблица 3.15 – Набор корреспонденций (перевозок) в маршруты

Этап 3. Определение очередности объезда пунктов маршрута

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

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

Таблица 3.16 – Таблица для применения метода сумм

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

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

Dl_kp = l_ki + l_ip - l_kp,

где l – расстояние (стоимость, время и т.п.);

k – первый соседний пункт;

p – второй соседний пункт;

i – индекс включаемого пункта.

Из всех получаемых величин Dl_kp выбирают минимальную и между пунктами k и p включают в маршрут пункт i.

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

Этап 4. Определение возможности одновременного развоза и сбора ресурсов на маршруте

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

Для проверки составляем таблицу нижеприведенного вида (таблица 3.17).

Таблица 3.17 – Расчет загрузки транспортного средства при перевозке на маршруте

Количество ресурса на транспортном средстве при выходе из пункта i определяется по формуле

Q_i,i+1 = Q_i-1,i - Q_pi + Q_ci,

где Q_i,i+1 – объем перевозимого ресурса на участке маршрута (при выходе из пункта i);

Q_i-1,i – объем перевозимого ресурса на предшествующем участке i-1, i маршрута;

Q_pi – объем выгрузки ресурса в пункте i;

Q_ci – объем погрузки ресурса в пункте i.

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

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

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

Схема маршрута в этом случае выглядит следующим образом:

базовый пункт – загрузка;

пункты повторного заезда – разгрузка;

прочие пункты – разгрузка-загрузка;

пункты повторного заезда – загрузка;

базовый пункт – разгрузка.

Пример. Составить развозочный маршрут для следующих исходных данных:

транспортная сеть района перевозок, заданная в примере при отыскании кратчайших расстояний;

базовым является пункт 3;

объемы завоза ресурса по пунктам 1 – 3 ед., 2 – 3 ед., 4 – 4 ед., 5 – 1 ед.;

вместимость транспортного средства – 7 ед.;

предельно-допустимое число пунктов заезда – 3.

Решение.

Этап 1. Используем ранее найденную кратчайшую связывающую сеть.

Этап 2. Набор пунктов в маршруты

В соответствии с ранее приведенным алгоритмом производим набор пунктов в маршруты (таблица 3.18).

Таблица 3.18 – Набор корреспонденций (перевозок) в маршруты для данных примера

Этап 3. Определение очередности объезда пунктов маршрута

Для нахождения порядка объезда пунктов строим таблицу по методу сумм для маршрута 1 (таблица 3.19). На маршруте 2 никаких вариантов объезда нет.

Затем строим начальный маршрут из трех пунктов, имеющих максимальную сумму по своим столбцам. В него включаем исходный пункт А, пункт 5 и один из пунктов 2 или 1 (принимаем пункт 2). Получаем маршрут А-5-2-А.

После этого включаем в маршрут пункт 1, который можно вставить между пунктами А и 5, 5 и 2, А и 2.

Таблица 3.19 – Таблица по методу сумм для маршрута 1

Расчет приращений Dl_kp для i=1 выполняем в расчетной таблице 3.20.

Таблица 3.20 – Расчет приращений для маршрута 1

Из всех получаемых величин Dl_kp выбираем минимальную =0 (k=5 и p=2) и между пунктами k=5 и p=2 вставляем включаемый пункт 1.

В результате получаем два маршрута:

Маршрут 1 – А-5-1-2-А (протяженность 25) и маршрут 2–А-4-А (протяженность 6) суммарной протяженностью 31.

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

Метод Кларка-Райта предусматривает совмещенное решение задачи маршрутизации перевозок по сборочным или развозочным, осуществляемых в общем случае парком транспортных средств различной вместимости.

Основой решения являются следующие исходные данные:

число K видов транспортных средств различной k-й вместимости и значения вместимостей q_k, ;

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

количество ресурса (Q_pi, ), подлежащего завозу или вывозу по промежуточным пунктам;

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

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

Алгоритм одной из реализаций метода следующий:

1) строится система маятниковых маршрутов, на каждом из которых предполагается обслуживать один пункт. Для каждого такого i-го маршрута назначается объем перевозок Q_i = Q_pi, число пунктов заезда n_i=1 и транспортное средство возможно минимальной вместимости, но не менее Q_i, т.е. ;

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

Выигрыши рассчитываются по формуле

Dс_ij = с_Ai + с_Aj -с_ij,

где Dс_ij – величина сокращения пробега транспортного средства при объединении маршрутов A-B_i-A и A-B_j-A;

с_Ai, с_Aj – стоимость перемещения от исходного пункта A соответственно до пунктов B_i и B_j;

с_ij – расстояние между пунктами B_i и B_j, ед. Вариантность попарного объединения пунктов описывается треугольной матрицей и соответственно общее число вариантов определяется выражением (m (m-1))/2, где m – число промежуточных пунктов;

3) последовательно производится объединение текущих маршрутов следующим образом:

3.1) находится максимальный выигрыш от возможного попарного объединения исходных маршрутов , где r и s – соответственно пункты, по которым может быть рассмотрено объединение маршрутов. Если максимальный выигрыш нулевой или отрицательный – то решение закончено;

3.2) оценивается возможность объединения маршрутов с учетом наличия транспортных средств необходимой вместимости и выполнения других заданных ограничений. Для этого необходимо рассчитать общий объем перевозимого ресурса как сумму ресурсов объединяемых маршрутов Q_т=Q_r+Q_s, число пунктов заезда на объединенном маршруте n_т = n_r+n_s и др. Если такое объединение невозможно ( или n_т ³ n_п и т.п.), то переход на пункт 3.5. Иначе на 3.3.

3.3) формируется новый объединенный маршрут, состоящий из двух объединяемых по пунктам r и s. Полученный маршрут имеет вид A-B_p-...-B_r-B_s-...-B_u-A;

3.4) производится корректировка текущих значений параметров в связи с объединением маршрутов:

· маршруты r и s, вошедшие в сформированный маршрут, аннулируются и соответственно присваиваются Q_r(…)= 0 и Q_s(…)= 0;

· формируется индекс маршрута, определяемый номерами крайних пунктов (пункты p и u);

· назначается на маршруте с индексом p(u) объем перевозок Q_p(u)= Q_т и число промежуточных пунктов заезда n_p(u)=n_т;

· назначается транспортное средство, удовлетворяющее условию ;

· если n_т>2, то на отрицательный, например, -1 заменяется выигрыш между конечными пунктами маршрута p и u (Dc_pu=-1);

· на отрицательные заменяются выигрыши всех других пунктов с пунктом r, если n_r>1 (Dс_ri= -1, ) и с пунктом s, если n_s>1 (Dс_si= -1, );

3.5) реальное значение выигрыша Dс_rs заменяется отрицательным (Dс_rs=-1) независимо от того состоялось формирование нового маршрута или нет;

3.6) переход на 3.1.

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

ПРИМЕР. Рассмотрим решение приведенной ранее задачи по методу Кларка-Райта:

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

2) рассчитываются выигрыши для всех возможных вариантов попарного объединения маршрутов, образованных согласно пункту 1. Число вариантов попарного объединения маршрутов равно m (m-1)/2, где m – число промежуточных пунктов (6 вариантов). Расчет выигрышей для данных примера приведен в таблице 3.22.

Таблица 3.21 – Данные по исходным маршрутам

Таблица 3.22 – Расчет выигрышей от попарного объединения маршрутов

Примечание. Число символов "*" показывает номер итерации, на котором происходит замена выигрыша на -1

3) последовательно производится объединение маршрутов следующим образом (последняя цифра в подпунктах – номер итерации):

3.1.1) находим максимальный выигрыш от возможного попарного объединения исходных маршрутов. Это два маршрута r =1 и s=5. Поскольку максимальный выигрыш Dc_rs ненулевой – то переход на 3.2.1;

3.2.1) оцениваем возможность объединения маршрутов с учетом наличия транспортных средств необходимой вместимости и выполнения других заданных ограничений. Для возможного нового маршрута определяем общий объем перевозимого ресурса как сумму ресурсов рассматриваемых маршрутов Q_т=Q_r+Q_s,=Q₁ +Q₅ =3+1=4 и число пунктов заезда на объединенном маршруте n_т = n_r+n_s = n₁+n₅ =1+1=2. В нашем случае полученные параметры не превышают допускаемых и объединение возможно.

3.3.1) формируется новый объединенный маршрут, состоящий из двух объединяемых по пунктам с найденным максимальным выигрышем. Полученный маршрут имеет вид A-1-5-A;

3.4.1)

· маршруты с шифрами 1 и 5, вошедшие в сформированный маршрут, аннулируются (Q₁=0; Q₅=0);

· формируется шифр маршрута, определяемый номерами крайних пунктов (пункты 1 и 5);

· назначается объем перевозок Q₁₍₅₎= Q_т=4 и число промежуточных пунктов заезда n₁₍₅₎= n_т=2;

· назначается транспортное средство, удовлетворяющее условию =7;

· поскольку n_т =2, то далее;

· поскольку не выполняется n_r>1 и n_s>1, то на 3.5.1;

3.5.1) реальное значение выигрыша с_1-5 заменяется отрицательным (с_1-5= -1);

3.6.1) переход на 3.1.2.

3.1.2) находим максимальный выигрыш от попарного объединения исходных маршрутов. Это два маршрута r =1 и s=2. Поскольку выигрыш ненулевой – то решение не закончено;

3.2.2) оцениваем возможность объединения маршрутов с учетом наличия транспортных средств необходимой вместимости и выполнения других заданных ограничений. Для возможного нового маршрута определяем общий объем перевозимого ресурса как сумму ресурсов объединяемых маршрутов Q_т=Q_r+Q_s=Q₁ +Q₂ =4+3=7 и число пунктов заезда на объединенном маршруте n_т = n_r+n_s = n₁+n₂ =2+1=3. Полученный параметр Q_т=7 и n_т =3 не превышают заданных ограничений и поэтому на 3.3.2;

3.3.2) принимаем маршрут А-2-1-5-А;

3.4.2)

· маршруты с шифрами 1(5) и 2, вошедшие в сформированный маршрут, аннулируются (Q₁₍₅₎=0; Q₂=0);

· формируется шифр маршрута, определяемый номерами крайних пунктов (пункты 2 и 5);

· назначается объем перевозок Q₂₍₅₎= 7 и число промежуточных пунктов заезда n₂₍₅₎=3;

· назначается транспортное средство, удовлетворяющее условию =7;

· поскольку n_т>2, то на -1 заменяется выигрыш между конечными пунктами маршрута 2 и 5 (Dc_2,5= -1);

· поскольку выполняется n_r>1, то Dc_1,i= -1, (для всех выигрышей с объединением по пункту 1) и на 3.5.2;

3.5.2) реальное значение выигрыша с_1,2 заменяется отрицательным (c_1-2= -1);

3.6.2) переход на 3.1.3.

3.1.3) находим максимальный выигрыш от попарного объединения исходных маршрутов. Это маршруты с конечными пунктами r =4 и s=5. Поскольку выигрыш ненулевой– то решение не закончено;

оцениваем возможность объединения маршрутов с учетом наличия транспортных средств необходимой вместимости и выполнения других заданных ограничений. Для возможного нового маршрута определяем общий объем перевозимого ресурса как сумму ресурсов объединяемых маршрутов Q_т=Q_r+Q_s,=Q₂ +Q₄ =7+4=11 и число пунктов заезда на объединенном маршруте n_т = n_r+n_s = n₄+n₅ =3+1=4. Полученный параметр Q_т=11 превышает вместимость транспортного средства, а n_т = 4 больше допустимого числа n_п и поэтому маршрут не возможен. Переходим на 3.5.3.

3.5.3) реальное значение выигрыша с_4,5 заменяется отрицательным (с_4,5= -1);

3.6.3) переход на 3.1.4)

3.1.4) находим максимальный выигрыш от попарного объединения исходных маршрутов. Это два маршрута r =2 и s=4. Максимальный выигрыш ненулевой и поэтому решение не закончено;

3.2.4) оцениваем возможность объединения маршрутов с учетом наличия транспортных средств необходимой вместимости и выполнения других заданных ограничений. Для возможного нового маршрута определяем общий объем перевозимого ресурса как сумму ресурсов объединяемых маршрутов Q_т=Q_r+Q_s,=Q₂ +Q₄ =7+4=11 и число пунктов заезда на объединенном маршруте n_т = n_r+n_s = n₁+n₃ =3+1=4. Поскольку объединение невозможно по ограничениям на вместимость и число промежуточных пунктов, то переход на 3.5.4.

3.5.4) реальное значение выигрыша с_2,4 заменяется отрицательным (с_2-4= -1);

3.6.4) переход на 3.1.5)

3.1.5) находим максимальный выигрыш от попарного объединения исходных маршрутов. Это два маршрута r =1 и s=2. При этом максимальный выигрыш отрицательный и поэтому решение закончено.

В результате получены следующие маршруты: А-2-1-5-А или А-5-1-2-А (протяженность 25) и А-4-А (протяженность 6), которые совпали с составленными на основе кратчайшей связывающей сети.

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

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

Компьютерная программа для составления маршрутов по ранее изложенному алгоритму дана в приложении 9.

Поиск по сайту: