Пример выполнения задания. Улично-дорожная сеть приведена на рисунке 6.1

Исходные данные.

Улично-дорожная сеть приведена на рисунке 6.1. Номенклатура и количества перевозимого груза приведены в таблице 6.2. Имеющиеся для осуществления перевозок автомобильные транспортные средства приведены в таблице 6.3.

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

Наименование груза	Класс груза [20]	Пункт назначения	Масса, тонн
Молочные изделия в бумажных пакетах, затаренные в ящиках		М2	0, 15
М3	0, 17
М4	0, 1
М5	0, 2
М6	0, 22
Мясо кур в ящиках		М2	0, 2
М3	0, 3
М4	0, 15
М5	0, 25
М6	0, 4
Вода минеральная в полиэтиленовых ящиках		М2	0, 2
М3	0, 25
М4	0, 15
М5	0, 4
М6	0, 1

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

Марка автомобиля	Грузоподъемность, тонн	Количество, ед.
ГАЗ-3302	1, 5
ЗИЛ-5301АО

 

Описание района перевозок.

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

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

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

Молочные изделия в бумажных пакетах, затаренные в ящиках являются грузом третьего класса, имеет средний коэффициент использования грузоподъемности =0, 60. Объем данного груза, предназначенный к перевозке – 840 кг. Объем потребления данного груза в грузопоглащающих пунктах составляет: М₂ – 150 кг; М₃ – 170 кг; М₄ – 100 кг; М₅ – 200 кг; М₆ – 220 кг.

Второй вид груза – мясо кур в ящиках, является грузом первого класса использования грузоподъемности с коэффициентом использования грузоподъемности =1. Объем этого груза, предназначенный к перевозке – 1300 кг. Объем потребления груза в грузопоглащающих пунктах составляет: М₂ – 200 кг; М₃ – 300 кг; М₄ – 150 кг; М₅ – 250 кг; М₆ –400 кг.

Третий вид перевозимого груза – вода минеральная в полиэтиленовых ящиках. Данный груз является грузом второго класса со средним коэффициентом использования грузоподъемности =0, 80. Объем данного груза, предназначенный к перевозке – 1100 кг. Объем потребления груза 3-го типа в грузопоглащающих пунктах составляет: М₂ – 200 кг; М₃ – 250 кг; М₄ – 150 кг; М₅ – 400 кг; М₆ – 100 кг.

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

- ГАЗ-3302, грузоподъемностью 1, 5 т, в количестве 5 единиц;

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

Разработка модели транспортной сети и поиск кратчайших расстояний.

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

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

Таблица 6.4 – Таблица связей между узлами транспортной сети

Б1

М2

М3

М4

М5

М6

Б1

М2

М3

М4

М5

М6

Таблица 6.5 – Матрица кратчайших расстояний между грузообразующими и грузопоглащающими узлами транспортной сети, м

Из/В	Б1	М2	М3	М4	М5	М6
Б1	-
М2		-
М3			-
М4				-
М5					-
М6						-

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

Из/В	Б1	М2	М3	М4	М5	М6
Б1	-	Б1-7-М2	Б1-7-11-12-13-М3	Б1-7-11-12-13-М4	Б1-7-11-14-17-М5	Б1-7-11-14-17-19-М6
М2		-	М2-7-11-12-13-М3	М2-7-11-12-13-М4	М2-7-11-14-17-М5	М2-7-11-14-17-19-М6
М3			-	М3-13-М4	М3-13-12-15-18-17-М5	М3-13-12-15-18-17-19-М6
М4				-	М4-13-12-15-18-17-М5	М4-13-12-15-18-17-19-М6
М5					-	М4-17-19-М6
М6						-

Выбор маршрутов движения автомобилей.

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

Шаг 1. Приведем матрицу расстояний по строкам (таблица 6.7).

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

Из/В	Б1	М2	М3	М4	М5	М6
Б1
М2
М3
М4
М5
М6

 

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

 

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

Из/В	Б1	М2	М3	М4	М5	М6
Б1						1340
М2						1200
М3						630
М4						350
М5						0
М6
	0	0	0	0	30	0

 

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

Таблица 6.9 – Полностью приведенная матрица

Из/В	Б1	М2	М3	М4	М5	М6
Б1
М2
М3
М4
М5
М6

 

Нижняя граница множества Гамильтоновых контуров равна

