Маршрутизация перевозок массовых грузов.

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

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

Алгоритм решения такой задачи следующий:

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

Маршрутизация перевозок мелкопартионных грузов

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

где 1oj . — длина оборота автотранспортного средства на j-м маршруте, км; n- общее число маршрутов для освоения заданного объема перевозок.

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

Наиболее распространенными являются методы. составления сборно-развозочных маршрутов по КCCи Кларка-Райта.

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

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

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

Расчет выигрышей. Основой решения являются следующие исходные данные: число автомобилей по грузовместимости; потребность в завозе '(вывозе) груза; стоимости перевозок груза (расстояние, время) . Для решения задачи маршрутизации составляется табл:

	A	B
Q1
Qn

В каждом столбце Вi в правой колонке указана стоимость (расстояние, время) на проезд от i-го пункта до любого другого (Вi+1, Вi+2, ...), а слева величины, характеризующие выигрыши, которые получают в результате объединения соотвествующих маршрутов в один.

Величина сокращения пробега автотранспортного средства при объединении маршрутовA-Bi-A и A-Bj-A (c 95)

Количество груза	J
Q1		В1
….	….	….	….
Qi	Ji	…	….	Bi

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

Кроме того, к матрице выигрышей присоединяется отдельный столбец (значения 0; I или 2) индикаторов J пунктов В.. Индикатор Ji строки В_i показывает, каким является пункт: внутренним (J =О), первым или последним (J = 1) в развозочном или включен еще в маятниковый маршрут вида А — В_i — А (J = 2) . Постепенно производится объединение маятниковых маршрутов в кольцевые (от большего выигрыша к меньшему). Затем в соответствующих строках меняются элементы первого и второго столбцов: в первых клетках указывается начальная загрузка автомобиля на объединенном маршруте и новые номера индикаторов. Максимальный выигрыш отыскивают в строках, которые соответствуют пунктам с индикаторами J=1 и J=2.

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

1)Нахождение КСС – вначале выбирают звено минимальной длины и вклячают его в КСС, затем рассм все звенья связанные с одной из своих вершин с выбранной ранее частью кратчайшей транспортной сети. Из них выбирают наименьшее не соединяющее 2 включенные в сеть вершины и присоединяют к ранее образованной части. Действия продолжаются до тех пор пока не будут выбраны все n вершин сети связанные с помощью n-1 звеньев.

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

3)Определение очередности объезда пунктов маршрута отсчитывая с начального осуществляется методом сумм, для которого строится таблица в виде симметричной матрицы. По главной диагонали расположены пункты маршрута , цифры указывают на кратчайшие расстояния между ними. Дополнительно в матрице имеется итоговая строка сумм по каждому столбцу. Начальный маршрут строится из 3 пунктов с наибольшей суммой. Затем в него вклячают очередной пункт с максим суммой по столбцу, который поочередно рассматривают между каждой соседней парой пунктов. Прирост пробега автомобилей на маршруте для каждого случая находят по формуле L_kp=L_ki-L_ip-L_kp где L- расстояния между пунктами тр сети, к р і – соотв индексы первого и второго соседних пунктов, а также включаемого пункта. Из полученных величин L_kp выбирают миним между пунктами к и р окончательно включают і-й пункт. Действия продолжаются до полного набора, в результате получаем миним или близкий к нему путь.

4)проверка возможности одновременного развоза и сбора груза на маршруте. Последовательность развоза и сбора груза аналогична маршруту объезда пунктов, полученному на 3 этапе расчетов. Объем груза при выходе из пункта j

Q_j,j+1=Q_j-1,j – Q_pj + Q_cj где Q_j,j+1 и Q_j-1,j – соотв объемы перевозимого груза на участке маршрута _j,j+1 (при выходе из пункта j) и на предшествующем участке j-1, j; Q_pj Q_cj – соотв объемы разгрузки и загрузки в пункте j.

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