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

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

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

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

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

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

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

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

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

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

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

Величины выигрышей, которые необходимо знать для дальнейших расчетов, представлены в табл. 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.

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

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