Нижняя граница множества Гамильтоновых контуров равна

Шаг 2. Каждый нуль в приведенной матрице (см. таблицу 6.9) условно заменяем на и находим сумму констант приведения . Значения записываем в соответствующие клетки рядом с нулями (таблица 6.10).

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

Из/В	Б1	М2	М3	М4	М5	М6
Б1		0 (1110+270=1380)
М2	0 (970+410=1380)
М3				0 (630+0=630)
М4			0 (350+970=1320)
М5						0 (670+350=1020)
М6				0 (0+0=0)	0 (0+1040=1040)

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

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

Шаг 4. Приводим полученную матрицу расстояний и определяем нижнюю границу подмножества гамильтоновых контуров { } (таблица 6.11 – 6.13).

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

Из/В	Б1	М2	М3	М4	М5	М6
Б1
М2
М3
М4
М5
М6

 

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

Из/В	Б1	М2	М3	М4	М5	М6
Б1
М2
М3
М4
М5
М6

 

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

Таблица 6.13 – Полностью приведенная матрица

Из/В	Б1	М2	М3	М4	М5	М6
Б1
М2
М3
М4
М5
М6

 

5. Априорно включаем дугу (1, 2) в гамильтонов контур, что ведет к исключению в матрице, полученной после выполнения шага 2, 1-й строки и 2-го столбца (см. таблицу 6.10). Заменяем элемент (2, 1) этой матрицы на , чтобы не допустить образования негамильтонова контура. Полученная матрица приведена в таблице 6.14.

Таблица 6.14 – Исключение 1-й строки и 2-го столбца

Из/В	Б1	М3	М4	М5	М6
М2
М3
М4
М5
М6

 

6. Приводим сокращенную матрицу и находим нижнюю границу (6.15 – 6.17).

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

Из/В	Б1	М3	М4	М5	М6
М2
М3
М4
М5
М6

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

Из/В	Б1	М3	М4	М5	М6
М2
М3
М4
М5
М6

 

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

Таблица 6.17 – Полностью приведенная матрица

Из/В	Б1	М3	М4	М5	М6
М2
М3
М4
М5
М6

Шаг 7. Проверяем размерность сокращенной матрицы. Так как сокращенная матрица не размерности 2х2, то переходим к выполнению шага 8.

Шаг 8. Сравниваем нижние границы подмножеств гамильтоновых контуров и и переходим к выполнению шага 2. При этом, если < , то разбиению подлежит подмножество { }(дальнейшему анализу, подвергается матрица, полученная в результате последнего выполнения шага 4). Если же < , разбиению подлежит подмножество { } (дальнейшему анализу подвергается матрица, полученная после последнего выполнения п.6). Так как = то разбиению будут подлежать и подмножество { } (таблица 6.13), и подмножество { } (таблица 6.17) до тех пор, пока размерность матриц не станет равной 2х2. После этого определяя длины гамильтоновых контуров и контур с наименьшей длиной, будет являться оптимальной последовательностью обхода узлов транспортной сети.

Для рассматриваемого примера контур с наименьшей длиной будет следующий: М4 – М6, М6 – М5, М3 – М4, М2 – М3, Б1 – М2, М5 – Б1. Учитывая то, что маршрут должен начинаться с пункта погрузки (Б1) и сопоставив адреса узлов транспортной сети с их наименованиями (см. рисунок 6.1) маршрут с минимальной длиной пути будет следующим: Б1 – М2 – М3 – М4 – М6 – М5 – Б1. Общая длина гамильтонова контура с учетом матрицы кратчайших расстояний (см. таблицу 6.5) составит 480 + 1730 + 1060 + 1410 + 1440 + 2250 = 8370 м.

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

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

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

