Менеджмент

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

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

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

Содержание:

Введение

1. Описание района перевозок и формирование транспортной сети региона

2. Определение кратчайших расстояний и кратчайших путей следования

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

. Определение потребности в транспортных средствах для работы на маршрутах

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

. Сравнительный анализ существующего и предлагаемого вариантов маршрутов

Заключение

список литературы

Приложение А

Приложение Б

Введение

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

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

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

В данной курсовой работе производится определение наиболее опти-мального плана развоза 3-х видов груза в 6 магазинов города Гомеля.

Для планирования перевозок грузов необходимо решить следующие задачи:

¾определить кратчайшие расстояния между пунктами транспортной сети;

¾оптимизировать грузовые потоки;

¾маршрутизировать перевозки грузов;

¾выбрать подвижной состав для движения по маршрутам;

рассчитать основные технико-эксплуатационные показатели работы подвижного состава при осуществлении перевозок.

. Описание района перевозок и формирование транспортной сети региона

В практике грузовых перевозок автомобильным транспортом исходными данными выступают: улично-дорожная сеть с указанием расположения пункта погрузки и пунктов выгрузки (приложение А); объемы поставки номенклатуры грузов каждому конечному потребителю (таблица 1.1); имеющийся парк грузовых автотранспортных средств (таблица 1.2).

Таблица 1.1 — Номенклатура и количества доставляемого груза

Наименование грузаКласс грузаПункт назначенияМасса, тоннМолочные изделия в бумажных пакетах, затаренные в ящиках3М10,22М20,25М30,51М40,28М50,42М60,47Мясо кур в ящиках1М10,31М20,32М30,34М40,29М50,28М60,26Вода минеральная в полиэтиленовых ящиках2М10,15М20,13М30,16М40,15М50,1М60,19

Таблица 1.2 — Имеющийся парк автомобильных транспортных средств

Марка автомобиляГрузоподъемность, тоннКоличество, ед.МАЗ 437040-0204,72ЗИЛ 5301ВА2,35

Районом перевозок является советский район города Гомеля. В транспортную сеть входят городские улицы и магазины. Крупнейшими улицами, входящими в состав транспортной сети, являются: ул. Бочкина, ул. Богдана Хмельницкого, ул. Барыкина. Средняя скорость движения по улицам транспортной сети 25 км/ч. Все улицы в данном районе имеют усовершенствованное покрытие.

В 1-ом пункте находится база (Б), из которой осуществляется поставка товаров в магазины. Магазины расположены в пунктах 1-6.

По транспортной сети осуществляется перевозка 3-х видов груза.

Молочные изделия в бумажных пакетах, затаренные в ящиках являются грузом третьего класса, имеет средний коэффициент использования грузоподъемности =0,6. объем данного груза, предназначенный к перевозке — 2150 кг. объем потребления данного груза в грузопоглащающих пунктах составляет: М1 — 220 кг; М2 — 250 кг; М3 — 510 кг; М4 — 280 кг; М5 — 420 кг; М6 -470 кг.

второй вид груза — мясо кур в ящиках, является грузом первого класса использования грузоподъемности с коэффициентом использования грузоподъемности =1. объем этого груза, предназначенный к перевозке — 1800кг. объем потребления груза в грузопоглащающих пунктах составляет: М1 — 310 кг; М2 — 320 кг; М3 — 340 кг; М4 — 290 кг; М5 — 280 кг; М6- 260 кг.

третий вид перевозимого груза — вода минеральная в полиэтиленовых ящиках. Данный груз является грузом второго класса со средним коэффициентом использования грузоподъемности = 0,8. объем данного груза, предназначенный к перевозке — 1010 кг. объем потребления груза 3-го типа в грузопоглащающих пунктах составляет: М1 — 150 кг; М2 — 130 кг; М3 — 160 кг; М4 — 150 кг; М5 — 100 кг; М6 — 190 кг.

Для выполнения перевозок могут использоваться автомобильные транспортные средства 2-х марок:

