Полная версия

Главная arrow Логистика arrow ЛОГИСТИКА: ТЕОРИЯ И ПРАКТИКА ПРОЕКТИРОВАНИЯ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

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

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

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

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

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

i

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

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

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

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

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

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

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

Введем ряд определений. Маршрутной цепочкой назовем последовательность определенным образом связанных и чередующихся ездок с грузом и ездок без грузаxig —ytp—x/ft —... —ym_,.п.

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

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

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

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

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

%г$

Замкнутый s-маршрут

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

Кольцевой s-маршрут

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

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

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

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

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

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

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

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

  • [1] Планы {хД и {уД выражаем в одних и тех же единицах: тонны, автомобили, автомобиле-ездки и пр. При расчетах необходимо учитывать класс грузаи величину коэффициента использования грузоподъемности.
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>