Маршрутизация транспортных потоков

Транспортировка – изменение местонахождения товара с помощью транспортного средства.

Для большинства компаний затраты на транспортировку составляют от 1/3 до 2/3 логистических затрат, поэтому их оптимизация – важная задача. Каждая транспортная система состоит из 3 элементов: транспортируемые грузы, средства транспортировки и процесс транспортировки. Различают внутрипроизводственную и внешнюю транспортировки.

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

Выбор маршрута зависит от множества факторов:

– количества, типа и технического состояния подвижного состава;

– наличия и эксплуатационных свойств различных транспортных путей и сетей;

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

Модель классической транспортной задачи: однородный продукт, находящийся в К пунктах производства в количестве P₁, P₂, …, P_i, …, P_K требуется доставить в L пунктов потребления. Потребность в продукции в этих пунктах равна S₁, S₂, …, S_j, …, S_L. Полагаем, что общий объем поставляемой продукции равен объему потребности:

.

Стоимость транспортных издержек по перевозке единицы продукции из любого пункта производства в любой пункт потребления C_ij, где: i – номер пункта производства; j – номер пункта потребления).

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

Целевая функция: продукция, отправляемая из пунктов производства: продукция, поступающая в пункты потребления x_ij > 0.

Задача о коммивояжере: имеются города – 1 … n. Выехав из одного города коммивояжер должен объехать все остальные города, побывав в каждом из них по одному разу и вернуться в исходный город.

Известны расстояния между городами – C_ij (i, j = 1 … n).

x_ij = 1 – если коммивояжер переезжает из i-го пункта в j-й пункт.

x_ij = 0 – если коммивояжер не переезжает из i-го пункта в j-й пункт.

Целевая функция:

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

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

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