МАЗ 437040-020, грузоподъемностью 4,7 т, в количестве 2 единиц;

ЗИЛ 5301ВА, грузоподъемностью 2,3 т, в количестве 5 единиц.

На основании исходной схемы улично-дорожной сети строим транспортную сеть (рисунок 1.1).

2. Определение кратчайших расстояний и кратчайших путей следования

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

Таблица 2.1- Расстояния между пунктами транспортировки грузов

ЗвеноДлина, мЗвеноДлина, мБ-1350017-64001-730006-1833007-2200018-135002-85001-2910008-9100029-304009-1070030-3150010-11100031-3240011-370032-333003-12200033-4170012-4300029-3430004-1350031-35300013-14250032-36300015-1425007-3410005-15100034-3510005-16200035-3670016-17150036-37100037-3870028-1380034-8200018-23100035-9200023-2440036-10200024-2550037-11200025-2640023-29350026-27130024-30350027-1480025-31350020-24100026-32350021-26100027-28250017-19220019-2040016-22100020-2180022-15200022-211200

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

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

)метод потенциалов;

)табличный метод;

)определение кратчайших расстояний на ЭВМ.

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

Таблица 2.2- Матрица кратчайших расстояний между пунктами транспортной сети района

Начальный пунктКонечный пунктБМ1М2М3М4М5М6Б-350085001240078001420010300М13500-500089004300107006800М285005000-390088001530011800М31240089003900-50001150014900М47800430088005000-65009900М5142001070015300115006500-3900М6103006800118001490099003900-

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

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

Приведем матрицу расстояний по строкам (таблица 3.1)

Таблица 3.1 — Приведение матрицы по строкам

Из/ВБМ1М2М3М4М5М6Б-3500850012400780014200103003500М13500-5000890043001070068003500М285005000-3900880015300118003900М31240089003900-500011500149003900М47800430088005000-650099004300М5142001070015300115006500-39003900М6103006800118001490099003900-3900

Приведем матрицу расстояний по столбцам (таблица 3.2)

Таблица 3.2 — Приведение матрицы по столбцам

Из/ВБМ1М2М3М4М5М6Б-0500089004300107006800М10-1500540080072003300М246001100-04900114007900М3850050000-1100760011000М4350004500700-22005600М51030068001140076002600-0М66400290079001100060000-000080000

полностью приведенная матрица приведена в таблице 3.3.

Таблица 3.3 — полностью приведенная матрица

Из/ВБМ1М2М3М4М5М6Б-0500089003500107006800М10-15005400072003300М246001100-04100114007900М3850050000-300760011000М4350004500700-22005600М51030068001140076001800-0М66400290079001100052000-

Определим нижнюю границу множества Гамильтоновых контуров:

= 27700

Каждый нуль в приведенной матрице (см. таблицу 1.6) условно заменяем на и находим сумму констант приведения . значения записываем в соответствующие клетки рядом с нулями (таблица 3.4).

Таблица 3.4 — Определение сумм констант приведения

Из/ВБМ1М2М3М4М5М6Б-0(3500)500089003500107006800М10(3500)-150054000(300)72003300М246001100-0(1800)4100114007900М3850050000(1800)-300760011000М435000(700)4500700-22005600М51030068001140076001800-0(5100)М66400290079001100052000(5100)-

Априорно исключаем из гамильтонова контура дугу (6,7), заменяя элементы а7,6 = 0 в матрице расстояний на . В результате исключения данной дуги будет образовано подмножество гамильтоновых контуров {}.

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

Таблица 3.5 — Исключение 6 строки и 7 столбца

Из/ВБМ1М2М3М4М5Б050008900350010700М101500540007200М2460011000410011400М38500500003007600М43500045007002200М6640029007900110005200

Таблица 3.6 — Приведение матрицы по строкам

Из/ВБМ1М2М3М4М5Б0500089003500107000М1015005400072000М24600110004100114000М385005000030076000М435000450070022000М66400290079001100052002900

