Маршрутизация

1

1. ОБЩИЕ ПОЛОЖЕНИЯ

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

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

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

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

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

2

2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ ПРАКТИЧЕСКОЙ РАБОТЫ

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

Цель: определить оптимальные маршруты при перевозке массовых грузов большими партиями (помашинными отправками).

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

Пусть груз, сосредоточенный в пунктах А1, А2, ..., Аi, ..., Аm в количествах соответственно а1, а2, ..., аi, ..., аm, необходимо доставить в пункты В1, В2, ..., Вj, ..., Вn в количествах b1, b2, ..., bj, ..., bn тонн. Объем перевозок из i-го пункта отправления в j-й пункт назначения составляет Pij тонн. Будем полагать, что для перевозок используют условные однотонные (q = 1 т) автомобили.

При выполнении перевозок в пункт Вj доставляют

тонн груза и соответственно прибывает такое же количество условных автомобилей, которые после разгрузки подают в пункты погрузки Аi. Так как из пунктов Аi нужно вывезти

тонн груза, то для пунктов А1, А2, ..., Аi, ..., Аm необходимо осуществить соответственно а1, а2, ..., аi, ..., аm подач порожних автомобилей.

Расстояния (lji = lij) от каждого потребителя Вj до каждого поставщика Аi известны.

Требуется определить количество xji подач порожних условных однотонных автомобилей от j-го пункта разгрузки в i-й пункт погрузки, с тем чтобы общий пробег автомобилей был минимальным. Иными словами, задача сводится к нахождению оптимального плана возврата (подач) порожних автомобилей.

3

Порожний пробег при выполнении из j-го в i-й пункт xji подач условных однотонных автомобилей равен ljixji. Тогда их суммарный пробег:

Поскольку количество ездок равно xji/q ст, то фактический пробег автомобиля с заданной грузоподъемностью q равен

Математическая формулировка задачи определяется следующим образом. Требуется определить совокупность величин x ji 0 (план возврата порожних автомобилей), удовлетворяю-

щих условиям

j1

иминимизирующих функцию

j 1i 1

Поскольку количество завозимых грузов равно количеству вывозимых, то справедливо равенство

mn

Данная задача представляет собой классическую задачу линейного программирования. Рассмотрим методику ее решения на примере.

Заявки на перевозки, включенные в план автотранспортного предприятия, перечислены в таблице 1.1. На основании заявок на перевозки составлена матрица (таблица 1.2), в которой указаны количества тонн грузов, вывозимых из каждого пункта Аi (i = 1, 2, 3, 4) и завозимых в каждый пункт Вj (j = 1, 2, 3, 4, 5, 6, 7), а также расстояния между этими пунктами (они представлены в верхнем правом углу соответствующих клеток).

4

Таблица 1.1 – Заявки на перевозки

Таблица 1.2 – План-заявка на перевозку грузов (матричная форма)

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

В матрицу (таблица 1.3) заносятся грузоотправители, грузополучатели, расстояния между ними, данные наличия порожних автомобилей и потребители. Последовательность вычислений при составлении оптимального плана показана на схеме (рисунок 1).

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

6

Расчет индексов:

1. Для занятых клеток матрицы должно соблюдаться следующее условие:

где Lij – расстояние между грузоотправителем и грузополучателем.

Коэффициенты Ui и Vj рассчитывают следующим образом: напротив любой загруженной клетки в дополнительным строке или столбце записывают коэффициент 0 (например для потребителя B1 V1 =0). Далее, двигаясь по цепочке загруженных клеток, по условию (1.6) находят все остальные коэффициенты. Например, коэффициент при A1 U1 = 1,9 – 0 =1,9; при B2 V2 =6,66 - U1 = = 6,66 - 1,9 = 4,76; при A4 U4 = 7,78 - V2 = 7,78 - 4,76 = 3,02 и т.д. Результаты заносят в таблицу 1.4.

Таблица 1.3 – Матрица

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

8

Таблица 1.5 – План возврата порожних автомобилей

2. А1 В6

Min = 18

A1 B6 – B6 A3 – A3 B7 – B7 A4 – А4 В2 – В2 А1

Последующие этапы представлены в таблицах 1.6 -1.9. Таблица 1.6 – План возврата порожних автомобилей