А.Ю. Тюрин Методы организации работы автомобильного транспорта. Методические указания к практическим занятиям по курсу Транспортно-технологические системы

1

Практическое занятие №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-й пункт погрузки, с тем чтобы общий пробег автомобилей был минимальным. Иными словами, задача сводится к нахождению оптимального плана возврата (подач) порожних автомобилей.

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

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

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

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

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

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

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

3

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

Таблица 1.2

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

4

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

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

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

Составление матрицы

Построение допустимого исходного плана

Подсчет количества занятых клеток матрицы (N) и сравнение его с

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

Проверка незанятых клеток матрицы с целью отыскания потенциальных

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

Расстановка знаков «+» и «–» по вершинам цепочки

Отыскание среди загрузок со знаком «–» наименьшей по величине

Изменение на эту величину загрузок на вершинах контура

Решение закончено: оптимальный план возврата порожних автомобилей составлен

Рис. 1. Блок-схема последовательности вычислений

Коэффициенты 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.

6

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

значение потенциала помещают в левый верхний угол клетки.

В табл. 1.4 в результате расчетов получилось пять потенциальных клеток. Выбирают клетку с максимальным потенциалом (A1 B4) и составляют контур пересчета. Согласно алгоритму (рис. 1) расставляют знаки «+» и «-» по вершинам контура и среди клеток со знаком «-» выбирают минимальное число. В нашем примере min=13 (клетка A2 B4).

На минимальную загрузку (13) делают перераспределение по вершинам контура (в клетки со знаком «+» прибавляют 13, а из клеток со знаком «-» отнимают 13). После перераспределения объемов новые значения (в скобках) заносят в новую матрицу (табл. 1.5).

7

8

В результате решения получаем оптимальный план возврата порожних автомобилей (в матрице нет больше потенциальных клеток) (табл. 1.10). Полученный оптимальный план совмещают с планомзаявкой на перевозку грузов (см. табл. 1.2), получая в результате совмещенный план (табл. 1.11).

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