Таблица 3.7- Приведение матрицы по столбцам

Из/ВБМ1М2М3М4М5Б050008900350010700М101500540007200М2460011000410011400М38500500003007600М43500045007002200М635000500081002300000002200

Тогда а Матрица, полученная после приведения по строкам и столбцам приведена в таблице 3.8.

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

Таблица 3.8 — полностью приведенная матрица

Из/ВБМ1М2М3М4М5Б05000890035008500М101500540005000М246001100041009200М38500500003005400М43500045007000М635000500081002300

Таблица 3.9 — Определение сумм констант приведения

Из/ВБМ1М2М3М4М5Б0(3500)5000890035008500М10(3500)150054000(300)5000М2460011000(1800)41009200М3850050000(1800)3005400М435000(0)45007000(5000)М635000(3500)500081002300

Из таблицы 3.9 видно, что наибольшее строки и 6 столбца и составляет 5000. Априорно исключаем из гамильтонова контура дугу (5,6) и проводим расчеты аналогичные предыдущим.

Таблица 3.10 — Исключение 5й строки и 6го столбца

Из/ВБМ1М2М3М4Б0500089003500М10150054000М24600110004100М3850050000300М63500050008100

Таблица 3.11 — Приведение матрицы по строкам

Из/ВБМ1М2М3М4Б05000890035000М101500540000М246001100041000М38500500003000М635000500081000

Таблица 3.12 — Приведение матрицы по столбцам

Из/ВБМ1М2М3М4Б0500089003500М10150054000М24600110004100М3850050000300М6350005000810000000

Тогда а Матрица, полученная после приведения по строкам и столбцам приведена в таблице 3.13.

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

Таблица 3.13 — полностью приведенная матрица

Из/ВБМ1М2М3М4Б0500089003500М10150054000М24600110004100М3850050000300М63500050008100

Таблица 3.14 — Определение сумм констант приведения

Из/ВБМ1М2М3М4Б0(3500)500089003500М10(3500)150054000(300)М2460011000(6500)4100М3850050000(1800)300М63500050008100

Из таблицы 3.14 видно, что наибольшее строки и 4 столбца и составляет 6500. Априорно исключаем из гамильтонова контура дугу (3,4), заменяя элемент а4,3 = 3100 в матрице расстояний на и проводим расчеты аналогичные предыдущим (таблицы 3.15-3.18)

Таблица 3.15 — Исключение 3 строки и 4 столбца

Из/ВБМ1М2М4Б050003500М1015000М385005000300М6350005000Таблица 3.16 — Приведение матрицы по строкам

Из/ВБМ1М2М4Б0500035000М10150000М385005000300300М63500050000

Таблица 3.17 — Приведение матрицы по столбцам

Из/ВБМ1М2М4Б050003500М1015000М3820047000М63500050000015000

Тогда а Матрица, полученная после приведения по строкам и столбцам приведена в таблице 3.18.

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

Таблица 3.18 — полностью приведенная матрица

Из/ВБМ1М2М4Б035003500М1000М3820047000М6350003500

Таблица 3.19 — Определение сумм констант приведения

Из/ВБМ1М2М4Б0(3500)35003500М10(3500)0(3500)0(0)М3820047000(4700)М6350003500

Из таблицы 3.19 видно, что наибольшее строки и 3 столбца и составляет 4700.

Априорно исключаем из гамильтонова контура дугу (3,4), заменяя элемент а4,3 = 3500 в матрице расстояний на и проводим расчеты аналогичные предыдущим (таблицы 3.20-3.23)

Таблица 3.20 — Исключение 4 строки и 3 столбца

Из/ВБМ1М2Б03500М100М635000

Таблица 3.21 — Приведение матрицы по строкам

Из/ВБМ1М2Б035000М1000М6350000

Таблица 3.22 — Приведение матрицы по столбцам

Из/ВБМ1М2Б03500М100М635000000