Пункт выгрузки	Груз	Масса груза, т	Коэффициент использования грузоподъемности	Масса груза с учетом коэффициента использования грузоподъемности, т	Общая масса груза, то
М2	Молочные изделия в бумажных пакетах, затаренные в ящиках	0, 15	0, 6	0, 250	0, 700
Мясо кур в ящиках	0, 2		0, 200
Вода минеральная в полиэтиленовых ящиках	0, 2	0, 8	0, 250
М3	Молочные изделия в бумажных пакетах, затаренные в ящиках	0, 17	0, 6	0, 283	0, 896
Мясо кур в ящиках	0, 3		0, 300
Вода минеральная в полиэтиленовых ящиках	0, 25	0, 8	0, 313
М4	Молочные изделия в бумажных пакетах, затаренные в ящиках	0, 1	0, 6	0, 167	0, 504
Мясо кур в ящиках	0, 15		0, 150
Вода минеральная в полиэтиленовых ящиках	0, 15	0, 8	0, 188
М5	Молочные изделия в бумажных пакетах, затаренные в ящиках	0, 2	0, 6	0, 333	1, 083
Мясо кур в ящиках	0, 25		0, 250
Вода минеральная в полиэтиленовых ящиках	0, 4	0, 8	0, 500
М6	Молочные изделия в бумажных пакетах, затаренные в ящиках	0, 22	0, 6	0, 367	0, 892
Мясо кур в ящиках	0, 4		0, 400
Вода минеральная в полиэтиленовых ящиках	0, 1	0, 8	0, 125
Итого	-	3, 24	-	4, 075

Согласно исходным данным (см. таблицу 6.3), перевозка может быть осуществлена автомобилями двух марок: ГАЗ-3302, грузоподъемностью 1, 5 т и ЗИЛ-5301АО, грузоподъемностью 3 т. Из таблицы 6.8 видно, что общая масса доставляемого груза, с учетом коэффициента использования грузоподъемности составляет 4, 075 т. Исходя из вышесказанного, можно утверждать, что в данном случае необходимо использовать по одному автомобилю каждого типа. Такое утверждение основано на следующих умозаключениях:

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

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

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

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

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

№ п/п	Автомобиль	Маршрут следования	Длина маршрута, км	Масса доставляемого груза с учетом коэффициента использования грузоподъемности, т
	ЗИЛ-5301АО	Б1–М2–М3–М4–М6–Б1	6, 50 (2, 3=0, 48+1, 82)	2, 44
	ГАЗ-3302	Б1–М6–М5–Б1	5, 51 (4, 07)	1, 392

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

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

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

g_с = 2, 44 / 3, 0 = 0, 89;

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

W _e = 2, 44 · 0, 48+1, 89 · 1, 73+1, 17 · 1, 06+0, 77 · 1, 41= 6, 77т·км;

W _в = 3 · 6, 5 = 19, 5 т·км;

g_д = 6, 77 / 19, 5 = 0, 35;

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

b = 4, 68 / 6, 5 = 0, 72;

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

L _гр = 6, 77 / 2, 44 = 2, 77 км.

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

 

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

Маршрут	L м, км	Q, т	W e, т-км	gс	gд	b	L гр
	6, 5	2, 44	6, 77	0, 89	0, 35	0, 72	2, 77
	5, 51	1, 39	3, 43	0, 72	0, 31	0, 79	2, 80
Итого	12, 01	3, 83	10, 22	-	-	-	-

 

Согласно полученным результатам суммарная транспортная работа по всем маршрутам равна 10, 22 т∙ км в сутки, а суточный объем перевозок составляет 12, 01 т. Максимальная длина маршрута составляет 6, 5 км, а минимальная равна 5, 51 км. Коэффициент статического использования грузоподъемности изменяется от 0, 72 до 0, 89, а коэффициент динамического использования грузоподъемности – от 0, 31 до 0, 35. Коэффициент использования пробега лежит в интервале от 0, 72 до 0, 79. Среднее расстояние перевозки груза – 2, 77 км. Таким образом, данные показатели являются весьма приемлемыми в сложившихся условиях перевозок продукции.

Маршрутизация мелкопартионных перевозок с использованием программы «umka».

Шаг 1. Ввод автомобильных транспортных средств.

Для добавления транспортного средства необходимо выбрать команду «Работа с транспортными средствами» основного меню и в ней выбрать «Добавить транспортное средство» (см. рисунок 6.3). В появившемся окне (см. рисунок 6.4) необходимо указать марку транспортного средства, его грузоподъемность (в тоннах) и нажать кнопку «Записать информацию о ТС». Эти действия производятся для каждого типа автомобилей.

Шаг 2. Ввод узлов транспортной сети.

