Модели маршрутизации при планировании потоков

Постановка задачи маршрутизации без учета ограничивающих параметров

Заданы: матрица |Ы|п, т расстояний пробегов без грузов между^{-пунктами} разгрузки (j = 1: п) и A-пунктами погрузки (i = I: т) (без нарушения общности задачи можно предположить, что су = с_{., где Су — расстояния пробегов с грузом), план перевозок грузов {х.}, который может быть получен предварительным решением L транспортных задач закрепления потребителей за поставщиками различных видов груза, число которых равно L.

При этом необходимо найти такую последовательность ездок с грузом {х"> и ездок без груза {у.}^[1], чередующихся между собой x_tg -уx_fn -. -у_т_j__n, чтобы холостой пробег подвижного состава" был бы минимальным и при этом выполнялись следующие ограничения:

• число ездок без груза в А_г-пункт погрузки равняется числу ездок с грузом из A-пункта в В₍-пункты (а, = ?ху):

• число ездок без груза из В_у-пункта разгрузки равняется числу ездок с грузом в Впункт из пунктов, А (Ь, = ^:

i

пробег без груза должен быть минимален:

При этом выполняются следующие условия:

В уравнениях (4.34) и (4.35) условно полагаем, что одна ездка осуществляется в пункт Л из автотранспортного предприятия (остальные из пунктов В.) и одна ездка выполняется из пунктов Bj в автотранспортное предприятие (остальные в пункты Д).

Задача маршрутизации в такой постановке может быть решена двумя методами: методом таблиц связей [10] и методом совмещенных матриц [4]. Решение и тем и другим методом состоит из двух этапов: первый этап — решение задачи на минимум пробегов без груза; второй этап — построение маршрутных цепочек.

Первый этап — задача (4.34)—(4.37) решается как транспортная задача линейного программирования любым из известных способов. Различия в методах таблиц связей и совмещенных матриц появляются на втором этапе решения.

В методе таблиц связей после вычислений первого этапа имеем две таблицы:

• 1) таблицу связей (ТС № 1), в которой записываем заданный план перевозок груза ({хЛ) из пунктов Д в пункты В.;
• 2) таблицу связей (ТС № 2), в которой записываем полученный в результате решения на первом этапе план (у._;) ездок без груза из пунктов В в пункты Д.

Введем ряд определений. Маршрутной цепочкой назовем последовательность определенным образом связанных и чередующихся ездок с грузом и ездок без грузаx_ig —y_tp—x_/ft —… —y_m_,._п.

Ездку с грузом x_jg будем называть связанной с ездкой без груза, если индексы пункта разгрузки совпадают (g = t).

Однозвенным назовем маршрут, в котором ездку с грузом будем считать связанной с ездкой без груза, если x_jg—y_gp (число звеньев в маршруте обозначим через В).

Однозвенный s-маршрут назовем замкнутым, если в х^ — у^¹, i = р (рис. 4.10). На первом шаге такие маршруты назовем маятниковыми.

Последовательность формирования маршрутных цепочек такова: сначала выписываем планы {х^} из ТС № 1 и {у^} из ТС № 2; формируем все возможные однозвенные (В = 1) связанные маршруты; выбираем из них замкнутые и определяем величину груза, перевозимую на маятниковых (В = 1) s-маршрутах 0^ = min (x^;у^р); величину 0⁽,^]) вычеркиваем из ТС № 1 и ТС № 2, включающих ездки х^^} и ygp. Одна из этих величин (или обе) обращается в нуль:

Первый шаг заканчиваем на выборе всех возможных замкнутых однозвенных маршрутов и на соответствующих изменениях величин планов {х_г} и {у.Д в ТС № 1 и ТС № 2.

%г$

Рис. 4.10. Замкнутый s-маршрут.

Рис. 4.11. Кольцевой s-маршрут.

Если в таблицах связей не все х-^ и х™ равны нулю, то переходим ко второму шагу. На втором шаге формируем маршрутные цепочки из двух звеньев (В = 2), которые назовем связанными, если индекс пункта погрузки, принадлежащий ездке без груза первого звена, совпадает с индексом пункта погрузки, принадлежащим ездке с грузом второго звена: х^—у._г — х_п —y_th. Маршрутную цепочку из двух звеньев назовем замкнутой, если индекс пункта погрузки, принадлежащий ездке с грузом первого звена, совпадает с индексом пункта погрузки, принадлежащим ездке без груза второго звена (g = k). Такие s-маршруты называют кольцевыми (рис. 4.11).

Снова определяем величину груза, перевозимого на s-маршрутах с В = 2:

На величину 0'²⁾ уменьшаем в ТС № 1 и ТС № 2 все участвующие в полученном маршруте ездки.

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

Таким образом, последовательность пар индексовМ= {(г,),) (i"j₂),…, (i_kj_k)} назовем /с-звенным маршрутом, если выполнены следующие условия:

Величину 0_S =тт (х$;у[$;х{/₁⁾₂;…; х??;уЩ) назовем интенсивностью маршрута. Будем считать маршрут зафиксированным, если он выписан, определена его интенсивность и в таблицах связей величины Ху и уji, входящие в маршрут, уменьшены на 0_s, т. е. выполнено преобразование по формулам:

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

• [1] Планы {хД и {уД выражаем в одних и тех же единицах: тонны, автомобили, автомобиле-ездки и пр. При расчетах необходимо учитывать класс грузаи величину коэффициента использования грузоподъемности.