Тогда а Матрица, полученная после приведения по строкам и столбцам приведена в таблице 3.23.

Таблица 3.23 — полностью приведенная матрица

Из/ВБМ1М2Б03500М100М635000

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

Таблица 3.24 — Определение сумм констант приведения

Из/ВБМ1М2Б0(3500)3500М10(3500)0(3500)М635000(3500)

Из таблицы 3.24 видно, что мы получили 4 одинаковых максимальных суммы констант приведения (3500). Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.Рассмотрим вариант (1,2).

Априорно исключаем из гамильтонова контура дугу (1,2), заменяя элемент а2,1 = 0 в матрице расстояний на и проводим расчеты аналогичные предыдущим (таблицы 3.25-3.28)

Таблица 3.25 — Исключение первой строки и второго столбца

Из/ВБМ2М100М63500Текущая Нижняя граница=34600.

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

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (М5,М6), (М4,М5), (М2, М3), (М3, М4), (Б, М1), (М1, М2), (М6, Б)

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

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

Минимальное значение имеет НГр=38100.

соответствующий оптимальный контур включает дуги: (М5,М6), (М4,М5), (М2, М3), (М3, М4), (Б, М1), (М1, М2), (М6, Б).

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

Таблица 3.19 Определение количества завозимого в каждый пункт груза

Пункт выгрузкиГрузМасса груза, тКоэффициент использования грузоподъемностиМасса груза с учетом коэффициента использования грузоподъемности, тОбщая масса груза, тоМ1Молочные изделия в бумажных пакетах, затаренные в ящиках0,220,60,3670,865Мясо кур в ящиках0,3110,31Вода минеральная в полиэтиленовых ящиках0,150,80,188М2Молочные изделия в бумажных пакетах, затаренные в ящиках0,250,60,4170,9Мясо кур в ящиках0,3210,32Вода минеральная в полиэтиленовых ящиках0,130,80,163М3Молочные изделия в бумажных пакетах, затаренные в ящиках0,510,60,851,39Мясо кур в ящиках0,3410,34Вода минеральная в полиэтиленовых ящиках0,160,80,2М4Молочные изделия в бумажных пакетах, затаренные в ящиках0,280,60,4670,945Мясо кур в ящиках0,2910,29Вода минеральная в полиэтиленовых ящиках0,150,80,188М5Молочные изделия в бумажных пакетах, затаренные в ящиках0,420,60,71,105Мясо кур в ящиках0,2810,28Вода минеральная в полиэтиленовых ящиках0,10,80,125М6Молочные изделия в бумажных пакетах, затаренные в ящиках 0,470,60,7831,281Мясо кур в ящиках0,2610,26Вода минеральная в полиэтиленовых ящиках0,190,80,238Итого-4,83-6,486

Согласно исходным данным, перевозка может быть осуществлена автомобилями 4-х марок: ЗИЛ-5301АО, грузоподъемностью 3 т; ГАЗ-3302, грузоподъемностью 1,5 т.; ЗИЛ-5301ВА, грузоподъемностью 2,3 т; МАЗ 437040-020, грузоподъемностью 4,7 т. Из таблицы 3.19 видно, что общая масса доставляемого груза, с учетом коэффициента использования грузоподъемности составляет 6,486 т. Исходя из вышесказанного, можно утверждать, что в данном случае необходимо использовать 1 автомобиль марки ЗИЛ-5301ВА и 1 автомобиль марки МАЗ 437040-020. Во втором перевозим: молочные изделия в бумажных пакетах и воду, затаренные в ящиках, в первом: мясо кур в ящиках. Такое утверждение основано на следующих умозаключениях:

должен быть перевезен весь груз;

приоритет необходимо отдавать автомобилям большей грузоподъемности, при этом должно обеспечиваться максимальное значение степени использования грузоподъемности автомобилей;

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

Рассмотрим существующий маршрут перевозки грузов для первого автомобиля:

Рассчитаем транспортную работу для данного маршрута и автомобиля:

Рассмотрим существующий маршрут перевозки грузов для второго автомобиля:

Рассчитаем транспортную работу для данного маршрута и автомобиля:

79378 тм

Общая транспортная работа на двух автомобилях:

Робщ =

Рассмотрим существующий маршрут перевозки грузов для первого автомобиля в обратном направлении, который и будет предлагаемым:

Рассчитаем транспортную работу для данного маршрута и автомобиля:

Рассмотрим существующий маршрут перевозки грузов для второго автомобиля:

Рассчитаем транспортную работу для данного маршрута и автомобиля в обратном направлении:

Общая транспортная работа на двух автомобилях в обратном направлении:

Робщ =

Исходя из того, что транспортная работа в обратном направлении больше чем в прямом, выбираем существующий маршрут в прямом направлении Б — М1 — М2 — М3 — М4 — М5- М6 — Б

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

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

К показателям, характеризующим степень использования ПС, относятся следующие показатели:

-коэффициент выпуска подвижного состава на линию, aв;

-коэффициент технической готовности подвижного состава, aт;

коэффициент статического использования грузоподъемности, gс;

коэффициент динамического использования грузоподъемности, gд;

коэффициент использования пробега, b;

средняя длина ездки, Lег;

среднее расстояние перевозки груза, Lгр;

время простоя ПС под погрузкой-разгрузкой, tпр;

время в наряде, Тн;

техническая скорость движения, Vт;

эксплуатационная скорость, Vэ.

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

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

gс = Qф / Q. (5.1)

Коэффициент динамического использования грузоподъемности определяется отношением фактически выполненной транспортной работы Wе к возможной работе Wв при условии полного использования грузоподъемности ПС на протяжении всего маршрута с грузом

gд = Wе / Wв; (5.2)

We = S Qi Lij; (5.3)

Wв = qi Lег. (5.4)

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

b = Lег / Lм. (5.5)

Среднее расстояние перевозки груза — это средняя дальность транспортирования одной тонны груза, определяется отношением выполненной транспортной работы Wе к объему перевезенного груза Qф

Lгр = Wе / Qф. (5.6)

Маршруты работы автомобилей приведены в таблице 5.1.

Таблица 5.1 — Определение количества завозимого в каждый пункт груза

№ п/пАвтомобильМаршрут следованияДлина маршрута, кмМасса доставляемого груза с учетом коэффициента использования грузоподъемности, т1МАЗ 437040-020Б — М1 — М2 — М3 — М4 — М5- М6 — Б38,1004,6862ЗИЛ- 5301ВАБ — М1 — М2 — М3 — М4 — М5- М6 — Б38,1001,83МАЗ 437040-020Б — М6 — М5 — М4 — М3 — М2- М1 — Б38,1004,6864ЗИЛ- 5301ВАБ — М6 — М5 — М4 — М3 — М2- М1 — Б38,1001,8

Для первого маршрута:

коэффициент статического использования грузоподъемности равен

gс = 4.686/ 4.7 = 0,997;

коэффициент динамического использования грузоподъемности равен

We = ;

Wв = 4.7 · 27.8 = 130.66 т·км;

gд = 79.378 / 130.66 = 0,6;

коэффициент использования пробега равен

b = 27.800 / 38.100 = 0,73;

среднее расстояние перевозки груза равно

Lгр = 79.378 / 4.686 = 16,94 км.

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

Таблица 5.2 — показатели использования автомобилей на маршрутах

Согласно полученным результатам суммарная транспортная работа по существующему маршруту равна 106,095 т∙км в сутки, а суточный объем перевозок составляет 6,486 т. Длина маршрута составляет 38,100 км. Коэффициент статического использования грузоподъемности изменяется от 0,997 до 0,78. Среднее расстояние перевозки груза — 16,94 и 14,84 км.

