новая папка 1 / 233236

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра управления автотранспортом

Организация перевозочных услуг и безопасность транспортного процесса

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению практических работ

Составители В.А. КОРЧАГИН, Ю.Н. РИЗАЕВА

Липецк Липецкий государственный технический университет

2013

2667

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра управления автотранспортом

Организация перевозочных услуг и безопасность транспортного процесса

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению практических работ

Составители В.А. КОРЧАГИН, Ю.Н. РИЗАЕВА

Липецк Липецкий государственный технический университет

2013

1.Оптимизация маятниковых маршрутов

Вработе поставлена задача оптимизировать перевозку груза с центрального склада потребителям при использовании однородного подвижного состава. Количество подвижного состава, используемого для перевозок данного вида груза, равно 6, так как каждому потребителю направляется по одному подвижному составу КамАЗ 4308, грузоподъемностью

5,5 т.

Имеется 6 потребителей, bi – количество ездок, которые нужно сделать к j-му потребителю, tj – время ездки от центрального склада j-му потребителю,

Т– время пребывания автомобиля в наряде, которое не может быть превышено

(иначе задача не имеет решения).

Очевидно, что следует выполнить 23 ездки, из них 5 по 60 мин, 4 по 120 мин, 3 по 50 мин, 3 по 30 мин, 4 по 60 мин и 4 по 40 мин, в сумме 1420 мин.

Поскольку продолжительность смены Т=8×60=480 мин., число автомобилей должно быть не менее 1420:480=3 автомобилей (округлено до целого).

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

Таким образом, решение задачи нужно искать в интервале 3≤ Z ≥4 автомобилей. Задача сводится к тому, чтобы попытаться ограничиться минимальным числом автомобилей.

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

Суммарный фонд рабочего времени 3-х автомобилей Т ·Z=480· 3=1440 мин. Трудозатраты на все 23 ездки составят 1420 мин. Таким образом,

существует запас рабочего времени: 1440-1420=20 мин.

Первый шаг. Берем 5 ездок к 1-му потребителю, 1 ездку ко 2-му потребителю и 1 ездку к 3-му потребителю. Получается: 60·5+120·1+50·1=470 мин. Недоиспользуется время первого автомобиля на 480-470=10 мин, что допустимо, так как запас рабочего времени равен 20 мин. Если считать наше решение верным, еще остается запас рабочего времени 20-10=10 мин.

На втором шаге можно взять оставшиеся 3 ездки ко второму потребителю и 2 ездки – к третьему. Получится 120·3+50·2=460 мин, недоиспользовано

20 мин, а запас всего лишь 10.Таким образом, задача на этом уровне не решается.

Таблица 3

Промежуточный результат после второго шага

120·3+50·1+30·2=470 мин, вновь будет недоиспользовано 10 мин. Рабочего времени автомобиля, выполняющего перевозки. Такая ситуация приемлема, однако запас рабочего времени останется равным нулю.

Четвертый шаг. Промежуточный результат после третьего шага.

Таблица 5

Промежуточный результат после третьего шага

Берем 1 ездку к третьему потребителю, 1 ездку к четвертому и по 4 ездки к пятому и шестому потребителю. Получаем 50·1+30·1+60·4+40·4=480 мин. Для третьего автомобиля запас рабочего времени равен нулю.

Задача решена, результат приемлем. Требуется 3 автомобиля. Первый – обслуживает первого потребителя, первый и второй автомобили – второго и третьего потребителей, третий – третьего, четвертого,пятогои шестогопотребителей.

2. Оптимальное построение кольцевых маршрутов

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

Таблица 6

Треугольная матрица

Алгоритм решения состоит из нескольких шагов.

Шаг 1. Исходную матрицу (см. табл. 6) заполнили так, чтобы матрица стала симметричной по отношению к главной диагонали (см. табл. 7).

Таблица 7

Симметричная матрица

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

нулевой элемент. Для получения приведенной матрицы в каждой строке находим минимальный элемент и выписываем его с правой стороны матрицы (см. табл.7). Это вектор-столбец вида (3, 3, 6, 5, 4). Из элементов соответствующей строки вычитаем минимальное значение элемента этой строки и получаем приведенную матрицу по строкам (табл. 8).

Таблица 8

Приведенная матрица по строкам

Затем в каждом столбце находим минимальный элемент и выписываем их внизу матрицы (см. табл. 8). Это вектор-строка вида (0, 0, 2, 2, 0). Из элементов соответствующего столбца вычитается минимальное значение элемента этого столбца, и получают приведенную матрицу (табл. 9). Математически доказано, что сделанные описанным способом процедуры получения приведенной матрицы (см. табл. 9) сохраняют свойства исходной матрицы.

Элемент приведенной матрицы cij будем называть полюсом, если cij = 0. Таблица 9

Шаг 3. Последовательно для каждого полюса выполнено следующее:

-для строки i0, где находится полюс, найден минимальный элемент этой строки, исключая значение только для самого этого полюса;

-для столбца j0, где находится полюс, найден минимальный элемент этого столбца, исключая значение только для самого этого полюса.

Найдено значение параметра d( i0, j0) по формуле

Если таких значений будет несколько, можно выбрать любое. Выбранный параметр h(i0,j0) показывает направление движения: нужно двигаться из пункта i0 в пункт j0. Чтобы не было возврата, делаем запрет, полагая c(j0,i0) = \\\\.

В нашем решении имеем:

h35 = 3 и h53 = 3. Выбран первый случай: h(i0,j0) = h35. Так как i0 = 3, а j0 = 5, то движение происходит из пункта 3 в пункт 5 (рис. 1, а.). Запрет будет иметь вид с53=\\\\.

Шаг 5. Вычеркиваем строку i0 и столбец j0, сохраняя номера строк и столбцов матрицы неизменными (табл. 10).

Шаг 6. Если после вычеркивания в полученной матрице нет ни одного полюса, то необходимо создать полюса, применяя процедуры, описанные для шага 2. Если после вычеркивания получаем матрицу (2Х2), то эту матрицу будем называть тривиальной, так как она позволяет однозначно достроить маршрут до кольцевого маршрута и получить решение задачи.

Так как в табл. 10 имеются полюса, то для каждого полюса найдены d-параметры:

d12= 2 + 0 = 2, d21= 0 + 0 = 0, d24= 0 + 2 = 2, d42= 2 + 0 = 2, d51= 3 + 0 = 3.

h-параметр найден: h(i0,j0) = d51 = 3.

Вычеркиваются строка i0 = 5 и столбец j0 = 1, и полагаем элемент c15=\\\\ (этот элемент отсутствует). Проводим стрелку от пункта 5 к пункту 1 согласно процедуре шага 4 (рис. 1, б). Однако, чтобы избежать зацикливания 3 - 5 - 1 - 3, полагаем с13=\\\\.

После этого составлена новая матрица (табл. 11).

Таблица 11

Промежуточная матрица