Для добавления узла необходимо выбрать команду «Работа с транспортной сетью» основного меню и в ней выбрать «Добавить узел» (см. рисунок 6.5). В результате появится окно (рисунок 6.19). Добавляем информацию о первом узле (Б1). Для этого в поле «Введите имя узла» необходимо ввести «Б1», в поле необходимо ввести «Адрес узла» вводим «ул. Телегина, 7» (см. рисунок 6.1), в поле «Укажите место расположения узла» необходимо ввести «Гомель» и нажать кнопку «Записать информацию о узле». Затем опять необходимо выбрать команду «Работа с транспортной сетью» основного меню и в ней выбрать «Добавить узел» (см. рисунок 6.5) и ввести следующий узел (М2). После ввода информации об этом узле и нажатия кнопки «Записать информацию о узле» появиться окно ввода связей между узлами, приведенное на рисунке 6.20. Необходимо нажать кнопку «Закрыть окно». Аналогично выполняется ввод данных для всех оставшихся узлов (М3–22). Следует помнить, что при вводе перекрестков (7–22) в поле «Введите имя узла» (см. рисунок 6.19) необходимо оставить слово «перекресток» а в поле «Укажите адрес узла» необходимо указать наименование перекрестка улиц.

 

Рисунок 6.19 – Окно «Добавить узел»

 

Рисунок 6.20 – Окно «Добавить узел»

 

После ввода всех транспортных узлов, необходимо добавить связи между ними. Для этого следует выбрать команду «Работа с транспортной сетью» основного меню и в ней выбрать «Добавить узел» (см. рисунок 6.5) и команду «Просмотр/корректировка транспортных связей» (см. рисунок 6.5), после нажатия на которую, программа выдает окно, приведенное на рисунке рисунок 6.10. Теперь необходимо ввести расстояния между узлами, которые связаны напрямую друг с другом в соответствии с таблицей связи (см. таблицу 6.2). Так, например, узел М3 напрямую связан с узлом 10. Расстояние между ними составляет 180 м (см. таблицу 6.2). Поэтому, в появившемся окне, на пересечении строки «ул. Чехова, 12» (это адрес М3) и столбца «10», а также строки «10» и столбца «ул. Чехова, 12» необходимо ввести «180» (рисунок 6.21). Аналогично выполняется ввод связей между всеми оставшимися транспортными узлами, в соответствии с таблицей связей (см. таблицу 6.2), после чего нажать кнопку «Сохранить изменения транспортных связей» (см. рисунок 6.21).

 

Рисунок 6.21 – Окно «Просмотр/корректировка транспортных связей»

 

Ввод информации о грузах.

Для добавления груза необходимо выбрать команду «Работа с грузами» основного меню и в ней выбрать «Добавить груз» (см. рисунок 6.11). В результате появится окно (см. рисунок 6.12). В поле «Введите наименование груза» (см. рисунок 6.12) необходимо ввести «Молочные изделия в бумажных пакетах, затаренные в ящиках» (см. таблицу 6.2). В поле «Коэффициент использования грузоподъемности» необходимо ввести «0, 6», согласно Постановлению Министерства транспорта и коммуникаций № 35 от 1 ноября 2002 г. Затем необходимо нажать кнопку «Записать информацию о грузе» (рисунок 6.22). Аналогичные действия выполняются для оставшихся грузов.

Рисунок 6.22 – Окно «Добавить груз»

 

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

Для составления развозочных маршрутов необходимо выбрать команду «Маршрутизация» основного меню и в ней выбрать «Составить развозочный маршрут» (см. рисунок 6.13). В результате появится окно (рисунок 6.23).

 

Рисунок 6.23 – Окно «Составить развозочный маршрут»

 

В окне «Укажите пункт погрузки» выбираем «Б1». Затем в окне «Укажите пункты выгрузки» выбираем «М2», в результате чего появиться окно ввода груза (рисунок 6.24).

Рисунок 6.24 – Окно «Составить развозочный маршрут»

 

В данном окне в поле «Укажите доставляемый груз» необходимо выбрать «Молочные изделия в пакетах, затаренные в ящиках», в соответствии с исходными данными, а в графе «Укажите массу груза, тонн» необходимо ввести массу доставляемых в М2 молочных изделий (0, 15 по исходным данным) и нажать кнопку «Записать информацию». Затем в окне «Укажите пункты выгрузки» снова выбираем «М2» и в появившемся окне выбираем следующий вид доставляемого в пункт «М2» груза и его массу. После ввода информации о грузах, доставляемых в М2, необходимо указать грузы, доставляемые в остальные пункты потребления (М3 – М6). После ввода информации о груз