Суммарная транспортная работа по предложенному(обратному) маршруту равна 140,701 т∙км в сутки, а суточный объем перевозок составляет 6,486 т. Длина маршрута составляет 38,100 км. Коэффициент статического использования грузоподъемности изменяется от 0,997 до 0,78. Среднее расстояние перевозки груза — 21,15 и 23,1 км.

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

6. Сравнительный анализ существующего и предлагаемого вариантов

маршрутизация перевозка груз транспортный

Сравним полученные технико-эксплуатационные показатели для существующего и предлагаемого вариантов.

Для существующего варианта:

а) выполненная транспортная работа We = 106,095 т-км;

б) общий пробег Lм = 38,100 км.

Для предлагаемого варианта:

а) выполненная транспортная работа We = 140,701 т-км;

б) общий пробег Lм = 38,100 км.

В результате сравнения видно, что существующий вариант более эффективен и применим к данной транспортной сети.

Заключение

В ходе данной курсовой работы были определены кратчайшие расстояния между пунктами транспортной сети с использованием компьютерной программы NAKRA. Были оптимизированы грузовые потоки при развозе 3-х видов грузов по 6 магазинам города Гомеля, а также были составлены маршруты перевозки этих грузов. Был выбран подвижной состав для осуществления данных перевозок.

кроме того, были рассчитаны основные технико-эксплуатационные показатели работы подвижного состава и был произведен сравнительный анализ существующего и предлагаемого вариантов маршрутов перевозок грузов. В результате чего был выбран предлагаемый маршрут с движением в прямом направлении Б — М1 — М2 — М3 — М4 — М5 — М6- Б, транспортная работа которого составляет 106,095 т-км, а общий пробег автомобилей работающих на данном маршруте 38,1 км, так как он является наиболее выгодным и целесообразным для данного района города Гомеля.

Литература

1 Автомобильные перевозки пассажиров и грузов. Практикум: учебное пособие / С.А. Аземша, С.В. Скирковский, С.В. Сушко; М-во образования Респ. Беларусь, Белорус. гос. ун-т трансп. — Гомель: БелГУТ, 2012. — 205 с.

Требования по оформлению отчетных документов самостоятельной работы студентов: учебно-методическое пособие / М.А. Бойкачев [и др.]; М-во образования Респ. Беларусь, Белорус. гос. ун-т трансп. — Гомель: БелГУТ, 2010. — 62 с.

#»justify»>приложение А

M (М1,Б) = М1 — Б ; L = 3500 м(М2,Б) = М2 — 7 — М1 — Б ; L = 8500 м(М3,Б) = М3 — 11 — М1 — 7 — М2 — 8 — 9 — 10 — Б ; L = 12400 м(М4,Б) = М4 — 33 — М1 — 29 — 30 — 31 — 32 — Б ; L = 7800 м(М5,Б) = М5 — 16 — М1 — 18 — 17 — М6 — Б ; L = 14200 м(М6,Б) = М6 — 18 — М1 — Б ; L = 10300 м

из/в Б М1 М2 М3 М4 М5 М6

Б —- 3500 8500 12400 7800 14200 10300

М1 3500 —- 5000 8900 4300 10700 6800

М2 8500 5000 —- 3900 8800 15300 11800

М3 12400 8900 3900 —- 5000 11500 14900

М4 7800 4300 8800 5000 —- 6500 9900

М5 14200 10700 15300 11500 6500 —- 3900

М6 10300 6800 11800 14900 9900 3900 —-

начальный пунктКонечный пунктБМ1М2М3М4М5М6Б-350085001240078001420010300М13500-500089004300107006800М285005000-390088001530011800М31240089003900-50001150014900М47800430088005000-65009900М5142001070015300115006500-3900М6103006800118001490099003900-

приложение Б

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

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

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

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

Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

Для каждого нулевого элемента рассчитаем строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,2=3500, Г2,1=3500, Г2,5=300, Г3,4=1800, Г4,3=1800, Г5,2=700, Г6,7=5100, Г7,6=5100,

