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

Заданы: матрица , т расстояний пробегов без грузов между Bj-пунктами разгрузки (j = 1:п) и Ai.-пунктами погрузки (i = I: т) (без нарушения общности задачи можно предположить, что , где –расстояния пробегов с грузом), план перевозок грузов , который может быть получен предварительным решением L транспортных задач закрепления потребителей за поставщиками различных видов груза, число которых равно L.

При этом необходимо найти такую последовательность ездок с грузом и ездок без груза ^[1], чередующихся между собой , чтобы холостой пробег подвижного состава был бы минимальным и при этом выполнялись следующие ограничения:

• число ездок без груза в Аi-пункт погрузки равняется числу ездок с грузом из Ai-пункта в Вj-пункты ():

(4.34)

• число ездок без груза из Вj-пункта разгрузки равняется

числу ездок с грузом в Вj-пункт из пунктов:

(4.35)

(4.36)

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

(4.37)

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

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

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

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

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

1) таблицу связей (ТС № 1), в которой записываем заданный план перевозок груза () из пунктов в пункты ;

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

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

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

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

Однозвенный s-маршрут назовем замкнутым, если в

, i = р (рис. 4.10). На первом шаге такие маршруты назовем маятниковыми.

Последовательность формирования маршрутных цепочек такова: сначала выписываем планы из ТС № 1 и из ТС №2; формируем все возможные однозвенные (В = 1) связанные маршруты; выбираем из них замкнутые и определяем величину груза, перевозимую на маятниковых (В = 1) s-маршрутах

; величину вычеркиваем из ТС № 1 и ТС №2, включающих ездкии. Одна из этих величин (или обе) обращается в нуль:

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

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

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

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

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

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

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

Таким образом, последовательность пар индексов назовем k-звенным маршрутом, если выполнены следующие условия:

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

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

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

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

1. Число В-ездки с грузом в одном обороте маршрута. В описанных методах теоретически , где т – число пунктов погрузки, но при перевозках массовых грузов в крупных городах часто т = 15–20. Выполнение маршрутов с таким числом звеньев не представляется возможным как из-за ограничения продолжительности пребывания автомобиля на линии, так и из-за увеличения числа пунктов погрузки и разгрузки на маршруте, что в свою очередь приводит к необходимости поисков водителем новых адресов этих пунктов. Описанные ранее попытки регулировать число В носят неформализованный характер, в значительной степени субъективны и практически не позволяют оценить погрешности отклонений от оптимального плана.

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

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

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

4. Продолжительность пребывания автомобиля в наряде. На внутригородских перевозках такое ограничение весьма существенно. В изложенных методах это ограничение не учитывается.

5. Соответствие видов грузов типам подвижного состава. В упомянутых выше методах предполагается, что любой из грузов плана {xij} может перевозиться на любом из типов подвижного состава, участвующих в перевозках. На практике это справедливо (в основном) для грузов, перевозимых автомобилями- самосвалами, и еще для некоторых видов грузов. Но для многих грузов (например, железобетонные изделия) неучитывание данного ограничения недопустимо и не позволяет получать наилучшие результаты.

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

В работе [5] предложен метод решения задачи маршрутизации, учитывающий допустимость ограничений по вышеперечисленным параметрам.