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

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

Для большинства компаний затраты на транспортировку составляют от 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-й пункт.

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

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

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

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