В результате сравнения мы получили 2 одинаковых максимальных Г=5100. Это означает, что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.

Рассмотрим вариант Г6,7=5100

Удалим из матрицы стоимости строку 6 и столбец 7, и присвоим элементу (7,6)

В строке 7 и столбце 6 отсутствует элемент равный ∞. Присвоим элементу (7,6) Текущая Нижняя граница=27700

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

Для каждого нулевого элемента рассчитаем строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,2=3500, Г2,1=3500, Г2,5=300, Г3,4=1800, Г4,3=1800, Г5,2=0, Г5,6=5000, Г7,2=2300,

максимальное значение имеет Г5,6=5000

Удалим из матрицы стоимости строку 5 и столбец 6. Внесем в текущий ориентированный граф дугу (5,6)

123451∞050008900350020∞150054000346001100∞041004850050000∞300735000500081002300

В строке 7 и столбце 5 отсутствует элемент равный ∞. Присвоим элементу (7,5) Текущая Нижняя граница=32800

123451∞050008900350020∞150054000346001100∞041004850050000∞30073500050008100∞

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,2=3500, Г2,1=3500, Г2,5=300, Г3,4=6500, Г4,3=1800, Г7,2=3500,

максимальное значение имеет Г3,4=6500

Удалим из матрицы стоимости строку 3 и столбец 4. Внесем в текущий ориентированный граф дугу (3,4)

12351∞05000350020∞1500048500500003007350005000∞

В строке 4 и столбце 3 отсутствует элемент равный ∞. Присвоим элементу (4,3) Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

12351∞05000350020∞15000482004700∞07350005000∞

12351∞03500350020∞00482004700∞07350003500∞

Г1,2=3500, Г2,1=3500, Г2,3=3500, Г2,5=0, Г4,5=4700, Г7,2=3500,

максимальное значение имеет Г4,5=4700

Удалим из матрицы стоимости строку 4 и столбец 5. Внесем в текущий ориентированный граф дугу (4,5)

1231∞0350020∞07350003500

В строке 7 и столбце 3 отсутствует элемент равный ∞. Присвоим элементу (7,3) Текущая Нижняя граница=34600

1231∞0350020∞0735000∞

Для каждого нулевого элемента рассчитаем строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,2=3500, Г2,1=3500, Г2,3=3500, Г7,2=3500,

В результате сравнения мы получили 4 одинаковых максимальных Г=3500. Это означает, что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно. Рассмотрим вариант Г1,2=3500

Удалим из матрицы стоимости строку 1 и столбец 2, и присвоим элементу (2,1)

1320073500∞

В строке 2 и столбце 1 отсутствует элемент равный ∞. Присвоим элементу (2,1) Текущая Нижняя граница=34600

после того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжёра дуги которым соответствуют нулевые элементы.

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (1, 2), (2, 3), (7, 1)

————————————————————————

Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г7,2. Удалим из матрицы стоимости строку 2 и столбец 7. Внесем в текущий ориентированный граф дугу (7,2)

131∞3500200

В строке 2 и столбце 3 отсутствует элемент равный ∞. Присвоим элементу (2,3) после того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы.

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (7, 2), (1, 3), (2, 1)

————————————————————————

Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г2,3. Удалим из матрицы стоимости строку 3 и столбец 2. Внесем в текущий ориентированный граф дугу (2,3)

121∞0735000

В строке 7 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (7,2) после того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы.

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (2, 3), (1, 2), (7, 1)

————————————————————————

Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г2,1. Удалим из матрицы стоимости строку 1 и столбец 2. Внесем в текущий ориентированный граф дугу (2,1)

2310350070∞

В строке 1 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (1,2) после того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы.

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (2, 1), (1, 3), (7, 2)

————————————————————————

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

1234571∞0500089003500680020∞1500540003300346001100∞0410079004850050000∞300110005350004500700∞5600610300680011400760018000

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

1234571∞0500089003500680020∞1500540003300346001100∞0410079004850050000∞300110005350004500700∞5600685005000960058000∞

1234571∞0500089003500350020∞1500540000346001100∞0410046004850050000∞30077005350004500700∞2300685005000960058000∞

Г1,2=3500, Г2,1=3500, Г2,5=0, Г2,7=2300, Г3,4=1800, Г4,3=1800, Г5,2=700, Г6,5=5000,

максимальное значение имеет Г6,5=5000

Удалим из матрицы стоимости строку 6 и столбец 5. Внесем в текущий ориентированный граф дугу (6,5)

123471∞050008900350020∞150054000346001100∞046004850050000∞770053500045007002300

В строке 5 и столбце 7 отсутствует элемент равный ∞. Присвоим элементу (5,7) Текущая Нижняя граница=32800

123471∞050008900350020∞150054000346001100∞046004850050000∞77005350004500700∞

Г1,2=3500, Г2,1=3500, Г2,7=3500, Г3,4=1800, Г4,3=6500, Г5,2=700,

максимальное значение имеет Г4,3=6500

Удалим из матрицы стоимости строку 4 и столбец 3. Внесем в текущий ориентированный граф дугу (4,3)

12471∞08900350020∞5400034600110004600535000700∞

Текущая Нижняя граница=32800

12471∞08900350020∞54000335000∞3500535000700∞

12471∞08200350020∞47000335000∞35005350000∞

Г1,2=3500, Г2,1=3500, Г2,7=3500, Г3,2=3500, Г5,2=0, Г5,4=4700,

максимальное значение имеет Г5,4=4700

Удалим из матрицы стоимости строку 5 и столбец 4. Внесем в текущий ориентированный граф дугу (5,4)

1271∞0350020∞03350003500

В строке 3 и столбце 7 отсутствует элемент равный ∞. Присвоим элементу (3,7) Текущая Нижняя граница=34600

1271∞0350020∞0335000∞

Для каждого нулевого элемента рассчитаем строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,2=3500, Г2,1=3500, Г2,7=3500, Г3,2=3500,

В результате сравнения мы получили 4 одинаковых максимальных Г=3500. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно. Рассмотрим вариант Г1,2=3500

Удалим из матрицы стоимости строку 1 и столбец 2, и присвоим элементу (2,1)

1720033500∞

В строке 2 и столбце 1 отсутствует элемент равный ∞. Присвоим элементу (2,1) Текущая Нижняя граница=34600

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

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (7, 6), (6, 5), (4, 3), (5, 4), (1, 2), (2, 7), (3, 1)

————————————————————————

Вернемся к возникшему у нас ветвлению и рассмотрим случай, при котором максимальное значение имеет Г3,2. Удалим из матрицы стоимости строку 2 и столбец 3. Внесем в текущий ориентированный граф дугу (3,2)

171∞3500200

В строке 2 и столбце 7 отсутствует элемент равный ∞. Присвоим элементу (2,7) после того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы.

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (7, 6), (6, 5), (4, 3), (5, 4), (3, 2), (1, 7), (2, 1)

————————————————————————

Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г2,7. Удалим из матрицы стоимости строку 7 и столбец 2. Внесем в текущий ориентированный граф дугу (2,7)

121∞0335000

В строке 3 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (3,2) после того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы.

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (7, 6), (6, 5), (4, 3), (5, 4), (2, 7), (1, 2), (3, 1)

————————————————————————

2710350030∞

В строке 1 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (1,2) после того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (7, 6), (6, 5), (4, 3), (5, 4), (2, 1), (1, 7), (3, 2)

————————————————————————-

Мы рассмотрели все возможные ветви алгоритма, теперь необходимо выбрать из полученых в результате рассмотрения каждой ветви значений нижней границы — минимальное. Это и будет оптимальной длиной пути коммивояжераМинимальное значение имеет НГр=38100

соответствующий оптимальный контур включет дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (1, 2), (2, 3), (7, 1)